Macchine di Turing

turing.md

Simulatore macchina di Turing

http://morphett.info/turing/turing.html

Consiglio: prima di scrivere la versione "a codice" vi conviene fare il disegnino :)

Macchine di Turing da realizzare

1) Una macchina che arriva alla fine dei dati (0/1) e si ferma

Realizzare da soli la prima macchina che abbiamo visto insieme. Dato questo stato iniziale:

_ _ _ 0 1 0 0 1 1 0 1 0 0 1 0 1 0 0 1 _ _ _ _
      ^

La macchina deve terminare col cursore nella prima cella vuota che trova alla sua destra:

_ _ _ 0 1 0 0 1 1 0 1 0 0 1 0 1 0 0 1 _ _ _ _
                                      ^

2) Una macchina che arriva alla fine dei dati (0/1) e ritorna indietro sulla posizione iniziale.

Realizzare da soli la seconda macchina che abbiamo visto insieme. Dato questo stato iniziale:

_ _ _ 0 1 0 0 1 1 0 1 0 0 1 0 1 0 0 1 _ _ _ _
      ^

La macchina deve arrivare col cursore nella prima cella vuota che trova alla sua destra, per poi tornare alla posizione di partenza:

_ _ _ 0 1 0 0 1 1 0 1 0 0 1 0 1 0 0 1 _ _ _ _
                                      ^

_ _ _ 0 1 0 0 1 1 0 1 0 0 1 0 1 0 0 1 _ _ _ _
      ^

3) Macchina pari/dispari

Dato questo stato di partenza:

_ _ _ 0 1 0 _ _ _ _
      ^

La macchina deve terminare in uno stato denominato dispari. Dato questo secondo stato di partenza invece:

_ _ _ 0 1 0 0 _ _ _ _
      ^

La macchina deve terminare in uno stato denominato pari. Massima libertà su dove si debba trovare il cursore al momento dell'halt.

4) Macchina che riconosce sequenze precise di valori

Dato questo stato di partenza:

_ _ _ 0 1 0 1 1 0 0 1 1 _ _ _ _
      ^

La macchina deve riconoscere la sequenza "1 1" e fermarsi nella cella successiva del nastro in uno stato chiamato "success".

Se il nastro non contiene la sequenza di caratteri invece (come in questo esempio):

_ _ _ 0 1 0 1 0 1 0 0 1 _ _ _ _
      ^

La macchina deve fermarsi sulla prima cella vuota che trova, in uno stato chiamato "failure" (o "puppa", come preferite).

_ _ _ 0 1 0 1 0 1 0 0 1 _ _ _ _
                        ^

5) Somma +1 di un numero binario

Dato questo nastro di partenza:

_ _ _ 0 1 1 _ _ _ _
      ^

La macchina deve trattare le cifre come un numero espresso in notazione binaria (in questo caso, 011 equivale a 3). Il risultato, all'halt della macchina dovrà essere il medesimo numero incrementato di 1 (nel nostro caso 100, ovvero 4):

_ _ _ 1 0 0 _ _ _ _

Il cursore all'halt può trovarsi dove vi pare :)

Aiutino :)

Se ci si pensa bene, l'operazione di incremento può essere vista in questo modo:

1. Arrivo col cursore fino all'ultima cifra presente
2. Tutti gli 1 che trovo spostandomi verso sinistra li converto in 0
3. Il primo 0 che trovo, lo coverto in 1 e mi blocco

6) Macchina "ordinatrice"

Dato questo nastro di partenza:

_ _ _ 0 1 1 0 1 1 0 0 1 0 1 _ _ _ _
      ^

Devo riordinare le cifre per grandezza crescente (prima gli "0", poi gli "1"), per poi bloccarsi.

_ _ _ 0 0 0 0 0 1 1 1 1 1 1 _ _ _ _