Videolezioni, parte II: teoria della computabilità
Lezione 12
Lezione 12
Parte 1: La gerarchia di linguaggi di Chomsky [12:20]
Parte 1: La gerarchia di linguaggi di Chomsky [12:20]
lez-12-01.mp4Parte 2: Introduzione alla macchina di Turing [12:17]
Parte 2: Introduzione alla macchina di Turing [12:17]
lez-12-02.mp4Parte 3: Definizione formale della macchina di Turing [25:42]
Parte 3: Definizione formale della macchina di Turing [25:42]
lez-12-03.mp4Parte 4: Linguaggi ricorsivamente enumerabili e linguaggi ricorsivi [9:14]
Parte 4: Linguaggi ricorsivamente enumerabili e linguaggi ricorsivi [9:14]
lez-12-04.mp4Parte 5: Esercizio: costruzione di una macchina di Turing [30:11]
Parte 5: Esercizio: costruzione di una macchina di Turing [30:11]
lez-12-05.mp4Lezione 13
Lezione 13
Parte 1: Esercizio: è decidibile stabilire se un numero è una potenza di due [17:32]
Parte 1: Esercizio: è decidibile stabilire se un numero è una potenza di due [17:32]
lez-13-01.mp4Parte 2: Esercizio: è decidibile stabilire se un numero è il prodotto di altri due [26:53]
Parte 2: Esercizio: è decidibile stabilire se un numero è il prodotto di altri due [26:53]
lez-13-02.mp4Parte 3: Varianti del modello di macchina di Turing e loro equivalenza [29:44]
Parte 3: Varianti del modello di macchina di Turing e loro equivalenza [29:44]
lez-13-03.mp4Parte 4: Macchine di Turing non deterministiche [25:36]
Parte 4: Macchine di Turing non deterministiche [25:36]
lez-13-04.mp4Lezione 14
Lezione 14
Parte 1: Enumeratori e linguaggi ricorsivamente enumerabili [19:37]
Parte 1: Enumeratori e linguaggi ricorsivamente enumerabili [19:37]
lez-14-01.mp4Parte 2: Definizione di algoritmo: la Tesi di Church-Turing [8:39]
Parte 2: Definizione di algoritmo: la Tesi di Church-Turing [8:39]
lez-14-02.mp4Parte 3: Esempi di relazione tra problema computazionale e linguaggio [18:52]
Parte 3: Esempi di relazione tra problema computazionale e linguaggio [18:52]
lez-14-03.mp4Parte 4: Problemi decidibili relativi a linguaggi regolari e liberi dal contesto [24:10]
Parte 4: Problemi decidibili relativi a linguaggi regolari e liberi dal contesto [24:10]
lez-14-04.mp4Parte 5: Altri problemi decidibili relativi a linguaggi regolari e liberi dal contesto [24:45]
Parte 5: Altri problemi decidibili relativi a linguaggi regolari e liberi dal contesto [24:45]
lez-14-05.mp4Lezione 15
Lezione 15
Parte 1: Riepilogo sui problemi relativi ad automi a stati finiti e grammatiche libere dal contesto [17:17]
Parte 1: Riepilogo sui problemi relativi ad automi a stati finiti e grammatiche libere dal contesto [17:17]
lez-15-01.mp4Parte 2: La macchina di Turing universale [7:59]
Parte 2: La macchina di Turing universale [7:59]
lez-15-02.mp4Parte 3: Il problema di accettazione delle TM ed il metodo di diagonalizzazione di Cantor [13:19]
Parte 3: Il problema di accettazione delle TM ed il metodo di diagonalizzazione di Cantor [13:19]
lez-15-03.mp4Parte 4: Esistenza di infiniti linguaggi non ricorsivamente enumerabili [18:34]
Parte 4: Esistenza di infiniti linguaggi non ricorsivamente enumerabili [18:34]
lez-15-04.mp4Parte 5: Il problema di accettazione delle TM non è decidibile [21:33]
Parte 5: Il problema di accettazione delle TM non è decidibile [21:33]
lez-15-05.mp4Parte 6: Il problema della fermata delle TM [13:09]
Parte 6: Il problema della fermata delle TM [13:09]
lez-15-06.mp4Lezione 16
Lezione 16
Parte 1: Ulteriori problemi indecidibili relativi a macchine di Turing [21:42]
Parte 1: Ulteriori problemi indecidibili relativi a macchine di Turing [21:42]
lez-16-01.mp4Parte 2: Il teorema di Rice [17:00]
Parte 2: Il teorema di Rice [17:00]
lez-16-02.mp4Parte 3: Problemi indecidibili relativi ad automi linearmente limitati [27:09]
Parte 3: Problemi indecidibili relativi ad automi linearmente limitati [27:09]
lez-16-03.mp4Parte 4: Problemi indecidibili relativi a grammatiche libere dal contesto [29:26]
Parte 4: Problemi indecidibili relativi a grammatiche libere dal contesto [29:26]
lez-16-04.mp4Lezione 17
Lezione 17
Parte 1: Il Problema della Corrispondenza di Post (PCP) [23:40]
Parte 1: Il Problema della Corrispondenza di Post (PCP) [23:40]
lez-17-01.mp4Parte 2: Il Problema della Corrispondenza di Post è non decidibile [18:36]
Parte 2: Il Problema della Corrispondenza di Post è non decidibile [18:36]
lez-17-02.mp4Parte 3: Esempio di riduzione tra il problema di accettazione di una TM e PCP [20:52]
Parte 3: Esempio di riduzione tra il problema di accettazione di una TM e PCP [20:52]
lez-17-03.mp4Parte 4: Riducibilità mediante funzione calcolabile e decidibilità [19:35]
Parte 4: Riducibilità mediante funzione calcolabile e decidibilità [19:35]
lez-17-04.mp4Parte 5: Riducibilità mediante funzione calcolabile e linguaggi ricorsivamente enumerabili [14:14]
Parte 5: Riducibilità mediante funzione calcolabile e linguaggi ricorsivamente enumerabili [14:14]
lez-17-05.mp4Lezione 18
Lezione 18
Parte 1: La macchina di Turing autoreferenziale (SELF) [20:12]
Parte 1: La macchina di Turing autoreferenziale (SELF) [20:12]
lez-18-01.mp4Parte 2: Il Teorema di Ricorsione [15:35]
Parte 2: Il Teorema di Ricorsione [15:35]
lez-18-02.mp4Parte 3: Applicazioni del Teorema di Ricorsione [19:45]
Parte 3: Applicazioni del Teorema di Ricorsione [19:45]
lez-18-03.mp4Parte 4: Macchine di Turing con oracolo e riducibilità secondo Turing [18:53]
Parte 4: Macchine di Turing con oracolo e riducibilità secondo Turing [18:53]
lez-18-04.mp4Parte 5: Misurazione quantitativa della informazione [19:02]
Parte 5: Misurazione quantitativa della informazione [19:02]
lez-18-05.mp4Lezione 19
Lezione 19
Parte 1: Complessità di Kolmogorov: introduzione [19:14]
Parte 1: Complessità di Kolmogorov: introduzione [19:14]
lez-19-01.mp4Parte 2: Complessità di Kolmogorov: definizione e risultati [25:58]
Parte 2: Complessità di Kolmogorov: definizione e risultati [25:58]
lez-19-02.mp4Parte 3: Ottimalità della complessità di Kolmogorov e stringhe incompressibili [15:26]
Parte 3: Ottimalità della complessità di Kolmogorov e stringhe incompressibili [15:26]
lez-19-03.mp4Parte 4: Relazione tra la complessità di Kolmogorov ed il problema della fermata delle macchine di Turing [17:43]
Parte 4: Relazione tra la complessità di Kolmogorov ed il problema della fermata delle macchine di Turing [17:43]
lez-19-04.mp4Parte 5: Le macchine Busy Beaver e le funzioni non calcolabili associate [19:13]
Parte 5: Le macchine Busy Beaver e le funzioni non calcolabili associate [19:13]
lez-19-05.mp4Lezione 20
Lezione 20
Parte 1: Formule, sentenze e regole della logica del primo ordine [17:47]
Parte 1: Formule, sentenze e regole della logica del primo ordine [17:47]
lez-20-01.mp4Parte 2: Modelli e verità delle sentenze in un modello [15:41]
Parte 2: Modelli e verità delle sentenze in un modello [15:41]
lez-20-02.mp4Parte 3: Decidibilità delle sentenze vere del modello dei numeri naturali con l'operazione di somma [28:42]
Parte 3: Decidibilità delle sentenze vere del modello dei numeri naturali con l'operazione di somma [28:42]
lez-20-03.mp4Parte 4: Indecidibilità delle sentenze vere del modello dei numeri naturali con le operazioni di somma e prodotto [`7:28]
Parte 4: Indecidibilità delle sentenze vere del modello dei numeri naturali con le operazioni di somma e prodotto [`7:28]
lez-20-04.mp4Parte 5: Sistemi formali consistenti, completi e robusti, ed il Teorema di Completezza di Gödel [16:38]
Parte 5: Sistemi formali consistenti, completi e robusti, ed il Teorema di Completezza di Gödel [16:38]
lez-20-05.mp4Parte 6: I Teoremi di Incompletezza di Gödel [12:13]
Parte 6: I Teoremi di Incompletezza di Gödel [12:13]
lez-20-06.mp4