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 1 da un
contatore)
Tutti i modelli sono equivalenti: accettano i linguaggi ricorsivamente enumerabili (tesi di Church, 1936).
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
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
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
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
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
Codice per una TM
Funzione di transizione: se (qi, Xj) = (qk, Xl, Dm), la
codifica `e 0i10j10k10l10m (mai due 1 consecutivi)
Per un’intera TM: codici per tutte le transizioni, separati da 11: C111C211...Cn 111Cn Esempio: M = ({q1, q2, q3}, {0, 1}, {0, 1, B}, , q1, B,{q2}), dove `e definita da: transizione codice (q1, 1) = (q3, 0, R) 0100100010100 (q3, 0) = (q1, 1, R) 0001010100100 (q3, 1) = (q2, 0, R) 00010010010100 (q3, B) = (q3, 1, L) 0001000100010010 Codice per M: 01001000101001100010101001001100010010010100110001000100010010 Codici equivalenti si ottengono cambiando l’ordine delle transizioni
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 input1011
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
`
E possibile che la diagonale complementata sia una riga? No, perch`e la diagonale complementata `e in disaccordo con ogni riga in almeno una posizione
Linguaggi ricorsivi
L `e ricorsivo se L = L(M) per una TM M tale che:
se w2 L, allora M la accetta (e si arresta) se w62 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
Propriet`a dei linguaggi ricorsivi
Theorem
Se L `e ricorsivo, anche ¯L `e ricorsivo
Proof.
Se L `e ricorsivo, esiste M che si arresta sempre. Modifichiamo M in M0 in modo che M0 accetti quando M non accetta, e viceversa. Anche M0 si arresta sempre e accetta ¯L. Allora ¯L `e ricorsivo.
Conseguenza: se L `e ricorsivamente enumerabile, ma ¯L non `e
Propriet`a dei linguaggi ricorsivamente enumerabili
Theorem
Se L e ¯L sono ricorsivamente enumerabili, allora L `e ricorsivo
Proof.
Sia L = L(M1) e ¯L = L(M2). Costruiamo M che esegue in parallelo
(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.
L e ¯L
Dove possono stare L e ¯L ? sia L che ¯L ricorsivi
n´e L n´e ¯L ricorsivamente enumerabili
L `e ricorsivamente enumerabile, e ¯L non `e ricorsivamente enumerabile
¯
L `e ricorsivamente enumerabile ma non ricorsivo, e L non `e 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
