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

• [-] lunedì ore 10.00-12.00 (lezione, Aula A-108, via della vasca navale);
• [-] mercoledì ore 10.00-12.00 (lezione, Aula A-108, via della vasca navale);
• [-] venerdì ore 10.00-12.0012.00-14.00 (lezione/esercitazione, Laboratorio di Informatica)

Lezione n. 1 - Monday 21 September 2020

Introduzione al corso. Cenni storici sulla teoria della calcolabilità.

Lezione n. 2 - Wednesday 23 September 2020

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. Insiemi decidibili per automa. Esercizio sulla decidibilita` per automa finito. Rappresentazione come grafo degli automi. Rappresentazione come matrice di adiacenza.

Lezione n. 3 - Monday 28 September 2020

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. 4 - Wednesday 30 September 2020

Insiemi regolari. Proprieta` di chiusura degli insiemi regolari. Automi Non-deterministici. Automi con transizioni epsilon.

Lezione n. 5 - Friday 2 October 2020

Introduzione a Wolfram Mathematica. Esperimenti sugli automi con la libreria TM-lib.ma.

Lezione n. 6 - Monday 5 October 2020

Lezione n. 7 - Wednesday 7 October 2020

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 - Friday 9 October 2020

Esercizi di programmazione di automi e macchine di Turing con mathematica. Programmazione di ordine superiore.

Lezione n. 9 - Monday 12 October 2020

Lezione n. 10 - Wednesday 14 October 2020

Lezione n. 11 - Friday 16 October 2020

Lezione n. 12 - Monday 19 October 2020

Lezione n. 13 - Wednesday 21 October 2020

Lezione n. 14 - Friday 23 October 2020

Lezione n. 15 - Friday 30 October 2020

Lezione n. 16 - Monday 2 November 2020

Lezione n. 17 - Wednesday 4 November 2020

Lezione n. 18 - Friday 6 November 2020

Lezione n. 19 - Monday 16 November 2020

Lezione n. 20 - Friday 20 November 2020

Lezione n. 21 - Monday 23 November 2020

Fine dimostrazione del teorema di equivalenza tra funzioni ricorsive e funzioni Turing computabili.

Lezione n. 22 - Wednesday 25 November 2020

Lezione n. 23 - Friday 27 November 2020

Lezione n. 24 - Monday 30 November 2020

Funzioni Costruibili in Tempo

Lezione n. 25 - Wednesday 2 December 2020

Lezione n. 26 - Friday 4 December 2020

Lezione n. 27 - Monday 7 December 2020

Lezione n. 28 - Wednesday 9 December 2020

Definizione dell'insieme dei lambda-termini. Interpretazione di alcuni lambda-termini come

Lezione n. 29 - Friday 11 December 2020

Proprietà della sostituzione semplice.

Lezione n. 30 - Monday 14 December 2020

Lezione n. 31 - Wednesday 16 December 2020

Lezione n. 32 - Friday 18 December 2020

Lezione n. 33 - Monday 21 December 2020