Automi e Linguaggi - Videolezioni II

Videolezioni, parte II: teoria della computabilità

Lezione 12

Parte 1: La gerarchia di linguaggi di Chomsky [12:20]

Parte 2: Introduzione alla macchina di Turing [12:17]

Parte 3: Definizione formale della macchina di Turing [25:42]

Parte 4: Linguaggi ricorsivamente enumerabili e linguaggi ricorsivi [9:14]

Parte 5: Esercizio: costruzione di una macchina di Turing [30:11]

Lezione 13

Parte 1: Esercizio: è decidibile stabilire se un numero è una potenza di due [17:32]

Parte 2: Esercizio: è decidibile stabilire se un numero è il prodotto di altri due [26:53]

Parte 3: Varianti del modello di macchina di Turing e loro equivalenza [29:44]

Parte 4: Macchine di Turing non deterministiche [25:36]

Lezione 14

Parte 1: Enumeratori e linguaggi ricorsivamente enumerabili [19:37]

Parte 2: Definizione di algoritmo: la Tesi di Church-Turing [8:39]

Parte 3: Esempi di relazione tra problema computazionale e linguaggio [18:52]

Parte 4: Problemi decidibili relativi a linguaggi regolari e liberi dal contesto [24:10]

Parte 5: Altri problemi decidibili relativi a linguaggi regolari e liberi dal contesto [24:45]

Lezione 15

Parte 1: Riepilogo sui problemi relativi ad automi a stati finiti e grammatiche libere dal contesto [17:17]

Parte 2: La macchina di Turing universale [7:59]

Parte 3: Il problema di accettazione delle TM ed il metodo di diagonalizzazione di Cantor [13:19]

Parte 4: Esistenza di infiniti linguaggi non ricorsivamente enumerabili [18:34]

Parte 5: Il problema di accettazione delle TM non è decidibile [21:33]

Parte 6: Il problema della fermata delle TM [13:09]

Lezione 16

Parte 1: Ulteriori problemi indecidibili relativi a macchine di Turing [21:42]

Parte 2: Il teorema di Rice [17:00]

Parte 3: Problemi indecidibili relativi ad automi linearmente limitati [27:09]

Parte 4: Problemi indecidibili relativi a grammatiche libere dal contesto [29:26]

Lezione 17

Parte 1: Il Problema della Corrispondenza di Post (PCP) [23:40]

Parte 2: Il Problema della Corrispondenza di Post è non decidibile [18:36]

Parte 3: Esempio di riduzione tra il problema di accettazione di una TM e PCP [20:52]

Parte 4: Riducibilità mediante funzione calcolabile e decidibilità [19:35]

Parte 5: Riducibilità mediante funzione calcolabile e linguaggi ricorsivamente enumerabili [14:14]

Lezione 18

Parte 1: La macchina di Turing autoreferenziale (SELF) [20:12]

Parte 2: Il Teorema di Ricorsione [15:35]

Parte 3: Applicazioni del Teorema di Ricorsione [19:45]

Parte 4: Macchine di Turing con oracolo e riducibilità secondo Turing [18:53]

Parte 5: Misurazione quantitativa della informazione [19:02]

Lezione 19

Parte 1: Complessità di Kolmogorov: introduzione [19:14]

Parte 2: Complessità di Kolmogorov: definizione e risultati [25:58]

Parte 3: Ottimalità della complessità di Kolmogorov e stringhe incompressibili [15:26]

Parte 4: Relazione tra la complessità di Kolmogorov ed il problema della fermata delle macchine di Turing [17:43]

Parte 5: Le macchine Busy Beaver e le funzioni non calcolabili associate [19:13]

Lezione 20

Parte 1: Formule, sentenze e regole della logica del primo ordine [17:47]

Parte 2: Modelli e verità delle sentenze in un modello [15:41]

Parte 3: Decidibilità delle sentenze vere del modello dei numeri naturali con l'operazione di somma [28:42]

Parte 4: Indecidibilità delle sentenze vere del modello dei numeri naturali con le operazioni di somma e prodotto [`7:28]

Parte 5: Sistemi formali consistenti, completi e robusti, ed il Teorema di Completezza di Gödel [16:38]

Parte 6: I Teoremi di Incompletezza di Gödel [12:13]

Page updated

Google Sites

Report abuse