Esercizi sui Modelli Computazionali

(N.B.: dall'A.A. 2015-16 il modello delle URM non e' in programma)


Esercizio 1

Progettare una macchina a stati finiti che manda in output 1 quando esattamente due degli ultimi 3 input sono a 1. Si assume come input una linea seriale ad 1 bit.

  • Soluzione.




    Esercizio 2

    Progettare un controller per un distributore automatico che accetta tre tipi di monete di valore 5,10 e 25, rispettivamente. La merce viene erogata al raggiungimento del valore 20. Il distributore prevede un resto massimo di una moneta da 5 e di una da 10.

  • Soluzione.



    Esercizio 3

    Fornire un automa a stati finiti che descriva il comportamento di un dispositivo che controlli un parcheggio con due posti macchina dotato di una sbarra al suo ingresso ed un'uscita (sempre aperta) diversa dall'ingresso. Ci sono anche delle cellule fotoelettriche all'ingresso ed all'uscita del parcheggio che permettono di sapere se una macchina ha attraversato un passaggio. 
               ------------------------------
           |                            |            
         + |                            | +            
           \\
---->       \\                            ------->
             \\
         + |                            | +           
           |                            |            
           ------------------------------
    Il dispositivo deve far abbassare la sbarra quando il parcheggio e' completo.

  • Soluzione.



    Esercizio 4

    In casa avete lo scaldabagno e la lavatrice, ma a causa di un impianto difettoso, non potete utilizzarli contemporaneamente. Fornire il diagramma degli stati di un automa a st ati finiti che descriva il comportamento di un dispositivo che, opportunamente collegato agli interruttori di tali elettrodomestici, impedisca di utilizzarli entrambi nello stesso momento (se la lavatrice e' accesa allora accendere lo scaldabagno non ha alcun effetto e viceversa; non ha alcun effetto anche accendere contemporaneamente tutti e due).


  • Soluzione (non testata).



    Esercizio 5

    In casa avete un sistema di cellule fotoelettriche che invia un segnale che indica se siete in casa o no; inoltre indica anche se siete in bagno o no. Descrivere, attraverso un automa a stati finiti, il comportamento di un dispositivo che che invii un segnale di accensione o spegnimento alla segreteria telefonica. La segreteria va accesa se siete fuori casa e spenta se siete dentro. Inoltre quando siete in casa deve accendersi quando siete in bagno.


    Esercizio 6
    Avete organizzato una mostra su "I transistor". Il materiale e' esposto in tre sezioni:
    Sezione 1: i transistor medioevali -- Sezione 2: i transistor nel rinascimento -- Sezione 3: i transistor nella Germania dell'800.
    Per far seguire un ordine nella visita del materiale della mostra, all'ingresso mettete un cartello che spiega che la Sezione 2 si puo' visitare solo se si e' appena visitata la Sezione 1 o la Sezione 3 e che la Sezione 3 si puo' visitare solo se si e' appena visitata la Sezione 2. Si puo' uscire dalla mostra quando si vuole.
    Per dare a tutti la tranquillita' necessaria per meditare sulle meraviglie della mostra, supponiamo che questa sia visitata da un unico visitatore alla volta (sara' il portiere a preoccuparsi che questo vincolo sia soddisfatto).
    Per esser sicuri che i visitatori seguano strettamente quel che avete scritto nel cartello, mettete un sistema di cellule fotoelettriche che invia le seguenti informazioni:
    - Il visitatore e' nella Sezione1
    - Il visitatore e' in Sezione2
    - Il visitatore e' in Sezione3
    - Non c'e' alcun visitatore
    Utilizzando le informazioni che arrivano dal sistema di fotocellule volete costruire un dispositivo che con il suo output controlli l'accensione di un altoparlante che diffonde la seguente registrazione: "Ignorantone! non hai letto il cartello all'ingresso?!?". La registrazione andra' diffusa non appena il visitarore non rispetta le indicazioni del cartello. Verra' interrotta non appena il visitatore ricomincia corretamente il giro oppure esce.

    Fornire l'automa a stati finiti che descriva il comportamento del dispositivo che volete costruire.
    Si suppone che il passaggio da una sezione all'altra della mostra avvenga istantaneamente (senza passaggi intermedi, per intenderci) e che non esistano vincoli fisici che impediscano agli ignorantoni di spostarsi tra tutte le varie sezioni contravvenendo alle disposizioni del cartello.


  • Soluzione.

    Esercizio 7
    Vogliamo costruire un giochino elettronico che ci permetta di giocare alla morra cinese (quella del "sasso", "forbice" e "foglio", per intenderci) premendo dei pulsanti anziche' fare sconvenienti gesti con le mani e che possa permettere ai giocatori di fare la loro mossa senza che questa sia necessariamente simultanea a quella dell'avversario. Ogni giocatore ha tre pulsanti ("sasso", "forbice" e "foglio"). Quando uno di questi viene premuto, premerne un'altro non ha alcun effetto finche' l'altro giocatore (che ovviamente non puo' vedere i pulsanti dell'altro) non fa la sua scelta. A questo punto il sistema indica con un breve segnale luminoso il risultato (vittoria giocatore 1, vittoria giocatore 2 o parita') e il gioco puo' continuare.
    La meccanica dei tasti e' tale che non si riescano a premere due o tre tasti insieme.
    Fornire l'automa a stati finiti che descrive il comportamento del nostro giochino.
    Nel caso la stesura di tutti i possibili ingressi ed uscite sugli archi risultasse eccessivamente pesante, scriverne alcuni significativi e spiegare brevemente cosa manca.

  • Soluzione.

    Esercizio 8
    Descrivere una macchina di Turing che riconosca il linguaggio delle stringhe palindromi sull'alfabeto {a,b}.

    Esercizio 9
    Descrivere una macchina di Turing che, preso in input il numero naturale n (rappresentato in binario), restituisca 2*n.

    Esercizio 10
    Descrivere una macchina di Turing che calcoli la funzione divisione intera per 2 (rappresentando i numeri in binario)

    Esercizio 11
    Descrivere una macchina di Turing che calcoli la funzione (n mod 2) (rappresentando i numeri in binario)

    Esercizio 12
    Descrivere una macchina di Turing che, preso n, restituisca n+2 (rappresentando i numeri in binario)

    Esercizio 13
    Fornire il programma URM che calcoli la funzione f tale che f(0)=0 e f(x)=x-1 (se x>0)

  • Soluzione.

    Esercizio 14
    Fornire il programma URM che, presi due numeri naturali, restituisca il massimo.

  • Soluzione.

    Esercizio 15
    Fornire il programma URM che calcoli la funzione somma di due numeri.


    Esercizio 16
    Fornire il programma URM che, utilizzando la funzione somma, calcoli la funzione prodotto.

  • Soluzione (by F.Vindigni)

    Esercizio 17
    Fornire la definizione di configurazione istantanea per il modello degli automi a stati finiti, per le macchine di Turing e per le URM.

    Fornire la definizione di passo computazionale per i tre modelli computazionali sopra elencati.


    Esercizio 18
    Dimostrare il Pumping Lemma per i linguaggi regolari.
    Perche' intuitivamente il Pumping Lemma ci dice che un automa a stati finiti non e' "capace di contare"?


    Esercizio 19
    Cos'e' un Modello Computazionale?


    Esercizio 20
    Qual e' la differenza tra automi deterministici e non deterministici?


    Esercizio 21
  • Cosa si intende per "programma" nel contesto dei linguaggi di programmazione funzionale?
  • In cosa consiste l'"esecuzione" di un programma in un linguaggio funzionale?
  • Elencare alcuni concetti tipici della programmazione imperativa che perdono completamente di significato in quella funzionale.
  • Cos'e' un Modello Computazionale?
  • Cosa si intende per "astrazione funzionale" e come questa viene formalizzata nel lambda-calcolo?
  • Cosa si intende per "currificazione" e quali sono i possibili vantaggi del suo utilizzo.
  • Cos'e' la relazione di alfa-convertibilita' tra termini?
    Esercizio 22
    Dato il seguente termine, cerchiare le sue variabili libere e collegare, utilizzando delle frecce, le sue variabili legate con i lambda relativi.

    λz.( ((λx.λx.yx)x)(vλz.λw.v) )

  • Soluzione.
    Esercizio 23


    Ridenominare alcune variabili legate nel seguente termine, in modo che non ci siano due lambda che leghino variabili con lo stesso nome.

    (λxxx.(zλz.x))(xλy.(y(λy.z)yy))

  • Soluzione.
    Esercizio 24


    Ricopiare il seguente termine sottolineando le variabili libere e mettendo un cerchietto intorno a quelle legate:

    (λx.(z(λz.((xyz)x))zx))x(λx.((λy.yy)(λz.zz)))

  • Soluzione.
    Esercizio 25


    Rinominare le variabili legate nel seguente termine in modo che non ci siano due variabili legate con lo stesso nome

    x(λx.((λx.x)x))



  • Soluzione.
    Esercizio 26


    Fornire un lambda-termine che contenga variabili con nome x, y e z ed in cui ci siano occorrenze sia legate che libere di variabili con tali nomi.

  • Soluzione.
    Esercizio 27


    Riscrivere il seguente termine utilizzando il minimo numero di parentesi secondo le convenzioni sintattiche

    ((xy)(λy.(λz.(z(xy)))))

  • Soluzione.
    Esercizio 28

    Supponendo di non utilizzare le convenzioni sintattiche sulle parentesi, riscrivere il seguente termine inserendo tutte le possibili parentesi.

    (λxyz.xy(xz))λxy.x

  • Soluzione.
    Esercizio 29

    Definire la nozione di "Currificazione". E' una nozione applicabile al lambda-calcolo? perche'?


  • Soluzione.
    Esercizio 30

    Fornire la definizione formale di sostituzione.
    Esercizio 31

    Qual e' la condizione che deve essere soddisfatta affinche' sia possibile applicare una sostituzione senza produrre "effetti indesiderati"?
    Esercizio 31.1

    E' corretto affermare che il lambda-termine
    λy.y(λt.λz.yt)
    e' il risultato della seguente sostituzione?
    λy.y(λz.xz)[ λz.y / x]
    Giustificare.
  • Soluzione.
    Esercizio 32

    Eseguire le seguenti sostituzioni
  • Soluzione.
    Esercizio 33

    Eseguire le seguenti sostituzioni:
    Esercizio 34

    Eseguire la seguente sostituzione:

    z(λy.wy)λz.((λx.yx)xz) [yz/x,yz/w]

    Esercizio 35

    Dire qual e' il risultato della seguente sostituzione:

    ((λy.xy)(λz.y(λy.x)))[xyz/x]

  • Soluzione.
    Esercizio 36

    Dire qual e' il risultato della seguente sostituzione:

    ((λy.yy)y(λy.y(λy.y)))[λy.zy/y]

    Esercizio 37

    Qual e' il risultato delle seguenti sostituzioni?
    Esercizio 38

    Qual e' il risultato della seguente sostituzione?

    ((λw.(xw))(λy.(yx)))[λx.(w(xy))/x]

    Esercizio 39

    Eseguire le seguenti sostituzioni:
    Esercizio 40

    Qual e' la condizione che deve essere necessariamente soddisfatta per poter correttamente effettuare una sostituzione M[N/x] ? Perche' tale condizione e' necessaria?

    Esercizio 41

    Eseguire le seguenti sostituzioni:
    Esercizio 42
    Qual e', se esiste, la forma normale del seguente termine? (\x.yy)((\z.z)x))
    Esercizio 43
    Trovare la forma normale di

    (λxxxx.xx)(λx.xx)(λx.x)y((λx.x)x)

  • Soluzione.
    Esercizio 44
    Trovare la forma normale di

    (λx.((λy.z)x))((λx.xx)(λx.xx))

    Esercizio 45
    Trovare la forma normale di

    (λx.((λy.z)x))((λx.xx)(λx.xx))

    Dire inoltre se questo termine e' fortemente normalizzabile.

    Esercizio 46
    Qual e' la formal normale del seguente termine?

    ((λw.(xw))(λy.(yx)))[λx.(w(xy))/x]

    Qual e' l'insieme delle sue variabili libere? e quale quello delle sue variabili legate?
    Esercizio 47
    Fornire un lambda-termine normalizzabile il cui insieme di variabili libere sia {x, y}, e tale che l'insieme delle variabili libere della sua forma normale sia {x, y, z}.
  • Soluzione.
    Esercizio 48
    Fornire un lambda termine che si riduca a forma normale in due passi di riduzione. Inoltre tale termine deve avere {x, y, z} come insieme di variabili libere, mentre le variabili libere della sua forma normale dovranno essere {x, y}.
  • Soluzione.
    Esercizio 49
    Portare in forma normale, se esiste, il seguente lambda-termine:

    (λx.((λz.zwz)(((λxyx.y)(λx.y)(λy.x))((λx.xx)(λy.yyy)))))t



  • Soluzione.
    Esercizio 50
    Qual e' la forma normale, se esiste, del seguente lambda-termine?

    (λx.xxy)(λxy.xyy)

  • Soluzione.
    Esercizio 51
    Dire in quale caso e' possibile avere un lambda-termine con piu' di una forma normale.
  • Soluzione.
    Esercizio 52
    Qual e' la forma normale del seguente termine?

    ((λw.(xw))(λy.(yx)))[λx.(w(xy))/x]

    Qual e' l'insieme delle sue variabili libere? e quale quello delle sue variabili legate?

    Esercizio 53
    Dire se il seguente termine possiede forma normale ed eventualmente fornirla insieme ai vari passi di riduzione:

    (λxxx.((λxx.x)(xx)(λx.x)))x(xx)


  • Soluzione.
    Esercizio 54
    Dire in quale caso e' possibile avere un lambda-termine con una sola forma normale.
  • Soluzione.
    Esercizio 55
    Fornire un algoritmo di semidecisione per la proprieta' di avere forma normale.
    Perche' non puo' esistere un algoritmo di decisione?
  • Soluzione.
    Esercizio 56
    Dimostrare che se un termine M contiene Omega ( (λx.xx)(λx.xx) ) come sottotermine proprio, allora non e' normalizzabile (non possiede forma normale).
  • Soluzione.
    Esercizio 57
    Enunciare e dimostrare il Corollario di Unicita' della forma normale.
    Esercizio 58
    Fornire la definizione di alfa-conversione. Qual e' il motivo per introdurre tale nozione nel lambda-calcolo?
    Esercizio 59
    Fornire un lambda termine che sia normalizzabile, ma a partire dal quale esista anche una sequenza infinita di beta-riduzioni.

  • Soluzione.
    Esercizio 60
    Cos'e' una strategia di riduzione?
    Esercizio 61
    Spiegare perche' talvolta, prima di eseguire una beta-riduzione, occorra rinominare le variabili legate (della lambda astrazione). In tali casi, si riuscirebbero ad evitare problemi se si operasse invece sulle variabili dell'argomento della beta riduzione? Motivare.
    Esercizio 62
    Trovare tre termini M,P e Q, tali che M contiene x e y tra le sue variabili libere e tali che M[P/x,Q/y] sia diverso da M[P/x][Q/y]

    Esercizio 63 (NO a.a.17-18)
    Descrivere la funzione somma nel formalismo delle funzioni primitive ricorsive.
    Successivamente, descrivere la funzione prodotto.


    Esercizio 64
    Dimostrare che la relazione binaria sui naturali "x e' il doppio di y" e' una funzione ricorsiva, fornendo la sua funzione caratteristica come URM. (Ricordiamo che una relazione binaria e' un insieme di coppie)

    Esercizio 65
    (a) Che cosa si intende per "modello computazionale"? Elencarne alcuni, descrivendoli a grandi linee.
    (b) Definire formalmente ed in dettaglio il modello computazionale delle URM.
    (c) Scrivere un programma URM che, partendo con il valore x nel primo registro (R1) e con il valore 0 in tutti gli altri registri, termini lasciando 1 in R1 se x e' dispari e 0 se e' pari. (ricordiamo che Z(n) e' l'istruzione di reset, S(n) quella di incremento, T(m,n) quella di assegnamento e J(m,n,q) quella di salto condizionato).
    Commentare il codice.

  • Soluzione.

    Esercizio 66
    Definire formalmente il modello computazionale delle Macchine di Turing.

    Esercizio 67
    Definire una macchina di Turing che riconosca il linguaggio regolare L=aa(a+b)*b
  • Soluzione.

    Esercizio 68 (NO a.a.17-18)
    Si possono codificare le stringhe del linguaggio dell'esercizio 67 punto (b) con 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 69
    Fornire la definizione formale di Automa a stati finiti deterministico e Automa a stati finiti non deterministico.

    Esercizio 70
    Discutere delle differenze tra programmazione imperativa (imperative programming) e funzionale (functional programming).

    Esercizio 71
    Definire informalmente la relazione di α-equivalenza tra lambda-termini. Fornire la stessa definizione in modo formale.

    Esercizio 72
    Enunciare il teorema di Church-Rosser e dimostrare la proprieta' di unicita' delle forme normali per il lambda-calcolo. Dedurre poi da quest'ultima la proprieta' di consistenza per la teoria della β-equivalenza.

    Esercizio 73 NO a.a.17/18
    Cos'e' la Teoria della Ricorsivita'? Enunciare inoltre la Tesi di Church.

    Esercizio 74 NO a.a.17/18
    Definire la classe delle funzione primitive ricorsive e quella delle funzioni parziali ricorsive.

    Esercizio 75 NO a.a.17/18
    Enunciare il Problema della fermata e dimostrarne l'insolubilita'.

    Esercizio 76
    Costruire una MT che calcoli la seguente funzione sui numeri naturali:    f(n) = n div 2
    Dove div e' la divisione intera.
  • Soluzione.

    Esercizio 77
    Dato il seguente termine, cerchiare le sue variabili libere e collegare, utilizzando delle frecce, le sue variabili legate con i lambda relativi.

    λz.( ((λx.λx.yx)x)(vλz.λw.v) )

    Sottolinare inoltre i redessi (redex) presenti in tale lambda-termine.
  • Soluzione.

    Esercizio 78
    Sia add il lambda termine λnmfx.nf(mfx) che rappresenta la somma nel lambda calcolo. Utilizzare tale termine per calcolare 1+1, mostrando i vari passaggi nel calcolo.
  • Soluzione.

    Esercizio 79 NO a.a.17/18
    Si consideri la seguente definizione della funzione parziale ricorsiva f: 
     f(0,x) = P11(x)
 f(y+1,x) = h(y,f(y,x),x)
    dove h e' definita da 
     h(y,z,x) = S(P32(y,z,x))
    Dire, giustificando la risposta, cosa calcola f.
    Dire inoltre qual e' il valore di g(0), dove g e' definita da 
     g(x) = μ{y|f(y,x)=0}
    Ricordiamo che la funzione di base Pkj e' definita da Pkj(n1,..,nk) = nj.
  • Soluzione.

    Esercizio 80
    Cosa si intende per "modello computazionale"? Definire il modello computazionale delle URM.

    Scrivere un programma URM che calcoli (n div 2), dove n e' l'input e div e' la divisione intera.
  • Possibile soluzione.

    Esercizio 81 NO a.a.17/18
    Descrivere il formalismo delle funzioni primitive ricorsive e delle funzioni parziali ricorsive.

    Esercizio 82 NO a.a.17/18
    Si supponga di aver definito la funzione primitiva ricorsiva f, di due argomenti, che calcola la somma.
    Si consideri quindi la seguente definizione della funzione primitiva ricorsiva g: 
     g(0,x) = C10(x)
 g(y+1,x) = q(y,g(y,x),x)
    dove q e' definita da 
     q(y,z,x) = f(P32(y,z,x),P33(y,z,x))
    Dire, giustificando la risposta, cosa calcola g.
    Si consideri inoltre la seguente definizione della funzione primitiva ricorsiva t: 
     t(0) = C01
 t(y+1) = u(y,t(y))
    dove u e' definita da 
     u(y,z) = g(S(P21(y,z)),P22(y,z))
    Dire, giustificando la risposta, cosa calcola t.
    Ricordiamo che la funzione di base Pkj e' definita da Pkj(n1,..,nk) = nj.
    Inoltre, la funzione di base costante Ckh e' definita da Ckh(n1,..,nk) = h.
    La funzione unaria di base S calcola invece il successore.
  • Soluzione.

    Esercizio 83
    Cos'e' un modello computazionale? Descrivere il modello computazionale delle Macchine di Turing.

    Esercizio 84 NO a.a.17/18
    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 85
    Descrivere una TM (transduttore) che calcola la funzione g:{a,b}* &arr; {a}* che restituisce la stringa composta da sole a in numero uguale alle a presenti nella stringa di input.
  • Possibile Soluzione (by Reversengineer, Earl).

    Esercizio 86
    Si consideri il seguente lambda-termine:
    (λw.wx)(λy.yx)
    Qual e' l'insieme delle sue variabili libere? e quale quello delle sue variabili legate? Mostrare il procedimento per arrivare alla sua forma normale, se quest'ultima esiste.
  • Soluzione.

    Esercizio 87
    Scrivere un programma URM che calcoli (n div 2), dove n e' l'input e div e' la divisione intera.
  • Soluzione.

    Esercizio 88
    Descrivere il modello computazionale del λ-calcolo.

    Esercizio 89
    Inserire le parentesi ed i lambda lasciati impliciti nel seguente termine. Rinominare inoltre le variabili legate in modo che non ci siano due lambda che legano variabili con lo stesso nome:
    (λxxxx.x(xx)x)xxx

  • Soluzione.

    Esercizio 90
    Enunciare il Teorema di Church-Rosser e dimostrare la proprieta' di unicita' della forma normale.
    Dimostrare inoltre la consistenza del λ-calcolo.
  • Soluzione.

    Esercizio 91
    I termini
    (λxxxx.xx)(λx.xx)(λx.x)y((λx.x)x)
    e
    (λb.λa.λc.λx.xx)(λx.xx)(λx.x)z((λw.w)x)
    possono essere considerati identici? Giustificare la risposta.
  • Soluzione.

    Esercizio 92 NO a.a.17/18
    Definire brevemente, ma formalmente , la nozione di passo di computazione nel contesto
    - degli automi a stati finiti
    - delle macchinedi Turing
    - del λ-calcolo
    - delle URM
    - del formalismo delle funzioni primitive ricorsive
    - della Logica di Hoare

  • Soluzione.

    Esercizio 93
    Definire formalmente la nozione di sostituzione ed effettuare la seguente sostituzione

    ((λy.xy)(λz.y(λy.x)))[xyz/x]


  • Soluzione.

    Esercizio 94
    Definire formalmente la nozione di sostituzione ed effettuare la seguente sostituzione

    ((λy.xy)(λz.y(λy.x)))[xyz/x]


  • Soluzione.

    Esercizio 94
    Cosa si intende per Modello Computazionale? Descrivere brevemente, ma formalmente, il Modello Computazionale del λ-calcolo.

    Esercizio 95
    La funzione "incremento di uno" viene rappresentata nel λ-calcolo con il termine λn.λf.λx.nf(fx) mentre il numero 0 viene rappresentato da λg.λy.y
    Calcolare nel λ-calcolo il valore che si ottiene incrementando di uno il numero zero.
  • Soluzione.

    Esercizio 96 NO a.a.17/18
    Nel modello computazionale delle funzioni parziali ricorsive, si supponga di aver gia' definito la funzione moltiplicazione (mult). Cosa calcola la funzione g definita nel modo seguente? 
    i(z,t,v) = mult( P32(z,t,v), P33(z,t,v) )
g(0,x) = C11(x)
g(y+1,x) = i(y, g(y,x), x)
    Giustificare brevemente la risposta.
  • Soluzione.

    Esercizio 97
    Descrivere una Macchina di Turing capace di effettuare la somma in binario di due numeri a quattro cifre. (Si assuma che tali numeri in input siano separati sul nastro da un carattere speciale "$").
  • Soluzione by Daniele Distefano (file .odt).

    Esercizio 98
    Fornire le definizioni formali di automa a stati finiti deterministico e non deterministico.

    Esercizio 99
    Si fornisca una macchina di Turing che, preso un numero intero n rappresentato in complemento a due, restituisca la rappresentazione in complemento a due del numero -n-1.
    Giustificare il procedimento utilizzato.
  • Soluzione.

    Esercizio 100
    Cos'e' il λ-calcolo? Definire formalmente l'insieme dei λ-termini, l'insieme delle variabili libere di un termine, l'operazione di sostituzione e la relazione di β-riduzione.

    Esercizio 101
    Nel contesto del λ-calcolo, enunciare il Teorema di Church-Rosser ed utilizzarlo per dimostrare il Corollario di Unicita' della forma normale.

    Esercizio 102
    Fornire il λ-termine che rappresenta l'operatore booleano OR, in modo diretto oppure utilizzando l'operatore IF_THEN_ELSE. In entrambi i casi, giustificare la risposta.
    (Ricordiamo che l'operatore IF_THEN_ELSE si rappresenta con λz.z, il valore TRUE con λx.λy.x e il valore FALSE con λx.λy.y).
  • Soluzione.

    Esercizio 103
    Cosa si intende per Macchina di Turing Universale? Descriverne informalmente il comportamento.

    Esercizio 104
    Cos'e' un modello computazionale? Si descriva il modello computazionale delle URM.

    Esercizio 105
    Dimostrare che la relazione binaria sui naturali "x e' il doppio di y" e' una relazione ricorsiva, fornendo la sua funzione caratteristica come URM. (Ricordiamo che una relazione binaria e' un insieme di coppie)
    Ricordiamo che le istruzioni delle URM sono Z(n), S(n), T(m,n) e J(m,n,q)
  • Soluzione.
    Esercizio 106 NO a.a.17/18
    Enunciare il Problema della fermata e dimostrarne l'insolubilita'.

    Esercizio 107
    Descrivere brevemente il modello computazionale del λ-calcolo.

    Esercizio 108
    Rinominare le variabili legate del seguente termine, in modo che non ci siano due astrazioni che legano variabili con lo stesso nome.

    (λx.xxy)(λxy.xyy)

    Qual e' il termine che si ottiene eseguendo due beta-riduzioni sul termine fornito?
  • Soluzione.

    Esercizio 109
    Fornire la definizione formale di Automa a Stati Finiti e la definizione formale di linguaggio accettato da un automa.
    Esercizio 110
    Sappiamo di avere la funzione + tra le funzioni parziali ricorsive. Definiamo ora
    g(x) = μ{ y | +(y,x)=0 }
    e definiamo anche
    h(v,w) = g(+(v,w))
    Consideriamo ora la seguente funzione
    q(x) = μ{ y | h(y,x)=0 }
    Cosa calcola g, cosa calcola h?
    Qual e' il valore di q(0)?
    Qual e' il valore di q(2)?
    Come vengono calcolati?
  • Soluzione.
    Esercizio 111 NO a.a.17/18
    Usare il metodo di Diagonalizzazione per dimostrare che ci sono funzioni calcolabili, da N in N, che non sono primitive ricorsive.
  • Soluzione.
    Esercizio 112
    Calcolare la forma normale (mostrando la computazione eseguita) del lambda-termine
    and T T
    dove
    and e' λab.abF
    T e' λxy.x
    F e' λxy.y

  • Soluzione.
    Esercizio 113
    Calcolare la forma normale (mostrando la computazione eseguita) del lambda-termine
    x(λ z.(zx)) [λt.(w(ty))/x]

  • Soluzione.
    Esercizio 114
    Il seguente λ-termine e' normalizzabile. Mostrare tutti i passi di β-riduzione che portano alla sua forma normale.

    (λx.xxy)(λxy.xyy)



  • Soluzione.
    Esercizio 115
    Descrivere brevemente le principali differenze tra linguaggi di programmazione imperativi e linguaggi di programmazione funzionali.
    Esercizio 116
    Definire, nel modo piu' completo possibile, la relazione di β-riduzione del λ-calcolo.
  • Soluzione.
    Esercizio 117
    Rinominare le variabili legate nel seguente termine in modo che non ci siano due variabili legate con lo stesso nome

    x(λx.((λx.x)x))

    Questo termine ha una forma normale? Se no, perche' e qual e' una possibile sequenza infinita di β-riduzioni a partire da questo termine? Se si, qual e' e come si ottiene?

  • Soluzione.
    Esercizio X

  • Soluzione.