KIT | KIT-Bibliothek | Impressum | Datenschutz

Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 28.01.2016, Vorlesung und Übung - 22

Sanders, Peter; Hübschle-Schneider, Lorenz; Maier, Tobias ORCID iD icon

Abstract:

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
... mehr


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 01.02.2016
Erstellungsdatum 28.01.2016
Sprache Deutsch
DOI 10.5445/DIVA/2016-131
Identifikator KITopen-ID: 1000113748
Lizenz KITopen-Lizenz
Serie Theoretische Grundlagen der Informatik, Vorlesung, WS 2015/2016
Folge 23
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page