Emanuele Scapin - Macchina di Turing

Un formalismo molto più potente degli automi è la macchina di Turing (MdT). Alan Turing tentò di carpire l’essenza del calcolo osservando un uomo che computava. L’uomo legge,cancella e scrive simboli, di fronte a ogni simbolo decide cosa fare guidato da una serie finita di regole. In ogni momento ha una quantità di carta finita, ma che potenzialmente non ha limiti di disponibilità.
La macchina di Turing si ottiene dotando un automa di un nastro illimitato su cui possono essere scritti e letti caratteri di un apposito alfabeto. L’automa a stati finito controlla i movimenti del nastro e decide se il procedimento è terminato. Le azioni dell’automa dipendono dal suo stato e dal simbolo letto. Le operazioni sul nastro consistono nella lettura del simbolo, della scrittura di un nuovo simbolo, nello spostamento dl punto di lettura a destra oppure a sinistra.
All’inizio dell’elaborazione il nastro contiene tutti simboli vuoti ad eccezione di una suo porzione finita che contiene una stringa di ingresso, l’automa è nel suo stato iniziale e il punto di lettura è posizionato all’inizio della stringa.
Se l’elaborazione termina in un numero finito di passi il risultato è formato dalla porzione di nastro, evidentemente finita, che contiene simboli diversi da quello vuoto. Se l’elaborazione non termina non c’è risultato.
Non è possibile sapere a priori quando l’elaborazione terminerà ed è una caratteristica di tutti i formalismi.

La novità fondamentale della macchina di Turing rispetto agli automi a stati finiti è nella possibilità oltre che di leggere simboli in ingresso anche di scriverli, e inoltre l’organo di lettura e scrittura può muoversi avanti e indietro potendo elaborare l’informazione in modo bidirezionale.

Definizione 10: Una macchina di Turing (MdT) è definita dalla quintupla T = < Q , S , d , s , F >, dove
Q è un insieme finito di stati,
S è un alfabeto finito di simboli di ingresso, che contiene il simbolo vuoto (l oppure b),
s ? Q è lo stato iniziale,
F Í Q è un insieme di stati finali,
d è la funzione di transizione, che associa ad ogni coppia (x, q), con x Î S e q Î Q, la tripla
(a, y, m) con a Î S , y Î Q, m Î {destra, sinistra}.
Non è richiesto che d sia definita per tutte le coppie (x, q), comunque la funzione è data elencando tutte le quintuple (x, q, a, y, m) per cui d(x, q) e definita.

Definizione 11: si dice configurazione di una MdT la tripla (a, q, i) dove q è lo stato attuale, a è la stringa ottenuta dal nastro togliendo gli spazi vuoti e i è la distanza del punto di lettura dall’inizio di a.

Definizione 12: si definisce mossa di una MdT il passaggio da una configurazione a un’altra, che avviene come segue:
sia a = a₁a₂…a_n, il simbolo di lettura a è a_i se 1 £ i £ n, altrimenti è l,
se d(a,q) = (b, y, m) allora la nuova configurazione sarà (b, y, j) con b la stringa ottenuta sul nastro, ignorando gli spazi vuoti, dopo aver sostituito il simbolo di lettura a con b, j è la posizione del nuovo punto di lettura rispetto all’inizio di b. Se il nuovo stato y appartiene a F il procedimento termina.

Se all’inizio la MdT è nella configurazione (a, s, 1) e al termine è nella configurazione (b, q, i), b sarà il risultato dell’applicazione della MdT alla stringa a.

Esempio 19: una semplice MdT che scandisce una stringa di 0 e 1, sostituendo gli 1 con 0 e fermandosi quando trova il primo spazio b (l).
T = ( {0, 1, b} , {A, B} , d, A, {B} ) con d data dalle seguenti quintuple:
0,A,A,0,destrache riscrive gli zeri e sposta a destra la testina,
1,A,A,0,destrache converte gli 1 in 0,
b,A,B,b,destrache termina quando la stringa è finita.
Se la stringa da elaborare è 0111010 e sapendo che la macchina all’inizio è nello stato A e il nastro contiene …bb0111010bb…, con il punto di lettura posizionato sul primo 0 a sinistra (il primo simbolo della stringa), si avrà
(A, b0111010b, 0) la configurazione iniziale,
indicando in neretto il simbolo da leggere (punto di lettura) si avrà la seguente sequenza di configurazioni
(A, b0111010b, 0),
(A, b0111010b, 1),
(A, b0011010b, 2),
(A, b0001010b, 3),
(A, b0111010b, 4),
(A, b0111010b, 5),
(A, b0111000b, 6),
(A, b0111010b, 7),
(B, b0111010b, 7),
e l’elaborazione termina in quanto B è lo stato finale.

Questa è una delle tante possibili definizione di macchina di Turing, è però possibile dimostrare che tutte le possibile definizioni sono equivalenti.

Definizione 13: una funzione f:A* àA* si dice Turing calcolabile se esiste una MdT che prendendo una stringa a Î A* come ingresso, produce f(a) come uscita.

Vediamo perché il formalismo delle MdT sia così rilevante e collega la calcolabilità alla possibilità di realizzare un sistema fisico che rappresenti adeguatamente i dati e il cui funzionamento sia una simulazione fisica di passi di calcolo.
I.Con le macchine di Turing è possibile realizzare ogni tipo di algoritmo ed è verificabile caso per caso per costruzione diretta.
II.Tutte le definizioni conosciute di modelli di calcolo sufficientemente potenti sono tra loro equivalenti ed equivalenti al modello delle macchine di Turing. E’ stato dimostrato rigorosamente, per ogni formalismo di una certa potenza, l’equivalenza con le MdT, mentre gli automi a stati finiti sono un formalismo meno potente e non equivalenti.
III.Ogni definizione che possa mai venire pensata di un modello di calcolo che soddisfi requisiti di potenza è equivalente a quelle conosciute e in particolar modo alle macchine di Turing. Questa è la nota tesi di Alonzo Church comunemente ritenuta vera ma non dimostrabile.

In altri termini si può scrivere la seguente.
Tesi di Church: le macchine di Turing sono una classe di automi computazionalmente universali.

Questo enunciato non è dimostrato, potrebbe infatti essere scoperta una macchina che calcola una funzione non Turing calcolabile. Non è possibile dimostrare matematicamente l’impossibilità di un tale evento in quanto nessuna teoria matematica può dimostrare la non esistenza di un oggetto che non è definito.
Fino ad oggi non ci sono smentite convincenti della tesi di Church, nonché tutti i modelli di calcolo che sono stati proposti, anche molto diversi tra loro, si sono sempre rivelati equivalenti alle macchine di Turing.
I vari modelli proposti rientrano in tre categorie fondamentali:
1.i tipi fisico-simulativi propri delle macchine, di Turing, a registri, di Von Neumann.
2.i tipi logico-simbolici basati sulla trasformazione di stringhe come i sistemi di Post, di Thue e di Markov.
3.i tipi matematico-funzionali basati su classi di funzioni costruite a partire da alcune funzioni iniziali, quali successore, selettori, costanti e metodi di definizione di funzioni composte (funzioni ricorsive, iterative, elementari).

Evidentemente l’equivalenza tra Macchine di Turing e macchine a registri e di Von Neumann si collega agli argomenti da trattare successivamente come la struttura e il funzionamento di un sistema a microprocessore generico e successivamente nel trattare un caso specifico come la classe Intel 8086/8088 oppure Motorola 68000.

Le macchine di Turing possono essere usate come riconoscitori di linguaggi. Si pone la stringa da esaminare sul nastro e la si considera accettata se e solo se dopo un numeri finito di passi l’elaborazione termina in uno stato finale. In questo modo ogni MdT definisce un linguaggio.

Teorema 2: un linguaggio è riconoscibile da una macchina di Turing se e solo se è generabile da una grammatica di tipo 0.

Che dimostra l’equivalenza tra macchine di Turing e grammatiche formali. La tesi di Church ci convince che non esistono formalismi più potenti delle grammatiche formali per generare linguaggi e che la classe dei linguaggi di tipo 0 è la più ampia di cui si può ragionare in termini algoritmici.

Altro materiale sulla Macchina di Turing (Università di Pisa)

Simulatore (Università di Pisa)