25 |

0:00:00 Starten

0:00:04 Kapitel 20: Turingmaschinen

0:00:25 Wo sind wir?

0:01:45 Codierungen von Turingmaschinen

0:04:54 Beispielcodierung

0:09:44 Eigenschaften dieser und ähnlicher Codierungen

0:11:50 Das Halteproblem ist unentscheidbar

0:18:37 Diagonalisierung

0:24:07 Das Halteproblem

0:24:22 Beweis der Unentscheidbarkeit des Halteproblems

0:28:37 Weitere unentscheidbare Probleme

0:36:10 Erinnerung: BB3

0:37:03 Bibermaschinen

0:38:26 Busy-Beaver-Funktion

0:42:51 Was ist wichtig

0:43:53 Steam-Powered Turing Machine

0:47:48 Zusammenfassung

0:51:51 Kapitel 21: Relationen

0:52:28 Überblick

0:52:51 Äquivalenzrelationen

0:53:41 Identität

0:54:18 Kongruenz ganzer Zahlen modulo n

0:55:12 Beispiel: asymptotisch gleiches Wachstum

0:55:24 Urbilder von Funktionswerten

0:57:50 Bild einer Äquivalenzrelation

0:59:27 Äquivalenzklassen und Faktormengen

1:00:40 Beispiel: Äquivalenzklassen und Kogruenz modulo 2

1:02:21 Was ist wichtig

1:02:49 Äquivalenzrelationen auf Mengen mit ""Struktur""

1:03:27 Verträglichkeit von Äquivalenzrelationen mit Abbildungen

1:05:49 Kongruenzrelation

1:06:28 Eine Operation für Äquivalenzklassen modulo n?

1:08:20 Verträglichkeit erlaubt die Übertragung einer Abbildung auf der Faktormenge

1:09:14 eine Operation für Äquivalenzklassen modulo n?

1:10:10 Was ist wichtig

1:10:54 Wo sind wir?

1:11:02 Motivation

1:13:02 Äquivalenzrelationen von Nerode einer Sprache

1:14:30 Beispiel

1:18:35 Die Nerode-Relation is immer eine Äquivalenzrelationen

1:19:09 Verträglichkeit: Beisoiel Nerode-Äquivalenzen

1:20:44 Eine Abbildung für Nerode-Äquivalenzklassen

1:21:22 Nerode-Äquivalenzen: Ausblick