Fondamenti di Informatica, 19 Settembre 2012
Non e' ammesso l'uso di alcun testo, appunti o
calcolatrici. Le risposte vanno scritte nel foglio di bella copia. Si
raccomanda la massima SINTETICITA'. L'eccessiva verbosita' verra'
considerata negativamente.
Occorre essersi prenotati sul portale studenti del nostro
ateneo. Se cio' non e' stato fatto, comunicatelo immediatamente
al docente o all'assistente in aula.
I risultati
verranno indicati nella pagina web del corso.
Date ed orari degli orali, sul Forum.
Esercizio 1
(a)
Cos'e' un modello computazionale? Descrivere il modello computazionale delle Macchine di Turing.
(b)
Descrivere la macchina di Turing che riconosce (decide) il linguaggio formato dalle stringhe
sull'alfabeto {a,b,c} tali che tutte le
sottosequenze massimali composte di sole `a` sono in numero pari.
(Consideriamo pari il numero 0).
(c)
Enunciare il problema della fermata (terminazione) per le macchine di Turing e
fornire la dimostrazione dell'impossibilita' della sua soluzione (nel testo di Odifreddi
si utilizzano le funzioni parziali ricorsive, ma se si considerano le macchine di Turing il ragionamento
e' lo stesso).
Esercizio 2
(a)
Sia {{a0,b0},{c2,p2}} una segnatura dove a e b sono simboli di costante, mentre c e p
sono simboli predicativi binari.
Interpretando a come "Antonella", b come
"Bruno", c(x, y) come "x conosce y", p(x, y) come "x e' parente di y",
traducete le seguenti frasi (scrivete cioe' le formule ben formate corrispondenti):
(i) Ogni parente di Bruno ha un parente che conosce Bruno;
(ii) Un parente di Bruno conosce una persona che conosce tutti i parenti di Antonella;
(iii) Se Antonella e Bruno hanno un parente in comune, allora sono parenti.
(b)
Nella logica dei predicati, considerare la segnatura seguente, dove
i simboli di funzione sono
{c0, k0, f1, g2}
mentre i simboli di predicato (relazioni) sono
{P1, Q2}
Fornire delle strutture (non banali) nelle quali le seguenti formule
risultino vere e strutture nelle quali risultino false.
(i) forall x.Q(x,x)
(ii) forall x. forall y.Q(x,y)
(iii) forall x. forall y. exists z. (P(x) -> Q(y,f(z)))
(iv) exists z. forall x. (P(x) ∨ Q(k,z))
(v) exists z. (P(g(z,c)) ∧ (forall x. Q(x,f(g(z,k)))))
(c)
Si consideri la seguente definizione di funzione Haskell dai naturali agli interi:
f 100 = 0
f n = if n > 100 then n + (f 0) else (f (n+1)) - 1
Dimostrare che f e' totale e che coincide con la funzione intera g(x) = x - 100.
Aiutino Utilizzare l'induzione ben-fondata sull'insieme ben-fondato
(N,[ ), dove N e' l'insieme dei numeri naturali e
la relazione di precedenza [ e' definita come segue:
n [ m sse (n=0 e m >100) oppure (m<100 e n=m+1)
Esercizio 3
Descrivere il formalismo delle funzioni primitive ricorsive e delle funzioni
parziali ricorsive.