Altri modelli di TM

Altri modelli di TM
Estensioni:
1
pi`
u nastri
2
non-determinismo
Restrizioni:
1
nastro illimitato solo in una direzione e divieto di sostituire un
simbolo del nastro con B
2
due pile al posto del nastro
3
due contatori (mossa: cambio stato e +1 o
contatore)
1 da un
Tutti i modelli sono equivalenti: accettano i linguaggi
ricorsivamente enumerabili (tesi di Church, 1936).
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
16 of 27
TM e computer
1
Da TM a computer: basta avere sempre memoria da
aggiungere, per simulare il nastro infinito
2
Da computer a TM: vari nastri (memoria, istruzione, indirizzo
di memoria, file di input, nastro ausiliario), controllo finito per
eseguire una istruzione dopo l’altra leggendo e scrivendo i
nastri
3
Di↵erenza di tempo tra computer e TM: polinomiale. La TM
pu`
o simulare n passi di un computer in O(n3 ) passi.
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
17 of 27
Linguaggi ricorsivamente enumerabili
D’ora in poi: calcolatore = macchina di Turing
L `e ricorsivamente enumerabile se L = L(M) per una TM M.
M si ferma se accetta una stringa, ma potrebbe non fermarsi
se non la accetta
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
18 of 27
Un linguaggio ricorsivamente enumerabili
Consideriamo il linguaggio formato dalle coppie (M, w ) tali
che:
M `e una TM (codificata in binario) con alfabeto {0, 1}
w `e una stringa di 0 e 1
M accetta w
Se questo problema `e indecidibile, allora lo `e anche il
problema in cui una TM pu`
o avere qualunque alfabeto
Primo passo: codificare una TM come una stringa di 0 e 1
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
19 of 27
Enumerazione stringhe binarie
Possiamo associare ad ogni stringa binaria w un indice intero
dato dalla rappresentazione binaria di 1w , cos`ı enumeriamo le
stringhe:
w
1w intero commento
✏
1✏
1
`e la prima stringa
0
10
2
`e la seconda stringa
1
11
3
`e la terza stringa
00 100
4
`e la quarta stringa
01 101
5
`e la quinta stringa
··· ···
···
···
Ordinamento per lunghezza, con stringhe lunghe uguali
ordinate lessicograficamente
Simbolo wi per la stringa i-esima
Vogliamo fare la stessa cosa anche per le TM
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
20 of 27
Codice per una TM
Per rappresentare
M = (Q, ⌃, , , q0 , B, F ),
come una stringa binaria, dobbiamo assegnare interi agli stati, ai
simboli di nastro, e alle direzioni L e R:
Supponiamo che gli stati siano q1 , q2 , . . . , qr , con stato
iniziale q1 e stato finale q2
Supponiamo che i simboli di nastro siano X1 , X2 , . . . , Xs
Fissiamo: 0 = X1 , 1 = X2 , B = X3
Inoltre, poniamo L = D1 e R = D2
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
21 of 27
Codice per una TM
Funzione di transizione: se (qi , Xj ) = (qk , Xl , Dm ), la
codifica `e 0i 10j 10k 10l 10m (mai due 1 consecutivi)
Per un’intera TM: codici per tutte le transizioni, separati da
11: C1 11C2 11...Cn 1 11Cn
Esempio: M = ({q1 , q2 , q3 }, {0, 1}, {0, 1, B}, , q1 , B, {q2 }),
dove
`e definita da:
transizione
(q1 , 1) = (q3 , 0, R)
(q3 , 0) = (q1 , 1, R)
(q3 , 1) = (q2 , 0, R)
(q3 , B) = (q3 , 1, L)
codice
0100100010100
0001010100100
00010010010100
0001000100010010
Codice per M:
01001000101001100010101001001100010010010100110001000100010010
Codici equivalenti si ottengono cambiando l’ordine delle transizioni
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
22 of 27
Codici e TM
Sia wi (i-esima stringa) la codifica di una data TM M:
M `e la i-esima TM, denotata con Mi
Molti interi non corrispondono a nessuna TM. Esempio:
11001 o 001110
Se wi non `e un codice valido, allora diciamo che Mi `e la TM
che si arresta subito per qualunque input (un solo stato e
nessuna transizione). Quindi L(Mi ) = ;
A noi interessa codificare (M, w ), cio`e M con input w :
codice di M seguito da 111 seguito da w
Esempio: la TM del lucido precedente con input 1011
010010001010011000101010010011000100100101001100010001000100101111011
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
23 of 27
Il linguaggio di diagonalizzazione
Il linguaggio di diagonalizzazione Ld `e l’insieme delle
stringhe wi tali che wi 62 L(Mi )
Tutte le stringhe w tali che M con codice w non accetta w
Matrice con TM sulle righe e stringhe sulle colonne
la diagonale corrisponde a stringhe wi e TM Mi
le stringhe di Ld corrispondono agli 0 della diagonale
` possibile che la diagonale complementata sia una riga? No,
E
perch`e la diagonale complementata `e in disaccordo con ogni
riga in almeno una posizione
) Ld non pu`
o essere accettato da nessuna TM
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
24 of 27
Linguaggi ricorsivi
L `e ricorsivo se L = L(M) per una TM M tale che:
se w 2 L, allora M la accetta (e si arresta)
se w 2
6 L, allora M non la accetta ma si arresta
Problema (dell’accettazione di L): `e decidibile se L `e ricorsivo,
altrimenti `e indecidibile
Classi di linguaggi
ricorsivi = decidibili = M si arresta sempre
ricorsivamente enumerabili = M si arresta se accetta
non ricorsivamente enumerabili. Esempio: Ld
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
25 of 27
Propriet`a dei linguaggi ricorsivi
Theorem
¯ `e ricorsivo
Se L `e ricorsivo, anche L
Proof.
Se L `e ricorsivo, esiste M che si arresta sempre. Modifichiamo M
in M 0 in modo che M 0 accetti quando M non accetta, e viceversa.
¯ Allora L
¯ `e ricorsivo.
Anche M 0 si arresta sempre e accetta L.
¯ non `e
Conseguenza: se L `e ricorsivamente enumerabile, ma L
ricorsivamente enumerabile, allora L non pu`
o essere ricorsivo.
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
26 of 27
Propriet`a dei linguaggi ricorsivamente enumerabili
Theorem
¯ sono ricorsivamente enumerabili, allora L `e ricorsivo
Se L e L
Proof.
¯ = L(M2 ). Costruiamo M che esegue in parallelo
Sia L = L(M1 ) e L
(due nastri, due testine) M1 e M2 . Se l’input `e in L, M1 lo accetta
e si ferma, quindi anche M accetta e si ferma. Se l’input non `e in
L, allora M2 lo accetta e si ferma, quindi M lo rifiuta ma si ferma.
Quindi M si ferma in ogni caso.
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
27 of 27
L e L¯
¯?
Dove possono stare L e L
¯ ricorsivi
sia L che L
¯ ricorsivamente enumerabili
n´e L n´e L
¯ non `e ricorsivamente
L `e ricorsivamente enumerabile, e L
enumerabile
¯ `e ricorsivamente enumerabile ma non ricorsivo, e L non `e
L
ricorsivamente enumerabile
Non `e possibile che un linguaggio sia ricorsivo e l’altro sia
ricorsivamente enumerabile o neanche ricorsivamente enumerabile
(primo teorema). Non `e possibile che siano entrambi
ricorsivamente enumerabili ma non ricorsivi (secondo teorema).
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
28 of 27

Download Report