La Macchina di Turing

Per meglio comprendere i processi mentali di una macchina analitica l'algoritmo della Macchina di Turing costituisce un modello universale. Un esempio applicativo su cui ci si può esercitare è fornito da un modello (assai semplice da comprendere) del Dipartimento di Informatica dell'Università di Milano:

https://aladdin.di.unimi.it/sw/turing/myturing.html?

Esempio n.1: data una stringa iniziale vuota di proceda con il seguente programma (così spiegato)

(0,*) > (1,C,s)  (se la casella è vuota scrivi C e vai a sinistra, passa alla istruzione 1)

(1,*) > (2,I,s)  (se la casella è vuota scrivi I e vai a sinistra, passa alla istruzione 2)

(2,*) > (3,A,s)  (se la casella è vuota scrivi A e vai a sinistra, passa alla istruzione 3)

(3,*) > (4,O,s)  (se la casella è vuota scrivi O e vai a sinistra, passa alla istruzione 4)

(4,*) > (5,X,d)  (se la casella è vuota scrivi X e vai a destra, passa alla istruzione 5)

(5,O) > (6,Y,d)  (se la casella è O scrivi Y e vai a sinistra, passa alla istruzione 6)

(a questo punto il programma si blocca).

Questo il risultato:

Esempio n. 2

(0,*) > (1,C,s)

(1,*) > (2,I,s)

(2,*) > (3,A,s)

(3,*) > (0,O,s)

Questo il risultato, e la stringa non si ferma mai: