Calcolabilit` a e Linguaggi Formali Parte I Compito BBBBB
10 Novembre 2014
Esercizio 1
Enunciare e dimostrare il terzo teorema di Rice.
Esercizio 2
Sia L ⊆ {0, 1}∗ l’insieme delle stringhe binarie definito per induzione come segue:
(i) 1 ∈ L;
(ii) Se α ∈ L allora α101 ∈ 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 (101)0 = and (101)n+1 = (101)n101. Per esempio, (101)3 = 101101101.
Allora abbiamo: L = {0(101)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, q10, 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 q10D; q1 1 1 qcicloD; q1 b b qcicloD q10 1 1 p D; q10 0 0 qcicloD; q10 b b qciclo D
qciclo 0 0 qciclo D; qciclo1 1 qcicloD; qciclob b qcicloD.
Esercizio 3
Definire per ricorsione primitiva la seguente funzione f (x, y) = x2+ y2. Determinare le funzioni g e h associate allo schema di ricorsione primitiva f = REC(g, h).
Soluzione : f (x, 0) = x2; f (x, y + 1) = x2+ (y + 1)2 = x2+ y2+ 2y + 1 = f (x, y) + 2y + 1. Quindi g(x) = x2 e h(x, y, z) = z + 2y + 1.
Esercizio 4
Applicare, se possibile, i tre teoremi di Rice all’insieme
I = {x : ∀y(φx(y) ≥ y)}.
Soluzione : I e’ estensionale. Se x ∈ I and φx= φzthen we have: φx(a) ≥ a per ogni a ∈ N . Allora φz(a) = φx(a) ≥ a per ogni a, da cui segue z ∈ I.
I 6= ∅: I programmi che calcolano la funzione identica f (x) = x 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 non e’ applicabile ad I perche’ I contiene solo programmi che terminano la computazione per ogni input. In altre parole programmi di funzioni titali che non sono propriamente estendibili.
Il terzo teorema di Rice e’ applicabile ad I: Sia θ un arbitraria restrizione finita della funzione identica. Allora tutti i programmi che calcolano θ appartengono al complementare di I, mentre i programmi che calcolano la funzione identica sono in I.
