Le lezioni si tengono al I semestre con il seguente orario:

• [-] lunedì ore 9.00-11.00 (lezione, Aula 009);
• [-] mercoledì ore 11.00-13.00 (lezione, Aula 009);
• [-] venerdì ore 9.00-11.00 (lezione/esercitazione, Aula 009)

Lezione n. 1 - Friday 29 September 2017

Presentazione del corso. Introduzione storica da Hilbert ai teoremi di incompletezza e di indecidibilità. I modelli di calcolo (macchina di Turing, lambda calcolo, le funzioni ricorsive). La complessita' degli algoritmi. Definizione degli algoritmi formali. Monoide libero delle parole su un alfabeto finito.

Lezione n. 2 - Monday 2 October 2017

Problemi di decisione. Semi-decidibiltà. Decidibile implica semi-decidibile. Automi a stati finiti (deterministici). Algoritmo formale associato ad un automa. Esempio di computazione per un automa a stati finiti. Rappresentazione grafica degli automi.

Lezione n. 3 - Wednesday 4 October 2017

Insiemi decidibili per automa. Esercizio sulla decidibilita` per automa finito. Rappresentazione come grafo degli automi. Rappresentazione come matrice di adiacenza. Semianello delle serie formali sul monoide libero delle parole di alfabeto A. Matrice sul semianello delle serie formali associata ad un automa finito. Formula dell'esecuzione dell'automa. Estrazione del linguaggio deciso dall'automa a partire dalla formula dell'esecuzione. Insiemi regolari. Proprieta` di chiusura degli insiemi regolari.

Lezione n. 4 - Friday 6 October 2017

Insiemi regolari. Proprieta` di chiusura degli insiemi regolari. Automi Non-deterministici. Automi con transizioni epsilon. Equivalenza tra la DFA-decidibilita` e NDFA-decidibilta`. Proprieta` di chiusura degli insiemi regolari. Automi Non-deterministici. Automi con transizioni epsilon. Equivalenza tra la DFA-decidibilita` e NDFA-decidibilta`.

Lezione n. 5 - Monday 9 October 2017

Proposizione: ogni insieme regolare e' interpretazione di una qualche espressione regolare. Definizione di espressione regolare. Interpretazione di un'espressione regolare con un insieme. Proposizione: ogni insieme regolare e' interpretazione di un'espressione regolare. Costruzione dell'Automa NDF-epsilon che decide l'insieme interpretazione di una qualsiasi espressione regolare. Dimostrazione ed esempi.

Lezione n. 6 - Wednesday 11 October 2017

Definizione di Macchina di Turing. Spazio delle configurazioni per una Macchina di Turing. Algoritmo associato ad una macchina di Turing. Insiemi decidibili per macchina di Turing. DFA-decidibile implica Turing decidibile.

Lezione n. 7 - Friday 13 October 2017

Esempio di insieme decidibile per macchina di Turing. Turing-decidibile implica Turing-semi-decidibile. Macchina di Turing che decide l'insieme 0^n1^n in tempo quadratico.

Lezione n. 8 - Monday 16 October 2017

Pumping Lemma per le macchine di Turing che decidono in tempo lineare. Applicazione del Pumping Lemma per mostrare che l'insieme 0^n1^n non puo' essere deciso in tempo lineare. Discussione di una macchina di Turing che decide lo stesso problema in tempo n Log(n). Definizione di simulazione tra algoritmi. Definizione di macchina di Turing a seminastro.

Lezione n. 9 - Wednesday 18 October 2017

Simulazione di machine mononastro con macchine a seminastro. Macchine di Turing multi-nastro.

Lezione n. 10 - Monday 23 October 2017

Teorema di simulazione di una macchina multinastro con una macchina mononastro. Considerazioni sul costo diella simulazione. Cambiamenti di alfabeto. Considerazioni sul costo di simulazione della computazione di una macchina di Turing su un alfabeto quando si considera un alfabeto ridotto.

Lezione n. 11 - Wednesday 25 October 2017

Cambiamenti di alfabeto. Invarianza della decidibilità per cambiamento di alfabeto. Teorema di speed-up. Dimostrazione del teorema di speed-up.

Lezione n. 12 - Monday 30 October 2017

Macchine di Turing speciali. Equivalenza rispetto alla decidibilità per macchina di Turing. Valutazione del costo di simulazione. Rappresentazione degli interi. Invarianza della decidibilità di un insieme di interi rispetto alla base di rappresentazione. Decidibilità di insiemi numerici.

Lezione n. 13 - Monday 13 November 2017

Turing calcolabilita`: definizione di funzione Turing calcolabile. Esempi. Funzioni caratteristiche di insiemi Turing decidibili, la classe delle funzioni Turing calcolabili e` chiusa per composizione, coppia, riorsione primitiva e minimalizzazione.

Lezione n. 14 - Wednesday 15 November 2017

Turing computabilità delle funzioni aritmetiche di base: somma, predecessore, costanti e proiezioni. Dimostrazione che la classe delle funzioni ricorsive è Turing computabile. Esempi di funzioni ricorsive.

Lezione n. 15 - Friday 17 November 2017

Funzioni Ricorsive: equivalenza tra Turing computabilita` e funzioni ricorsive. Definizione di funzione ricorsiva primitiva. Ogni funzione ricorsiva primitiva e' totale. Funzioni ricorsive totali e funzioni ricorsive totali non ricorsive primitive: la funzione di Ackermann.

Lezione n. 16 - Wednesday 22 November 2017

Lezione n. 17 - Friday 24 November 2017

Lezione n. 18 - Monday 27 November 2017

Lezione n. 19 - Wednesday 29 November 2017

Lezione n. 20 - Friday 1 December 2017

Lezione n. 21 - Monday 4 December 2017

Lezione n. 22 - Wednesday 6 December 2017

Lezione n. 23 - Monday 11 December 2017

Decidibiltà degli insiemi proiezione. Esistenza di insiemi decidibili la cui proiezione è semidecidibile ma non decidibile. Definizione di classe di complessità non-deterministica basata sulla decidibilità degli insiemi proiezione. Macchine di Turing con oracolo. Relazione tra macchine di Turing con oracolo e macchine di Turing non-deterministiche. Confronto tra le classi di complessità deterministiche e le due non-deterministiche (proiezioni e oracolo). Teorema di equivalenza.

Lezione n. 24 - Wednesday 13 December 2017

Lezione n. 25 - Monday 18 December 2017

Definizione di riduzione beta0 e beta conversione. Proprieta' della chiusura transitiva. Definizione di termine in forma normale. Termine normalizzabile e fortemente normalizzabile. Teorema di Church-Rosser. Beta equivalenza. Unicita' della forma normale. Riduzione sinistra. Teorema: la riduzione sinistra e' una strategia normalizzante. Caratterizzazione delle forme normali. Albero di Bohm. Riduzione di testa. Termini risolubili. Caratterizzazione della risolubilita' via riduzione di testa.

Lezione n. 26 - Wednesday 20 December 2017

Lezione n. 27 - Friday 22 December 2017

Rappresentazione di alcuni tipi di dato nel lambda-calcolo: interi, liste, alberi binari. Rappresentazione dell'operatore di minimalizzazione.