La macchina ufficiale – Programmare con la macchina di Turing!

Esistono molte implementazioni della macchina di Turing, reperibili in rete, che permettono di sperimentare.

Attenzione: implementazioni diverse hanno sintassi diverse!

La macchina ufficiale della Gara Nazionale è quella a destra: Turing Machine Simulator.

Alcune informazioni

Scrivi il programma nell’area di testo in alto a destra.
Inserisci l’input nella casella di testo in basso a sinistra.
Velocità: si può rallentare o accelerare l’esecuzione del programma (0, 1, …, 9, 10).
Esegui: inizia l’esecuzione del programma.
Stop: ferma l’esecuzione del programma.
Lo stato attuale è visibile sullo schermo (lo stato iniziale è sempre 0).
Non è specificato uno stato di arresto ufficiale, la macchina si arresta quando incontra una situazione non prevista.
La macchina non fa distinzione tra le lettere minuscole e maiuscole.
La testina inizia a lavorare sempre sul primo carattere a sinistra della stringa input.
Se non specificato altrimenti negli esercizi, le sequenze iniziali su nastro si intendono non vuote, ovvero contenenti almeno un simbolo.
Nel fornire le soluzioni, ricordarsi di pulire il nastro finale da ogni simbolo che non costituisca la risposta!
Per numero decimale si intende un numero positivo o nullo rappresentato con le cifre 0, 1, 2, …, 9, senza zeri iniziali non significativi. Per esempio 0 e 19 sono numeri validi, mentre 0032 deve essere scritto come 32.

Quintuple

Le quintuple hanno la forma: $(s_x,c_1,s_y,c_2,>)$
Dopo la virgola si può lasciare uno spazio: $(s_x, c_1, s_y, c_2, >)$
Il carattere vuoto (spazio) viene rappresentato con il segno meno: $(s_x, -, s_y, -, >)$
Lo spostamento è uno dei 3 caratteri
- > , destra
- <, sinistra
- -, fermo
Il segno meno indica il carattere bianco/vuoto e anche lo spostamento nullo.

Per semplificare la scrittura delle quintuple sono state introdotte delle regole sintattiche che permettono di riassumere quintuple simili

Quintupla	equivale a…	?
$(s_x, c_1c_2c_3, s_y, c_ac_bc_c, >)$	$(s_x, c_1, s_y, c_a, >)$ $(s_x, c_2, s_y, c_b, >)$ $(s_x, c_3, s_y, c_c, >)$	Una sequenza di caratteri in input Una sequenza di caratteri in output
$(s_x, [c_1c_2c_3], s_y, c, >)$	$(s_x, c_1, s_y, c, >)$ $(s_x, c_2, s_y, c, >)$ $(s_x, c_3, s_y, c, >)$	Una sequenza di caratteri in input Un carattere in output
$[0..9]$	$[0123456789]$	Un intervallo di cifre
$[A..Z]$	$[ABCDEFGHIJKLMNOPQRSTUVWXY]$	Un intervallo di lettere
$stato[A..Z]$	$statoA$ … $statoZ$	Una sequenza di stati