Subpage under development, new version coming soon!
Subject: [Rompicapi&Logica] Turing machine simulator
- 1
EricinaFC [del] to
All
C'è un simpatico simulatore di macchina di Turing in rete a questo indirizzo. Io mi sto esercitando per un esame universitario. Se siete appassionati di rompicapo, creare una macchina di Turing per semplici problemi logici può essere una valida alternativa al Sudoku; secondo me è pure più divertente.
A chi è interessato, ecco come funzionano le macchine di Turing.
NASTRO
Una macchina di Turing possiede una sequenza infinita di celle dentro le quali è possibile mettere un
simbolo per volta. Le celle non possono essere spostate ma mantengono la posizione originaria; pertanto tale sequenza può essere vista come un nastro.
TESTINA
Esiste una testina che può essere spostata avanti e indietro lungo il nastro e che può leggere il contenuto di una cella del nastro per volta.
ISTRUZIONI
La parte risolutiva del problema sta nelle istruzioni. A differenza dei linguaggi di programmazione classici, che forse alcuni di voi già conoscono, un "programma" per TM non viene eseguito sequenzialmente. L'insieme di istruzioni di una TM è infatti un insieme di coppie Condizione-Azione.
La condizione è, a sua volta, una coppia [STATO_CORRENTE, SIMBOLO_CORRENTE].
L'azione è, a sua volta, una tripla [NUOVO_SIMBOLO, DIREZIONE_SPOSTAMENTO, NUOVO_STATO].
STATO_CORRENTE e NUOVO_STATO possono essere qualunque stringa mnemonica utile a ricordare il significato operativo dello stato, ma per TM semplici ci si può limitare all'uso di numeri interi positivi; casi speciali: lo stato iniziale si indica sempre con 0, mentre lo stato finale si indica sempre con halt;
SIMBOLO_CORRENTE e NUOVO_SIMBOLO possono essere qualunque carattere ASCII stampabile;
DIREZIONE può essere L per sinistra, R per destra e * per nessun movimento;
Un esempio aiuterà a capire meglio:
Esempio
Stampa in output "1" se il carattere in input è 'a'; altrimenti, se il carattere in input è qualcosa di differente da 'a', la macchina si arresta comunicando che manca la coppia Condizione-Azione corrispondente.
0 a 1 * halt
0 è lo stato iniziale;
a è l'ipotetico carattere puntato dalla testina;
1 è il carattere che viene scritto dalla testina se la condizione è soddisfatta;
* indica che nessuno spostamento della testina verrà effettuato;
halt è lo stato finale del programma.
Altro esempio
0 a 1 R S1
S1 _ 2 * S3
S3 * * L S3
S3 _ _ R halt
Questo "programma" parte (stato 0) controllando se la cella in cui è posizionata la testina contiene 'a'. Se no, la macchina si arresta forzatamente. Se sì, scrive 1, la testina si sposta a destra e la macchina passa allo stato S1.
Adesso, essendo nello stato S1, controlla se la testina punta a _ (carattere vuoto); se sì, scrive 2, la testina rimane ferma (notate l'uso di *) e si passa allo stato S3; se no, la macchina si arresta per i motivi precedenti.
Se siamo allo stato S3 e la testina sta leggendo * (che vuol dire «qualsiasi carattere a parte quelli già dichiarati per lo stato corrente»), riscrive cosa c'era (equiv. lascia inalterato ciò che c'è) e si sposta a sinistra.
Se siamo allo stato S3 e la testina sta leggendo _, allora si riscrive lo stesso carattere (in altre parole, si lascia inalterato quello che c'era), ci si sposta a destra e la macchina termina la sua esecuzione con la testina che punta esattamente al prima carattere dell'output, che è 12.
In altre parole, questa TM restituisce 12 se l'input è il carattere 'a' e si arresta anzitempo se l'input non è il carattere 'a'.
Se qualcuno vuole capire meglio come si crea una TM per cimentarsi con qualche semplice problema da risolvere, sono disponibile per ogni domanda o chiarimento.
(edited)
A chi è interessato, ecco come funzionano le macchine di Turing.
NASTRO
Una macchina di Turing possiede una sequenza infinita di celle dentro le quali è possibile mettere un
simbolo per volta. Le celle non possono essere spostate ma mantengono la posizione originaria; pertanto tale sequenza può essere vista come un nastro.
TESTINA
Esiste una testina che può essere spostata avanti e indietro lungo il nastro e che può leggere il contenuto di una cella del nastro per volta.
ISTRUZIONI
La parte risolutiva del problema sta nelle istruzioni. A differenza dei linguaggi di programmazione classici, che forse alcuni di voi già conoscono, un "programma" per TM non viene eseguito sequenzialmente. L'insieme di istruzioni di una TM è infatti un insieme di coppie Condizione-Azione.
La condizione è, a sua volta, una coppia [STATO_CORRENTE, SIMBOLO_CORRENTE].
L'azione è, a sua volta, una tripla [NUOVO_SIMBOLO, DIREZIONE_SPOSTAMENTO, NUOVO_STATO].
STATO_CORRENTE e NUOVO_STATO possono essere qualunque stringa mnemonica utile a ricordare il significato operativo dello stato, ma per TM semplici ci si può limitare all'uso di numeri interi positivi; casi speciali: lo stato iniziale si indica sempre con 0, mentre lo stato finale si indica sempre con halt;
SIMBOLO_CORRENTE e NUOVO_SIMBOLO possono essere qualunque carattere ASCII stampabile;
DIREZIONE può essere L per sinistra, R per destra e * per nessun movimento;
Un esempio aiuterà a capire meglio:
Esempio
Stampa in output "1" se il carattere in input è 'a'; altrimenti, se il carattere in input è qualcosa di differente da 'a', la macchina si arresta comunicando che manca la coppia Condizione-Azione corrispondente.
0 a 1 * halt
0 è lo stato iniziale;
a è l'ipotetico carattere puntato dalla testina;
1 è il carattere che viene scritto dalla testina se la condizione è soddisfatta;
* indica che nessuno spostamento della testina verrà effettuato;
halt è lo stato finale del programma.
Altro esempio
0 a 1 R S1
S1 _ 2 * S3
S3 * * L S3
S3 _ _ R halt
Questo "programma" parte (stato 0) controllando se la cella in cui è posizionata la testina contiene 'a'. Se no, la macchina si arresta forzatamente. Se sì, scrive 1, la testina si sposta a destra e la macchina passa allo stato S1.
Adesso, essendo nello stato S1, controlla se la testina punta a _ (carattere vuoto); se sì, scrive 2, la testina rimane ferma (notate l'uso di *) e si passa allo stato S3; se no, la macchina si arresta per i motivi precedenti.
Se siamo allo stato S3 e la testina sta leggendo * (che vuol dire «qualsiasi carattere a parte quelli già dichiarati per lo stato corrente»), riscrive cosa c'era (equiv. lascia inalterato ciò che c'è) e si sposta a sinistra.
Se siamo allo stato S3 e la testina sta leggendo _, allora si riscrive lo stesso carattere (in altre parole, si lascia inalterato quello che c'era), ci si sposta a destra e la macchina termina la sua esecuzione con la testina che punta esattamente al prima carattere dell'output, che è 12.
In altre parole, questa TM restituisce 12 se l'input è il carattere 'a' e si arresta anzitempo se l'input non è il carattere 'a'.
Se qualcuno vuole capire meglio come si crea una TM per cimentarsi con qualche semplice problema da risolvere, sono disponibile per ogni domanda o chiarimento.
(edited)
Suvvia, vi pongo un quesito iniziale.
Sareste capaci di creare una macchina di Turing che, presa in input una stringa fatta da tutte 'a' stampi in output una stringa della stessa lunghezza ma fatta di tutte 'b'?
Ad esempio:
input: aaaa
output: bbbb
oppure:
input: aa
ouput: bb
Vediamo un po' chi si fa avanti :-)
(edited)
Sareste capaci di creare una macchina di Turing che, presa in input una stringa fatta da tutte 'a' stampi in output una stringa della stessa lunghezza ma fatta di tutte 'b'?
Ad esempio:
input: aaaa
output: bbbb
oppure:
input: aa
ouput: bb
Vediamo un po' chi si fa avanti :-)
(edited)
Quando c'avevan fatto il doodle di google non c'avevo capito na mazza...
Ho letto.. ma davvero, non ci ho capito nulla.. sorry :/
Ok, Ste. Supponi che allo stato iniziale ci sia un carattere 'a' sulla testina. Qualcosa del genere:
| a | | | | ...
↑
Mettiamo il caso che io voglia costruire una macchina di Turing che se vede 'a' allo stato iniziale ci scrive sopra un 1 e termina, e se non vede 'a' si ferma senza fare niente. Ecco le coppie [CONDIZIONE, AZIONE]:
0 a 1 * halt
0 * * * halt
La prima dice che, se nello stato iniziale (0) la testina sta leggendo 'a', allora scrive '1', la testina rimane ferma (*) e la macchina si arresta (halt).
La seconda dice che se nello stato 0 la testina vede qualunque altra cosa (primo *), allora non scrive nulla (secondo *), non si sposta (terzo *), e la macchina si arresta (halt).
Adesso ti è più chiaro come interpretare queste quintuple?
(edited)
| a | | | | ...
↑
Mettiamo il caso che io voglia costruire una macchina di Turing che se vede 'a' allo stato iniziale ci scrive sopra un 1 e termina, e se non vede 'a' si ferma senza fare niente. Ecco le coppie [CONDIZIONE, AZIONE]:
0 a 1 * halt
0 * * * halt
La prima dice che, se nello stato iniziale (0) la testina sta leggendo 'a', allora scrive '1', la testina rimane ferma (*) e la macchina si arresta (halt).
La seconda dice che se nello stato 0 la testina vede qualunque altra cosa (primo *), allora non scrive nulla (secondo *), non si sposta (terzo *), e la macchina si arresta (halt).
Adesso ti è più chiaro come interpretare queste quintuple?
(edited)
Ok, prova risolvere il quesito che ho posto scrivendo delle quintuple che "mettano in moto" il simulatore che ho linkato e fammi sapere :-D.
- 1