23: Halteproblem und Unentscheidbare Probleme in der Informatik

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 Dozenten: Dr. Thomas Worsch | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik Vorlesungsaufzeichnung: KIT | WEBCAST http://webcast.kit.edu