Calcolabilit` a e Linguaggi Formali Parte I Recupero Primo Compitino
14 Gennaio 2015
Esercizio 1
Enunciare e dimostrare il primo teorema di Rice.
Esercizio 2
Dimostrare che K = {x : Px↓ x} non `e decidibile.
Esercizio 3
Applicare i teoremi di Rice all’insieme I = {x : dom(φx) = {3, 5, 6}} ed al suo complementare.
Soluzione
L’insieme I rispetta le funzioni. Se x ∈ I e φx= φy, allora dom(φy) = dom(φx) = {3, 5, 6}, da cui segue y ∈ I. I 6= ∅:
i programmi che calcolano la funzione costante di valore 0 sul dominio {3, 5, 6} appartengono ad I.
I 6= N : i programmi della funzione vuota appartengono al complementare di I.
Dal primo teorema di Rice segue che I ed il suo complementare non sono decidibili, ed il complementare di I non e’
semidecidibile.
Rice II per I: e’ applicabile con f la funzione costante di valore 0 sul dominio {3, 5, 6}, e g la funzione costante su tutto l’insieme N . Allora f < g e quindi I non e’ semidecidibile.
Rice II per il complementare di I: f funzione vuota, g la funzione costante di valore 0 sul dominio {3, 5, 6}; allora f < g e quindi il complementare di I non e’ semidecidibile.
Rice III per I: non e’ applicabile. Ad I non appartengono programmi di funzione infinite.
Rice III per il complementare di I: non e’ applicabile. Si consideri una qualsiasi funzione infinita f . Allora {x : φx= f } ⊆ N \ I, ma esistono approssimazione finite di f che non stanno in I.
Esercizio 4
Sia A l’insieme di numeri naturali definito induttivamente come segue:
• 2 ∈ A;
• Se x ∈ A allora x2+ 5 ∈ A.
Determinare se `e possibile applicare ad A i teoremi di Rice.
Soluzione
L’insieme A e’ decidibile ed infinito. Quindi non e’ possibile applicare ad A i teoremi di Rice.
