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

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

Lezione n. 1 - Monday 24 September 2018

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. Monoide delle parole di un certo alfabeto.

Lezione n. 2 - Wednesday 26 September 2018

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. Insiemi decidibili per automa.

Lezione n. 3 - Friday 28 September 2018

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 - Monday 1 October 2018

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. 5 - Wednesday 3 October 2018

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. 6 - Friday 5 October 2018

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. 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. 7 - Monday 8 October 2018

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. 8 - Wednesday 10 October 2018

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

Lezione n. 9 - Friday 12 October 2018

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. 10 - Monday 15 October 2018

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

Lezione n. 11 - Wednesday 17 October 2018

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

Lezione n. 12 - Monday 22 October 2018

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. 13 - Wednesday 24 October 2018

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

Lezione n. 14 - Wednesday 31 October 2018

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. 15 - Monday 12 November 2018

Equivalenza tra decidibilita' e Turing calcolabilita' della funzione caratteristica. Equivalenza tra Turing calcolabilita' e decidibilita' del grafico di una funzione. Funzioni Turing Computabili: chiusura per composizione seriale, composizione parallela e ricorsione primitiva.

Lezione n. 16 - Wednesday 14 November 2018

Lezione n. 17 - Friday 16 November 2018

Lezione n. 18 - Monday 19 November 2018

Lezione n. 19 - Wednesday 21 November 2018

Fine dimostrazione della rappresentazione ricorsiva delle funzioni Turing computabili. Definizione di macchina di Turing Universale.

Lezione n. 20 - Friday 23 November 2018

Indecidibilita` del problema dell'arresto.

Lezione n. 21 - Monday 26 November 2018

Funzioni Costruibili in tempo. Chiusura per composizione e per prodotto. Esempi di funzioni costruibili in tempo.

Lezione n. 22 - Wednesday 28 November 2018

Costruzione della gerarchia in tempo.

Lezione n. 23 - Friday 30 November 2018

Introduzione al lambda-calcolo. Relazione con le dimostrazioni in deduzione naturale. Corrispondenza tra eliminazione del taglio e beta-riduzione. Rappresentazione degli interi (numerali di Church). Esistenza di termini con sequenza di riduzione infinita (il termine omega).

Lezione n. 24 - Monday 3 December 2018

Decidibilta` degli insiemi proiezione. Esistenza di insiemi decidibili la cui proiezione e` semidecidibile ma non decidibile. Definizione di classe di complessita` non-deterministica basata sulla decidibilita` 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 complessita` deterministiche e le due non-deterministiche (proiezioni e oracolo). Teorema di equivalenza.

Lezione n. 25 - Wednesday 5 December 2018

Equivalenza delle classi di complessita' derivanti dalle diverse nozioni di calcolo non-deterministico. Classi di complessita' P ed NP. Definizione induttiva dell'insieme dei

Lezione n. 26 - Monday 10 December 2018

Lezione n. 27 - Wednesday 12 December 2018

Lezione n. 28 - Wednesday 19 December 2018

Rappresetazione forte di fuzioni numeriche nel lambda calcolo.

Lezione n. 29 - Friday 21 December 2018

Teorema di Lambda-definibilita' (solo funzioni di base)