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

• [-] lunedì ore 11.00-13.00 (lezione, Aula M4);
• [-] mercoledì ore 11.00-13.00 (lezione, Aula 009);
• [-] venerdì ore 9.00-11.00 ore 11.00-13.00 (lezione/esercitazione, C - Edificio Fisica a Vasca Navale Laboratorio di Informatica)

Lezione n. 1 - Monday 23 September 2019

Presentazione del corso. Modalita` di esame. Orario delle lezioni. Cenni storici intorno al concetto di calcolabilita`, Macchine di Turing. Automi. Lambda-calcolo. Rappresentabilita`. Alfabeto finito. Computazione associata ad un algoritmo formale. Esempio di Algoritmo Formale. Descrizione del modello di computazione a stati finiti. Definizione di automa a stati finiti. Definizione dell'algoritmo associato.

Lezione n. 2 - Wednesday 25 September 2019

Descrizione del modello di computazione a stati finiti. Definizione di automa a stati finiti. Definizione dell'algoritmo associato. Insiemi decidibili per automa. Esercizio sulla decidibilita` per automa finito. Rappresentazione come grafo degli automi. Rappresentazione come matrice di adiacenza.

Lezione n. 3 - Friday 27 September 2019

Introduzione a Wolfram Mathematica

Lezione n. 4 - Monday 30 September 2019

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.

Lezione n. 5 - Wednesday 2 October 2019

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

Lezione n. 6 - Friday 4 October 2019

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

Lezione n. 7 - Monday 7 October 2019

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.

Lezione n. 8 - Wednesday 9 October 2019

DFA-decidibile implica Turing decidibile. 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. 9 - Friday 11 October 2019

Esercitazione Automi e Macchine di Turing.

Lezione n. 10 - Monday 14 October 2019

Pumping Lemma. Dimostrazione del Pumping Lemma. Discussione di una macchina di Turing che decide lo stesso problema in tempo n Log(n). Definizione di simulazione tra algoritmi.

Lezione n. 11 - Friday 18 October 2019

Definizione di macchina di Turing a seminastro. Simulazione di macchine mono-nastro con macchine a semi-nastro. Macchine di Turing multi-nastro. Teorema di simulazione di una macchina multinastro con una macchina mononastro. Considerazioni sul costo della simulazione.

Lezione n. 12 - Monday 21 October 2019

Cambiamenti di alfabeto. Invarianza della decidibilita` per cambiamento di alfabeto. Teorema di speed-up. Dimostrazione del teorema di speed-up.

Lezione n. 13 - Wednesday 23 October 2019

Rappresentazione degli interi. Decidibilità di insiemi numerici. Costo computazionale della conversione da una base ad un'altra.

Lezione n. 14 - Friday 25 October 2019

Espressione regolare associata ad un automa non deterministico. Composizione Parallela di Macchine di Turing. Relazione tra Semidecidibilità e decidibilità.

Lezione n. 15 - Monday 28 October 2019

La classe delle funzioni Turing calcolabili è chiusa per composizione, coppia, ricorsione primitiva e minimalizzazione. 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. 16 - Wednesday 30 October 2019

Funzioni Ricorsive: equivalenza tra Turing computabilità e funzioni ricorsive. Definizione di funzione ricor- siva primitiva. Ogni funzione ricorsiva primitiva è totale.

Lezione n. 17 - Monday 4 November 2019

Ricorsività delle funzioni Turing-computabili

Lezione n. 18 - Wednesday 6 November 2019

Esempi di funzioni ricorsive parziali definite per casi. Simulazione di Automi per macchine di Turing. Esempi di insiemi DFA-decidibili.

Lezione n. 19 - Friday 8 November 2019

Esempi di insiemi semi-decidibili. Esempio di trasformazione di un automa non-deterministico in uno deterministico.

Lezione n. 20 - Monday 18 November 2019

Semidecidibilità del Problema dell'arresto. Macchina di Turing universale. Esistenza (per ogni alfabeto) di un insieme che è semi-decidibile ma non è decidibile.

Lezione n. 21 - Wednesday 20 November 2019

Definizione di T-timer. Definizione di Funzione Costruibile in Tempo. Primi esempi di funzioni costruibili in tempo. Proprietà di chiusura. Ogni funzione costruibile in tempo è anche Turing computabile. Ogni funzione Turing computabile è maggiorata da una funzione costruibile in tempo.

Lezione n. 22 - Friday 22 November 2019

Costruzione della Gerarchia di Classi di complessità in Tempo

Lezione n. 23 - Monday 25 November 2019

Macchine di Turing non deterministiche. Esistenza di insiemi decidibili la cui proiezione è semidecidibile ma non decidibile. Definizione di classe di complessità non-deterministica basata sulla decidibilità degli insiemi proiezione.

Lezione n. 24 - Wednesday 27 November 2019

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. Equivalenza delle classi di complessità derivanti dalle diverse nozioni di calcolo non-deterministico. Classi di complessità P ed NP.

Lezione n. 25 - Friday 29 November 2019

Definizione dell'insieme dei lambda-termini. Interpretazione di alcuni lambda-termini come funzioni. Definizione di sostituzione semplice. Proprietà della sostituzione semplice.

Lezione n. 26 - Monday 2 December 2019

Lambda calcolo. Prime proprietà della sostituzione semplice.

Lezione n. 27 - Wednesday 4 December 2019

Relazione di alpha equivalenza. Relazione che passa al contesto. L'alpha-equivalenza passa al contesto.

Lezione n. 28 - Friday 6 December 2019

Risoluzione di esercizi sulle funzioni ricorsive. Rappresentazione di liste mediante lambda termini.

Lezione n. 29 - Monday 9 December 2019

Definizione della beta-riduzione e della beta-equivalenza. Principali proprietà della beta-riduzione. Terminazione e confluenza. Strategia di riduzione di testa e relative proprietà.

Lezione n. 30 - Wednesday 11 December 2019

Proprieà di Church-Rosser. Dimostrazione che la beta-riduzione ha la proprietà di Church-Rosser. Unicità della forma normale. Riduzione di testa. Termini Risolubili. Equivalenza tra termini e risolubilità.

Lezione n. 31 - Friday 13 December 2019

Beta-riduzione. Numerali di Church. Principio di Induzione. Esempi di funzioni rappresentate mediante l'induzione.

Lezione n. 32 - Monday 16 December 2019

Rappresentazione dei Booleani nel lambda-calcolo. Operazioni logiche: congiunzione, disgiunzione, negazione, implicazione. Presentazione delle funzioni ricorsive.

Lezione n. 33 - Wednesday 18 December 2019

Teoremi di punto fisso nel lambda-calcolo. Rappresentazione dello schema di minimalizzazione.

Lezione n. 34 - Friday 20 December 2019

Rappresentazione di altri tipi di dato. Liste e Alberi.

Lezione n. 35 - Wednesday 8 January 2020

Riduzioni di lambda-termini mediante i grafi di condivisione.