22: Vorlesung und Übung| 0:00:00 Starten 0:00:10 2: Berechenbarkeitstheorie | 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These 0:00:41 Berechenbarkeit Hauptergebnis 0:01:26 2.2 Intuitiver Berechenbarkeitsbgegriff 0:01:48 Beispiel 0:07:15 2.3 LOOP-, WHILE-, GOTO (=Registermaschinen) und RAM-Berechenbarkeit 0:08:41 LOOP-Programme 0:10:29 Äquivalenz von Maschinenmodellen 0:12:04 Markov-Algorithmen 0:14:08 Zellularautomaten 0:15:16 2.4 Primitiv rekursive Funktionen 0:16:11 2.5 Die Ackermannfunktion 0:18:06 Mehr schnell wachsende Funktionen 0:19:06 Wissen über Fleißige Biber 0:20:12 2.6 Halterproblem, Unentscheidbarkeit, Reduzierbarkeit 0:21:05 Paradoxien und Selbstbezüglichkeit 0:22:07 Semi-Entscheidbarkeit 0:24:02 Rekursive Aufzählbarkeit 0:24:51 Äquivalente Aussagen 0:25:30 2.7 Nicht-entscheidbare Probleme 0:26:32 Gödelnummer einer Turingmaschine 0:26:52 Diagonalsprache 0:28:34 Universelle Turingmaschine 0:30:35 Halteproblem 0:31:48 Das beschränkte Halteproblem 0:31:57 Mehr unentscheidbare Probleme 0:32:46 Unentscheidbarkeit von Leerheit 0:33:50 Postsches Korrespondenzproblem (PKP) 0:34:32 Hilberts 10. Problem - Diophantische Gleichungen 0:35:05 Abgeschlossenheit entscheidbarer Sprachen 0:35:31 Nebenläufige Ausführung 0:36:11 Terminologie und Konventionen 0:36:26 Komplexitätsmaße 0:37:37 Obere Schranken 0:37:53 Untere Schranken: Lösungsansätze 0:38:43 Eine Komplexitätsklasse 0:41:07 Polynomiale Reduzierbarkeit 0:43:20 Beispiel 0:48:02 Weitere NP-vollständige Probleme 0:48:31 11. Übung 0:49:09 NP-Schwere Reduktionen