Monthly Archives: ottobre 2014

Edizione I – Problema 1

Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo n, <> 0, termina la sua esecuzione lasciando sul nastro la rappresentazione decimale di n*100.

Esempi

NASTRO INIZIALE NASTRO FINALE
431 43100
6 600

0101Algoritmo

  • Si posiziona a destra
  • Scrive i due 0

Codice 1

(0,0,0,0,>)
(0,1,0,1,>)
(0,2,0,2,>)
(0,3,0,3,>)
(0,4,0,4,>)
(0,5,0,5,>)
(0,6,0,6,>)
(0,7,0,7,>)
(0,8,0,8,>)
(0,9,0,9,>)
(0,-,1,0,>)
(1,-,H,0,>)
Per ogni cifra da 0 a 9 vai a destra
'
'
'
'
'
'
'
'
'
Scrivi il primo 0
Scrivi il secondo 0

Codice 2

(0,0123456789,0,0123456789,>)
(0,-,1,0,>)
(1,-,H,0,>)
Per ogni cifra da 0 a 9 vai a destra
Scrivi il primo 0
Scrivi il secondo 0

Codice 3

(0,[0..9],0,[0..9],>)
(0,-,1,0,>)
(1,-,H,0,>)
Per ogni cifra da 0 a 9 vai a destra
Scrivi il primo 0
Scrivi il secondo 0

Uguaglianza > Base 1

Date due sequenze di 1 separate da *, scrive 1 se sono uguali, 0 altrimenti

Esempi

NASTRO INIZIALE NASTRO FINALE
11*11 1
11*111 0

Algoritmo

  • Elimina un 1 a sinistra e un 1 a destra finché non rimane soltanto *
  • Nei casi di errore cancella tutto e scrive 0

Tabella

Delle transizione di stato

1 *
0 D > F >
D DD < D 1 > D * >
DD S < SS <
F H 1 > FF >
FF H 0 > FF >
S 0 > S 1 < S * <
SS H 0 < SS <

Codice

(0,1,D,-,>)
(0,*,F,-,>)
(F,-,H,1,>)
(F,1,FF,-,>)
(FF,1,FF,-,>)
(FF,-,H,0,>)
(D,1*,D,1*,>)
(D,-,DD,-,<)
(DD,1,S,-,<)
(DD,*,SS,-,<)
(SS,1,SS,-,<)
(SS,-,H,0,<)
(S,1*,S,1*,<)
(S,-,0,-,>)
Elimina un 1 a sinistra
'
'
'
'
'
Vai a destra
'
'
'
'
'
Elimina un 1 a destra
Vai a sinistra

Scrive 0/1

Se sul nastro trova CIAO scrive 0, se sul nastro trova BYE scrive 1.

Esempi

NASTRO INIZIALE NASTRO FINALE
CIAO 0
BYE 1

Algoritmo

scrive_0_1Ci sono due percorsi distinti di lettura controllata del nastro

  • Input iniziale è CIAO allora scrive 0
  • input iniziale è BYE allora scrive 1

Codice

(0,C,1,-,>)
(1,I,2,-,>)
(2,A,3,-,>)
(3,O,H,0,>)
(0,B,4,-,>)
(4,Y,5,-,>)
(5,E,H,1,>)
Inizia con C
...
...
Scrive 0
Inizia con B
...
Scrive 1

Scrive CIAO/BYE

Se sul nastro trova 0 scrive CIAO, se trova 1 scrive BYE.

Esempi

NASTRO INIZIALE NASTRO FINALE
0 CIAO
1 BYE

Algoritmo

scrive_ciao_byeCi sono due percorsi distinti di scrittura su nastro

  • Input iniziale è 0 allora scrive CIAO
  • input iniziale è 1 allora scrive BYE

Codice

(0,0,1,C,>)
(1,-,2,I,>)
(2,-,3,A,>)
(3,-,H,O,>)
(0,1,4,B,>)
(4,-,5,Y,>)
(5,-,H,E,>)
Inizia con C
...
...
...
Inizia con B
...
...

Scrive CIAO

Scrivere CIAO con il nastro inizialmente vuoto

Esempi

NASTRO INIZIALE NASTRO FINALE
CIAO

Algoritmo

scrive_ciao

Codice 1

(0,-,1,C,>)
(1,-,2,I,>)
(2,-,3,A,>)
(3,-,H,O,>)
Scrive C
... I
... A
... O

A dispari in B

Tratto dal sito ufficiale

Consideriamo una macchina che modifica una sequenza di A rimpiazzando ogni A in posizione dispari con una B.
La prima A ha posizione pari uguale a 0.

Esempi

NASTRO INIZIALE NASTRO FINALE
A A
AA AB
AAA ABA
AAAA ABAB

a_dispariAlgoritmo

  • Lo stato 0 è pari, A rimane
  • Lo stato 1 è dispari, A diventa B

Codice

(0,A,1,A,>)
(1,A,0,B,>)
A dispari
A pari diventa B

Controllo di parità > Base 2

Aggiunge, a destra, il bit di parità a una sequenza binaria

Esempi

NASTRO INIZIALE NASTRO FINALE
1 11
0 00
11111 111111
11011 110110

Algoritmo

  1. I bit 0 mantengono lo stato Pari oppure Dispari
  2. I bit 1 cambiano lo stato da Dispari in Pari, oppure da Pari in Dispari
  3. Se termina in Pari scrive 0
  4. Se termina in Dispari scrive 1

Codice

(0,0,P,0,>)
(0,1,D,1,>)
(P,0,P,0,>)
(P,1,D,1,>)
(P,-,H,0,>)
(D,0,D,0,>)
(D,1,P,1,>)
(D,-,H,1,>)
0
1
0
1, cambia...
Scrive 0
0
1, cambia...
Scrive 1

Controllo di parità > Base 1

Se il numero di 1, in una sequenza unaria, è pari/dispari scrive EVEN/ODD.

Esempi

NASTRO INIZIALE NASTRO FINALE
111 ODD
11 EVEN
EVEN

Algoritmo

  • All’inizio il numero di 1 è pari (0…)
  • Per ogni 1 cambia stato: 0 -> 1 -> 0 -> … (Pari -> Dispari -> Pari -> …)
  • Se il nastro è vuoto scrive EVEN

Codice

(0,1,1,-,>)
(0,-,2,E,>)
(2,-,3,V,>)
(3,-,4,E,>)
(4,-,H,N,>)
(1,1,0,-,>)
(1,-,5,O,>)
(5,-,6,D,>)
(6,-,H,D,>)
-> Dispari
Inizia a scrivere EVEN
...
...
...
-> Pari
Inizia a scrivere ODD
...
...

Contatore > Base 10

Incrementare di 1 per sempre…

Esempi

NASTRO INIZIALE NASTRO FINALE
999 1000 1001 1002 …
118 119 120 121 …
0 1 2 3 …

conta_10Algoritmo

  1. Si sposta a destra, sull’ultima cifra
  2. Se incontra una cifra diversa da 9 scrive la cifra successiva e ritorna a destra
  3. Se incontra un 9 scrive 0 col riporto di 1… e continua a sinistra

Codice

(0,0123456789,0,0123456789,>)
(0,-,S,-,<)
(S,012345678-,0,1234567891,>)
(S,9,S,0,<)
Vai a destra
Comincia
Scrivi il successivo, ritorna a destra
Scrivi 0 col riporto di 1

Sequenza palindroma > A..Z

Tratto dal sito ufficiale

Scrivere un programma per macchina di Turing che, ricevuta sul nastro una stringa sull’alfabeto a-z, lasci il nastro vuoto alla fine della computazione se e solo se la stringa originale era palindroma.

Si dicono palindrome le stringhe che si leggono identicamente da sinistra a destra o da destra verso sinistra.

Esempi

NASTRO INIZIALE NASTRO FINALE
ailatiditalia
ailatidtalia d
satorras torr

Algoritmo

  1. Posizionati sul primo carattere a sinistra della stringa, lo cancelliamo, memorizziamo nel nome dello stato il carattere letto, passando nello stato lettoa (se abbiamo letto una a) fino a lettoz (se abbiamo letto una z).
  2. Quindi scorriamo tutta la stringa, mantenendo memoria nello stato di quale carattere avevamo letto, e riscrivendo sempre il carattere letto.
  3. Arrivati in fondo alla stringa, ci spostiamo di una cella a destra (sempre mantenendo il carattere letto originalmente nello stato), e verifichiamo di trovare all’estremità sinistra della stringa lo stesso carattere che avevamo letto a destra.
  4. In caso positivo, si cancella il carattere e si ritorna in cima alla stringa, ripetendo poi l’algoritmo (fino a consumare tutta la stringa).
  5. In caso negativo si interrompe il calcolo, lasciando sul nastro la parte di stringa non palindroma.

Codice 1

(0,[a..z],letto[a..z],-,>)
(letto[a..z],{a..z},letto[a..z],{a..z},>)
(letto[a..z],-,destra[a..z],-,<)
(destra[a..z],[a..z],ritorno,-,<)
(ritorno,[a..z],ritorno,[a..z],<) (ritorno,-,0,-,>)