Rekursionstheorie, das Halteproblem und der Satz von Rice (Theoretische Informatik)

Das historisch bedeutsame Resultat von Turing und die gleichsam dramatische Verallgemeinerung von Rice. Wann bezeichnet man Funktionen als berechenbar oder Mengen als entscheidbar? Inwiefern kann etwas nur "halb entscheidbar" sein und was hat das mit rekursivem Aufzählen zu tun? Was machen universelle Turingmaschinen? Welche Fragen können Computer nicht beantworten? Und was haben fleißige Biber damit zu tun?
* Das GANZ NEUE Buch: weitz.de/GDM/
* Das NEUE Buch: weitz.de/PP/
* Skript: weitz.de/files/ti-skript.pdf
* KORREKTUREN: weitz.de/corr/tZkCBWM43pM
* Cantors 1. Diagonalargument: • Die Menge der rational...
* Cantors 2. Diagonalargument: • Die Menge der reellen ...
* Mehr zum Thema Unendlichkeit: • Das Banach-Tarski-Para...
* Gödels Unvollständigkeitssätze: • Gödel (miss)verstehen ...
* Das Video im Playlist-Kontext: weitz.de/y/tZkCBWM43pM?list=PL...
* Liste aller Videos: weitz.de/haw-videos/
* Das etwas andere Mathe-Lehrbuch: weitz.de/KMFI/
* "FAQ": weitz.de/youtube.html
0:00:00 Berechenbarkeit
0:04:11 Entscheidbarkeit / Rekursivität
0:07:15 Turingmaschinen, die mit Zahlen arbeiten
0:14:16 Semi-entscheidbare Mengen
0:16:30 Rekursiv aufzählbare Mengen
0:19:03 Äquivalenz der beiden Begriffe
0:25:25 Maschinenbeschreibungen / Standardaufzählung
0:33:14 Universelle Turingmaschinen
0:39:38 Turings Halteproblem
0:47:40 Das gleichmäßige Halteproblem
0:52:38 Fleißige Biber
0:58:23 Der Satz von Rice
1:04:17 Konsequenzen aus dem Satz von Rice
Corrections:
21:49 Bitte beachten Sie die Korrekturhinweise in der Videobeschreibung.