Die Church-Turing-These (Theoretische Informatik)

Durch eine spezielle Turingmaschinenvariante und zwei fiktive Programmiersprachen namens TOLL und NICHSODOLL (eine Art Registermaschine) überzeugen wir uns, dass Turingmaschinen im Prinzip alles können, was "normale" Computer auch können. Das führt zur sogenannten Church-Turing-These und zum Begriff der Turingvollständigkeit. Nebenbei lernen wir noch, was Gödelisierung ist. Und fragen uns, was das mit künstlicher Intelligenz (KI) und Quantencomputern zu tun hat. Außerdem geht es um FRACTRAN, das Game of Life und Minecraft.
* Das GANZ NEUE Buch: weitz.de/GDM/
* Das NEUE Buch: weitz.de/PP/
* Skript: weitz.de/files/...
* Kurt Gödels bekanntestes Resultat: • Gödel (miss)verstehen ...
* Fundamentalsatz der Arithmetik: • Primzahlen - die Basics
* Sieb des Eratosthenes: • Das Sieb des Eratosthenes
* FRACTRAN: • Die einfachste Program...
* Quantencomputer: • Quantencomputer
* Game of Life: • Game of Life (JavaScript)
* Das Video im Playlist-Kontext: weitz.de/y/8zFv...
* Liste aller Videos: weitz.de/haw-vi...
* Das etwas andere Mathe-Lehrbuch: weitz.de/KMFI/
* Illustrationen von Heike Stephan: / haiartandillustration
* "FAQ": weitz.de/youtub...
0:00:00 Die Turingmaschine TM2012
0:09:00 Beispielprogramme in der TM2012
0:23:26 Was sind eigentlich Programme?
0:28:35 Gödelisierung
0:39:28 Die Programmiersprache TOLL
1:01:41 TOLL "verdummen"
1:11:09 Die Programmiersprache NICHSODOLL
1:17:43 TOLL in NICHSODOLL übersetzen
1:20:36 NICHSODOLL in TM2012 übersetzen
1:27:23 Turing-Äquivalenz der drei Modelle
1:33:31 Die Church-Turing-These
1:40:16 Turingvollständigkeit