Una macchina di Turing in CML 18 December 2010
Le macchine di Turing, ad oggi …hanno scarse applicazioni nella programmazione pratica. O meglio …lavorano così a basso livello che è estremamente difficile riuscire a programmarci qualcosa senza diventare pazzi!
Nonostante questo sono ancora il fulcro di tutta la teoria della calcolabilità su cui si basano gli attuali calcolatori.
E sono anche un modo simpatico per dimostrare la potenza di un linguaggio: se riuscite a creare una macchina di Turing con un linguaggio, allora quel linguaggio è Turing completo, e significa che può potenzialmente calcolare tutte le cose che sono calcolabili da mostri sacri come C o Java.
Certo, tra realizzare un programma in Java o in Assembler c’è una gran bella differenza, ma è solo una questione di espressività. Ovvero, di ciò che possiamo tralasciare. Ma questa è un’altra storia…
Vediamo ora come è possibile realizzare nel linguaggio CML una macchina di Turing.
Una macchina di Turing è definita dalla quintupla composta da:
- S: elenco degli stati,
- S0: stato iniziale,
- F: insieme degli stati finali,
- A: alfabeto del nastro,
- b: segno della casella vuota,
- d: funzione di transizione degli stati.
Per implementare in CML il concetto di stato, verrà usata un’emozione. Gli stati saranno identificati da un numero che varia da 0 a “max_state”. Lo stato iniziale sarà considerato senza perdita di generalità “0”.
<EMOTION name = "state" initialValue = "0" minValue = "0" maxValue = "max_state" decay = "0" />
Quando l’emozione “state” assumerà il valore “x” affermeremo che la macchina di Turing si trova nello stato rappresentato dal codice “x”.
Dovendo materialmente definire il nastro sul quale la computazione avrà luogo, ci limiteremo ad un insieme finito di celle disponibili. Tuttavia sarà sempre possibile modificare il programma per prevederne un numero arbitrariamente grande e potenzialmente non limitato.
Ogni cella del nastro è rappresentata da una singola emozione che potrà assumere valori numerici tra zero e la cardinalità dell’insieme “A“, con la seguente semantica: quando l’emozione “cell_xx” assume il valore “x”, la cella numero “xx” conterrà l’”x”-esimo simbolo dell’alfabeto .
<EMOTION name = "cell_xx" initialValue = "0" minValue = "0" maxValue = "max_symbols" decay = "0" />
Il puntatore alla cella corrente sarà rappresentato da un’emozione, esattamente come fatto per lo stato.
<EMOTION name = "cell" initialValue = "0" minValue = "0" maxValue = "max_cells" decay = "0" />
Per convenzione, la testina della macchina di Turing sarà posizionata sulla prima cella, con indice “0”.
Il punto cruciale è realizzare il programma, definito dalla funzione di transizione “d“, nel seguente formato:
d : S x A → S x A x { -1, 0, +1 }
Quando la macchina di Turing si trova nello stato “s1” e legge “a1” dalla cella “c1” , passa allo stato “s2”, scrive “a2” nella cella corrente e decide come spostare il nastro (avanti, indietro o fermarsi) arrivando alla cella “c2”.
Per ogni combinazione della tripletta composta da uno stato non terminale, da una cella e dal suo valore presente, sarà creata una regola come segue:
<!-- Siamo nello stato “s1” --> <REQUIRED emotion = "state" type = "EQUALS" value = "s1" > <!-- Siamo nella cella “c1” --> <REQUIRED emotion = "cell" type = "EQUALS" value = "c1" > <!-- Il valore della cella “c1” è “a1” --> <REQUIRED emotion = "cell_c1" type = "EQUALS" value = "a1" > <!-- Questa regola si attiva sempre: ogni messaggio ricevuto manda la computazione avanti di un passo. --> <RULE regexp = ""> <!-- Trace dell'elaborazione --> <ANSWER text = "<s1 X a1 @ c1> → <s2 x a2 @ c2>" /> <!-- Cambia stato --> <UPDATE emotion = "state" value = "=s2" postpone = "true" /> <!-- Aggiorna il valore della cella --> <UPDATE emotion = "cell_c1" value = "=a2" postpone = "true" /> <!-- Sposta il nastro --> <UPDATE emotion = "cell" value = "=c2" postpone = "true" /> </RULE> </REQUIRED> </REQUIRED> </REQUIRED>
Per gli stati terminali possono essere create regole molto più semplici, poiché non richiedono alcuna computazione.
<!-- Siamo nello stato terminale “st” --> <REQUIRED emotion = "state" type = "EQUALS" value = "st" > <!-- Questa regola si attiva sempre: ogni messaggio ricevuto manda la computazione avanti di un passo. --> <RULE regexp = ""> <ANSWER text = "Stato terminale st raggiunto." /> </RULE> </REQUIRED>
Partendo una macchina di Turing con “s” stati (di cui “f” terminali), “a” simboli ed un nastro finito di “c” celle, abbiamo ottenuto un programma CML composto da:
- c+3 emozioni (una per lo stato corrente, una per la cella corrente, “c” per il valore delle celle ed “unknown” obbligatoria in CML),
- (s – f) x c x a + f regole (“f” per gli stati terminali e le restanti per la funzione di transizione degli stati non terminali),
- 1 categoria (“UNKNOWN”, obbligatoria in CML).
Varianti più significative di questa macchina di Turing potrebbero essere realizzate leggendo gli input dall’utente, invece che direttamente dal nastro, o effettuando calcoli aritmetici incrementando e decrementando le emozioni come avviene nel linguaggio Brainfuck.
Come detto all’inizio …una macchina di Turing in CML è sostanzialmente inutile.
Ma è la dimostrazione pratica che anche il CML è Turing completo. Alla faccia di chi pensa che ci si possano fare solo bot!