La macchina ufficiale

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 è Turing Machine Simulator.

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. Velocità: si può rallentare o accelerare l’esecuzione del programma (0, 1, …, 9, 10).
  4. Esegui: inizia l’esecuzione del programma.
  5. Stop: ferma l’esecuzione del programma.
  6. Lo stato attuale è visibile sullo schermo (lo stato iniziale è sempre 0).

Quintuple

La sintassi delle quintuple è specifica…

  1. Le quintuple hanno la forma: (s_x,c_1,s_y,c_2,>)
  2. Dopo la virgola si può lasciare uno spazio: (s_x, c_1, s_y, c_2, >)
  3. Il carattere vuoto (spazio) viene rappresentato con il segno meno: (s_x, -, s_y, -, >)
  4. Lo spostamento è uno dei 3 caratteri
    • > , destra
    • <, sinistra
    • -, fermo
  5. 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

Quintuplaequivale 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 … statoZUna sequenza di stati

Regole specifiche della competizione

  • 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.

Lascia un commento