lezione Macchina di Turing
	Tipo: lezione
	Materia: Informatica teorica
	Avanzamento: lezione completa al 100%

Lezione precedente: Automa a pila

Corso: Materia:Informatica Teorica

Prossima lezione: Automa a stati finiti non deterministico

Obiettivo della lezione

L'obiettivo della presente lezione è l'introduzione di un nuovo modello computazionale: la macchina di Turing. Seppure questo formalismo possa sembrare semplicemente un'estensione degli automi a pila e degli automi a stati finiti, discuteremo i motivi che ci spingono a pensarlo come uno strumento differente, evidenziando la sua centralità nello studio della teoria della computazione sia in quanto formalismo a sé stante, sia come strumento per introdurre, discutere ed approfondire le tematiche della decidibilità e della complessità.

Introduzione storica

Nella seconda metà del diciannovesimo secolo il celebre matematico tedesco David Hilbert completò il monumentale lavoro di assiomatizzazione della geometria, riuscendo nell'impresa di ricostruire la disciplina a partire dalle sue fondamenta.

In seguito, la sua attenzione si rivolse al più generale ambito della matematica: la scoperta delle antinomie (paradossi) ed il lavoro di Bertrand Russell mettevano in evidenza alcune falle proprio nelle fondamenta della disciplina ed era necessario ripetere per questa materia lo stesso tipo di lavoro già svolto per la geometria. Le differenze tra i due ambiti sono però molte e Hilbert se ne rese conto; scelse perciò di non affrontare la sfida da solo, ma di coinvolgere il più possibile la comunità internazionale dei matematici.

Fu con questo spirito che Hilbert prese parte al Secondo Congresso Internazionale dei Matematici, svolto a Parigi nel 1900; in quella sede presentò la famosa lista dei problemi del secolo, ossia le sfide che avrebbero atteso i matematici durante il ventesimo secolo. Negli atti del congresso è presente la lista completa dei 23 problemi e tra questi ce n'è uno che merita particolare attenzione: nel decimo problema, Hilbert chiede di "Trovare un algoritmo che determini se una data equazione diofantea in n incognite abbia soluzione". L'aspetto curioso del problema si concentra interamente nel verbo trovare: Hilbert non si pone alcun dubbio circa l'esistenza dell'algoritmo, semplicemente chiede di identificarlo.

Nel 1970 il matematico russo Jurij Vladimirovič Matijasevič dimostrò una volta per tutte che l'algoritmo richiesto da Hilbert non può esistere. Nel lasso di tempo intercorso tra l'enunciazione del problema e la dimostrazione di non esistenza di una soluzione si inserisce il lavoro di un matematico inglese, Alan Mathison Turing, che con le sue intuizioni riuscì non solo a gettare chiarezza su uno degli aspetti più delicati dei fondamenti della matematica, ma diede il via ad una serie di eventi che portarono alla rivoluzione informatica che oggi tutti conosciamo.

Per capire meglio come andarono le cose, facciamo un passo indietro e torniamo al 1928. In quell'anno David Hilbert ed il suo allievo Wilhelm Ackermann scrissero un testo di logica formale dal titolo Grundzüge der theoretischen Logik. All'interno del libro veniva formulato il cosiddetto Entscheidungsproblem, di cui riportiamo una libera traduzione: "Il problema di decisione si risolve identificando una procedura che possa decidere in un numero finito di calcoli se una data espressione logica è generalmente valida o soddisfacibile. La soluzione al problema è di fondamentale importanza in molte discipline, nelle quali i teoremi vengono sviluppati logicamente a partire da un numero finito di assiomi".

I due autori si chiesero quindi se esistesse un algoritmo che, dati un insieme di assiomi ed una proposizione, permettesse di stabilire se quest'ultima si potesse dimostrare partendo dagli assiomi.

Di per sé il problema non è ben posto in quanto né Hilbert né Ackermann chiarirono cosa significasse sviluppare logicamente dei teoremi a partire da assiomi. Al di là di questa difficoltà, il senso della sfida fu chiaro per tutti ed i risultati non tardarono ad arrivare: già tre anni dopo Kurt Gödel, dimostrando il teorema di incompletezza, gettò qualche dubbio sulla possibilità che il problema di decisione potesse trovare una risposta positiva.

Si dovette attendere il 1936 quando, nel giro di pochi mesi, due matematici pubblicarono altrettanti lavori dimostrando che l'algoritmo cercato da Hilbert ed Ackermann in realtà non può esistere. I due protagonisti sono Alonzo Church ed Alan Turing che giunsero alla medesima conclusione seguendo strategie profondamente diverse.

Church basò il suo lavoro sulla logica e sull'algebra, sviluppando un'argomentazione fortemente astratta; al contrario, Turing immaginò un generico risolutore di problemi che, svolgendo ripetutamente uno stesso processo meccanico, sarebbe stato in grado di eseguire qualsiasi procedimento legato al calcolo.

Sebbene i risultati ottenuti dai due matematici siano logicamente equivalenti il lavoro di Turing acquisì più importanza in quanto, accanto alla soluzione del problema di scelta, delineava tramite la Macchina di Turing Universale (di cui parleremo più avanti) la possibilità di costruire dispositivi capaci di eseguire qualunque procedimento di calcolo: gli attuali computer. Col senno di poi possiamo affermare che dal punto di vista dell'architettura dei calcolatori, sviluppare macchine simili a quelle congetturate da Turing non sarebbe un buon affare; nonostante ciò, lo stimolo fornito dal matematico britannico è davvero pregevole.

Oltre alle ricadute tecnologiche derivanti dai principi descritti da Turing, c'è anche una questione di natura concettuale: il modello computazionale che chiamiamo macchina di Turing costituisce un fondamentale banco di prova per gli algoritmi; inoltre, la tesi di Church-Turing (che avremo modo di discutere più approfonditamente nella seconda parte del corso) afferma che un problema può essere risolto da un algoritmo se e solo se esiste una macchina di Turing in grado di risolverlo, definendo quindi il modello di Turing come un formalismo massimo, un punto di riferimento che si può al più eguagliare.

Contestualizzazione

Prima di addentrarci nello studio della macchina di Turing è corretto sottolineare il drastico cambiamento di punto di vista che stiamo attuando rispetto alle scorse lezioni: gli automi a stati finiti e gli automi a pila sono nati come strumenti di supporto allo svolgimento di attività molto concrete e solo in un secondo momento sono stati generalizzati; al contrario, la macchina di Turing è nata come modello computazionale astratto ed è proprio in tal senso che esprime il suo massimo potenziale.

Come gli automi a stati e a pila la macchina di Turing è un formalismo evolutivo, nel senso che è dotata di stati che cambiano durante la computazione, mostrando un'evoluzione. Come avremo modo di dimostrare, la classe di linguaggi riconoscibili da un accettore di Turing è più ampia rispetto a quelle degli altri automi visti finora, nel senso che gli accettori di Turing sono in grado di riconoscere tutti i linguaggi accettati dagli altri formalismi e anche linguaggi che questi ultimi non sono in grado di accettare. In questa parte della lezione cercheremo di capire il motivo per cui le macchine di Turing sono accettori migliori rispetto agli automi a pila ed a stati finiti.

Come prima cosa è bene riflettere sulle differenze esistenti tra gli automi che conosciamo: sappiamo infatti che gli accettori a pila sono più potenti degli accettori a stati finiti ed il motivo è dovuto alla possibilità di memorizzare dei dati. D'altra parte sappiamo anche che gli automi a pila non sono in grado di riconoscere il linguaggio $L=\left\{a^{n}b^{n}c^{n}|n>0\right\}$ : il motivo sta nella necessità di svuotare la pila per verificare che il numero di simboli $b$ combaci con il numero di simboli $a$ : al termine del conteggio si è persa l'informazione riguardante il numero di simboli da contare e non è più possibile garantire che il numero di simboli $c$ rispetti il vincolo richiesto.

Questa osservazione permette di intuire come dovrebbe essere fatta la macchina di Turing per migliorare il modello degli automi a pila: il formalismo dovrebbe consentire di accedere a qualunque cella del nastro di memoria senza dover necessariamente rimuovere i precedenti; andrà quindi rivista la politica LIFO di gestione del nastro, prevedendo un accesso meno vincolato ai suoi contenuti.

Prima di presentare il modello computazionale della macchina di Turing è opportuno fare un confronto tra le strategie utilizzate nelle lezioni precedenti per introdurre gli automi e quella che invece verrà impiegata in questo caso; gli automi sono stati descritti a partire dalle loro possibili applicazioni, mentre per la macchina di Turing viene preferita una trattazione più astratta. Il bagaglio di conoscenze acquisito finora sarà senz'altro sufficiente a comprendere il contenuto della lezione.

Principio di funzionamento

Una macchina di Turing può essere immaginata come un dispositivo che legge e scrive dati su un nastro virtualmente infinito. L'immagine sottostante mostra una schematizzazione della macchina, dalla quale emergono tutti gli elementi che la caratterizzano.

La macchina è composta da tre parti:

un'unità di controllo;
un nastro di lunghezza illimitata, suddiviso in celle;
una testina che può leggere e scrivere dei simboli nelle celle del nastro; la testina può muoversi sia a destra che a sinistra.

Più precisamente, ogni cella può contenere solamente un simbolo e in un dato istante la testina può leggere o scrivere il contenuto di una sola cella. È possibile confrontare l'immagine schematica della macchina di Turing con quelle proposte per gli automi: si nota subito la mancanza della pila ed una certa somiglianza con lo schema degli automi a stati finiti.

La vera novità di questo modello computazionale è la grande libertà offerta alla testina: essa può leggere, scrivere e muoversi a destra e a sinistra. La possibilità di scrivere sul nastro garantisce alla macchina di Turing l'opportunità di conservare delle informazioni in modo da utilizzarle in un momento successivo della computazione. La possibilità di muovere la testina in due direzioni rende virtualmente accessibile qualsiasi cella del nastro in qualsiasi momento; questo comportamento contrasta molto con la situazione vista nel caso del nastro d'ingresso per gli automi: in quel contesto, dopo aver prelevato un simbolo dal nastro d'ingresso, la cella in cui si trovava non sarebbe stata più accessibile dal momento che la testina si sarebbe mossa inesorabilmente verso destra. La macchina di Turing ha quindi il pregio di garantire la massima accessibilità al nastro; a fronte di questo vantaggio c'è però un rischio: nulla vieta di costruire una macchina di Turing che ripeta ciclicamente le stesse operazioni lavorando sulle stesse celle del nastro, per un tempo indefinito. Esiste cioè la possibilità che, durante la computazione, una macchina di Turing entri in un ciclo da cui non uscirà più; come vedremo questa caratteristica avrà conseguenze importanti.

Prima di passare ad una definizione più formale del modello computazionale, descriviamo il ciclo di lavoro di questo dispositivo, in modo da formarci un'idea sul suo principio di funzionamento. Il ciclo di lavoro è costituito da tre passi:

lettura di un simbolo dal nastro d'ingresso;
scrittura di un simbolo sul nastro d'ingresso (opzionale);
modifica dello stato della macchina (opzionale).

In aggiunta a queste informazioni è importante sapere che, per poter operare correttamente, la macchina deve partire da uno stato iniziale ben preciso.

Caratteristiche della macchina di Turing

L'obiettivo di questa parte della lezione è analizzare la struttura formale della macchina di Turing in modo da raccogliere elementi utili per definire il modello computazionale in modo rigoroso. Il punto di riferimento sarà l'articolo di Turing del 1936, dove tutto ebbe inizio.

Secondo Turing la macchina deve contenere un insieme di stati (che lui chiama m-configurazioni): ognuno di essi descrive una condizione operativa del dispositivo.

La macchina deve poi interagire con il nastro, leggendo e scrivendo simboli; a tal proposito Turing parla di due diversi tipi di simboli: alcuni servono per descrivere il risultato della computazione (simboli del primo tipo), mentre altri servono da supporto (simboli del secondo tipo). I simboli dei due tipi, comunque, fanno parte di un unico alfabeto.

Infine la descrizione della macchina deve contenere un elemento che sia in grado di spiegare come evolve la computazione: nel suo articolo Turing impiega delle tabelle; seguiremo anche in questo caso il suo esempio, ma sarà necessario spiegare bene come sono strutturate. A tal proposito è necessario introdurre due concetti: la configurazione e la mossa.

Una configurazione di una macchina di Turing è una coppia ordinata di elementi in cui il primo è uno stato ed il secondo è una stringa di simboli che rappresenta il contenuto del nastro che si trova sotto alla testina e sulla sua destra. L'autore ha anche ideato una tecnica che permette di rappresentare la configurazione della macchina in modo molto semplice e leggibile: si tratta di scrivere una stringa nella forma $uqv$ , dove $u$ è una stringa che contiene i simboli del nastro che si trovano a sinistra della testina, $v$ è una stringa che contiene i simboli del nastro che si trovano a destra della testina e sotto di essa, $q$ indica lo stato in cui si trova la macchina ed infine il primo carattere della stringa $v$ è quello che si trova sotto la testina.

Per comprendere la tecnica scriviamo la configurazione della macchina di Turing presentata nella descrizione schematica del modello: a sinistra della testina ci sono i simboli $ab$ , sotto la testina e sulla sua destra c'è la stringa $baab$ e la macchina si trova nello stato $q_{1}$ . Sinteticamente, scriveremo $ab{\text{ }}q_{1}{\text{ }}baab$ ; si consideri poi che le due stringhe di simboli possono anche essere vuote: quando è vuota la stringa $u$ vuol dire che ci si trova all'inizio del nastro, mentre quando è vuota la stringa $v$ vuol dire che ci si trova alla fine.

Una mossa di una macchina di Turing è una terna ordinata di elementi in cui il primo indica lo stato prossimo, il secondo è un simbolo che la macchina scriverà al posto di quello che si trova sotto la testina ed il terzo è un comando per la testina. Più precisamente la testina può ricevere due comandi: il simbolo $L$ indica uno spostamento di una cella verso sinistra mentre il simbolo $R$ indica uno spostamento di una cella verso destra.

Prima di passare alla definizione formale è utile discutere un'ultima caratteristica riguardante il nastro: per avere la garanzia che la cella letta sia vuota viene utilizzato un simbolo convenzionale che deve sempre far parte dell'alfabeto.

Con questi elementi è ora possibile definire in modo rigoroso che cosa sia una macchina di Turing.

Definizione di macchina di Turing

Una macchina di Turing è una sestupla ordinata di elementi $M=(Q,\Gamma ,\Sigma ,\delta ,q_{0},\Delta )$ in cui ogni elemento è definito come segue:

$Q$ è un insieme finito di stati;
$\Gamma$ è un insieme finito di simboli detto alfabeto del nastro;
$\Sigma$ è un insieme finito di simboli detto alfabeto d'ingresso. Deve verificarsi la condizione $\Sigma \subseteq \Gamma$ ;
$\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \left\{L,R\right\}$ è la funzione di transizione;
$q_{0}\in Q$ è lo stato iniziale;
$\Delta \in \Gamma$ è un simbolo che indica la cella vuota.

Ora che abbiamo elencato gli elementi che caratterizzano le macchine di Turing, il miglior modo per comprenderli consiste nella presentazione di alcuni esempi, con il pretesto di osservare il formalismo all'opera.

Esempio 1 - Stampa di una successione illimitata

In questo esempio mostreremo una macchina di Turing molto semplice, la stessa che viene riportata dal matematico inglese nel suo articolo; si tratta di una macchina che stampa una successione di simboli 0 e 1 alternati: 010101010101...

Vista l'illimitatezza della successione, questa macchina non termina mai l'esecuzione e presenta quel comportamento ciclico che è stato anticipato discutendo le caratteristiche generali del modello.

Prima di fornire un elenco dettagliato di tutte le caratteristiche di cui la macchina dispone è utile presentare, pur informalmente, il meccanismo di funzionamento che desideriamo implementare.

Inizialmente la macchina riceverà un nastro vuoto: questo significa che tutte le caselle del nastro conterranno il simbolo $\Delta$ che abbiamo designato come l'indicatore della cella vuota. La testina della macchina viene portata all'inizio del nastro.

Lo stato iniziale della macchina dovrà permetterle di sostituire il simbolo di cella vuota con uno 0. Fatto questo la macchina sposterà la testina verso destra, dove incontrerà una cella vuota. A questo punto la macchina cambierà stato, acquisendo la possibilità di sostituire il simbolo di cella vuota con un simbolo 1. L'elaborazione della macchina a questo punto procede spostando la testina ancora una volta verso destra e riportando lo stato della macchina a quello iniziale. Quest'ultima mossa crea la ripetizione indefinita del medesimo comportamento.

Ora che abbiamo descritto nelle grandi linee l'algoritmo che verrà implementato dalla macchina, passiamo ad una discussione più rigorosa degli elementi costitutivi del modello per il caso in esame.

Insieme degli stati - Dalla descrizione che abbiamo svolto si deduce che ci sono due stati:

$q_{0}$ : è lo stato in cui la macchina scrive un simbolo 0;
$q_{1}$ : è lo stato in cui la macchina scrive un simbolo 1.

Si forma quindi l'insieme $Q=\left\{q_{0},q_{1}\right\}$ , dove $q_{0}$ è lo stato iniziale.

Alfabeto del nastro - L'alfabeto del nastro contiene tutti i simboli che si possono trovare sul nastro; in questo caso saranno 0, 1 e $\Delta$ . Si forma quindi l'insieme $\Gamma =\left\{0,1,\Delta \right\}$ .

Alfabeto d'ingresso - La macchina non prevede che il nastro d'ingresso contenga simboli, di conseguenza $\Sigma =\emptyset$ .

Funzione di transizione - Abbiamo anticipato che la descrizione dell'algoritmo della macchina di Turing è stata data, nell'articolo iniziale, in termini di una tabella. Ogni riga della tabella può essere pensata come un'istruzione, caratterizzata da una quintupla ordinata di elementi: lo stato in cui si trova la macchina, il simbolo letto dal nastro, il simbolo scritto sul nastro, il movimento compiuto dalla testina e lo stato prossimo.

La funzione di transizione, riportata nella tabella sottostante, rappresenta in effetti un elenco di istruzioni e quindi un programma.

Numero istruzione	Stato attuale	Simbolo letto dal nastro	Simbolo scritto sul nastro	Movimento della testina	Stato prossimo
1	$q_{0}$	$\Delta$	0	R	$q_{1}$
2	$q_{1}$	$\Delta$	1	R	$q_{0}$

Diagramma degli stati - L'immagine sottostante mostra il diagramma degli stati per la macchina di Turing che abbiamo progettato. Anche in questo caso il diagramma introduce una novità riguardante il modo in vengono descritte le transizioni: l'etichettatura ha il formato $a,b,c$ dove $a$ è il simbolo letto dal nastro, $b$ è il simbolo scritto sul nastro e $c$ indica il movimento della testina.

Esempio 2 - Successivo di un numero naturale in base 2

Pur essendo adatto a mostrare un'applicazione basilare della macchina di Turing, il primo esempio è senza ombra di dubbio troppo semplice per poter apprezzare il potenziale del modello computazionale. Uno dei fattori che limitano l'interesse per macchine simili è senz'altro l'assenza di un vero e proprio ingresso: il formalismo infatti è stato pensato per mettere simboli sul nastro rilevando unicamente la condizione di cella vuota.

Analizziamo ora un esempio più articolato: calcolare il successivo di un numero naturale rappresentato in base 2. L'algoritmo per il calcolo che desideriamo svolgere è molto semplice: si guarda l'ultima cifra del numero; se è 0, la si trasforma in 1, mentre se è 1 si scorrono le cifre del numero a ritroso finché non si incontra il primo valore 0. Tutti i valori 1 incontrati sul percorso vengono sostituiti da 0, mentre il valore 0 incontrato per ultimo viene sostituito da un 1.

Come in precedenza, descriviamo informalmente il funzionamento desiderato per la macchina, prima di formalizzarne la struttura.

Inizialmente la macchina riceve un nastro sul quale è riportato il numero, codificato come una sequenza di simboli 0 ed 1, ognuno dei quali occupa una cella. Il numero dovrà necessariamente riportare il simbolo 0 come prima cifra.

La macchina inizia l'esecuzione scorrendo il nastro verso destra e si ferma una volta raggiunto il primo simbolo di cella vuota: a questo punto il numero è stato attraversato interamente e basta muoversi di una cella a sinistra per giungere all'ultima cifra.

Se l'ultima cifra del numero è uno 0, si sostituisce il simbolo con 1.

Se l'ultima cifra del numero è un 1, lo si sostituisce con uno zero e si muove la testina verso sinistra; ogni volta che la macchina legge un 1, scrive uno 0 e sposta la testina a sinistra. Quando viene raggiunto un simbolo 0, la macchina lo sostituisce con 1 e termina l'esecuzione.

Veniamo ora ad una descrizione più formale del dispositivo.

Insieme degli stati - La macchina è composta da cinque stati, con i seguenti significati:

$q_{0}$ : la macchina sfrutta questo stato per attraversare la stringa dei simboli già presenti sul nastro;
$q_{1}$ : in questo stato la macchina rileva il raggiungimento della prima cella successiva all'ultimo simbolo che codifica il numero;
$q_{2}$ : questo stato rappresenta il successivo del numero quando l'ultima cifra è 0;
$q_{3}$ : la macchina sfrutta questo stato per la sostituzione dei simboli;
$q_{4}$ : questo stato rappresenta il successivo del numero quando l'ultima cifra è 1.

Si crea quindi l'insieme $Q=\left\{q_{0},q_{1},q_{2},q_{3},q_{4}\right\}$ ; inoltre lo stato $q_{0}$ è lo stato iniziale.

Alfabeto del nastro - In questo caso sul nastro si possono trovare i simboli 0, 1 e $\Delta$ . Si forma quindi l'insieme $\Gamma =\left\{0,1,\Delta \right\}$ .

Alfabeto d'ingresso - Inizialmente, sul nastro è codificato un numero impiegando solamente i simboli 0 e 1. Di conseguenza l'alfabeto d'ingresso sarà $\Sigma =\left\{0,1\right\}$ . Come si può notare, il vincolo $\Sigma \subseteq \Gamma$ è rispettato.

Funzione di transizione - Riportiamo di seguito l'elenco delle istruzioni che definiscono il modello computazionale.

Numero istruzione	Stato attuale	Simbolo letto dal nastro	Simbolo scritto sul nastro	Movimento della testina	Stato prossimo
1	$q_{0}$	0	0	R	$q_{0}$
2	$q_{0}$	1	1	R	$q_{0}$
3	$q_{0}$	$\Delta$	$\Delta$	L	$q_{1}$
4	$q_{1}$	0	1	R	$q_{2}$
5	$q_{1}$	1	0	L	$q_{3}$
6	$q_{3}$	1	0	L	$q_{3}$
7	$q_{3}$	0	1	R	$q_{4}$

Diagramma degli stati Sulla base della descrizione soprastante, il diagramma degli stati associato a questa realizzazione della macchina di Turing è riportato di seguito.

Seguire la computazione di una macchina di Turing

Prendendo spunto dall'esempio appena presentato è utile provare a seguire la computazione della macchina di Turing, impiegando la tecnica introdotta dallo stesso autore ed accennata nella prima parte della lezione.

Presenteremo due diverse computazioni associate alla macchina di Turing appena progettata: la prima calcolerà il successivo del numero 2 mentre la seconda troverà il successivo di 3. La scelta di due numeri così piccoli ci offre la possibilità di completare le computazioni in un numero ragionevole di passi, evidenziando comunque gli aspetti più rilevanti dell'algoritmo impiegato.

Calcolo del successivo di 2

Prima di analizzare nel dettaglio la computazione è utile stabilire cosa ci aspettiamo di ottenere. Il numero naturale 2 rappresentato in forma binaria si scrive 10, mentre il suo successivo, ossia il numero 3, si scrive 11. Ci aspettiamo quindi di fornire alla macchina di Turing che abbiamo preparato la sequenza di simboli 10 e di ottenere come risultato la sequenza 11.

La macchina richiede che la sequenza di simboli in ingresso cominci sempre con uno zero: per questo motivo il nastro d'ingresso conterrà inizialmente i tre simboli 0, 1, 0, seguiti da una successione illimitata di simboli $\Delta$ .

Forniamo ora qualche dettaglio in più circa la computazione svolta dalla macchina su questa particolare sequenza d'ingresso. Inizialmente la macchina si trova nella configurazione $q_{0}010\Delta$ . Il simbolo letto dal nastro sarà 0: la mossa della macchina consiste nel riscrivere lo 0 sul nastro e spostare la testina a destra, rimanendo nello stato $q_{0}$ .

La nuova configurazione della macchina è quindi $0q_{0}10\Delta$ . La testina legge ora il simbolo 1 e la macchina reagisce riscrivendolo sul nastro, spostando la testina verso destra e rimanendo ancora nello stato $q_{0}$ .

La configurazione della macchina è adesso $01q_{0}0\Delta$ . Il simbolo letto dal nastro è 0 e visto che lo stato finora non è cambiato la macchina svolgerà le stesse operazioni viste all'inizio della computazione.

La configurazione della macchina diventa $010q_{0}\Delta$ . La macchina legge il simbolo di cella vuota, segno che la sequenza di simboli che codifica il numero è stata attraversata completamente; il simbolo viene quindi scritto sul nastro e, dopo aver spostato la testina verso sinistra, lo stato diventa $q_{1}$ . Il fatto che in questo momento della computazione avvenga un cambiamento nello stato della macchina indica che si è appena conclusa una delle fasi dell'algoritmo: in questo caso l'attraversamento della stringa in ingresso.

La transizione precedente lascia la macchina nella configurazione $01q_{1}0\Delta$ . Il simbolo letto dal nastro è 0 ed in questo caso la macchina lo sostituisce con 1, sposta la testina sulla destra e si porta nello stato $q_{2}$ , introdotto nella macchina per indicare che è stato trovato il successivo di un numero pari.

La macchina si trova ora nella configurazione $011q_{2}\Delta$ ; osservando il contenuto del nastro notiamo che l'obiettivo prefissato è stato raggiunto.

Calcolo del successivo di 3

Anche in questo caso, prima di seguire la computazione è preferibile stabilire quali siano le nostre aspettative. Sappiamo che il numero 3 codificato in binario si scrive 11; il suo successore, ossia il 4, si scrive invece 100. Vediamo come si comporta la macchina di Turing in questa situazione; velocizzeremo la computazione saltando alcuni dei passi che sono del tutto analoghi ai precedenti.

Il nastro d'ingresso conterrà, in questo caso, la sequenza di simboli 0, 1, 1 seguiti da una successione illimitata di simboli $\Delta$ .

La macchina inizierà l'esecuzione nella configurazione $q_{0}011\Delta$ ed eseguirà come prima cosa un attraversamento completo della sequenza di simboli in ingresso posizionandosi poi sull'ultimo, nello stato $q_{1}$ .

La nuova configurazione della macchina sarà $001q_{1}1\Delta$ . Il simbolo letto dal nastro è 1 e la macchina lo sostituisce con 0, muovendo la testina verso sinistra portandosi nello stato $q_{3}$ .

La macchina si trova ora nella configurazione $0q_{3}10\Delta$ . Il simbolo letto dal nastro è 1 e quindi viene sostituito da uno 0, la testina si sposta di una cella verso sinistra e rimane nello stato $q_{3}$ .

Ora la configurazione è $q_{3}000\Delta$ . Leggendo il simbolo 0 la macchina lo sostituisce con 1, sposta la testina di lettura verso destra e si porta nello stato $q_{4}$ ; quest'ultimo stabilisce che si è trovato il successivo di un numero dispari.

La macchina termina quindi la computazione nella configurazione $1q_{4}00\Delta$ ; la sequenza di simboli riportati sul nastro è esattamente quella desiderata.

Le macchine di Turing come accettori di linguaggi

La prima parte di questa lezione è stata dedicata ad un esame del modello computazionale proposto originariamente da Alan Turing; questa impostazione ci ha consentito di familiarizzare sia con le caratteristiche del formalismo, sia con il suo funzionamento.

Va detto che nell'ambito dell'informatica teorica il modello originale viene utilizzato molto raramente: al suo posto vengono preferite delle varianti che aggiungono caratteristiche pensate per assecondare il tipo di analisi per cui il formalismo viene impiegato.

Una delle varianti è proprio l'accettore, di cui parleremo estesamente in questa parte della lezione. Sfortunatamente non esiste una definizione univoca e condivisa di riconoscitore di Turing, pertanto quella proposta in questa sede va intesa solamente come una delle tante; le differenze tra le varie definizioni (vedi ad esempio il testo di Ullman oppure quello di Michael Sipser) vanno prese in seria considerazione poiché conducono a comportamenti sottilmente diversi durante la computazione.

Avendo già discusso il tema del riconoscimento delle stringhe nei due modelli computazionali che sono già stati presentati, sappiamo che questa categoria di formalismi è in grado di stabilire se una stringa appartenga ad un linguaggio oppure no.

Gli accettori a pila si differenziano da quelli a stati finiti perché sono in grado di riconoscere un insieme più vasto di stringhe; a dispetto di ciò la loro struttura ed il principio di funzionamento sono i medesimi: se al termine della computazione l'automa si trova in uno stato finale, allora la stringa in ingresso verrà accettata.

Stando alla definizione che proporremo i riconoscitori di Turing agiscono in modo diverso: anzitutto dispongono sempre di due stati finali, uno dedicato all'accettazione della stringa ed uno pensato per il rifiuto; inoltre quando la macchina raggiunge tali stati la computazione si arresta.

È ancora possibile pensare ai riconoscitori di Turing come a delle macchine e l'immagine sottostante ne illustra una versione stilizzata.

Osservando l'immagine si può notare che la struttura di base della macchina è la stessa vista prima; l'unica differenza risiede nella capacità dell'unità di controllo di comunicare con l'esterno l'accettazione od il rifiuto della sequenza di simboli ricevuti in ingresso.

Come di consueto è utile descrivere il ciclo di lavoro della macchina, poiché vi sono differenze rispetto al modello precedente che si rifletteranno anche nella definizione formale.

Il ciclo di lavoro normalmente associato ad un riconoscitore di Turing è composto dai seguenti quattro passi:

lettura di un simbolo dal nastro d'ingresso;
scrittura di un simbolo sul nastro d'ingresso (opzionale);
modifica dello stato della macchina (opzionale);
se la macchina si trova nello stato di accettazione oppure nello stato di rifiuto, la computazione termina.

Grazie a questa descrizione è ora possibile fornire una definizione più rigorosa.

Definizione di riconoscitore di Turing

Un riconoscitore di Turing è una n-upla ordinata composta da otto elementi $R=(Q,\Gamma ,\Sigma ,\delta ,q_{0},\Delta ,q_{F})$ descritti di seguito:

$Q$ è un insieme finito di stati;
$\Gamma$ è un l'alfabeto del nastro;
$\Sigma \subseteq \Gamma$ è l'alfabeto d'ingresso;
$\delta :(Q\setminus \left\{q_{F},q_{R}\right\})\times \Gamma \rightarrow Q\times \Gamma \times \left\{L,R\right\}$ è un insieme finito di stati;
$q_{0}\in Q\setminus \left\{q_{F},q_{R}\right\}$ è lo stato iniziale;
$\Delta \in \Gamma$ è il simbolo di cella vuota;
$q_{F}\in Q$ è lo stato finale o stato di accettazione;
$q_{R}\in Q,q_{R}\neq q_{F}$ è lo stato di rifiuto.

La definizione comprende due aspetti che meritano particolare attenzione:

nella definizione della funzione di transizione si specifica che nessuna transizione può partire dallo stato finale, né dallo stato iniziale: questa condizione è necessaria in quanto abbiamo imposto che il raggiungimento di questi stati provochi l'immediata interruzione della computazione;
per lo stesso motivo, lo stato iniziale del riconoscitore non può essere né lo stato di accettazione, né di rifiuto.

Ora che abbiamo stabilito una definizione formale di riconoscitore di Turing, è giunto il momento di vedere all'opera il modello computazionale analizzando alcuni esempi di accettazione.

Nel seguito della lezione presenteremo tre riconoscitori di Turing in grado di accettare altrettanti linguaggi: nei primi due casi sarebbe stato possibile costruire automi accettori, a stati finiti oppure a pila, per riconoscere i medesimi linguaggi, mentre nell'ultimo caso solamente il formalismo di Turing è in grado di identificare correttamente le stringhe che appartengono al linguaggio.

Il fatto che le macchine di Turing riescano a riconoscere un linguaggio per il quale è impossibile costruire un accettore a stati o a pila equivalente suggerisce che le capacità di riconoscimento del modello computazionale di Turing siano più elevate di quelle dei formalismi visti finora.

Esempio 3 - Accettazione delle stringhe che iniziano con la sequenza $ab$

Consideriamo l'alfabeto $A=\left\{a,b\right\}$ ed il linguaggio formale $L=\left\{w|w{\text{ inizia con i simboli }}ab\right\}$ .

Vogliamo costruire un riconoscitore di Turing per il linguaggio $L$ .

Prima di elencare gli elementi che costituiscono la definizione formale del modello, discutiamo qualitativamente quale dovrebbe essere il comportamento del riconoscitore.

A partire dallo stato iniziale, il modello inizia a leggere simboli dal nastro; già alla prima lettura possono essere prese due decisioni drasticamente differenti: la presenza di un simbolo $a$ è compatibile con il prefisso che desideriamo riconoscere, mentre un simbolo $b$ porta la macchina subito nello stato di rifiuto.

Giunti al secondo simbolo si ragiona in modo analogo: in presenza di un simbolo $a$ si passa allo stato di rifiuto, mentre con un simbolo $b$ ci si porta in uno stato di accettazione.

Dato che il raggiungimento di uno degli stati di accettazione o di rigetto comporta l'immediata interruzione della computazione, possiamo concludere che il riconoscitore di Turing sia interessato solamente ai primi due simboli, un comportamento perfettamente comprensibile.

Veniamo ora all'elencazione delle caratteristiche formali dell'automa.

Insieme degli stati - il riconoscitore in questione è caratterizzato dai seguenti tre stati:

$q_{0}$ : l'accettore si trova in questo stato quando non ha ancora elaborato alcun simbolo;
$q_{1}$ : in questo stato il riconoscitore ha identificato il simbolo $a$ come primo elemento della stringa;
$q_{2}$ : questo stato attesta il corretto riconoscimento del prefisso $ab$ ;
$q_{3}$ : questo stato attesta il rifiuto della stringa;

Concludiamo che $Q=\left\{q_{0},q_{1},q_{2}\right\}$ .

Alfabeti - In questo caso sul nastro potranno comparire tre simboli: $a,b,\Delta$ ; le stringhe fornite al riconoscitore come ingressi saranno tuttavia composte solamente dai simboli $a,b$ . Da queste osservazioni segue che $\Gamma =\left\{a,b,\Delta \right\}$ e $\Sigma =\left\{a,b\right\}$ .

Funzione di transizione - Nel caso del riconoscitore che stiamo costruendo la funzione di transizione è molto elementare:

Numero istruzione	Stato attuale	Simbolo letto dal nastro	Simbolo scritto sul nastro	Movimento della testina	Stato prossimo
1	$q_{0}$	$a$	$a$	$R$	$q_{1}$
2	$q_{1}$	$b$	$b$	$R$	$q_{2}$

Vista l'estrema semplicità dell'esempio, vale la pena di mostrare un'altra tecnica di rappresentazione della funzione di transizione, molto simile a quella presentata nella lezione sugli automi a stati finiti, come si può desumere osservando l'immagine sottostante.

	$a$	$b$
$q_{0}$	$(q_{1},a,R)$	$(q_{3},b,R)$
$q_{1}$	$(q_{3},a,R)$	$(q_{2},b,R)$
$q_{2}$	-	-
$q_{3}$	-	-

Diagramma degli stati - Illustriamo infine il diagramma degli stati per il riconoscitore di Turing delineato dalla nostra descrizione.

Esempio 4 - Accettazione del linguaggio $a^{n}b^{n}$

A partire dal medesimo alfabeto presentato nell'esempio precedente, consideriamo il linguaggio formale $L=\left\{a^{n}b^{n},n>0\right\}$ , per il quale è già stato costruito un accettore a pila nella lezione precedente.

Dopo aver identificato le caratteristiche costitutive del riconoscitore di Turing che raggiunge il medesimo obiettivo, sarà utile operare un confronto tra la strategia di riconoscimento adottata dall'automa a pila e quella seguita dalla macchina di Turing.

La logica dell'algoritmo impiegato dal riconoscitore è basata sulla struttura delle stringhe: infatti, ogni stringa appartenente al linguaggio può essere pensata come una sequenza di simboli $ab$ nidificati; come conseguenza, alla prima $a$ corrisponde l'ultima $b$ , alla seconda $a$ corrisponde la penultima $b$ e così via.

Questa osservazione permette di pensare ad un algoritmo che procede per cancellazione dei simboli corrispondenti: si cancella la prima $a$ , poi l'ultima $b$ , poi la seconda $a$ , poi la penultima $b$ e così via. Scegliamo la convenzione di cancellare i simboli $a$ sostituendoli con delle $X$ ed ogni simbolo $b$ sostituendolo con delle $Y$ .

L'algoritmo scorre la successione dei simboli a zig-zag, eliminando ogni volta l'ultimo simbolo incontrato prima di una $X$ o di una $Y$ . L'esecuzione termina quando il riconoscitore incontra la sequenza $XY$ .

Naturalmente vanno previste anche alcune condizioni relative al rifiuto delle stringhe; più precisamente, vogliamo che l'automa rifiuti le seguenti categorie di stringhe:

tutte quelle che cominciano con il simbolo $b$ ;
tutte quelle che finiscono con il simbolo $a$ ;
tutte quelle che presentano un simbolo $a$ che segue un simbolo $b$ ;
tutte quelle che non hanno un ugual numero di simboli $a$ e $b$ .

Ora che ci siamo formati un'idea sul principio di funzionamento dell'algoritmo, vediamo quali caratteristiche dovrebbe avere la macchina di Turing che lo implementa.

Insieme degli stati - Il problema del riconoscimento viene risolto in questo caso ricorrendo ad una macchina a otto stati:

$q_{0}$ : stato iniziale;
$q_{1}$ : in questo stato il riconoscitore attraversa tutti i simboli $a$ , da sinistra verso destra;
$q_{2}$ : questo stato permette l'attraversamento di tutti i simboli $b$ , da sinistra verso destra;
$q_{3}$ : in questo stato termina l'attraversamento da sinistra verso destra, incontrando una $Y$ oppure il simbolo di cella vuota;
$q_{4}$ : questo stato indica che un simbolo $b$ è stato sostituito da una $Y$ e che sta avvenendo l'attraversamento della stringa da destra verso sinistra;
$q_{5}$ : in questo stato avviene l'attraversamento dei simboli $a$ da sinistra verso destra;
$q_{6}$ : in questo stato si incontra il primo simbolo $X$ e si inverte il verso di percorrenza della stringa;
$q_{A}$ : stato di accettazione;
$q_{R}$ : stato di rifiuto;

L'insieme degli stati sarà quindi $Q=\left\{q_{0},q_{1},q_{2},q_{3},q_{4},q_{5},q_{6},q_{A},q_{R}\right\}$ ; lo stato $q_{5}$ è lo stato finale.

Alfabeti - In questo caso sul nastro potranno comparire cinque simboli: $a,b,X,Y,\Delta$ ; le stringhe fornite al riconoscitore come ingressi saranno tuttavia composte solamente dai simboli $a,b$ . Da queste osservazioni segue che $\Gamma =\left\{a,b,X,Y,\Delta \right\}$ e $\Sigma =\left\{a,b\right\}$ .

Funzione di transizione - Nel caso del riconoscitore che stiamo costruendo la funzione di transizione è riportata di seguito.

Numero istruzione	Stato attuale	Simbolo letto dal nastro	Simbolo scritto sul nastro	Movimento della testina	Stato prossimo
1	$q_{0}$	$a$	$X$	$R$	$q_{1}$
2	$q_{0}$	$b$	$b$	$R$	$q_{R}$
3	$q_{1}$	$a$	$a$	$R$	$q_{1}$
4	$q_{1}$	$b$	$b$	$R$	$q_{2}$
5	$q_{1}$	$Y$	$Y$	$L$	$q_{R}$
6	$q_{2}$	$a$	$a$	$L$	$q_{R}$
7	$q_{2}$	$b$	$b$	$R$	$q_{2}$
8	$q_{2}$	$\Delta$	$\Delta$	$L$	$q_{3}$
9	$q_{2}$	$Y$	$Y$	$L$	$q_{3}$
10	$q_{3}$	$b$	$Y$	$L$	$q_{4}$
11	$q_{4}$	$b$	$b$	$L$	$q_{4}$
12	$q_{4}$	$a$	$a$	$L$	$q_{4}$
13	$q_{4}$	$X$	$X$	$R$	$q_{5}$
14	$q_{5}$	$a$	$X$	$R$	$q_{1}$
15	$q_{5}$	$b$	$b$	$L$	$q_{R}$
16	$q_{5}$	$Y$	$Y$	$L$	$q_{F}$

Diagramma degli stati - L'immagine sottostante mostra il diagramma degli stati per il riconoscitore di Turing che abbiamo costruito.

Prima di passare ad un confronto fra l'algoritmo appena implementato e quello utilizzato nell'automa a pila, è utile seguire la computazione dell'automa in un paio di situazioni; più precisamente illustreremo i casi in cui la stringa d'ingresso sia $ab$ e $aabb$ .

Analisi di due computazioni del riconoscitore

Consideriamo anzitutto il caso in cui la stringa d'ingresso sia $ab$ . La computazione eseguita dal riconoscitore di Turing è rappresentata dalla seguente successione di configurazioni.

$q_{0}ab\Delta \vdash Xq_{1}b\Delta \vdash Xbq_{2}\Delta \vdash Xq_{3}b\Delta \vdash q_{4}XY\Delta \vdash Xq_{5}Y\Delta \vdash q_{F}XY\Delta$ .

Si vede quindi come l'automa riconosca la stringa in ingresso.

Vediamo cosa succede quando l'ingresso è costituito dalla stringa $aabb$ .

$q_{0}aabb\Delta \vdash Xq_{1}abb\Delta \vdash Xaq_{1}bb\Delta \vdash Xq_{3}aYb\Delta \vdash q_{4}XaYb\Delta \vdash$

$\vdash Xq_{5}aYb\Delta \vdash XXq_{1}Yb\Delta \vdash XXYq_{2}b\Delta \vdash XXq_{3}YY\Delta \vdash Xq_{4}XYY\Delta \vdash$

$\vdash XXq_{5}YY\Delta \vdash Xq_{A}XYY\Delta$

Anche in questa computazione il riconoscitore giunge allo stato finale; la stringa di simboli è dunque accettata.

Confronto fra l'accettore a pila ed il riconoscitore di Turing

Il riconoscitore di Turing porta a termine l'accettazione delle stringhe senza memorizzare informazioni parziali relative ai simboli incontrati; non è così per l'automa a pila, che ha bisogno di conservare il numero di simboli $a$ in modo da poter successivamente verificare che i simboli $b$ siano presenti esattamente nella stessa quantità.

La memorizzazione diventa indispensabile poiché l'accettore a pila non ha la possibilità di spostare la testina di lettura verso sinistra, movimento indispensabile per poter rileggere un simbolo; il riconoscitore di Turing, quindi, rende superfluo l'impiego di una memoria aggiuntiva grazie alla mobilità della propria testina.

La maggiore libertà concessa alla testina è quindi un elemento chiave per il successo del riconoscitore di Turing, che paga però pegno in quanto la computazione dura di più: possiamo concludere che, almeno in questo caso, la rimozione della memoria ausiliaria ha richiesto un aumento della durata della computazione.

Esempio 5 - Linguaggio $a^{n}b^{n}$ : un algoritmo alternativo

Il riconoscitore di Turing che abbiamo presentato nell'esempio precedente svolgeva il riconoscimento impiegando una tecnica a zig-zag per l'attraversamento della stringa.

Questa strategia non è l'unica possibile; in questo paragrafo presenteremo un riconoscitore di Turing pensato per accettare il medesimo linguaggio, ma basato su un algoritmo differente.

L'utilità di presentare questo risultato è duplice: da un lato comporta in modo implicito che a partire da un linguaggio Turing-riconoscibile si può costruire più di un riconoscitore; dall'altro ci offre la possibilità di confrontare i due algoritmi, avviando una discussione sulle prestazioni che costituirà il cardine della terza parte del corso.

Presentiamo ora l'algoritmo nelle sue grandi linee: inizialmente il riconoscitore scorre la stringa in ingresso da sinistra verso destra, sostituendo il primo simbolo $a$ con una $X$ ed il primo simbolo $b$ con una $Y$ ; a questo punto la stringa viene percorsa a ritroso, fino a trovare il primo simbolo $a$ non convertito. Il ciclo riprende dall'inizio finché viene incontrata la sequenza di simboli $XY$ , che rappresenta una possibile condizione di terminazione: per confermarla, la stringa viene percorsa fino in fondo, in modo da assicurarsi che non ci siano simboli $b$ ; se anche questa condizione si verifica, la computazione termina. Come in precedenza, il riconoscitore si occupa anche di scartare alcune stringhe, nel momento in cui c'è la garanzia che non appartengano al linguaggio.

A questo punto presentiamo le caratteristiche dell'automa, concentrandoci su quelle che cambiano rispetto alla situazione precedente: gli stati, le transizioni e di conseguenza il diagramma degli stati.

Insieme degli stati - Il riconoscitore di Turing che implementa questo nuovo algoritmo è caratterizzato da otto stati:

$q_{0}$ : stato iniziale;
$q_{1}$ : stato dedicato all'attraversamento da sinistra verso destra per i soli simboli $a$ ;
$q_{2}$ : in questo stato l'automa si occupa dell'attraversamento dei simboli $Y$ , fino al raggiungimento della prima $b$ ;
$q_{3}$ : in questo stato viene invertito il verso di percorrenza della stringa, attraversando le $Y$ e le $a$ fino ad incontrare una $X$ ;
$q_{4}$ : questo stato serve per riavviare il ciclo di sostituzione o per avviare il ciclo conclusivo;
$q_{5}$ : questo stato esegue il ciclo conclusivo;
$q_{A}$ : stato di accettazione;
$q_{R}$ : stato di rifiuto.

Funzione di transizione - La tabella sottostante mostra l'insieme delle istruzioni del riconoscitore

Numero istruzione	Stato attuale	Simbolo letto dal nastro	Simbolo scritto sul nastro	Movimento della testina	Stato prossimo
1	$q_{0}$	$a$	$X$	$R$	$q_{1}$
2	$q_{0}$	$b$	$b$	$R$	$q_{R}$
3	$q_{1}$	$a$	$a$	$R$	$q_{1}$
4	$q_{1}$	$Y$	$Y$	$R$	$q_{2}$
5	$q_{1}$	$b$	$Y$	$L$	$q_{3}$
6	$q_{2}$	$a$	$a$	$L$	$q_{R}$
7	$q_{2}$	$b$	$Y$	$L$	$q_{3}$
8	$q_{2}$	$\Delta$	$\Delta$	$L$	$q_{R}$
9	$q_{2}$	$Y$	$Y$	$R$	$q_{2}$
10	$q_{3}$	$a$	$a$	$L$	$q_{3}$
11	$q_{3}$	$Y$	$Y$	$L$	$q_{3}$
12	$q_{3}$	$X$	$X$	$R$	$q_{4}$
13	$q_{4}$	$a$	$X$	$R$	$q_{1}$
14	$q_{4}$	$Y$	$Y$	$R$	$q_{5}$
15	$q_{5}$	$a$	$a$	$L$	$q_{R}$
16	$q_{5}$	$b$	$b$	$L$	$q_{R}$
17	$q_{5}$	$Y$	$Y$	$R$	$q_{5}$
18	$q_{5}$	$\Delta$	$\Delta$	$L$	$q_{A}$

Diagramma degli stati - Il diagramma degli stati per il riconoscitore di Turing che implementa questo nuovo algoritmo è proposto di seguito.

Analisi di due computazioni con il nuovo algoritmo

Per poter confrontare i risultati di questo riconoscitore con quelli del precedente, svolgeremo le medesime computazioni. Vediamo anzitutto come si comporta questa macchina di Turing con la stringa $ab$ .

$q_{0}ab\Delta \vdash Xq_{1}b\Delta \vdash q_{3}XY/Delta\vdash Xq_{4}Y\Delta \vdash XYq_{5}\Delta \vdash Xq_{A}Y\Delta$

Analizziamo ora la computazione riguardante la stringa d'ingresso $aabb$

$q_{0}aabb\Delta \vdash Xq_{1}abb\Delta \vdash Xaq_{1}bb\Delta \vdash Xq_{3}aYb\Delta \vdash q_{3}XaYb\Delta \vdash$

$\vdash Xq_{4}aYb\Delta \vdash XXq_{1}Yb\Delta \vdash XXYq_{2}b\Delta \vdash XXq_{3}YY\Delta \vdash Xq_{3}XYY\Delta \vdash$

$\vdash XXq_{4}YY\Delta \vdash XXYq_{5}Y\Delta \vdash XXYYq_{5}\Delta \vdash XXYq_{a}Y\Delta$

Confronto delle computazioni degli esempi 4 e 5

Un aspetto che salta immediatamente all'occhio confrontando le computazioni è la differente lunghezza: per il riconoscimento della stringa $ab$ il nuovo algoritmo passa attraverso sei configurazioni mentre quello precedente ne richiedeva sette. Per il riconoscimento della stringa $aabb$ il nuovo algoritmo passa attraverso quattordici configurazioni, mentre al precedente ne bastavano dodici.

Osservando bene le configurazioni riguardanti la seconda stringa, ci si rende conto che il nuovo algoritmo attraversa ben sei configurazioni senza sostituire simboli, transizioni obbligatorie per accertarsi che tutte le $b$ siano effettivamente state sostituite. Questo problema non si pone nel primo algoritmo, dato che la sostituzione parte dagli estremi della stringa.

Nonostante le due macchine di Turing riconoscano il medesimo linguaggio, le loro prestazioni sono differenti e sarebbe giustificato, a questo punto, disporre di criteri che permettano per lo meno di intuire quali siano le implementazioni più appetibili dal punto di vista delle prestazioni. Riprenderemo questi aspetti, fornendo utili strumenti d'analisi, nella terza parte del corso.

Esempio 6 - Accettazione del linguaggio $a^{n}b^{n}c^{n}$

Al termine della lezione sugli gli automi a pila è stato osservato che, durante la computazione, in questi modelli si riscontrano due momenti caratteristici: la memorizzazione di informazioni ed il loro recupero, con relativa rimozione dalla pila. Una volta eliminati dalla memoria, i dati non sono più utilizzabili e questo comportamento influenza sia il tipo di computazione per cui gli automi a pila sono consigliati, sia e soprattutto la struttura delle stringhe che essi sono in grado di riconoscere.

Il linguaggio che stiamo per descrivere è stato concepito per evidenziare questa limitazione, chiedendo di ripetere il conteggio dei simboli dopo la loro eliminazione dalla pila; di conseguenza, nessun automa a pila potrà mai essere in grado di riconoscere correttamente le stringhe di questo linguaggio.

Come vedremo è invece possibile progettare un riconoscitore di Turing che riesca ad accettare il linguaggio proposto; ciò dimostra che tale classe di modelli computazionali riconosce almeno un linguaggio in più rispetto agli automi a pila.

Formalizziamo ora il problema che desideriamo affrontare, a partire da un alfabeto $A=\left\{a,b,c\right\}$ ; il linguaggio formale da riconoscere sarà $L=\left\{a^{n}b^{n}c^{n},n\in \mathbb {N} \setminus \left\{0\right\}\right\}$ .

Il riconoscitore di Turing accetterà le stringhe del linguaggio ricorrendo al seguente algoritmo: inizialmente, la macchina scorrerà l'intera stringa da sinistra verso destra; durante questa fase sostituirà il primo simbolo $a$ con un simbolo $X$ , il primo simbolo $b$ con un simbolo $Y$ ed il primo simbolo $c$ con un simbolo $Z$ . A questo punto percorrerà la successione dei simboli da destra verso sinistra, fermandosi al raggiungimento della prima occorrenza del simbolo $X$ ; fatto questo, il riconoscitore riprenderà dall'inizio, rimuovendo ad ogni passata tre simboli. Nel momento in cui il modello incontra il simbolo di cella vuota vuol dire che è stata effettuata la sostituzione dell'ultimo simbolo $c$ e quindi che la computazione può terminare.

Dopo questa descrizione per grandi linee dell'algoritmo da implementare sulla macchina di Turing, passiamo ad una più precisa e dettagliata descrizione formale.

Insieme degli stati - Il riconoscitore è dotato di 6 stati:

$q_{0}$ : stato iniziale;
$q_{1}$ : è lo stato in cui, dopo la sostituzione di un simbolo $a$ , si attraversa la stringa verso destra;
$q_{2}$ : l'attraversamento verso destra continua, dopo la sostituzione di un simbolo $b$ ;
$q_{3}$ : continua l'attraversamento verso destra, dopo la sostituzione di un simbolo $c$ ;
$q_{4}$ : stato di accettazione;
$q_{5}$ : in questo stato la stringa d'ingresso viene attraversata verso sinistra fino all'incontro del primo simbolo $a$ .

L'insieme degli stati sarà quindi $Q=\left\{q_{0},q_{1},q_{2},q_{3},q_{4},q_{5}\right\}$ .

Alfabeti - In questo esempio il nastro contiene un insieme più ricco di simboli: necessariamente dovranno essere presenti i simboli $a,b,c$ , ripresi dall'alfabeto del linguaggio; vi sono inoltre i simboli $X,Y,Z$ che servono come sostituti di $a,b,c$ . C'è infine il consueto simbolo di cella vuota. Da questa descrizione si deduce che $\Gamma =\left\{a,b,c,X,Y,Z,\Delta \right\}$ . L'alfabeto d'ingresso coincide con l'alfabeto del linguaggio da riconoscere.

Funzione di transizione - La funzione di transizione per il riconoscitore di Turing che vogliamo sviluppare è proposta nella tabella seguente, che elenca le transizioni presenti.

Numero istruzione	Stato attuale	Simbolo letto dal nastro	Simbolo scritto sul nastro	Movimento della testina	Stato prossimo
1	$q_{0}$	$a$	$X$	$R$	$q_{1}$
2	$q_{1}$	$a$	$a$	$R$	$q_{1}$
3	$q_{1}$	$Y$	$Y$	$R$	$q_{1}$
4	$q_{1}$	$b$	$Y$	$R$	$q_{2}$
5	$q_{2}$	$b$	$b$	$R$	$q_{2}$
6	$q_{2}$	$Z$	$Z$	$R$	$q_{2}$
7	$q_{2}$	$c$	$Z$	$R$	$q_{3}$
8	$q_{3}$	$\Delta$	$\Delta$	$L$	$q_{4}$
9	$q_{3}$	$c$	$c$	$L$	$q_{5}$
10	$q_{5}$	$b$	$b$	$L$	$q_{5}$
11	$q_{5}$	$Y$	$Y$	$L$	$q_{5}$
12	$q_{5}$	$Z$	$Z$	$L$	$q_{5}$
13	$q_{5}$	$a$	$X$	$R$	$q_{1}$

Diagramma degli stati - L'immagine seguente mostra il diagramma degli stati che si ottiene in base alle informazioni che abbiamo appena fornito.

Analisi di due computazioni del riconoscitore

Per mettere alla prova il funzionamento dell'automa analizzeremo due computazioni impiegando il riconoscitore appena realizzato; più precisamente ci occuperemo dell'accettazione delle stringhe $ab$ e $aabbcc$ .

La prima delle due computazione è rappresentata dalla seguente successione:

$q_{0}abc\Delta \vdash Xq_{1}bc\Delta \vdash XYq_{2}c\Delta \vdash XYq_{2}c\Delta \vdash XYZq_{3}\Delta \vdash XYq_{4}Z\Delta$

Il riconoscitore termina la computazione nello stato di accettazione.

La seconda computazione è più lunga in quanto richiede più di un attraversamento per essere completata:

$q_{0}aabbcc\Delta \vdash Xq_{1}abbcc\Delta \vdash Xaq_{1}bbcc\Delta \vdash XaYq_{2}bcc\Delta \vdash XaYbq_{2}cc\Delta \vdash$

$\vdash XaYbZq_{3}c\Delta \vdash XaYbq_{5}Zc\Delta \vdash XaYq_{5}bZc\Delta \vdash Xaq_{5}YbZc\Delta \vdash Xq_{5}aYbZc\Delta \vdash$

$\vdash XXq_{1}YbZc\Delta \vdash XXYq_{1}bZc\Delta \vdash XXYYq_{2}Zc\Delta \vdash XXYYZq_{2}c\Delta \vdash XXYYZZq_{3}\Delta \vdash XXYYZq_{4}Z\Delta$

Anche in questo caso il riconoscitore termina la computazione nello stato di accettazione.

Le macchine di Turing come decisori di linguaggi

Analizzando il funzionamento di un generico riconoscitore di Turing è facile rendersi conto che la computazione può svilupparsi in tre modi:

terminare segnalando l'accettazione della stringa;
terminare segnalando il rifiuto della stringa;
non terminare mai.

L'ultima condizione è nota come loop e si manifesta in due casi: quando la macchina non termina la propria computazione oppure quando termina la computazione in uno stato che non è nè di accettazione nè di rifiuto.

Al fine di avere garanzie circa l'effettiva capacità della macchina di Turing di riconoscere tutte le stringhe appartenenti al linguaggio e di rifiutare tutte quelle che non vi appartengono, la presenza di una condizione che porti la macchina a non fermarsi mai è un problema. Per questo motivo, fra tutti i possibili riconoscitori di Turing volgeremo la nostra attenzione ad una categoria particolare: quella in cui la macchina termina sempre la computazione. In questa categoria, quindi, si trovano tutti i riconoscitori che terminano la computazione indicando l'accettazione od il rifiuto della stringa.

Ci riferiremo a questa classe di riconoscitori attribuendogli il nome di decisori: macchine di Turing che sono sempre in grado di ultimare le computazioni indicando accettazione oppure rifiuto.

Un riconoscitore di Turing ha sempre a che fare con due linguaggi: il linguaggio $L$ che contiene le stringhe da accettare ed il linguaggio $L^{C}$ contenente le stringhe da rifiutare. Il riconoscitore è senz'altro in grado di stabilire se una stringa appartenga ad un linguaggio dato; è ragionevole supporre, dunque, che tutte le computazioni riguardanti stringhe appartenenti al linguaggio terminino nello stato di accettazione. Come conseguenza un riconoscitore di Turing entrerà nello stato di loop solamente analizzando stringhe che non appartengano al linguaggio. Possiamo concludere che il problema dello stato di loop non riguarda il linguaggio riconosciuto, bensì il suo linguaggio complementare.

Da questo punto di vista i decisori sono macchine di Turing in grado di accettare il linguaggio $L$ e rifiutare il linguaggio $L^{C}$ senza entrare mai in una condizione di loop.

Ci si può a questo punto chiedere come sia possibile, dato un riconoscitore di Turing, capire se è anche un decisore. Per poter rispondere a questa domanda dovremmo disporre di un metodo che, data una descrizione della macchina di Turing, sia in grado di determinare quanto segue:

la macchina data termina sempre le computazioni che riguardano il riconoscimento di stringhe del linguaggio $L$ ;
la macchina data termina sempre le computazioni che riguardano il rifiuto di stringhe del linguaggio $L^{C}$ .

Come avremo modo di vedere nella seconda parte del corso, tale metodo non può esistere ed è quindi praticamente impossibile stabilire se un riconoscitore di Turing sia anche un decisore.

Una cosa comunque è certa: la classe dei linguaggi accettati dai riconoscitori di Turing è più ampia di quella dei linguaggi accettati dai decisori ed è proprio per questo motivo che le due classi hanno nomi diversi. Più precisamente i linguaggi accettati da un riconoscitore si dicono Turing-riconoscibili o anche linguaggi ricorsivamente enumerabili, mentre i linguaggi accettati da un decisore si dicono Turing-decidibili o anche linguaggi ricorsivi.

Varianti della macchina di Turing

In quest'ultima parte della lezione presenteremo alcune varianti della macchina di Turing, ossia modelli computazionali derivati da quello originale con l'obiettivo di semplificarne l'uso oppure di ridurre la durata delle computazioni.

I nuovi modelli sono equivalenti all'originale, nel senso che sono in grado di trattare gli stessi linguaggi; questo aspetto è particolarmente delicato ed imporrà di dimostrare, per ogni nuovo formalismo, l'effettiva equivalenza con la macchina di Turing.

Nelle dimostrazioni di equivalenza impiegheremo in genere due strategie: la prima potrebbe essere definita riduzione, nel senso che la macchina di Turing originale verrà ottenuta a partire dalla sua variante, apportando opportune semplificazioni; la seconda si potrebbe definire simulazione e consiste nel simulare la variante impiegando la macchina di Turing originale.

Macchina di Turing multinastro

La prima variante che verrà presentata è la macchina di Turing multinastro: un modello computazionale strutturato in modo analogo all'originale, ma dotato di un numero arbitrario di nastri. L'immagine sottostante è una rappresentazione schematica del modello computazionale, nella sua versione a tre nastri.

Prima di offrire una descrizione dettagliata vale la pena di interrogarsi sul significato di questo modello computazionale: per quale motivo, ad un certo punto, qualcuno ha sentito la necessità di modificare l'idea originale di Alan Turing?

Chiunque abbia provato ad implementare un algoritmo mediante una macchina di Turing si sarà trovato in difficoltà con la gestione del nastro: un compito particolarmente gravoso, poiché anche operazioni logicamente semplici possono richiedere un gran numero di movimenti della testina. A loro volta gli spostamenti comportano la creazione di nuovi stati e nuove transizioni, rendendo tedioso il lavoro di sviluppo e complicando la verifica della correttezza.

Molti dei movimenti compiuti dalla testina si rendono necessari perché il modello computazionale originale consente di memorizzare informazioni; a modo suo Turing aveva già notato questa caratteristica e vi aveva posto rimedio immaginando che sul nastro si alternassero due tipi di celle: quelle che l'autore chiamava F-squares, destinate a contenere i simboli dell'alfabeto e quelle chiamate E-squares, pensate come supporto di memoria.

La variante della macchina di Turing multinastro offre la possibilità di impiegare un numero arbitrario di memorie, una per ogni nastro aggiuntivo, gestite in modo indipendente rispetto al nastro principale, contribuendo alla riduzione dei movimenti della sua testina.

Il vantaggio che deriva dall'adozione di questo modello è duplice: da un lato, come vedremo, le computazioni hanno una durata inferiore; dall'altro, contribuisce a limitare il numero di stati e di transizioni necessari per l'implementazione di un algoritmo.

A queste condizioni viene da pensare che la potenza del formalismo appena introdotto possa davvero superare quella della macchina di Turing: in realtà il guadagno prestazionale, come pure il minor numero di stati, sono legati all'introduzione del parallelismo mediante il contemporaneo movimento di più testine.

Sebbene l'obiettivo della lezione non contempli la rigorosa dimostrazione dell'equivalenza dei formalismi, non possiamo certo liquidare l'argomento basandoci sulle considerazioni intuitive appena presentate e discuteremo quindi, per lo meno nelle grandi linee, una dimostrazione più formale di questo importante risultato. Prima di ciò analizzeremo invece la struttura concettuale del modello, come pure il suo ciclo di lavoro.

Struttura e ciclo di lavoro

Osservando il modello fisico proposto nell'immagine soprastante si nota che la macchina ha la dotazione seguente:

un'unità di controllo;
un insieme di $k$ nastri illimitati verso destra;
un insieme di $k$ testine, una per ogni nastro, in grado di muoversi indipendentemente.

Ogni testina può leggere e scrivere sul suo nastro, esattamente come accade nel modello di Turing; contrariamente ad esso, tuttavia, le testine possono ricevere tre tipi di comando: ai consueti $R$ ed $L$ si aggiunge il comando $S$ che mantiene la testina in posizione. Questo accorgimento è indispensabile per garantire la possibilità di agire, se necessario, anche su un nastro solo, lasciando inalterati gli altri.

L'introduzione di una caratteristica come questa va giustificata: infatti, come abbiamo visto all'inizio della lezione, le prestazioni della testina sono uno dei fattori che determinano il potenziale della macchina di Turing; si potrebbe quindi pensare che un ulteriore affinamento della testina possa influenzare le caratteristiche del modello.

In realtà non è così e lo dimostriamo utilizzando la strategia della simulazione, che consiste in questo caso nell'utilizzo di una macchina di Turing a un nastro solo per simulare il blocco della testina. La simulazione può avvenire, ad esempio, associando al nuovo comando $S$ due movimenti della testina tradizionale: uno a destra e l'altro a sinistra, o viceversa; ciò richiede l'introduzione di un nuovo stato, ma non rappresenta un problema.

Una volta stabilite le caratteristiche "strutturali" del modello, passiamo alla descrizione del ciclo di lavoro. A tal proposito è necessario stabilire quali sono le condizioni iniziali: lo stato dell'unità di controllo è lo stato iniziale, il primo nastro contiene la stringa dei simboli da elaborare, la testina del primo nastro si trova in corrispondenza della prima cella, gli altri nastri sono completamente vuoti e le loro testine occupano una posizione arbitraria.

A partire da queste condizioni, la macchina ripete ciclicamente i seguenti passi

legge da tutti i nastri il simbolo che si trova sotto la testina;
basandosi sullo stato attuale e sull'insieme dei simboli letti, decide quale sarà lo stato prossimo. Lo stato prossimo può essere identico allo stato attuale;
sostituisce tutti i simboli dei nastri con altri simboli. Ognuno dei nuovi simboli può essere uguale al precedente;
muove ogni testina in una nuova posizione.

Ora che abbiamo descritto il ciclo di lavoro è giunto il momento di porre la definizione formale del modello: ci interesseremo in particolare ai riconoscitori multinastro.

Definizione di riconoscitore di Turing multinastro

Una macchina di Turing multinastro con $k$ nastri è una ottupla ordinata di elementi $M=(Q,\Gamma ,\Sigma ,\delta ,q_{A},q_{R},q_{0},\Delta )$ definiti come segue:

$Q$ : insieme finito di stati;
$\Gamma$ : insieme finito di simboli detto alfabeto dei nastri;
$\Sigma \subseteq \Gamma$ : insieme finito di simboli detto alfabeto d'ingresso;
$\delta :Q\times \Gamma ^{k}\rightarrow Q\times \Gamma ^{k}\times \left\{R,L,S\right\}$ : funzione di transizione. Generalmente si tratta di una funzione parziale;
$q_{A}\in Q$ : stato di accettazione;
$q_{R}\in Q,q_{R}\neq q_{A}$ : stato di rifiuto;
$q_{0}\in Q\setminus \left\{q_{A},q_{R}\right\}$ : stato iniziale;
$\Delta \in \Gamma$ : simbolo di cella vuota.

Si noti come la funzione di transizione disponga, in questo caso, di $k+1$ parametri: uno riguarda lo stato, gli altri i simboli letti dai nastri.

Ora che anche la definizione formale è stata posta sarà indispensabile dimostrare, pur sommariamente, l'equivalenza tra questo modello computazionale ed il riconoscitore di Turing a nastro singolo.

Equivalenza di un riconoscitore multinastro con un riconoscitore a nastro singolo

Questa parte della lezione presenta per sommi capi la dimostrazione di equivalenza tra un riconoscitore di Turing multinastro ed un riconoscitore di Turing tradizionale. Iniziamo quindi la nostra discussione enunciando un importante teorema.

Teorema di equivalenza

Un linguaggio Turing-riconoscibile è accettato da un riconoscitore di Turing multinastro se e solo se è accettato da un riconoscitore di Turing.

Idea della dimostrazione

Dato che il teorema viene enunciato utilizzando una doppia implicazione, la sua dimostrazione avverrà in due fasi: prima dimostreremo l'implicazione diretta, poi l'inversa.

Implicazione diretta - In questo caso dobbiamo dimostrare che, se un linguaggio viene accettato da un riconoscitore di Turing, allora esiste un riconoscitore di Turing multinastro che accetta il medesimo linguaggio. Questa parte della dimostrazione è semplice e può essere svolta ricorrendo alla strategia della riduzione: nulla vieta di utilizzare un riconoscitore di Turing multinastro dotato di un nastro solo. L'implicazione diretta è così dimostrata.

Implicazione inversa - In questo caso dobbiamo dimostrare che, se un linguaggio viene accettato da un riconoscitore di Turing multinastro con $k$ nastri, allora esiste un riconoscitore di Turing che accetta il medesimo linguaggio. Questa parte della dimostrazione è più intricata; viene affrontata impiegando la strategia della simulazione, mediante la quale si cercherà di simulare il comportamento di una macchina multinastro utilizzando una macchina di Turing con un nastro solo. L'idea migliore consiste nell'adattare le condizioni iniziali ed il ciclo di lavoro di un riconoscitore di Turing in modo che possa funzionare come nel caso multinastro.

Le condizioni iniziali riguardano sia lo stato della macchina, sia i nastri e le testine; affrontiamo anzitutto il problema della rappresentazione del contenuto di più nastri impiegando un nastro solo. Autori diversi offrono strategie differenti per risolvere la questione; quella che adotteremo in questo corso è una generalizzazione della strategia impiegata da Alan Turing quando, nel suo articolo, distingue le celle denominate F-squares da quelle dette E-squares. Questo modo di procedere corrisponde infatti a suddividere il nastro in due categorie: una contiene le celle che occupano posizioni pari, l'altra quelle che occupano posizioni dispari; concettualmente è come se Turing avesse disposto due nastri su uno solo, intercalando le celle del primo con quelle del secondo. Il suo principio può essere generalizzato a $k$ nastri: suddividendo il singolo nastro in gruppi di $k$ celle, ogni gruppo conterrà un simbolo proveniente da $k$ nastri diversi. Abbiamo così stabilito l'organizzazione del nastro: si tratta ora di riportare su di esso i simboli contenuti nel nastro principale della macchina multinastro.

Una volta che il contenuto del nastro sia stato correttamente impostato bisogna affrontare il problema delle testine: com'è possibile rappresentare $k$ testine su un dispositivo che ne ha una sola? Una possibilità è quella di inserire una marcatura nelle celle del nastro che si trovano sotto le testine; ogni simbolo del nastro appartenente alla macchina di Turing tradizionale esisterà quindi in due versioni: quella semplice e quella marcata. La scelta della strategia delle marcature comporta quindi un'espansione dell'alfabeto del nastro.

A questo punto disponiamo di un nastro che raccoglie tutti i simboli dei $k$ nastri e contiene una marcatura che permette di identificare le testine; le condizioni iniziali sono definite a dovere, quindi dobbiamo passare alla descrizione del ciclo di lavoro.

Nel riconoscitore multinastro la prima parte del ciclo concerne la lettura dei simboli dai $k$ nastri: dovremo quindi simulare questa operazione impiegando la macchina di Turing tradizionale. È possibile pensare ad un algoritmo che identifichi le testine una alla volta:

la testina della macchina viene posta in corrispondenza della prima cella del nastro; in questo modo si leggerà il contenuto della prima cella del primo nastro.
la macchina cerca, solamente nelle caselle del nastro che stiamo analizzando, un simbolo dotato di marcatura: in questo modo identifica sia la posizione della testina, sia il simbolo da leggere;
in base al valore trovato, la macchina si porta in un nuovo stato;
la macchina ritorna alla posizione iniziale del nastro, portandosi poi nella prima cella del nastro successivo.

A questo punto il ciclo si ripete a partire dal punto 2, effettuando una scansione di tutti i nastri alla ricerca dei simboli presenti sotto alle testine.

Al termine di questa procedura la macchina di Turing si trova in uno stato che codifica sia lo stato della macchina multinastro, sia i valori letti dalle testine. Queste informazioni possono essere impiegate per determinare lo stato prossimo della macchina ed in questo modo si completa la seconda parte del ciclo di lavoro della macchina.

La terza e la quarta parte del ciclo consistono nella sostituzione dei simboli presenti sui $k$ nastri e nel movimento delle testine. Una delle difficoltà che incontreremo sarà data dal fatto che, mentre la macchina di Turing multinastro può conservare la posizione delle testine, in quella con un nastro solo la testina è obbligata a muoversi sempre. Vediamo nelle grandi linee come queste operazioni possano essere svolte:

si porta la testina della macchina nella cella più a sinistra;
si attraversano solamente le celle del nastro che si sta analizzando fino a raggiungere la cella dotata del marcatore;
se il comando della testina è una $S$ , si sostituisce il simbolo marcato con un altro simbolo marcato (eventualmente lo stesso);
se il comando della testina è una $R$ , si sostituisce il simbolo marcato con un simbolo non marcato (eventualmente lo stesso), poi si raggiunge la prima cella del nastro sulla destra e si sostituisce il simbolo presente con la sua versione marcata;
se il comando della testina è una $L$ , si sostituisce il simbolo marcato con un simbolo non marcato (eventualmente lo stesso), poi si raggiunge la prima cella del nastro sulla sinistra e si sostituisce il simbolo presente con la sua versione marcata;
si porta la testina della macchina di Turing all'inizio del nastro, quindi si raggiunge la prima cella del nastro successivo;
si riprende il procedimento dal punto 2, fino all'esaurimento dei nastri.

Abbiamo quindi fornito un'idea generale circa la dimostrazione di equivalenza tra un riconoscitore di Turing a nastro singolo e la sua versione multinastro. Prima di discutere un esempio applicativo è importante stabilire il modo in cui si possono rappresentare le configurazioni e la computazione nelle macchine di Turing multinastro.

Configurazione, transizione e computazione in una macchina di Turing multinastro

Al fine di descrivere l'evoluzione della computazione dei riconoscitori multinastro è importante stabilire una rappresentazione per la configurazione; come sappiamo, tale concetto rappresenta in un'unica entità lo stato del riconoscitore e la stringa che viene letta, indicando anche la posizione della testina.

Nel caso delle macchine multinastro c'è una difficoltà legata alla presenza di più nastri, ognuno dei quali contiene simboli che influenzano la computazione; la configurazioni di tali macchine dovrà quindi contemplare il contenuto di tutti i nastri.

La configurazione verrà rappresentata da una ennupla ordinata composta da $k+1$ elementi $c=(q,s_{1},s_{2},...,s_{k})$ , dove $s_{i}\in \Gamma ^{*}$ indica la stringa presente sul nastro numero $i$ .

Per indicare la posizione della testina sui diversi nastri viene utilizzata la sottolineatura; ad esempio, nella configurazione $c=(q_{4},aaaa{\underline {b}}bbb,YYYY{\underline {\Delta }})$ indica un riconoscitore multinastro dotato di due nastri che si trova nello stato $q_{4}$ ; la testina del nastro principale si trova sul primo simbolo $b$ , mentre la testina del secondo nastro si trova sulla prima cella vuota disponibile dopo una stringa di quattro simboli $Y$ .

La transizione si rappresenta, come di consueto, con la cosiddetta turnstile notation; se $c_{1}$ e $c_{2}$ sono due configurazioni scelte in modo che sia possibile passare da $c_{1}$ a $c_{2}$ con una sola transizione, potremo scrivere $c_{1}\vdash c_{2}$ .

Anche il concetto di computazione come successione di configurazioni legate da transizioni viene confermato.

Esempio 7 - Linguaggio $a^{n}b^{n}c^{n}$ con un riconoscitore multinastro

Presentiamo a questo punto un esempio di riconoscitore multinastro, basandoci sul linguaggio $L=\left\{a^{n}b^{n}c^{n},n>0\right\}$ per il quale è già stato sviluppato un riconoscitore basato sul modello a nastro singolo.

La scelta di un linguaggio conosciuto ci permette di confrontare le prestazioni del nuovo tipo di riconoscitore con quelle del modello tradizionale; più precisamente, gli aspetti su cui ci soffermeremo saranno la semplicità del modello e la velocità di esecuzione. Per valutare la semplicità ci baseremo sul numero di stati e sul numero di transizioni, mentre la velocità di esecuzione verrà stimata in base alla lunghezza delle computazioni.

Prima di presentare la struttura dettagliata del riconoscitore, spenderemo qualche parola sull'algoritmo che verrà impiegato, mostrando l'impostazione generale:

quando si legge un simbolo $a$ vengono scritti due simboli, una $Y$ ed una $Z$ , su altri due nastri;
ogni volta che si legge un simbolo $b$ viene cancellata una $Y$ dal secondo nastro;
ogni volta che si legge un simbolo $c$ viene cancellata una $Z$ dal terzo nastro.

La computazione si può considerare terminata con accettazione quando, dopo aver letto l'ultimo simbolo $c$ della stringa, i due nastri aggiuntivi sono vuoti.

Da questa breve descrizione si comprende che il modello computazionale scelto prevede tre nastri: uno per i simboli d'ingresso e due aggiuntivi impiegati per conservare il numero di simboli $a$ letti. Sebbene vi siano molti aspetti in comune con il caso del riconoscitore a nastro singolo, questo nuovo formalismo presenta novità che riguardano due caratteristiche: l'insieme degli stati e, di conseguenza, le transizioni.

Insieme degli stati - Il riconoscitore multinastro è dotato di cinque stati, due dei quali riguardano accettazione e rifiuto delle stringhe:

$q_{0}$ è lo stato iniziale e viene impiegato per il conteggio dei simboli $a$ , riportato sui due nastri;
$q_{1}$ è lo stato in cui i simboli $b$ vengono confrontati con il contenuto del primo nastro aggiuntivo;
$q_{2}$ è lo stato in cui i simboli $c$ vengono confrontati con il contenuto del secondo nastro aggiuntivo;
$q_{A}$ è lo stato di accettazione;
$q_{R}$ è lo stato di rifiuto.

Funzione di transizione - Presenteremo due diverse versioni della stessa funzione di transizione: la prima sarà fedele alla definizione data, la seconda prevede una riorganizzazione delle colonne in modo da evidenziare la struttura dei nastri. Le due opzioni vengono presentate per offrire al lettore la possibilità di scegliere, di volta in volta, quale rappresentazione sia più adatta allo scopo

Numero istruzione	Stato attuale	Simboli letti dal nastro	Simboli scritti sul nastro	Movimenti delle testine	Stato prossimo
1	$q_{0}$	$(a,\Delta ,\Delta )$	$(a,X,Y)$	$(R,R,R)$	$q_{0}$
2	$q_{0}$	$(b,\Delta ,\Delta )$	$(b,\Delta ,\Delta )$	$(R,L,L)$	$q_{1}$
3	$q_{1}$	$(b,X,Y)$	$(b,\Delta ,Y)$	$(R,L,S)$	$q_{1}$
4	$q_{1}$	$(c,X,Y)$	$(c,\Delta ,\Delta )$	$(R,L,L)$	$q_{2}$
5	$q_{2}$	$(c,X,Y)$	$(c,\Delta ,\Delta )$	$(R,L,L)$	$q_{2}$
6	$q_{2}$	$(c,\Delta ,Y)$	$(c,\Delta ,\Delta )$	$(R,S,L)$	$q_{2}$
7	$q_{2}$	$(\Delta ,\Delta ,\Delta )$	$(\Delta ,\Delta ,\Delta )$	$(S,S,S)$	$q_{A}$
8	$q_{2}$	$(\Delta ,X,\Delta )$	$(\Delta ,X,\Delta )$	$(S,S,S)$	$q_{R}$
9	$q_{2}$	$(\Delta ,\Delta ,Y)$	$(\Delta ,\Delta ,Y)$	$(S,S,S)$	$q_{R}$
10	$q_{2}$	$(\Delta ,X,Y)$	$(\Delta ,X,Y)$	$(S,S,S)$	$q_{R}$

Confrontando questa tabella con quella presentata per il riconoscitore a nastro singolo si nota maggior brevità, da ricercare sia nel numero di stati più contenuto, sia nel numero di transizioni.

Come anticipato poco fa, esaminiamo ora una tabella molto simile, in cui i dati sono organizzati per nastro.

Numero istruzione	Stato attuale	Nastro principale	Nastro 1	Nastro 2	Stato prossimo
1	$q_{0}$	$(a,a,R)$	$(\Delta ,X,R)$	$(\Delta ,Y,R)$	$q_{0}$
2	$q_{0}$	$(b,b,R)$	$(\Delta ,\Delta ,L)$	$(\Delta ,\Delta ,L)$	$q_{1}$
3	$q_{1}$	$(b,b,R)$	$(X,\Delta ,L)$	$(Y,Y,S)$	$q_{1}$
4	$q_{1}$	$(c,c,R)$	$(X,\Delta ,L)$	$(Y,\Delta ,L)$	$q_{2}$
5	$q_{2}$	$(c,c,R)$	$(\Delta ,\Delta ,S)$	$(Y,\Delta ,L)$	$q_{2}$
6	$q_{2}$	$(c,c,R)$	$(X,\Delta ,L)$	$(Y,\Delta ,L)$	$q_{2}$
7	$q_{2}$	$(\Delta ,\Delta ,S)$	$(\Delta ,\Delta ,S)$	$(\Delta ,\Delta ,S)$	$q_{A}$
8	$q_{2}$	$(\Delta ,\Delta ,S)$	$(X,X,S)$	$(\Delta ,\Delta ,S)$	$q_{R}$
9	$q_{2}$	$(\Delta ,\Delta ,S)$	$(\Delta ,\Delta ,S)$	$(Y,Y,S)$	$q_{R}$
10	$q_{2}$	$(\Delta ,\Delta ,S)$	$(X,X,S)$	$(Y,Y,S)$	$q_{R}$

Per completare il confronto con il caso del nastro singolo, presentiamo ora due computazioni di esempio.

Due computazioni del riconoscitore multinastro

Consideriamo inizialmente la stringa $abc$ ; la computazione del riconoscitore, in questo caso, sarà la seguente:

$(q_{0},{\underline {a}}bc\Delta ,{\underline {\Delta }}\Delta ,{\underline {\Delta }}\Delta )\vdash (q_{0},a{\underline {b}}c\Delta ,X{\underline {\Delta }},Y{\underline {\Delta }})\vdash (q_{1},ab{\underline {c}}\Delta ,{\underline {X}}\Delta ,{\underline {X}}\Delta )\vdash (q_{2},abc{\underline {\Delta }},{\underline {\Delta }}\Delta ,{\underline {\Delta }}\Delta )\vdash (q_{A},abc{\underline {\Delta }},{\underline {\Delta }}\Delta ,{\underline {\Delta }}\Delta )$

Analizziamo ora la computazione riguardante la stringa $aabbcc$ .

$(q_{0},{\underline {a}}abbcc\Delta ,{\underline {\Delta }}\Delta ,{\underline {\Delta }}\Delta )\vdash (q_{0},a{\underline {a}}bbcc\Delta ,X{\underline {\Delta }},Y{\underline {\Delta }})\vdash (q_{0},aa{\underline {b}}bcc\Delta ,XX{\underline {\Delta }},YY{\underline {\Delta }})\vdash (q_{1},aab{\underline {b}}cc\Delta ,X{\underline {X}},Y{\underline {Y}})\vdash (q_{1},aabb{\underline {c}}c\Delta ,{\underline {X}}\Delta ,Y{\underline {Y}})\vdash$

$\vdash (q_{2},aabbc{\underline {c}}\Delta ,{\underline {\Delta }}\Delta ,{\underline {Y}}\Delta )\vdash (q_{2},aabbcc{\underline {\Delta }},{\underline {\Delta }}\Delta ,{\underline {\Delta }}\Delta )\vdash$

Si nota che entrambe le computazioni sono più brevi rispetto alle analoghe svolte con la macchina a nastro singolo.

Riflessione sul ruolo delle prestazioni

Abbiamo dimostrato che le macchine multinastro sono equivalenti a quelle a nastro singolo, nel senso che riconoscono esattamente gli stessi linguaggi; in apparenza, quindi, non c'è ragione di preferire un modello rispetto ad un altro.

In realtà la progettazione della macchina multinastro ha richiesto uno sforzo minore rispetto al modello a nastro singolo; inoltre la struttura del è più semplice e, come abbiamo sottolineato, le computazioni sono molto più brevi.

Queste osservazioni permettono di concludere che, al di là delle capacità di riconoscimento dei linguaggi, le prestazioni giocano un ruolo importante da diversi punti di vista: progettazione, leggibilità e rapidità di esecuzione.

La macchina a nastro singolo è quindi adatta per un'analisi teorica, ma in ambito applicativo è possibile che la sua struttura ostacoli sia lo sviluppo sia l'esecuzione. È anche possibile che gli ostacoli presentati da questo modello computazionale diventino, in alcuni casi, talmente evidenti da rendere poco conveniente investire energie nell'implementazione degli algoritmi.

Queste riflessioni portano ad introdurre, pur superficialmente, il tema della trattabilità, secondo cui l'esistenza di un algoritmo non è sufficiente a rendere conveniente la sua implementazione. La terza parte di questo corso è interamente dedicata ad affrontare ed approfondire questo tema.

Macchina di Turing multitestina

Un altro modello computazionale che in qualche caso può mostrarsi utile é la macchina di Turing multitestina, in cui più testine si trovano contemporaneamente sullo stesso nastro. Intuitivamente, questa particolare configurazione della macchina può migliorare le prestazioni del modello in tutte le situazioni in cui è necessario confrontare tra loro diverse parti del nastro d'ingresso.

Introdurremo questo nuovo formalismo seguendo la stessa logica vista per la macchina multinastro, partendo dall'analisi della struttura del modello, passando per la dimostrazione di equivalenza con la macchina di Turing a nastro singolo e terminando il tutto con un esempio commentato.

Condizione iniziale e ciclo di lavoro

Se fosse possibile realizzare un'implementazione fisica di questa variante della macchina di Turing, noteremmo i seguenti dispositivi:

un'unità di controllo;
un nastro illimitato verso destra;
un insieme di testine libere di muoversi a destra e sinistra sul nastro; le testine possono leggere e scrivere simboli.

L'immagine sottostante mostra una rappresentazione schematica di un riconoscitore di Turing multitestina.

Esaminiamo ora quali sono le condizioni iniziali della macchina: lo stato viene impostato al suo valore iniziale, la testina 1 si trova all'inizio del nastro, mentre le altre $k-1$ testine si trovano in posizioni arbitrarie. A partire da questa situazione la macchina svolgerà ciclicamente le seguenti operazioni:

legge i simboli sotto alle $k$ testine. Le letture avvengono simultaneamente;
in base allo stato attuale e ai $k$ simboli letti, cambia stato (lo stato prossimo può coincidere con quello attuale);
scrive nuovi simboli sul nastro. Le scritture avvengono sequenzialmente e non simultaneamente ed i simboli scritti possono coincidere con quelli attuali;
muove le testine. I movimenti avvengono simultaneamente.

L'aspetto più particolare del ciclo di lavoro riguarda la scrittura dei simboli: è stato specificato che essa avviene sequenzialmente e non simultaneamente perché le testine possono trovarsi sulla stessa cella del nastro. Un modo per affrontare questo problema consiste nello stabilire un ordine di scrittura: in questo caso le testine sostituiscono i simboli partendo dalla prima fino alla $k$ -esima; in questo modo c'è la certezza che, se una cella è puntata da almeno due testine, il simbolo che verrà scritto sarà quello della testina con indice più alto. Questa impostazione non è unica e può essere sostituita con qualsiasi altra convenzione, a condizione che renda sempre prevedibile il simbolo che verrà posto nelle celle puntate da più testine. Una volta chiarita questa particolarità, possiamo dare la definizione di riconoscitore di Turing multitestina.

Definizione di riconoscitore di Turing multitestina

Un riconoscitore di Turing multitestina dotato di $k$ testine è una ottupla ordinata di elementi $M=()$ definiti come segue:

$Q$ è un insieme finito di stati;
$\Gamma$ è un insieme finito di simboli detto alfabeto del nastro;
$\Sigma$ è un insieme finito di simboli detto alfabeto d'ingresso
$\delta :Q\times \Gamma ^{k}\rightarrow Q\times \Gamma ^{k}\times \left\{R,L\right\}^{k}$ è la funzione di transizione, generalmente parziale;
$q_{A}\in Q$ è lo stato di accettazione;
$q_{R}\in Q\setminus \left\{q_{A}\right\}$ è lo stato di rifiuto;
$q_{0}\in Q\setminus \left\{q_{A},q_{R}\right\}$ è lo stato iniziale;
$\Delta \in \Gamma$ è il simbolo di cella vuota.

Equivalenza tra il riconoscitore di Turing multitestina e il riconoscitore di Turing

Come già avvenuto per la macchina di Turing multinastro, anche in questo caso è necessario anzitutto dimostrare l'equivalenza del presente modello computazionale con quello a nastro singolo e con una testina sola. Adotteremo la stessa convenzione: enunciando un teorema, proporremo le linee guida della sua dimostrazione, in modo da fornire uno spunto sui motivi che portano all'equivalenza.

Teorema

Un linguaggio Turing-riconoscibile è accettato da un riconoscitore di Turing multitestina se e solo se è accettato da un riconoscitore di Turing.

Idea generale della dimostrazione

Visto che il teorema è stato enunciato per mezzo di una doppia implicazione, la dimostrazione verrà suddivisa in due fasi: prima verrà dimostrata l'implicazione diretta, poi quella inversa. In tutta la dimostrazione indicheremo con $L$ il linguaggio da riconoscere, con $M$ il riconoscitore dotato di $k$ testine e con $T$ il riconoscitore di Turing con una testina sola.

Implicazione diretta - In questo caso bisogna dimostrare che, se esiste un riconoscitore di Turing $T$ che accetta $L$ , allora esiste anche un riconoscitore multitestina $M$ che accetta il medesimo linguaggio. Per dimostrare questa affermazione è sufficiente considerare il riconoscitore $M$ con $k=1$ .

L'implicazione diretta è quindi dimostrata.

Implicazione inversa - In questo caso bisogna dimostrare che, se esiste un riconoscitore di Turing $M$ dotato di $k$ testine capace di accettare il linguaggio $L$ , allora esiste un riconoscitore di Turing $T$ con una testina sola in grado di accettare $L$ . Come in precedenza, la dimostrazione verrà affrontata impiegando la strategia della simulazione, mediante la quale faremo in modo di simulare $M$ impiegando $T$ .

Per effettuare la simulazione ci occuperemo anzitutto della condizione iniziale, poi delle singole fasi del ciclo. Visto che dobbiamo simulare la presenza di $k$ testine, vale la pena impiegare la stessa strategia adottata nella macchina multinastro: estendere l'alfabeto del nastro aggiungendo per ogni simbolo dei simboli con marcature, utilizzati per indicare la presenza di una testina. La situazione della macchina multitestina è però più delicata, poiché in linea di massima le testine possono occupare anche la stessa cella; questo aspetto rende necessario prevedere, per ogni simbolo, anche delle coppie di marcature e, generalizzando, le terne, le quaterne... fino ad arrivare a $k$ marcature su un simbolo solo. L'ordine in cui prendiamo le testine non ha importanza: quindi, se su una cella si trovano le testine numero 1 e numero 4 avremmo la medesima situazione che si otterrebbe con le testine numer 4 e numero 1. È possibile contare le coppie di testine che si possono formare con $k$ elementi: si tratta di ${\frac {1}{2}}\cdot {k \choose 2}$ . In modo analogo, il numero di terne di testine sarà dato da: ${\frac {1}{2}}\cdot {k \choose 3}$ .

Generalizzando questo metodo e sommando i singoli contributi avremo: ${\frac {1}{2}}\cdot \sum _{i=0}^{k}{k \choose i}$ .

A questo punto si riconosce che il risultato ottenuto è derivato dalla formula del binomio di Newton nel caso in cui $a=1,b=1$ , e si può calcolare il numero totale di possibili marcature per ogni simbolo dell'alfabeto del nastro: ${\frac {1}{2}}\cdot \sum _{i=0}^{k}{k \choose i}={\frac {1}{2}}2^{k}=2^{k-1}$

Il fatto che il numero di simboli da utilizzare cresca esponenzialmente con il numero di testine non è una buona notizia, ma è comunque indice del fatto che l'alfabeto del nastro conterrà sempre un numero finito di simboli. Sistemata la questione delle marcature, possiamo immaginare di preparare il nastro della macchina $T$ sostituendo ad ogni simbolo che si trovi in corrispondenza ad una o più testine il simbolo con marcatore che gli corrisponde. Si pone a questo punto la testina del riconoscitore in corrispondenza della prima cella del nastro e si inizia il ciclo di lavoro.

Vediamo ora come vengono simulate le fasi di lavoro della macchina $M$ .

Nella prima fase del ciclo vengono letti i simboli presenti sotto le $k$ testine; la macchina $T$ dovrà quindi svolgere la lettura iterativamente:

cercare la cella che contiene una marcatura compatibile con la testina considerata: questa cella può avere anche più di una marcatura;
la macchina si porta in uno stato che rappresenta il simbolo trovato;
la testina torna all'inizio del nastro e si ripete il punto 1, concentrandosi sulla testina successiva.

La seconda fase del ciclo deve cambiare lo stato della macchina $T$ in accordo con lo stato attuale e con i valori letti dalle testine: queste informazioni sono codificate nello stato in cui si trova la macchina al termine della fase precedente.

Nella terza e nella quarta fase del ciclo la macchina deve sostituire i simboli che si trovano sotto le testine con quelli previsti dalla transizione e muovere tutte le testine. L'operazione viene svolta in modo iterativo, modificando una testina alla volta:

la macchina parte dall'inizio del nastro e continua a spostarsi verso destra finché trova un simbolo dotato di una marcatura che comprende la testina che si sta analizzando;
il simbolo viene sostituito con quello previsto dalla transizione e con una marcatura che non preveda più la presenza della testina;
in base alla transizione, la testina si muove nella cella immediatamente a destra oppure a sinistra;
il simbolo della cella viene sostituito con uno dotato di una marcatura che tiene conto anche della testina attuale;
la testina torna all'inizio del nastro e si ripete il procedimento dal punto 1, prestando attenzione alla testina successiva.

Tutte le fasi del ciclo di lavoro sono state simulate in modo appropriato, possiamo pertanto ritenere conclusa la simulazione e dimostrato il teorema.

Configurazione, transizione e computazione con una macchina multitestina

Anche per questo formalismo è necessario fornire un metodo per rappresentare la configurazione: dovendo indicare la posizione di $k$ testine sceglieremo la convenzione di riportare l'indice della testina sotto al simbolo in cui si trova. Per fare un esempio, in un riconoscitore multitestina con 4 testine che lavora sulla stringa $aabbccddee$ e si trova nello stato $q_{3}$ e che ha le testine in posizione 3, 5, 5, 9, la configurazione sarà $(q_{3},aa{\underset {1}{b}}b{\underset {2,3}{c}}cdd{\underset {4}{e}}e)$ .

Come di consueto, due configurazioni $c_{1}$ e $c_{2}$ si dicono consecutive se è possibile passare da una configurazione alla successiva in un solo ciclo di lavoro del modello computazionale; le due configurazioni saranno quindi legate dalla relazione di transizione e potremo scrivere $c_{1}\vdash c_{2}$ .

Inoltre, una successione finita di configurazioni a due a due consecutive prende il nome di computazione e viene in genere indicata con $c_{1}{\overset {*}{\vdash }}c_{n}$ .

Esempio 8 - Linguaggio $a^{n}b^{n}c^{n}$ con un riconoscitore multitestina

A questo punto affrontiamo la progettazione di una macchina di Turing multitestina che analizzi il consueto linguaggio $L=\left\{a^{n}b^{n}c^{n},n>0\right\}$ , con l'obiettivo di confrontare le prestazioni sia con il modello originale, sia con il riconoscitore di Turing multinastro.

Prima di fornire i dettagli del modello computazionale è utile premettere alcune considerazioni riguardanti la struttura dell'algoritmo da implementare: svilupperemo un riconoscitore multitestina dotato di tre testine, una per ogni tipo di simbolo. Ci sarà quindi una testina dedicata ai simboli $a$ (testina 1), una dedicata ai simboli $b$ (testina 2) ed una dedicata ai simboli $c$ (testina 3). Inizialmente la testina 1 viene posizionata in corrispondenza alla prima cella del nastro, mentre la testina 2 si troverà sulla cella che contiene la prima occorrenza del simbolo $b$ e la testina 3 verrà posizionata sulla prima $c$ . Da questo momento le testine vengono mosse all'unisono verso destra e, se la stringa è formata regolarmente, ad un certo punto la testina 1 leggerà un simbolo $b$ , la testina 2 un simbolo $c$ e la testina 3 si trvoerà su una cella vuota. In tutti gli altri casi si potrà concludere che la stringa non è ben formata.

La tabella sottostante rappresenta la funzione di transizione del riconoscitore che implementa l'algoritmo appena descritto: dalla tabella è possibile dedurre tutte le caratteristiche del modello.

Numero istruzione	Stato attuale	Simboli letti dal nastro	Simboli scritti sul nastro	Movimenti delle testine	Stato prossimo
1	$q_{0}$	$(a,b,c)$	$(a,b,c)$	$(R,R,R)$	$q_{0}$
2	$q_{0}$	$(b,c,\Delta )$	$(b,c,\Delta )$	$(L,L,L)$	$q_{A}$
3	$q_{0}$	$(b,b,c)$	$(b,b,c)$	$(L,L,L)$	$q_{R}$
4	$q_{0}$	$(a,c,c)$	$(a,c,c)$	$(L,L,L)$	$q_{R}$
5	$q_{0}$	$(a,b,\Delta )$	$(a,b,\Delta )$	$(L,L,L)$	$q_{R}$

Analisi di due computazioni

Come già fatto nel caso degli altri formalismi che abbiamo sottoposto al medesimo linguaggio, analizzeremo le computazioni riguardanti le due stringhe $abc$ e $aabbcc$

Nel primo caso la computazione sarà:

$(q_{0},{\underset {1}{a}}{\underset {2}{b}}{\underset {3}{c}})\vdash (q_{0},a{\underset {1}{b}}{\underset {2}{c}}{\underset {3}{\Delta }})\vdash (q_{A},{\underset {1}{a}}{\underset {2}{b}}{\underset {3}{c}})$

Nel secondo caso la computazione sarà:

$(q_{0},{\underset {1}{a}}a{\underset {2}{b}}b{\underset {3}{c}}c)\vdash (q_{0},a{\underset {1}{a}}b{\underset {2}{b}}c{\underset {3}{c}})\vdash (q_{0},aa{\underset {1}{b}}b{\underset {2}{c}}c{\underset {3}{\Delta }})\vdash (q_{A},a{\underset {1}{a}}b{\underset {2}{b}}c{\underset {3}{c}})$

Osservando le due computazioni è davvero evidente la grande differenza con gli altri formalismi; notevole soprattutto il fatto che, passando dalla prima alla seconda stringa, la lunghezza della computazione sia aumentata di una sola unità.

Enumeratore di Turing

L'ultima variante che prenderemo in considerazione sarà l'enumeratore di Turing, un modello computazionale particolarmente interessante a causa dello stretto nesso esistente tra le sue caratteristiche strutturali ed i linguaggi che possono essere accettati dai riconoscitori di Turing.

Come vedremo, l'enumeratore di Turing è un tipo di macchina multinastro, dunque non sarà necessario dimostrare l'equivalenza con il modello computazionale a nastro singolo. Esamineremo la struttura dell'enumeratore, il suo ciclo di lavoro e analizzeremo in seguito un semplice esempio, presentato per intuirne le potenzialità.

Struttura e ciclo di lavoro

Come è stato anticipato, l'enumeratore di Turing è una macchina multinastro, più precisamente è una macchina dotata di due nastri: il primo viene impiegato per produrre singole stringhe, il secondo contiene l'elenco di tutte le stringhe prodotte dall'enumeratore. È quindi possibile intuire il principio di funzionamento di un dispositivo fisico che si comporti come il modello: l'unità di controllo scrive una stringa sul primo nastro; una volta terminata la scrittura, la stringa viene copiata sul secondo nastro. Volendo immaginare il dispositivo fisico, si potrebbe pensare ad un'unità di controllo che non legge alcun ingresso, ma scrive singole stringhe su un nastro e poi le stampa.

Considerando che il secondo nastro raccoglie tutte le stringhe generate dall'enumeratore, possiamo concludere che esso rappresenterà il linguaggio dell'enumeratore; è proprio per questo motivo che la classe dei linguaggi che vengono accettati da un riconoscitore di Turing si chiama anche classe dei linguaggi ricorsivamente enumerabili: ognuno di essi è associato ad un enumeratore che può stamparlo su un nastro.

Esaminiamo l'algoritmo con cui opera l'enumeratore: c'è una fase iniziale in cui il dispositivo scrive simboli dell'alfabeto d'ingresso sul primo nastro; ad ogni simbolo scritto corrisponde una transizione, che eventualmente può mantenere lo stesso stato. Durante l'evoluzione, ad un certo punto l'enumeratore raggiunge lo stato di stampa: a questo punto la testina del primo nastro viene portata indietro fino all'inizio e comincia a copiare il contenuto del primo nastro sul nastro di stampa. A questo punto l'enumeratore aggiunge un simbolo sul nastro di stampa, in modo da separare la stringa appena stampata da quella che verrà stampata in seguito. Il ciclo di lavoro della macchina riprende quindi dall'inizio, producendo la stringa successiva.

Entriamo ora più nel dettaglio, indagando il comportamento della macchina nelle due fasi che abbiamo esaminato: la costruzione di una stringa e la sua stampa. Nella fase di costruzione sono previste le seguenti attività:

la macchina scrive sul primo nastro un simbolo $, utilizzato per indicare l'inizio del nastro, poi muove la prima testina a destra e tiene ferma la seconda testina;
il simbolo $\Delta$ presente sul nastro viene sostituito da un simbolo dell'alfabeto d'ingresso;
la testina del primo nastro si sposta a destra, mentre quella del secondo nastro rimane ferma;
in base al simbolo $\Delta$ ed al simbolo impiegato per la sostituzione, si decide lo stato prossimo;
se lo stato prossimo è lo stato di stampa, la prima fase del ciclo termina. In caso contrario, si riprende il ciclo a partire dal punto 2.

Nella fase di stampa della stringa sono previsti due momenti: il ritorno all'inizio del primo nastro e la copiatura verso il secondo nastro.

si inizia l'esecuzione nello stato di stampa; se il simbolo letto sul primo nastro non è $ si sposta la prima testina a sinistra, mentre la seconda testina rimane ferma;
se il simbolo letto sul primo nastro è $ ci si porta nello stato di copiatura. La testina del primo nastro viene spostata a destra, mentre la seconda testina rimane ferma;
se il carattere letto sul primo nastro appartiene all'alfabeto d'ingresso, lo si scrive sul secondo nastro. Le due testine vengono spostate a destra;
se il carattere letto sul primo nastro è $\Delta$ , si scrive # sul secondo nastro.

Al termine della fase di stampa bisognerebbe riprendere l'esecuzione dalla fase di costruzione della stringa, producendone un'altra appartenente al linguaggio; questa fase può avvenire in tre modi: aggiungendo caratteri alla stringa già presente, alterando parzialmente la stringa oppure sovrascrivendola completamente. A seconda della strategia adottata, la ripresa del ciclo cambia; non è quindi possibile descrivere questo passaggio mediante un unico algoritmo generale.

Ora che abbiamo descritto i principi di funzionamento del modello, possiamo fornire una definizione più accurata.

Definizione di enumeratore di Turing

Un enumeratore è una nonupla ordinata di elementi $E=(Q,\Gamma ,\Sigma ,\delta ,q_{P},q_{0},\Delta ,\$,\#)$ , definiti come segue:

$Q$ è un insieme finito di stati;
$\Gamma$ è un insieme finito di simboli, detto alfabeto dei nastri;
$\Sigma \in \Gamma$ è un insieme finito di simboli, detto alfabeto d'ingresso;
$\delta :Q\times \Gamma ^{2}\rightarrow Q\times \Gamma ^{2}\times \left\{R,L,S\right\}^{2}$ è la funzione di transizione;
$q_{P}\in Q$ è lo stato di stampa;
$q_{0}\in Q$ è lo stato iniziale;
$\Delta \in \Gamma$ è il simbolo di cella vuota;
$\$\in \Gamma$ è il simbolo iniziale del primo nastro;
$\#\in \Gamma$ è il simbolo separatore del secondo nastro.

Esempio 9 - Il linguaggio $(ab)^{n}$

Consideriamo l'alfabeto d'ingresso $\Sigma =\left\{a,b\right\}$ e costruiamo il linguaggio formale $L=\left\{(ab)^{n},n>0\right\}$ . Vogliamo progettare un enumeratore di Turing in grado di stampare il linguaggio $L$ . Iniziamo dicendo che il linguaggio proposto è regolare, quindi è anche ricorsivamente enumerabile ed esisterà di conseguenza un enumeratore in grado di stamparlo.

La tabella seguente rappresenta la funzione di transizione per l'enumeratore proposto.

Numero istruzione	Stato attuale	Nastro principale	Nastro di stampa	Stato prossimo
1	$q_{0}$	$(\Delta ,\$,R)$	$(\Delta ,\Delta ,S)$	$q_{1}$
2	$q_{1}$	$(\Delta ,a,R)$	$(\Delta ,\Delta ,S)$	$q_{2}$
3	$q_{2}$	$(\Delta ,b,R)$	$(\Delta ,\Delta ,S)$	$q_{P}$
4	$q_{P}$	$(a,a,L)$	$(\Delta ,\Delta ,S)$	$q_{P}$
5	$q_{P}$	$(b,b,L)$	$(\Delta ,\Delta ,S)$	$q_{p}$
6	$q_{P}$	$(\$,\$,R)$	$(\Delta ,\Delta ,S)$	$q_{C}$
7	$q_{C}$	$(a,a,R)$	$(\Delta ,a,R)$	$q_{C}$
8	$q_{C}$	$(b,b,R)$	$(\Delta ,b,R)$	$q_{C}$
9	$q_{C}$	$(\Delta ,\Delta ,S)$	$(\Delta ,\#,R)$	$q_{1}$

Lo stato $q_{P}$ è lo stato di stampa e viene impiegato, in questo caso, per arretrare la posizione della testina del primo nastro fino a raggiungere l'estremo più a sinistra. Lo stato $q_{C}$ è invece dedicato alla copiatura della stringa dal primo nastro verso il secondo. Infine, in questo semplice esempio, la strategia adottata per riprendere il ciclo di lavoro consiste nell'aggiunta di simboli alla stringa già presente.

Altre varianti della macchina di Turing multinastro

Abbiamo presentato alcune delle varianti della macchina di Turing multinastro, ma l'elenco è molto più lungo; senza pretendere di fornire una lista dettagliata dei modelli, vale la pena di richiamare per lo meno alcuni di essi. Sebbene non vengano descritti nel dettaglio,

Macchina di Turing non deterministica

In realtà questo modello computazionale verrà analizzato in maggior dettaglio, poiché vi sarà un'intera lezione dedicata ad esso; per ora ci limitiamo a segnalare che l'interesse per la versione non deterministica del modello ha a che fare con la sua capacità di riconoscimento dei linguaggi: dimostreremo che la macchina di Turing non deterministica riconosce gli stessi linguaggi della versione determinisitica.

Macchina di Turing multitraccia

Si tratta di una macchina di Turing multinastro in cui le testine vengono azionate in contemporanea, permettendo numerose letture e scritture in parallelo.

Macchina di Turing ad accesso casuale

Uno dei fattori che rallentano l'esecuzione di una macchina di Turing è la necessità di scorrere tutte le celle del nastro prima di giungere a quella desiderata. Sarebbe meglio poter accedere alle celle in maniera immediata, decidendo quale leggere in base alla sua posizione nel nastro. La macchina di Turing ad accesso casuale permette questo comportamento, associando ad ogni cella un numero naturale che la identifica univocamente. Il modello computazionale risultante è radicalmente diverso da quello che abbiamo presentato, in quanto cade nella categoria delle macchine a registri. Interpretando il nastro come una memoria, il numero naturale che identifica le celle può essere visto come un indirizzo di memoria. L'impiego dei registri e l'uso degli indirizzi di memoria avvicinano di molto questa variante della macchina di Turing ai computer moderni.

Macchina di Turing con nastro doppiamente illimitato

Questa variante introduce la possibilità di impiegare un nastro d'ingresso che sia illimitato sia verso destra che verso sinistra.

Lezione precedente: Automa a pila

Corso: Materia:Informatica Teorica

Prossima lezione: Grammatiche

Obiettivo della lezione

Introduzione storica

Contestualizzazione

Principio di funzionamento

Caratteristiche della macchina di Turing

Definizione di macchina di Turing

Esempio 1 - Stampa di una successione illimitata

Esempio 2 - Successivo di un numero naturale in base 2

Seguire la computazione di una macchina di Turing

Calcolo del successivo di 2

Calcolo del successivo di 3

Le macchine di Turing come accettori di linguaggi

Definizione di riconoscitore di Turing

Esempio 3 - Accettazione delle stringhe che iniziano con la sequenza a b {\displaystyle ab}

Esempio 4 - Accettazione del linguaggio a n b n {\displaystyle a^{n}b^{n}}

Analisi di due computazioni del riconoscitore

Confronto fra l'accettore a pila ed il riconoscitore di Turing

Esempio 5 - Linguaggio a n b n {\displaystyle a^{n}b^{n}} : un algoritmo alternativo

Analisi di due computazioni con il nuovo algoritmo

Confronto delle computazioni degli esempi 4 e 5

Esempio 6 - Accettazione del linguaggio a n b n c n {\displaystyle a^{n}b^{n}c^{n}}

Analisi di due computazioni del riconoscitore

Le macchine di Turing come decisori di linguaggi

Varianti della macchina di Turing

Macchina di Turing multinastro

Struttura e ciclo di lavoro

Definizione di riconoscitore di Turing multinastro

Equivalenza di un riconoscitore multinastro con un riconoscitore a nastro singolo

Teorema di equivalenza

Idea della dimostrazione

Configurazione, transizione e computazione in una macchina di Turing multinastro

Esempio 7 - Linguaggio a n b n c n {\displaystyle a^{n}b^{n}c^{n}} con un riconoscitore multinastro

Due computazioni del riconoscitore multinastro

Riflessione sul ruolo delle prestazioni

Macchina di Turing multitestina

Condizione iniziale e ciclo di lavoro

Definizione di riconoscitore di Turing multitestina

Equivalenza tra il riconoscitore di Turing multitestina e il riconoscitore di Turing

Teorema

Idea generale della dimostrazione

Configurazione, transizione e computazione con una macchina multitestina

Esempio 8 - Linguaggio a n b n c n {\displaystyle a^{n}b^{n}c^{n}} con un riconoscitore multitestina

Analisi di due computazioni

Enumeratore di Turing

Struttura e ciclo di lavoro

Definizione di enumeratore di Turing

Esempio 9 - Il linguaggio ( a b ) n {\displaystyle (ab)^{n}}

Altre varianti della macchina di Turing multinastro

Macchina di Turing non deterministica

Macchina di Turing multitraccia

Macchina di Turing ad accesso casuale

Macchina di Turing con nastro doppiamente illimitato

Esempio 3 - Accettazione delle stringhe che iniziano con la sequenza $ab$

Esempio 4 - Accettazione del linguaggio $a^{n}b^{n}$

Esempio 5 - Linguaggio $a^{n}b^{n}$ : un algoritmo alternativo

Esempio 6 - Accettazione del linguaggio $a^{n}b^{n}c^{n}$

Esempio 7 - Linguaggio $a^{n}b^{n}c^{n}$ con un riconoscitore multinastro

Esempio 8 - Linguaggio $a^{n}b^{n}c^{n}$ con un riconoscitore multitestina

Esempio 9 - Il linguaggio $(ab)^{n}$