Accesso

Cherubino     Gara nazionale di programmazione della
Macchina di Turing
 
 

Estensioni 2006 al Simulatore



Il Simulatore usato negli anni precedenti includeva già una forma di abbreviazione sintattica, consistente nel specificare una sequenza di caratteri anziché un carattere singolo nei campi della quintupla che indicano il carattere letto da nastro e quello scritto su nastro. Tale abbreviazione veniva poi espansa in un numero di regole pari alla lunghezza della sequenza di caratteri, come nell'esempio seguente:

regola con abbreviazione:

( stato1, ABCD, stato2, EFGH, > )

regole generate dall'espansione:

( stato1, A, stato2, E, > )

( stato1, B, stato2, F, > )

( stato1, C, stato2, G, > )

( stato1, D, stato2, H, > )



La versione 2006 del Simulatore generalizza questo meccanismo, introducendo i concetti di classe di simboli e di espansione parallela.



Classi di simboli

Una classe di simboli è una abbreviazione sintattica che denota una sequenza di simboli compresi nell'alfabeto della macchina (con lo spazio primo elemento dell'alfabeto):

 !\"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^-{|}

La denotazione è costituita da una coppia di parentesi quadre [] o graffe {}, contenenti uno o più simboli appartenenti alla sequenza, o il simbolo di intervallo (due volte punto) s1..s2, che indica tutti i simboli compresi fra s1 e s2 nell'alfabeto della macchina. Inoltre, se il primo carattere all'interno delle parentesi è un accento circonflesso ^ (in Inglese caret), si intende che la sequenza denotata è data dall'insieme complementare di quello indicato, ovvero comprende tutti i simboli non elencati all'interno delle parentesi. In questo caso, l'ordine della sequenza è quello naturale dell'alfabeto usato. Infine, il simbolo di barra inversa \ (in Inglese backslash) indica che il successivo carattere deve essere inteso letteralmente: per esempio, \] denota il simbolo “]”, non l'eventuale parentesi di chiusura di una sequenza; \- denota il simbolo “-” e non lo spazio, ecc. Allo stesso modo, \\ denota il simbolo “\”, che altrimenti non sarebbe esprimibile.

NOTA: se si specificano pida quelle con parentesi. Questo fatto è importante per quanto riguarda l'espansione parallela discussa in seguito. La classe di caratteri senza parentesi è stata mantenuta per compatibilità con l'estensione precedente della macchina, ed è limitata solo alle componenti della regola differenti da uno stato.

Gli esempi seguenti chiariscono la notazione usata per le classi di simboli:

Abbreviazione

Sequenza di simboli corrispondente

[abc]

{a, b, c}

[0..9]

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

[^aeiou]

qualunque simbolo tranne le vocali, nell'ordine naturale

[\[\]()]

{ [, ], (, ) }

[^+\-*/0..9]

qualunque simbolo tranne le cifre e i simboli delle quattro operazioni: +, -, *, /, nell'ordine naturale

[0..9a..f+\-]

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, +, - } (cifre esadecimali con segno)



Le classi di simboli possono essere usate nei seguenti contesti:

  • per indicare uno stato iniziale o finale, nel qual caso può essere usato un prefisso e/o un postfisso che, unito a ciascuno dei simboli indicati dalla classe, genera il nome effettivo dello stato. Per esempio, lo stato indicato in maniera abbreviata con letto[0..9]r viene espanso nella sequenza di stati { letto0r, letto1r, letto2r, letto3r, letto4r, letto5r, letto6r, letto7r, letto8r, letto9r }.

  • per indicare un simbolo letto o da scrivere, nel qual caso la classe fornisce direttamente la sequenza dei simboli indicati. Per esempio, [0..9] viene espanso nella lista di simboli { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } (analogamente a quanto possibile con la precedente notazione 0123456789, che comunque rimane disponibile).

  • per indicare una direzione di movimento, nel qual caso la classe deve denotare una sequenza composta esclusivamente di simboli > e <. Per esempio, [>>><] viene espanso nella lista di direzioni { >, >, >, < }.



Espansione parallela

Abbiamo visto sopra che le classi di simboli possono essere delimitate da parentesi quadre [] o da parentesi graffe {}. In aggiunta, è possibile usare classi senza delimitatori, come per le vecchie sequenze del tipo 0123456789 (ora esprimibili anche con la sintassi abbreviata 0..9). Al momento dell'espansione di una regola abbreviata in un insieme di regole base, i tre diversi gruppi di classi di simboli vengono espansi parallelamente: tutte le classi delimitate con lo stesso tipo di parentesi vengono espanse, per ogni regola, nei simboli che occupano la stessa posizione nella sequenza; classi delimitate da parentesi diverse vengono invece espanse indipendentemente (e in combinazione fra loro).

Ciò consente di esprimere sinteticamente un grande numero di regole basate su prodotti cartesiani delle corrispondenti sequenze, come illustrato nei seguenti esempi:

Regola abbreviata

Espansione delle classi

Regole generate dall'espansione

( s, [0..3], q, [a..d], > )

In questo caso, le due classi racchiuse fra parentesi quadre vengono espanse in parallelo; quando il simbolo letto è 0 (primo elemento di [0..3]), il simbolo scritto sarà a (primo elemento di [a..d]), e così via.

[0..3] = 0, 1, 2, 3

[a..d] = a, b, c, d

(s, 0, q, a, >)

(s, 1, q, b, >)

(s, 2, q, c, >)

(s, 3, q, d, >)


( s, [0..9], riporto[000000001], [1..90], > )

Questa regola mostra come sia possibile legare il simbolo letto, quello scritto, e il nome dello stato finale tramite un'unica espansione. In questo caso, se viene letto un simbolo fra 0 e 8 viene scritto lo stesso simbolo aumentato di 1 (quindi, fra 1 e 9) e si va nello stato riporto0; se invece viene letto un 9, si scrive uno 0 e si passa allo stato riporto1.

[0..9] = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

riporto[000000001] = riporto0, riporto0, riporto0, riporto0, riporto0, riporto0, riporto0, riporto0, riporto1

[1..90] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 0

(s, 0, riporto0, 1, >)

(s, 1, riporto0, 2, >)

(s, 2, riporto0, 3, >)

(s, 3, riporto0, 4, >)

(s, 4, riporto0, 5, >)

(s, 5, riporto0, 6, >)

(s, 6, riporto0, 7, >)

(s, 7, riporto0, 8, >)

(s, 8, riporto0, 9, >)

(s, 9, riporto1, 0, >)

( s[0..4], a..d, r[0..4], [a..d], <><>)

In questa regola si fa uso di due gruppi di classi, uno senza parentesi e uno fra parentesi quadre. Ciascun gruppo si espande in sequenze di lunghezza 4, quindi verranno prodotte complessivamente 16 regole. Anche in questo caso, le classi corrispondenti vengono espanse in parallelo (il primo simbolo di ogni sequenza con il primo simbolo di tutte le altre sequenze che usano lo stesso delimitatore), mentre classi con delimitatori diversi vengono espanse indipendentemente.

Nel nostro caso, tutte le volte che s[0..4] espande in s0, r[0..4] espanderà in r0 e [a..d] in a (primo simbolo di ciascuna sequenza); quando s[0..4] espande in s1, r[0..4] espanderà in r1 e [a..d] in b, ecc.

In ciascuno di questi casi, a..d e <><> espanderanno, rispettivamente, nel primo, secondo, terzo e quarto elemento della sequenza, rispettivamente. Il risultato finale sono le 16 regole visibili accanto.

Classi senza parentesi:

a..d = a, b, c, d

<><> = <, >, <, >


Classi con parentesi quadre:

s[0..4] = s0, s1, s2, s3, s4

r[0..4] = r0, r1, r2, r3, r4

[a..d] = a, b, c, d

( s0, a, r0, a, <)

( s0, b, r0, a, >)

( s0, c, r0, a, <)

( s0, d, r0, a, >)



( s1, a, r1, b, <)

( s1, b, r1, b, >)

( s1, c, r1, b, <)

( s1, d, r1, b, >)



( s2, a, r2, c, <)

( s2, b, r2, c, >)

( s2, c, r2, c, <)

( s2, d, r2, c, >)



( s3, a, r3, d, <)

( s3, b, r3, d, >)

( s3, c, r3, d, <)

( s3, d, r3, d, >)

(rd_[ab], {012}, wr_[ab], {abc}, <)

Anche in questo caso vengono usati due gruppi di classi, quelle delimitate da [] e quelle delimitate da {}. Come visto in precedenza, i due gruppi vengono espansi in parallelo; verranno quindi generate in totale 6 regole.

Classi con parentesi quadre:

rd_[ab] = rd_a, rd_b

wr_[ab] = wr_a, wr_b


Classi con parentesi graffe:

{012} = 0, 1, 2

{abc} = a, b, c

(rd_a, 0, wr_a, a, <)

(rd_a, 1, wr_a, b, <)

(rd_a, 2, wr_a, c, <)



(rd_b, 0, wr_b, a, <)

(rd_b, 1, wr_b, b, <)

(rd_b, 2, wr_b, c, <)



Alcuni esempi

Mostriamo ora alcuni esempi di utilizzo dei nuovi costrutti. Per ciascun esempio, sono indicate il testo del problema che viene risolto, una versione della soluzione usando la sintassi tradizionale, una versione con la nuova sintassi, e l'espansione delle regole con la nuova sintassi.

  1. Odometro: scrivere un programma per macchina di Turing che, ricevuto sul nastro una stringa di cifre decimali, lasci sul nastro al termine dell'esecuzione la stringa di cifre corrispondente al numero iniziale, incrementato di uno. Se il risultato supera il numero di cifre inizialmente presenti, il programma deve lasciare sul nastro una stringa di soli 0 (comportamento simile a quello dei normali contachilometri).

    Strategia di soluzione

    Versione abbreviata

    Versione espansa

    Dapprima (stato 0) ci si posiziona sull'ultima cifra a destra del numero; quindi (stato 1) si incrementa la cifra corrente. Se la cifra era compresa fra 0 e 8, viene fatto l'incremento e l'esecuzione termina. Se invece la cifra corrente era 9, viene scritto al suo posto uno 0 e si passa a incrementare la cifra precedente (riporto).

    (0,[0..9],0,[0..9],>)

    (0,-,1,-,<)

    (1,[0..8],FINE,[1..9],>)

    (1,9,1,0,<)

    (0,0,0,0,>)

    (0,1,0,1,>)

    (0,2,0,2,>)

    (0,3,0,3,>)

    (0,4,0,4,>)

    (0,5,0,5,>)

    (0,6,0,6,>)

    (0,7,0,7,>)

    (0,8,0,8,>)

    (0,9,0,9,>)

    (0,-,1,-,<)

    (1,0,FINE,1,>)

    (1,1,FINE,2,>)

    (1,2,FINE,3,>)

    (1,3,FINE,4,>)

    (1,4,FINE,5,>)

    (1,5,FINE,6,>)

    (1,6,FINE,7,>)

    (1,7,FINE,8,>)

    (1,8,FINE,9,>)

    (1,9,1,0,<)

  2. Palindrome: scrivere un programma per macchina di Turing che, ricevuta sul nastro una stringa sull'alfabeto a-z, lasci il nastro vuoto alla fine della computazione se e solo se la stringa originale era palindroma (si dicono palindrome le stringhe che si leggono identicamente da sinistra a destra o da destra verso sinistra, per esempio “ailatiditalia” o “satorrotas”).

    Strategia di soluzione

    Versione abbreviata

    Versione espansa

    Posizionati sul primo carattere a sinistra della stringa, lo cancelliamo, memorizziamo nel nome dello stato il carattere letto, passando nello stato lettoa (se abbiamo letto una a) fino a lettoz (se abbiamo letto una z). Quindi scorriamo tutta la stringa, mantenendo memoria nello stato di quale carattere avevamo letto, e riscrivendo sempre il carattere letto. Arrivati in fondo alla stringa, ci spostiamo di una cella a destra (sempre mantenendo il carattere letto originalmente nello stato), e verifichiamo di trovare all'estremità sinistra della stringa lo stesso carattere che avevamo letto a destra. In caso positivo, si cancella il carattere e si ritorna in cima alla stringa, ripetendo poi l'algoritmo (fino a consumare tutta la stringa); in caso negativo si interrompe il calcolo, lasciando sul nastro la parte di stringa non palindroma.

    (0,[a..z],letto[a..z],-,>)

    (letto[a..z],{a..z},letto[a..z],{a..z},>)

    (letto[a..z],-,destra[a..z],-,<)

    (destra[a..z],[a..z],ritorno,-,<)

    (ritorno,[a..z],ritorno,[a..z],<)

    (ritorno,-,0,-,>)

    (0,a,lettoa,-,>)

    ...

    (0,z,lettoz,-,>)

    (lettoa,a,lettoa,a,>)

    (lettoa,b,lettoa,b,>)

    ...

    (lettoa,z,lettoa,z,>)

    (lettob,a,lettob,a,>)

    ...

    (lettob,z,lettob,z,>)

    ...

    (lettoz,a,lettoz,a,>)

    ...

    (lettoz,z,lettoz,z,>)

    (lettoa,-,destraa,-,<)

    ...

    (lettoz,-,destraz,-,<)

    (destraa,a,ritorno,-,<)

    ...

    (destraz,z,ritorno,-,<)

    (ritorno,a,ritorno,a,<)

    ...

    (ritorno,z,ritorno,z,<)

    (ritorno,-,0,-,>)