23: Halteproblem und Unentscheidbare Probleme in der Informatik
In dieser Episode werden zentrale Konzepte der Informatik behandelt, darunter Turingmaschinen, das Halteproblem, die Busy-Beaver-Funktion, reguläre Sprachen sowie die Unterschiede zwischen Akzeptoren und Entscheidern. Der Podcast beginnt mit einer Einführ
KIT Lehre und Wissen
1.0K views • Jan 29, 2019
About this video
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
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
Tags and Topics
Browse our collection to discover more content in these categories.
Video Information
Views
1.0K
Likes
6
Duration
01:29:05
Published
Jan 29, 2019
User Reviews
4.0
(1) Related Trending Topics
LIVE TRENDSRelated trending topics. Click any trend to explore more videos.
Trending Now