Fondamenti di Informatica, 6 Luglio 2011 A.A. 2010/11

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 sistema formale? Quando un sistema formale si dice Consistente? Quando un insieme di formule ben formate di un sistema formale e' una Teoria? Cos'e' la Teoria pura di un sistema formale? Una teoria pura e' una teoria? Perche'?
    (b) Quella che segue e' una dimostrazione, nella logica dei predicati, di α, ¬α |- β . A tale dimostrazione pero' mancano delle parti. 
    1.   α → (¬β → α)                 Ak
2.   ??                           ipotesi
3.   ¬β → α                       MP(1,??)
4.   ¬α → (¬β → ¬α)               Ak
5.   ¬α                           ipotesi
6.   ??                           MP(4,5)
7.   (¬β → ¬α) → ((¬β → α) → β)   A¬
8.   ??                           MP(6,7)
9.   β                            ??
    Ricopiare la dimostrazione riempiendo le parti "??" in modo da completarla.

    (c) Descrivere i principi di Induzione, Induzione completa ed Induzione Ben Fondata ed un loro possibile uso nell'Informatica.
    Esercizio 2
    (a) Definire formalmente il modello computazionale delle Macchine di Turing.
    (b) Definire la macchina di Turing che riconosca il linguaggio regolare L=aa(a+b)*b
    (c) Si possono rappresentare le stringhe del linguaggio del punto (b) come numeri naturali?
    Se si, mostrare brevemente come, e dire poi se la funzione caratteristica dell'insieme dei numeri naturali corrispondenti al linguaggio L si puo' rappresentare come funzione totale ricorsiva e perche'.
    In caso contrario, fornire una stringa di L che non e' rappresentabile come numero naturale, dimostrando poi che questo si puo' fare per ogni linguaggio regolare.
    Esercizio 3
    Dimostrare che nella codifica in complemento a due dei numeri interi la rappresentazione dei i numeri positivi ha "0" come cifra piu' a sinistra, mentre quella dei numeri negativi "1".