La Macchina di Turing
Introduzione
Questa pagina offre una implementazione in javascript di un simulatore di macchine di Turing.
La macchina di Turing è un modello di calcolo, ed è stata definita da Alan M. Turing nel suo famoso paper del 1936 (ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM).
Maggiori informazioni teoriche rispetto alla macchina di Turing sono presenti alla fine della seguente pagina. Inoltre, per aiutare a capire meglio il funzionamento del simulatore sono stati preparati i seguenti esempi:
Simulatore
A seguire, in ordine: la tabella che contiene le istruzioni che governano il comportamento della macchina di Turing che si vuole simulare; il nastro contenente l'input della macchina; la posizione della testina; il pannello di controllo e il pulsante di avvio.
| Stato corrente | Simbolo letto | → | Nuovo stato | Simbolo scritto | Movimento | |
|---|---|---|---|---|---|---|
| ↓ | ||||||
| Stato Interno: | |
|---|---|
| Velocità (ms): | |
| Passi eseguiti: |
Note Tecniche
Seguono alcune note tecniche sull'implementazione dei vari componenti della macchina:
Per cambiare la posizione della testina basta cliccare nella riga sopra la cella su cui si vuole spostare la testina (non nella cella, ma sopra la cella).
NOTA 2
Descrizione Teorica
Nella sua essenza, un modello di calcolo è la descrizione matematica di una macchina in grado di eseguire degli algoritmi. Di modelli di calcolo nel corso degli anni ne sono stati definiti tantissimi. Tra questi però la macchina di Turing è unica, in quanto, nella sua semplicità, riesce a catturare in modo intuitivo il concetto di calcolabilità.
Per questi, e tanti altri motivi, la macchina di Turing continua ad essere studiata da tutti gli studenti di informatica teorica, e Alan M. Turing è considerato uno dei padri fondatori dell'informatica.
Una macchina di Turing è formata dai seguenti componenti:
- Il nastro di lavoro : La macchina di Turing lavora su un nastro unidimensionale, diviso in celle, che si può estendere sia a destra che a sinistra di quanto si vuole. Le varie celle del nostro possono contenere vari simboli.
- Una testina: La macchina ha a disposizione una testina, che gli permette in ogni momento di vedere una singola cella del nastro di lavoro. Tramite la testina quindi la macchina è in grado di capire quale simbolo è scritto nella cella su cui la testina è puntata.
- Uno stato inerno: In ogni momento la macchina si trova in un determinato stato interno. Quando viene azionata questo stato interno può cambiare a seconda delle istruzioni della macchina.
- La tabella delle istruzioni: La parte
fondamentale della macchina, rappresenta il programma che si
vuole eseguire. Ogni istruzione è formata da cinque
elementi
(STATO_CORRENTE, SIMBOLO_LETTO, NUOVO_STATO, SIMBOLO_SCRITTO, MOVIMENTO) Ad esempio l'istruzione (A, 1, B, 0, D) deve essere letta così: se mi trovo nello stato A e la cella puntata testina contiene il simbolo 1, allora cambio lo stato interno nello stato B, scrivo nella cella puntata dalla testina il simbolo 0 e infine sposto la testina della macchina di una cella a destra.