Search this site
Embedded Files
Skip to main content
Skip to navigation
Automi e Linguaggi
Informazioni generali
Organizzazione didattica
Videolezioni
Calendario
Esami
Valutazione
Automi e Linguaggi
Informazioni generali
Organizzazione didattica
Videolezioni
Calendario
Esami
Valutazione
More
Informazioni generali
Organizzazione didattica
Videolezioni
Calendario
Esami
Valutazione
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 [2
4
:
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:1
7
]
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 [2
7
:
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 [1
4
:
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
]
Google Sites
Report abuse
Page details
Page updated
Google Sites
Report abuse