23: Grundbegriffe der Informatik, Vorlesung und Übung, WS 2018/19, 25.01.2019 Grundbegriffe der Informatik, Vorlesung, WS18/19

23 |
0:00:00 Start
0:00:05 Turingmaschinen
0:04:32 Unentscheidbare Probleme
0:04:59 Beispielcodierung
0:16:51 Das Halteproblem
0:19:24 Beweis mit Diagonalisierung
0:30:28 Weitere unentscheidbare Probleme
0:34:48 Erinnerung: BB3
0:36:22 Fleißige Biber und die Busy-Beaver-Funktion
0:43:20 Steam-Powered Turing Machine ;-)
0:44:04 Zusammenfassung
0:44:25 Beginn der Übung
0:44:56 Endlicher Akzeptor
0:48:28 Beispiele regulärer Sprachen
0:52:19 Akzeptoren: Komplement
0:54:53 Akzeptoren: Schnitt
0:59:54 Akzeptoren: Vereinigung
1:03:32 Reguläre Sprachen und kontextfreie Grammatiken
1:07:38 Turing-Maschinen (TMs)
1:17:10 Analyse: Zeit- und Platzbedarf
1:18:56 TM: Akzeptor, Entscheider
1:25:34 TMs und endliche Akzeptoren
1:27:35 Church-Turing-These