La macchina ufficiale

Esistono molte implementazioni della macchina di Turing, reperibili in rete, che permettono di sperimentare.
La sintassi può presentare notevoli differenze!

La macchina ufficiale della Gara Nazionale è

Alcune informazioni

  1. Scrivi il programma nell’area di testo in alto a destra
  2. Inserisci l’input nella casella di testo in basso a sinistra
  3. Passa all’esecuzione (e al debugging…)
    • 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
  4. Lo stato iniziale è sempre 0.
  5. Non è specificato uno stato di arresto ufficiale, la macchina si arresta quando incontra una situazione non prevista.
  6. La macchina non fa distinzione tra le lettere minuscole e maiuscole.
  7. La testina inizia a lavorare sempre sul primo carattere a sinistra della stringa input.

Quintuple

  1. Le quintuple hanno la forma : (stato1,carattere1,stato2,carattere2,spostamento)
  2. Dopo la virgola si può lasciare uno spazio: (stato1, carattere1, stato2, carattere2, spostamento)
  3. Il carattere vuoto (spazio) viene rappresentato con – (il segno meno)
  4. Gli spostamenti sono
    • > , destra
    • <, sinistra
    • –, fermo
  5. Quindi il segno meno indica il carattere bianco/vuoto e indica anche lo spostamento nullo.

Sintassi aggiuntiva

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

(sx, c1c2c3, sy, cacbcc, m)(sx, c1, sy, ca, m)
(sx, c2, sy, cb, m)
(sx, c3, sy, cc, m)		Una sequenza di caratteri in input
Una sequenza di caratteri in output
(sx, [c1c2c3], sy, ca, m)(sx, c1, sy, ca, m)
(sx, c2, sy, ca, m)
(sx, c3, sy, ca, m)		Una sequenza di caratteri in input
Un carattere in output
[0..9][0123456789]Intervallo delle cifre
[A..Z][ABCDEFGHIJKLMNOPQRSTUVWXYZ]Intervallo delle lettere
stato[A..Z]statoA, statoB, statoC, …, statoZSequenza di stati

Avvisi ufficiali per la soluzione degli esercizi

  1. Se non specificato altrimenti negli esercizi, le sequenze iniziali su nastro si intendono non vuote, ovvero contenenti almeno un simbolo.
  2. 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.
  3. Nel fornire le soluzioni, ricordarsi di pulire il nastro finale da ogni simbolo che non costituisca la risposta!

Lascia un commento