Valeria Vittorini » 4.La Macchina di Turing

La macchina di Turing

La Macchina di Turing (1936) è un modello fondamentale nella teoria dell’informatica.
Consente di approfondire il concetto di algoritmo.
Ha consentito di ottenere importanti risultati relativamente alla calcolabilità, alla complessità ed alla equivalenza di algoritmi.

La Macchina di Turing è un ASF (vedi lezione 3) esteso con un meccanismo di lettura e memorizzazione dei simboli.

E’ di fatto un dispositivo composto da:

Un ideale nastro, cioè una striscia continua di celle ciascuna delle quali può essere vuota o contenere i simboli di un alfabeto.
Una testina di lettura-scrittura.
Un dispositivo di controllo (ASF) che in ogni istante si trova in uno tra un numero finito di stati.

La testina di lettura-scrittura può compiere le seguenti azioni elaborative (vedi lezione 2) elementari:

Spostamento testina di una posizione (a sinistra o a destra).
Scrittura di un simbolo nella cella sotto la testina (sostituendo il contenuto precedente).

Il dispositivo di controllo per ciascuna coppia (stato-simbolo letto):

Una TM è completamente individuata dalle seguenti informazioni:

Contenuto iniziale del nastro.
Descrizione della TM, d(TM):
- Posizione iniziale della testina.
- Stato iniziale del dispositivo di controllo.
- Tabella delle transizioni di stato (che indica in corrispondenza della coppia stato-simbolo letto, oltre allo stato successivo ed all’eventuale simbolo scritto anche la direzione del movimento della testina).

Una TM esegue una elaborazione Y=F(X) (vedi lezione 2)

NOTA: d(TM) descrive la macchina.

Costruiamo una TM che risolva lo stesso problema affrontato nella lezione precedente (automi a stati finiti): costruiamo una macchina che valuti se il numero di occorrenze del simbolo 1 in una sequenza di 0 e 1 è pari.
In questo caso consideriamo in aggiunta che la sequenza debba iniziare e terminare con un simbolo speciale, ad esempio @.
Rappresentazione della sequenza: @0101110@
Rappresentazione del risultato:
- Numero di 1 pari, la macchina scrive 1 nella prima casella a destra della stringa di ingresso
- Numero di 1 dispari, la macchina scrive 0 nella prima casella a destra della stringa di ingresso

Il dispositivo di Controllo è un automa:

Stati:

Stato S: stato iniziale in cui la macchina resta fino a quando non individua la stringa di ingresso sul nastro.
Stato P: il numero di 1 esaminato è pari.
Stato D: il numero di 1 esaminato è dispari.
Stato E: la macchina ha eseguito l’algoritmo e si ferma.

Ingressi

Uscite

Spostamento a destra (>), spostamento a sinistra (<), resta fermo (f), scrivi 1 (S1), scrivi 0 (S0)

Una TM che si arresti e trasformi un nastro t in un nastro t’ rappresenta l’algoritmo per l’elaborazione Y=F(X).
In altre parole la TM “calcola” Y=F(X).
Tesi di Church: non esiste un formalismo né una macchina concreta che possa calcolare una funzione F non calcolabile secondo Turing.

Un algoritmo è ciò che può essere realizzato con una macchina di Turing!
Le funzioni sono tutte calcolabili? La risposta è NO! Cioè esiste una classe di funzioni F per le quali non esiste una macchina di Turing in grado di calcolarle.
- In particolare, si dimostra che non esiste una TM – e quindi un algoritmo – in grado di decidere se data una qualsiasi macchina d(T) ed un qualsiasi nastro t, la macchina d(T) si arresta sul nastro t (problema dell’arresto).
Quindi: esistono problemi che per loro natura non sono risolvibili da alcuna macchina finora costruita!