Università degli studi di Lecce
Corso di laurea in Matematica e Informatica
Corso Seminariale a.a. 2005 - 2006
Automi e
macchine di Turing
Macchia Sara
Automi e macchine di Turing
Introduzione
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Perché si studia la teoria degli automi?
La teoria degli automi è lo studio di
dispositivi computazionali o “macchine”.
Gli automi, originariamente, furono proposti
per creare un modello matematico che
riproducesse il funzionamento del cervello.
2/61
Automi e macchine di Turing
Introduzione
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Gli automi finiti sono degli utili modelli per
molti importanti tipi di software:
• software per la progettazione e la verifica
del comportamento dei circuiti digitali;
• l’ ”analizzatore lessicale” di un compilatore;
• software che eseguono una scansione di testi
molto lunghi per trovare parole, frasi, ecc.;
• software per verificare i protocolli di
comunicazione o protocolli per lo scambio
sicuro di informazioni.
3/61
Automi e macchine di Turing
Automi
Introduzione
• Cos’è un automa?
Macchine di
Turing
Un automa è un dispositivo, o un sistema in
forma di macchina sequenziale, che, ad ogni
istante, può trovarsi in un determinato “stato”.
Funzioni
calcolabili con
MdT
Lo scopo dello stato è quello di ricordare la
parte rilavante della storia del sistema.
Problema
dell’arresto
Finché ci sono solo un numero finito di stati,
l’intera storia del sistema non può essere
ricordata.
Automi
4/61
Automi e macchine di Turing
Automi
Introduzione
Automi
• Esempio 1
Un automa finito che rappresenta un interruttore on/off
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
rappresenta gli stati
rappresenta l’input
indica lo stato iniziale
5/61
Automi e macchine di Turing
Automi
Introduzione
Automi
• Esempio 2
Un automa finito che riconosce la parola then
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
L’automa ha bisogno di cinque stati
rappresenta l’unico stato
finale possibile
6/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Descrizione modellistica
Il modello di un automa consiste di un dispositivo
di controllo, con un numero finito di stati, una
testina di lettura e un nastro infinito diviso in
celle.
…
Stato
…
Testina
Controllo a stati finiti
7/61
Automi e macchine di Turing
Automi
Introduzione
• Definizione
Automi
Si chiama automa a stati finiti deterministico (ASFD)
un sistema M definito come segue
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
M = (Q,A,t,q0,F)
dove
Q è un insieme finito di stati
A è un insieme finito di caratteri che costituiscono
l’alfabeto
t: QxA->Q è una funzione che associa ad ogni coppia
(stato, carattere) uno stato (detta di transizione)
Q
q0 è lo stato iniziale con q0
F è l’insieme degli stati finali, F  Q
8/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Vediamo come un ASFD accetta o meno una sequenza
di simboli in input:
sequenza di simboli in input
stato iniziale
a1 a2 … an
q0
funzione di transizione t(q0, a1) = q1
a2 ->
t(q1, a2) = q2
…
trovo così q3 q4 q5 … qn
Se qn F allora l’input a1 a2 … an viene
accettato, cioè la parola viene riconosciuta.
9/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Automi a stati finiti NON deterministici
Come un ASFD, un automa a stati finiti non
deterministico (ASFND) ha:
• un insieme finito di stati;
• un insieme finito di simboli in input
• una funzione di transizione t
In questo caso t non ritorna sempre e solo uno stato,
ma un insieme di zero, uno o più stati, cioè l’automa può
essere nello stesso tempo in stati diversi.
10/61
Automi e macchine di Turing
Automi
Introduzione
Automi
• Esempio
Un ASFND che accetta tutte e sole le stringhe di 0 e 1
che finiscono per 01.
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Sebbene abbia più alternative ad ogni passo, un
ASFND non usa nessun meccanismo probabilistico
(potrebbe portare al non riconoscimento della
parola) bensì utilizza tutte le possibili transizioni.
Se almeno una di esse lo porta in uno stato finale,
la parola è riconosciuta.
11/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
• Esempio
Rappresentazione tramite albero delle alternative
Vediamo cosa succede quando il nostro automa riceve
come input la sequenza 00101
Funzioni
calcolabili con
MdT
Problema
dell’arresto
12/61
Automi e macchine di Turing
Automi
Introduzione
• Definizione
Automi
Si chiama automa a stati finiti non deterministico
(ASFND) un sistema M definito come segue
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
M = (Q,A,t,q0,F)
dove
Q, A, q0, F sono definiti come per gli ASFD
t: QxA->2Q è una funzione che associa ad ogni coppia
(stato, carattere) uno stato appartenente all’insieme
2Q, dove 2Q è l’insieme di tutti i sottoinsiemi di Q.
Es.
t(q0, a) = {q1, q2 ,q3}
indica che la macchina nello stato q0, se legge
a può transitare in uno dei tre possibili stati
13/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Un altro modo per visualizzare il funzionamento di un
ASFND è quello di immaginare che esistano più copie
dello stesso automa.
Si inizia ad esaminare la parola in ingresso con un
automa solo. Quando sono possibili più di una
transizione si creano tanti automi quante sono le
alternative.
Ad ogni passo esiste un insieme di automi tutti in stati
diversi.
Se non è possibile una transizione l’automa viene
soppresso.
La parola sarà riconosciuta se alla fine almeno una
14/61
delle macchine è in uno stato finale.
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Equivalenza tra ASFD e ASFND
Teorema
Per ogni ASFND, N, ne esiste uno
equivalente deterministico, D, cioè tale
che L(N) = L(D)
Dato N = (QN, A, tN, q0, FN) definiamo D come segue:
1.
Gli stati QD rappresentano tutti i possibili
sottoinsiemi di QN (se QN ha n stati QD ne avrà 2n)
[ q0, q1 , … , qk] = stato corrispondente all’insieme
{ q0, q1 , … , qk}
2. Gli stati finali FD sono tutti i sottoinsiemi S di QN
tali che SFN  
15/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
3. Lo stato iniziale è quello che corrisponde all’insieme
{q0} con q0 stato iniziale di N
4. La funzione di transizione è data da:
tD([q0, … , qi], a) = [tN(q0, a)  tN(q1, a)  …  tN(qi, a)
con a generico simbolo dell’alfabeto A
5. L’alfabeto di D è identico a quello di N
Resta così definito D = (QD, A, tD, q0, FD)
16/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Automi a stati finiti e grammatiche regolari
Abbiamo appena visto come ASFD e ASFND
accettano la stessa classe di linguaggi. Vogliamo
mostrare che questa classe coincide con le
espressioni regolari, cioè che:
1.
ogni linguaggio definito da uno dei tipi di
automi è anche definito da una espressione
regolare.
2. ogni linguaggio definito da un’espressione
regolare è definito da uno di questi automi.
17/61
Automi e macchine di Turing
Automi
Introduzione
• Automi a stati finiti e grammatiche regolari
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
2.
1.
 - NFA = automa a stati finiti non
deterministico con transizione su
cioè sulla stringa vuota.
,
18/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Automi a stati finiti e grammatiche regolari
Teorema
Dato un automa a stati finiti M, esiste una
grammatica regolare G t.c. L(G) = L(M)
Assegnato un ASFD M = (Q,A,t,q0,F) si costruisce la
grammatica regolare con la seguente procedura:
1.
l’insieme dei simboli terminali VT coincide con A;
2. l’insieme dei simboli non terminali VN coincide o è in
corrispondenza biunivoca con Q;
3. il simbolo iniziale S di G è il simbolo non terminale
che corrisponde a q0;
19/61
Automi e macchine di Turing
Automi
Introduzione
• Automi a stati finiti e grammatiche regolari
Automi
4. L’insieme delle produzioni P è dato da:
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
ad ogni transizione dallo stato qi allo stato qj per
effetto del carattere ah si associa una produzione
Ni-> ah Nj, con Ni e Nj simboli non terminali
corrispondenti a qi e qj
Se qj

F si aggiunge la produzione Ni-> ah
Allo stesso modo si dimostra che …
20/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
• Automi a stati finiti e grammatiche regolari
Teorema
Ogni linguaggio definito da un’espressione
regolare è anche definito da un automa a
stati finito (non deterministico con
transizione  ).
Funzioni
calcolabili con
MdT
Problema
dell’arresto
21/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Esempio
Supponiamo di avere il linguaggio
L = { anbn con n>1}
Vogliamo vedere se questo è riconoscibile da un
automa a stati finiti.
Gli automi a stati finiti posseggono una memoria
finita e quindi non sono in grado di riconoscere
linguaggi che, per la loro struttura, richiedono di
ricordare una quantità di “informazioni” non
limitate.
22/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
• Automi a pila
Un automa a pila è costituito da:
• un controllo a stati finiti
• un nastro di ingresso
• una memoria ausiliaria a pila di lunghezza infinita
a
b
c
a
a
nastro di ingresso
b
Problema
dell’arresto
controllo
finito
p1
p2
…
memoria a
pila
23/61
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
• Automi a pila
In ogni situazione l’automa a pila può compiere due
tipi di mosse:
Funzioni
calcolabili con
MdT
leggere il contenuto di una cella del nastro ed il
simbolo in cima alla pila, passare in un nuovo stato
e sostituire il simbolo letto dalla pila con una
stringa (la testina avanza);
Problema
dell’arresto
come prima, ma senza leggere alcun simbolo dal
nastro e senza avanzamento della testina;
Questa seconda mossa permette all’automa di
manipolare il contenuto della pila.
24/61
Automi e macchine di Turing
Automi
Introduzione
• Definizione
Automi
Un automa a pila M è un sistema (Q,A,R,t,q0,Z0,F)
dove
Macchine di
Turing
Q è un insieme finito di stati
Funzioni
calcolabili con
MdT
R è un alfabeto finito, detto alfabeto della pila
Problema
dell’arresto
A è un alfabeto finito, detto alfabeto del nastro
 Q è lo stato iniziale
Z0R è il simbolo iniziale, cioè l’unico simbolo che
q0
appare all’inizio della pila
F  Q è l’insieme degli stati finali
t: Q x A x R -> Q x R è la funzione di transizione
Automi e macchine di Turing
Automi
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Esempio
Supponiamo di avere il linguaggio
L = { 0n1n2n con n>1}
Vogliamo vedere se questo è riconoscibile da un
automa a pila.
Così come abbiamo visto nel caso degli automi a
stati finiti, anche in questo caso la “memoria” del
nostro automa non basta a riconoscere questo
linguaggio.
Dobbiamo potenziare ancora il nostro automa.
26/61
Automi e macchine di Turing
Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
• Descrizione modellistica della Macchina di Turing
Una MdT può essere vista come un organo di
controllo a a stati finiti con associato un nastro di
lunghezza infinita nel quale vengono immagazzinate
le sequenze di simboli su cui si opera.
programma
CONTROLLO
comandi della testina
e del nastro
Problema
dell’arresto
…
A
0
1
3
…
27/61
Automi e macchine di Turing
Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
• Descrizione modellistica della Macchina di Turing
Il comportamento della MdT può essere descritto
mediante una tabella detta matrice funzionale in
cui le righe rappresentano gli stati del controllo e
le colonne rappresentano i simboli in ingresso.
Es. la macchina si trova nello stato qi e legge il
simbolo sj
sj
Problema
dell’arresto
qi
scrive un altro simbolo sk
si porta nello stato qr
skqrxt
si sposta sul nastro di una
casella a sx o a dx a
seconda che sia xt=D o xt=S
Automi e macchine di Turing
Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Descrizione modellistica della Macchina di Turing
La specifica delle condizioni, ad ogni passo, della
configurazione del nastro, della posizione della
testina e dello stato del controllo, prende il nome
di descrizione istantanea (DI).
Per computazione di una MdT intendiamo la
sequenza finita di DI, di cui la prima è iniziale e
l’ultima è finale, e ognuna è ottenuta dalla
precedente in un passo.
29/61
Automi e macchine di Turing
Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Descrizione matematica della Macchina di Turing
S = {s0, … , sn} alfabeto finito di simboli
Q = {q1, … , qm} alfabeto finito di stati
M = {D, S} insieme dei simboli degli spostamenti
s0 rappresenta la casella bianca sul nastro
La configurazione di una MdT ad ogni istante può
essere rappresentata come una stringa infinita di
simboli
… s0 s0 s0 si1 si2 si3 … sik-1 qr sik sik+1 … sif s0 s0 s0 …
di cui solo un numero finito è diverso da s0
30/61
Automi e macchine di Turing
Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Descrizione matematica della Macchina di Turing
Questa stringa infinita si può rappresentare
schematicamente con
qs
dove qQ, sS,
 , S*
dove S* rappresenta l’insieme di tutte le sequenze
finite di simboli di S.
Quindi una stringa del tipo
della MdT.
qs
sarà una DI
Il modo di funzionare della macchina è descritto da
quintuple del tipo qisjsijqijxij con si,sj  S
xijM
qi,qij Q
Automi e macchine di Turing
Macchine di Turing
Introduzione
• Definizione
Automi
Una macchina di Turing Z è una terna (Q, S, P) dove
Macchine di
Turing
Q è un insieme finito di stati
Funzioni
calcolabili con
MdT
Problema
dell’arresto
S è un insieme finito di simboli (con s0 bianco)
P è un sottoinsieme di Q x S x S x Q x {S, D}, cioè
l’insieme delle quintuple di Z, con la proprietà che
non ci sono due quintuple con i primi due membri
uguali
32/61
Automi e macchine di Turing
Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Definizione
Introduciamo ora la relazione |- tra descrizioni
istantanee DI.
Diremo che due DI sono in relazione |- tra loro se
la seconda DI rappresenta la configurazione
ottenuta in un passo da quella rappresentata dalla
prima DI.
Definizione
Sia Z = (Q, S, P) una MdT. La
relazione |- è definita come segue:
qs | s' q'
 sqs | q' ss'
P
se qss’q’S  P
se qss’q’D
33/61
Automi e macchine di Turing
Macchine di Turing
Introduzione
Automi
• Definizione
Una computazione della MdT Z è una sequenza finita
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
z0, z1, z2, … , zm
di descrizioni istantanee DI di Z tali che
zm è una DI terminale, cioè se zm=
qs
allora
nessuna quintupla in P inizia con qs, ed inoltre zj|- zj+1
per 0  j  m .
34/61
Automi e macchine di Turing
Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Esempio
Calcolo del successivo di un numero
Costruire la MdT che, dato un numero scritto in base
10, ne calcola il successivo.
La matrice funzionale è:
q0
0
1
2
3
4
5
6
7
8
9
b
1q1D
2q1D
3q1D
4q1D
5q1D
6q1D
7q1D
8q1D
9q1D
0q0S
1q1D
q1
q0 1 deve ancora essere sommato
q1 1 è già stato sommato
35/61
Automi e macchine di Turing
Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Macchine di Turing generalizzate
Teorema di equivalenza tra MdT ordinarie e
generalizzate
Data una MdT Z con n nastri, il j-esimo dei quali è di
dimensione kj ed è esaminato da hj testine, questa
può essere simulata da una MdT Z’ con nastro
monodimensionale esaminato da una sola testina.
36/61
Automi e macchine di Turing
Macchine di Turing
Introduzione
• Macchine di Turing generalizzate
Automi
Teorema (Shannon, 1956)
Macchine di
Turing
Una qualsiasi Mdt con n simboli ed m stati può essere
simulata da una MdT a due stati, aumentando
opportunamente il numero di simboli del suo alfabeto.
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Teorema (Shannon, 1956)
Una qualsiasi Mdt può essere simulata da una MdT
con un alfabeto di due simboli, aumentando
opportunamente il numero dei suoi stati.
37/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
Automi
• Nonesistenza di algoritmi per tutte le funzioni
Sia S un linguaggio in cui descrivere i nostri
algoritmi.
Macchine di
Turing
Un algoritmo che termini sempre definisce una
funzione fA.
Funzioni
calcolabili con
MdT
Se i dati iniziali e i risultati finali si considerano la
codifica dei numeri naturali, ad ogni algoritmo A
che termina viene associata una funzione
Problema
dell’arresto
fA: N -> N
funzione calcolata dall’algoritmo
Nel caso la funzione non sia definita per alcuni
valori verrà detta parziale.
38/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Nonesistenza di algoritmi per tutte le funzioni
Si noti che mentre ad ogni algoritmo A di S è
associata una sola funzione fA, la stessa funzione f
può essere associata a più di un algoritmo f=fA’=fA’’.
Sia AS l’insieme di tutti i possibili algoritmi in S.
L’insieme
FS={fA|A
AS}
è l’insieme delle funzioni calcolabili in S e la sua
ampiezza è la più chiara misura della potenza del
linguaggio S.
Ci chiediamo se esiste un formalismo S t.c. il suo
insieme FS comprenda tutte le funzioni.
39/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Nonesistenza di algoritmi per tutte le funzioni
Sia S un insieme finito di N elementi, allora la sua
cardinalità sarà uguale a N (#S=N)
Un sottoinsieme di S è perfettamente individuato
da un numero binario di N cifre: la i-esima cifra
dice se nel sottoinsieme è presente o no l’i-esimo
elemento si di S.
Es. Se S={s1, s2, s3} allora il numero binario 011
indica il sottoinsieme {s2, s3} .
Il numero dei possibili sottoinsiemi di S è pari al
numero di numeri binari di N cifre, cioè 2N.
40/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
• Nonesistenza di algoritmi per tutte le funzioni
Automi
Quindi la cardinalità dell’insieme dei sottoinsiemi di
S (2S) sarà 2N.
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Ragionando in modo analogo si vede come un
sottoinsieme dell’insieme N sia individuato da un
numero binario di infinite cifre.
Es.
1010101…
corrisponde biunivocamente
al sottoinsieme dei numeri pari
Quindi se esistesse una corrispondenza biunivoca tra
i numeri naturali e sottoinsiemi di numeri naturali,
allora esisterebbe anche una corrisp. biunivoca tra
naturali e numeri binari di infinite cifre
41/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
• Nonesistenza di algoritmi per tutte le funzioni
Automi
Ragioniamo per assurdo e ammettiamo che tale
corrispondenza esista.
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Sia Bi= bio, bi1, … il numero binario corrispondente
al naturale i e sia bij la sua j-esima cifra.
0
1
…
j
…
0
b00
b01
…
b0j
…
1
b10
b11
…
b1j
…
…
…
…
…
…
…
i
bi0
bi1
…
bij
…
…
…
…
…
…
…
42/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
• Nonesistenza di algoritmi per tutte le funzioni
Automi
Consideriamo il numero B = b00, b11, … , bii, … ottenuto
prendendo gli elementi sulla diagonale.
Macchine di
Turing
Calcoliamo il suo complementare B’.
Funzioni
calcolabili con
MdT
B’ non è contenuto nella tabella perché se così fosse
apparirebbe in una certa riga, ad esempio la k-esima
e risulterebbe B’=Bk ASSURDO
Problema
dell’arresto
perché la k-esima cifra di B’ starebbe sulla diagonale
e quindi sarebbe bkk anziché il suo complementare.
Questo ci dice che la corrispondenza cercata nn
esiste e che quindi
#N < #2N
43/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
• Nonesistenza di algoritmi per tutte le funzioni
Automi
Se Fb = {f|f: N ->{0, 1} }
Macchine di
Turing
abbiamo che #2N = Fb
Funzioni
calcolabili con
MdT
Problema
dell’arresto
insieme delle funzioni
binarie definite su N
Infine ponendo F = {f|f: N -> N} , poiché Fb F si
ottiene
#Fb <= #F
Quindi
#N < #2N = #Fb <= #F
da cui
#N < #F
cioè le funzioni dai naturali ai naturali non sono
numerabili.
44/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
• Nonesistenza di algoritmi per tutte le funzioni
Automi
Torniamo al nostro generico linguaggio S.
Macchine di
Turing
Supponiamo di aver ordinato tutti i simboli di S
(finiti) in un modo qualsiasi.
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Supponiamo poi di considerare tutti gli algoritmi
scritti in S (infiniti) e di ordinarli in base al numero
di simboli da cui sono composti, poi seguendo le
precedenze tra simboli.
Appena fatto l’ordinamento abbiamo ottenuto anche
una corrispondenza biunivoca tra gli algoritmi di S e
alcuni (o tutti) i numeri naturali.
45/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
• Nonesistenza di algoritmi per tutte le funzioni
Automi
Quindi, ricordando che AS denota l’insieme degli
algoritmi di S, abbiamo
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
#AS <= #N, ma abbiamo appena dimostrato che
#N < # F, pertanto #AS < #F.
Dalla definizione di FS abbiamo #FS <= #AS (poiché
FS può essere messo in corrispondenza biunivoca con
il sottoinsieme di AS ottenuto togliendo da AS tutti
gli algoritmi che calcolano la stessa funzione, tranne
quello di indice minimo).
46/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
• Nonesistenza di algoritmi per tutte le funzioni
Automi
Ricapitolando, abbiamo che
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
#FS <= #AS < # F
da cui
#FS < # F e,
essendo FS  F,
abbiamo finalmente
FS  F
che era quanto volevamo dimostrare, cioè che
l’insieme delle funzioni calcolabili in S è solo un
sottoinsieme dell’insieme di tutte le funzioni dai
naturali ai naturali.
47/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Vogliamo ora associare alla generica macchina di
Turing Z una funzione dai naturali ai naturali, così
come abbiamo fatto per il generico algoritmo A.
Bisogna definire innanzitutto una codifica dei
numeri naturali in termini delle DI iniziali delle MdT
ci: N -> DI
Anche se non tutte le DI iniziali sono codifica di
qualche naturale, ciò non importa. Invece, ad ogni
naturale deve corrispondere una diversa DI iniziale.
48/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Bisogna poi definire una seconda (de)codifica tra le
DI finali e i naturali
cf: Df -> N
In questo caso ogni naturale deve essere la decodifica
di qualche DI finale, ma non necessariamente una sola.
Infine, ricordando che una MdT Z definisce una
funzione parziale
gz : DI -> DF
allora la composizione delle tre funzioni ci, gz e cf
definisce una funzione parziale fz : N -> N che è detta
funzione calcolata dalla MdT Z.
49/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Come codifica ci scegliamo:
ad ogni numero naturale corrisponde una DI
iniziale in cui tutto il nastro è bianco, eccetto
una sequenza di n simboli s1 consecutivi, lo
stato interno è q0 e la testina è posizionata col
simbolo s1 più a sinistra.
Es. Al numero 3 corrisponde la DI iniziale
… s0s0 q0 s1 s1 s1 s0 s0s0 …
50/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Come codifica cf scegliamo:
il numero di s1 consecutivi alla destra della
testina, compreso il simbolo puntato dalla
testina stessa
Es. … s0s0 s1 s1s0 s1qi s1 s1 s0 s1 s0 s0
… s0s0 s1qi s0 s1 s0 s0 …
corrisponde a 2
vale 0
Con queste convenzioni resta univocamente individuata
la funzione
i  x  cioè la funzione calcolata dall’i-
esima macchina di Turing.
51/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
Consideriamo ora l’insieme di funzioni
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
FT = {
 i | i = 1, 2, …}
Ci chiediamo:
• quanto è ampia la classe FT ?
• esiste una funzione f(x) non in FT ma calcolabile in
altri formalismi?
A queste domande risponde la Tesi di Church o Tesi di
Turing.
52/61
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Tesi di Church
La tesi di Church ci permette:
a)
di fare riferimento all’insieme delle funzioni
calcolabili FC senza specificare “con macchine di
Turing”;
b) di assumere l’esistenza di una MdT equivalente
per ogni algoritmo che sia intuitivamente tale.
Esamina in dettaglio ogni ragionevole passo elementare
di ogni ragionevole definizione di algoritmo e fa vedere
come tale passo possa essere realizzato con una MdT.
Sono solo intuitive, non costituiscono dimostrazione.
Automi e macchine di Turing
Funzioni calcolabili con Macchine di Turing
Introduzione
Automi
• Esistenza della macchina di Turing Universale
Un esempio molto importante di applicazione della tesi
di Church è costituito dalla MdT universale.
Macchine di
Turing
Essa accetta come dati:
Funzioni
calcolabili con
MdT
b) il dato iniziale x.
Problema
dell’arresto
a) la descrizione di una certa MdT Zy;
Una MdT universale è quindi una particolare MdT
capace di simulare, o di interpretare, ogni altra MdT.
Essa è la formalizzazione più corretta di un ordinario
calcolatore, infatti introduce la possibilità di avere il
programma memorizzato.
54/61
Automi e macchine di Turing
Problema dell’arresto
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
L’aver dimostrato l’esistenza della MdT universale, ci
mette di fronte ad un altro problema:
Esiste una MdT in gradi di decidere, per una qualsiasi
coppia (M,d) costituita da una MdT M e da una
stringa di dati d, se quando si fornisce d a M, questa
si evolve fino ad arrestarsi (o meno)?
Turing ha dimostrato che la MdT universale non è in
grado di decidere in ogni caso il problema
dell’arresto, quindi nessuna MdT può farlo.
55/61
Automi e macchine di Turing
Problema dell’arresto
Introduzione
• Esempio
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
Proviamo a modificare questo semplice programma.
56/61
Automi e macchine di Turing
Problema dell’arresto
Introduzione
• Esempio
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
57/61
Automi e macchine di Turing
Problema dell’arresto
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
L’ultimo teorema di Fermat afferma che non esistono
quattro interi x, y, z e n con n>2 tali che
xn + yn = zn
Supponiamo di prendere ora il nostro programma P.
Vogliamo trovare un programma che, preso in input il
programma P e l’input I, dica se P (con l’input I)
scrive “hello, world”.
Problema
dell’arresto
58/61
Automi e macchine di Turing
Problema dell’arresto
Introduzione
Macchine di
Turing
Se un problema ha un algoritmo come H, che dice
sempre correttamente se un’istanza del problema ha
risposta “si” o “no” allora il problema si dice
decidibile, altrimenti si dice indecidibile.
Funzioni
calcolabili con
MdT
Si prova che tale H non esiste per il nostro problema
e cioè che il problema “hello, world” è indecidibile.
Problema
dell’arresto
Questo risultato negativo costruisce un limite per
tutti i meccanismi computazionali.
Automi
59/61
Automi e macchine di Turing
Problema dell’arresto
Introduzione
Automi
Macchine di
Turing
Funzioni
calcolabili con
MdT
Problema
dell’arresto
• Teorema di incompletezza di Gödel (primo)
L’indecidibilità del problema dell’arresto si dimostra
equivalente al teorema di incompletezza di Gödel:
“In ogni teoria matematica T sufficientemente
espressiva da contenere l’aritmetica, esiste una
formula  tale che, se T è coerente, allora né  né

la sua negazione  sono dimostrabili in T”
Questo teorema dimostra che qualsiasi sistema che
permette di definire i numeri naturali è
necessariamente incompleto: esso contiene
affermazioni di cui non si può dimostrare né la verità
né la falsità.
60/61
Automi e macchine di Turing
Fonti principali:
•AIELLO, ALBANO, ATTARDI, MONTANARI
“Teoria della computabilità, logica, teoria dei
linguaggi formali”
•HOPCROFT, MOTWANI, ULLMAN
“Introduction to Automata Theory, Languages,
and Computation”
•http://it.wikipedia.org
•http://www.turing.org.uk
61/61