Stato
Passi
Simboli sul nastro
Situazione

Nello stato Legge Scrive Si sposta Stato successivo

Di più sulle macchine di Turing

Simulatore di macchina di Turing

Una macchina di Turing è il computer più semplice possibile: una testina che legge un simbolo di un nastro infinito, scrive un simbolo, si sposta di una cella a sinistra o a destra e cambia stato, seguendo una breve tabella di regole. Alan Turing la inventò nel 1936, e tutto ciò che fa il tuo computer potrebbe in linea di principio essere fatto così. Scrivi le tue regole o carica un esempio, premi Esegui e guarda il nastro cambiare passo dopo passo, con sotto un diagramma di tutta la sua storia. Scegli un programma o scrivine uno tuo, inserisci l'input e premi Esegui, oppure Passo per seguire una regola alla volta; Indietro annulla un passo. Ogni riga del programma è una regola: stato, simbolo letto, simbolo da scrivere, movimento (L, R o N per nessun movimento) e stato successivo, per esempio A 0 -> 1 R B. Usa _ per una cella vuota. La macchina parte nello stato della prima regola, sul primo simbolo dell'input, e si ferma in H, accept o reject, oppure quando nessuna regola è applicabile. Il diagramma mostra il nastro dopo ogni passo, dall'alto verso il basso.

Come funziona

  1. Scegli un programma di esempio o scrivi regole come A 0 -> 1 R B, una per riga, e digita l'input.
  2. Premi Esegui per vedere la testina muoversi, oppure Passo per seguire una regola alla volta; Indietro annulla un passo.
  3. Leggi lo stato, i passi e i simboli sul nastro nei riquadri, e la storia del nastro nel diagramma.

Come funziona la macchina

In ogni istante la macchina si trova in uno di pochi stati e la sua testina è su una cella del nastro. La regola per quello stato e per il simbolo sotto la testina dice tre cose: quale simbolo scrivere nella cella, se spostarsi a sinistra, a destra o per niente, e in quale stato passare. Questa è l'intera macchina. Si ferma quando raggiunge uno stato di arresto, come H, accept o reject, oppure quando nessuna regola è applicabile. Un programma che aggiunge 1 a un numero binario ha bisogno di sole nove regole di questo tipo.

Castori indaffarati

Quale macchina con n stati, avviata su un nastro vuoto, scrive il maggior numero di 1 prima di fermarsi? Se lo chiese Tibor Radó nel 1962. Le macchine campioni si chiamano castori indaffarati, e crescono più in fretta di qualsiasi funzione che un computer possa calcolare. Due stati danno 4 uni in 6 passi, tre stati 6 uni, quattro stati 13 uni in 107 passi. La macchina campione a cinque stati, trovata nel 1989, scrive 4.098 uni in 47.176.870 passi, e nel 2024 una collaborazione online ha dimostrato con una matematica verificata al computer che nessun'altra macchina a cinque stati che si ferma va avanti più a lungo.

Domande frequenti

Come si scrive una regola?

Una regola per riga: lo stato attuale, il simbolo letto, il simbolo da scrivere, il movimento (L, R o N) e lo stato successivo, per esempio A 0 -> 1 R B. La freccia e le virgole sono facoltative. Usa _ per una cella vuota e # per un commento. La macchina parte nello stato della prima regola; uno stato successivo chiamato H o halt la ferma, e accept e reject la fermano con un verdetto.

Una macchina di Turing può davvero calcolare qualsiasi cosa?

Qualsiasi cosa che un computer possa calcolare, con abbastanza nastro e tempo: questa è la tesi di Church-Turing. Una macchina di Turing non ha limiti di memoria, quindi in questo senso è più potente di qualsiasi computer reale, anche se molto più lenta. Ciò che non può fare è rispondere a ogni domanda: Turing dimostrò che nessuna macchina può decidere, per ogni programma e ogni input, se si fermerà.

Perché il contatore non si ferma mai?

Le sue regole non portano mai a uno stato di arresto. Continua ad aggiungere 1 a un numero binario all'estremità destra del nastro e a tornare indietro, così il numero cresce all'infinito. Il problema della fermata di Turing dice che nessun metodo generale può stabilire, per ogni macchina, se si fermerà; per questo semplice contatore lo si vede, ma per alcune macchine con soli sei stati ancora nessuno lo sa.

Come può il castoro indaffarato a cinque stati compiere qui 47 milioni di passi?

Il nastro è memorizzato come un array compatto che cresce in entrambe le direzioni, e all'impostazione Velocissima l'app esegue centinaia di migliaia di passi tra un aggiornamento dello schermo e l'altro, così l'intera esecuzione richiede pochi secondi in un browser moderno. Il diagramma registra solo i primi 400 passi, perché un'immagine di 47 milioni di righe non entrerebbe in nessuno schermo.

Viene inviato qualcosa a un server?

No. Il programma viene eseguito nel tuo browser, e il tuo programma e il tuo input restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor