Calcolabilit` a e Linguaggi Formali Parte I Compito AAAAA
10 Novembre 2014
Esercizio 1
Enunciare e dimostrare il secondo teorema di Rice.
Esercizio 2
Sia L ⊆ {0, 1}∗ l’insieme delle stringhe binarie definito per induzione come segue:
(i) 0 ∈ L;
(ii) Se α ∈ L allora α10 ∈ L;
Scrivere un programma di MdT che termina la computazione su una stringa binaria α se e solo se α ∈ L.
Soluzione : Sia la stringa vuota e sia (10)0 = and (10)n+1 = (10)n10. Per esempio, (10)3 = 101010. Allora abbiamo: L = {0(10)n: n ≥ 0}.
Ecco un programma di una macchina di Turing che riconosce L (b e’ il carattere blank):
Alfabeto = {0, 1, b}; Stati = {q0, p, q1, qciclo, qf ine}; Stato iniziale q0. q0 b b qcicloD; q0 1 1 qciclo D; q00 0 p D;
p b b qf ine D; p 1 1 q1 D; p 0 0 qciclo D q1 0 0 p D; q1 1 1 qcicloD; q1 b b qciclo D
qciclo 0 0 qciclo D; qciclo1 1 qcicloD; qciclob b qcicloD.
Esercizio 3
1. Siano A, B due insiemi decidibili non vuoti. E’ possibile che A ≤T B (in altre parole, ridurre A a B)?
2. Sia K = {x : Px↓ x}. Ridurre, se possibile, K all’insieme dei numeri primi.
Soluzione : E’ possibile ridurre A a B se B 6= N . Sia b0∈ B e b1∈ N \ B. Allora la funzione s(x) = b0se x ∈ A and s(x) = b1 se x /∈ A e’ totale e calcolabile. Essa riduce A a B.
Sia P l’insieme dei numeri primi. P e’ un insieme decidibile, mentre K non lo e’. Non e’ possibile ridurre K a P perche’ altrimenti anche K sarebbe decidibile. Ricordiamo che le proprieta’ positive, per esempio essere decidibile oppure essere semidecidibile, tornano indietro.
Esercizio 4
Applicare, se possibile, i tre teoremi di Rice all’insieme
I = {x : ∃y(φx(y) ≤ 100)}.
Soluzione : I e’ estensionale. Se x ∈ I and φx = φz then we have: φx(a) ≤ 100 per qualche a ∈ N . Allora φz(a) = φx(a) ≤ 100, da cui segue z ∈ I.
I 6= ∅: I programmi che calcolano la funzione costante f (x) = 0 per ogni x appartengono a I.
I 6= N : I programmi che calcolano la funzione vuota appartengono al complementare di I.
Quindi possiamo applicare il primo teorema di Rice e deriviamo che I non e’ decidibile (ed il complementare di I non e’ semidecidibile).
Il secondo teorema di Rice ed il terzo teorema di Rice non sono applicabili ad I perche’ I e’ semidecidibile: dato x, decodifichiamo x per ottenere il programma Px. Spazziamo il piano (input, tempo di esecuzione) in maniera tale da non trascurare nessun incrocio. Ogni volta che abbiamo terminazione controlliamo se l’output e’ ≤ 100.
