Teoretická informatika: Turingovy stroje

Turingovy stroje. Deterministický Turingův stroj. Konfigurace deterministického Turingova stroje. Krok výpočtu deterministického Turingova stroje. Výpočet deterministického Turingova stroje. Turingův stroj jako prostředek k vyčíslení funkcí. Turingův stroj jako akceptor jazyků. k-páskové Turingovy stroje. Převod k-páskového Turingova stroje na jednopáskový. Nedeterministický Turingův stroj. Determinizace Turingova stroje. Kódování Turingových strojů, univerzální Turingův stroj. Kontextové jazyky. Kontextové a monotónní gramatiky. Převod monotónní gramatiky na kontextovou gramatiku. Konstrukce monotónní gramatiky. Rekurzivní a rekurzivně vyčíslitelné jazyky. Důkazy rekurzivity a rekurzivní vyčíslitelnosti jazyků. Uzávěrové vlastnosti kontextových, rekurzivních a rekurzivně vyčíslitelných jazyků.

0:00:00 - Předehra
0:00:20 - Úvod
0:09:09 - Deterministický Turingův stroj
0:16:58 - Konfigurace deterministického Turingova stroje
0:23:15 - Krok výpočtu deterministického Turingova stroje
0:39:35 - Výpočet deterministického Turingova stroje
0:46:26 - Turingův stroj jako prostředek k vyčíslení funkcí
1:25:01 - Turingův stroj jako akceptor jazyků
1:51:32 - k-páskové Turingovy stroje
2:10:19 - Převod k-páskového Turingova stroje na jednopáskový
2:17:37 - Nedeterministický Turingův stroj
2:30:39 - Determinizace Turingova stroje
2:38:58 - Kódování Turingových strojů, univerzální Turingův stroj
2:58:29 - Kontextové jazyky
3:10:18 - Kontextové a monotónní gramatiky
3:19:04 - Převod monotónní gramatiky na kontextovou gramatiku
3:28:55 - Konstrukce monotónní gramatiky
3:36:25 - Rekurzivní a rekurzivně vyčíslitelné jazyky
3:51:36 - Důkazy rekurzivity a rekurzivní vyčíslitelnosti jazyků
5:20:29 - Uzávěrové vlastnosti kontextových, rekurzivních a rekurzivně vyčíslitelných jazyků
5:35:16 - Rekapitulace, nástin dalšího streamu
5:37:11 - Závěr
5:37:36 - Dohra