Università degli studi di Lecce Automi e macchine di Turing Automi e macchine di Turing Corso...
-
Upload
fredo-corradi -
Category
Documents
-
view
216 -
download
0
Transcript of Università degli studi di Lecce Automi e macchine di Turing Automi e macchine di Turing Corso...
Università degli studi di Lecce
Automi e
macchine di Turing
Automi e
macchine di Turing
Corso Seminariale a.a. 2005 - 2006
Macchia Sara
Corso di laurea in Matematica e Informatica
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
2/61
Automi e macchine di TuringIntroduzione
• 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.
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi e macchine di Turing
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.
Introduzione
3/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• Cos’è un automa?
Un automa è un dispositivo, o un sistema in forma di macchina sequenziale, che, ad ogni istante, può trovarsi in un determinato “stato”. Lo scopo dello stato è quello di ricordare la parte rilavante della storia del sistema.
Finché ci sono solo un numero finito di stati, l’intera storia del sistema non può essere ricordata.
4/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• Esempio 1
rappresenta gli stati
rappresenta l’input
indica lo stato iniziale
Un automa finito che rappresenta un interruttore on/off
5/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• Esempio 2
Un automa finito che riconosce la parola then
L’automa ha bisogno di cinque stati
rappresenta l’unico stato finale possibile
6/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• Definizione
Si chiama automa a stati finiti deterministico (ASFD) un sistema M definito come segue
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)
q0 è lo stato iniziale con q0 Q
F è l’insieme degli stati finali, F Q
8/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
AutomiVediamo come un ASFD accetta o meno una sequenza di simboli in input:
sequenza di simboli in input a1 a2 … an
stato iniziale 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• Automi a stati finiti NON deterministiciCome 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• Esempio
Un ASFND che accetta tutte e sole le stringhe di 0 e 1 che finiscono per 01.
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• Esempio
Rappresentazione tramite albero delle alternative
Vediamo cosa succede quando il nostro automa riceve come input la sequenza 00101
12/61
• DefinizioneIntroduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi e macchine di TuringAutomi
Si chiama automa a stati finiti non deterministico (ASFND) un sistema M definito come segue
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi e macchine di TuringAutomi
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 delle macchine è in uno stato finale. 14/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• 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 SFN
15/61
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi e macchine di TuringAutomi
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 a stati finiti e grammatiche regolari
Automi
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• Automi a stati finiti e grammatiche regolari
2.
1.
- NFA = automa a stati finiti non deterministico con transizione su , cioè sulla stringa vuota.
18/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi e macchine di TuringAutomi
• Automi a stati finiti e grammatiche regolari
4. L’insieme delle produzioni P è dato da:
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• 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 ).
21/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• 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 b nastro di ingresso
controllo finito
p1 p2 … memoria a pila
23/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• Automi a pila
In ogni situazione l’automa a pila può compiere due tipi di mosse:
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);
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• Definizione
Un automa a pila M è un sistema (Q,A,R,t,q0,Z0,F) dove
Q è un insieme finito di stati
A è un alfabeto finito, detto alfabeto del nastro
R è un alfabeto finito, detto alfabeto della pila
q0 Q è lo stato iniziale
Z0 R è il simbolo iniziale, cioè l’unico simbolo che 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi• 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi e macchine di TuringMacchine di Turing
• Descrizione modellistica della Macchina di TuringUna 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
comandi della testina e del nastro
CONTROLLO
… …A 0 1 327/61
Automi e macchine di TuringMacchine di Turing
• Descrizione modellistica della Macchina di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
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
skqr
xt
sj
qi
scrive un altro simbolo sk
si porta nello stato qr
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Macchine di Turing• 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Macchine di Turing• 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 TuringMacchine di Turing
• Descrizione matematica della Macchina di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Questa stringa infinita si può rappresentare schematicamente con
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 sarà una DI della MdT.
Il modo di funzionare della macchina è descritto da quintuple del tipo qisjsijqijxij con
si,sj S
qs ,
qs
qi,qij Q xij M
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Macchine di Turing• Definizione
Una macchina di Turing Z è una terna (Q, S, P)
dove
Q è un insieme finito di stati
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 uguali32/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Macchine di Turing• 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: ''| qsqs
''| ssqqss se qss’q’D P
se qss’q’S P
33/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Macchine di Turing• Definizione
Una computazione della MdT Z è una sequenza
finita
z0, z1, z2, … , zm
di descrizioni istantanee DI di Z tali che
zm è una DI terminale, cioè se zm=
allora nessuna quintupla in P inizia con qs, ed
inoltre zj|- zj+1 per .
qs
mj 0
34/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Macchine di Turing• Esempio
Calcolo del successivo di un numeroCostruire la MdT che, dato un numero scritto in base 10, ne calcola il successivo.
La matrice funzionale è:
0 1 2 3 4 5 6 7 8 9 b
q01q1
D2q1D
3q1
D4q1
D5q1
D6q1
D7q1
D8q1
D9q1
D0q0S
1q1
D
q1
q0 1 deve ancora essere sommato
q1 1 è già stato sommato 35/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Macchine di Turing• 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Macchine di Turing• Macchine di Turing generalizzate
Teorema (Shannon, 1956)
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.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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Nonesistenza di algoritmi per tutte le funzioniSia S un linguaggio in cui descrivere i nostri algoritmi.
Un algoritmo che termini sempre definisce una funzione fA.
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
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Nonesistenza di algoritmi per tutte le funzioniSi 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Nonesistenza di algoritmi per tutte le funzioniSia 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Nonesistenza di algoritmi per tutte le funzioniQuindi la cardinalità dell’insieme dei sottoinsiemi di S (2S) sarà 2N.
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Nonesistenza di algoritmi per tutte le funzioniRagioniamo per assurdo e ammettiamo che tale corrispondenza esista.
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Nonesistenza di algoritmi per tutte le funzioniConsideriamo il numero B = b00, b11, … , bii, …
ottenuto prendendo gli elementi sulla diagonale.
Calcoliamo il suo complementare B’.
B’ non è contenuto nella tabella perché se così fosse apparirebbe in una certa riga, ad esempio la k-esima e risulterebbe B’=Bk ASSURDO
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Nonesistenza di algoritmi per tutte le funzioniSe Fb = {f|f: N ->{0, 1} } insieme delle
funzioni binarie definite su N
abbiamo che #2N = Fb
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Nonesistenza di algoritmi per tutte le funzioniTorniamo al nostro generico linguaggio S.
Supponiamo di aver ordinato tutti i simboli di S (finiti) in un modo qualsiasi.
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Nonesistenza di algoritmi per tutte le funzioniQuindi, ricordando che AS denota l’insieme degli
algoritmi di S, abbiamo
#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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Nonesistenza di algoritmi per tutte le funzioniRicapitolando, abbiamo che
#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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di TuringVogliamo 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing
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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di TuringCome 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 corrisponde a 2
… s0s0 s1qi s0 s1 s0 s0 … vale 0
Con queste convenzioni resta univocamente
individuata la funzione cioè la funzione
calcolata dall’i-esima macchina di Turing.
xi
51/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing
Consideriamo ora l’insieme di funzioni
FT = { | 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.
i
52/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Tesi di ChurchLa 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Funzioni calcolabili con Macchine di Turing• Esistenza della macchina di Turing Universale
Essa accetta come dati:
a) la descrizione di una certa MdT Zy;
b) il dato iniziale x.
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.
Un esempio molto importante di applicazione della tesi di Church è costituito dalla MdT universale.
54/61
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi e macchine di TuringProblema 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
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi e macchine di TuringProblema dell’arresto
• Esempio
Proviamo a modificare questo semplice programma.
56/61
Automi e macchine di Turing
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Problema dell’arresto• Esempio
57/61
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi e macchine di TuringProblema dell’arresto
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”.
58/61
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi e macchine di TuringProblema dell’arresto
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.
Si prova che tale H non esiste per il nostro problema e cioè che il problema “hello, world” è indecidibile.
Questo risultato negativo costruisce un limite per tutti i meccanismi computazionali.
59/61
Introduzione
Automi
Macchine di Turing
Funzioni calcolabili con MdT
Problema dell’arresto
Automi e macchine di TuringProblema 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 TuringFonti 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