Differences

This shows you the differences between two versions of the page.

--- kurse:ef05a-2021:turingmaschinen:halting_problem [2021/08/31 19:26] – [Konsequenzen] Ivo Blöchliger
+++ kurse:ef05a-2021:turingmaschinen:halting_problem [2021/09/16 06:33] (current) – [Literatur] Ivo Blöchliger
@@ Line 1: / Line 1: @@
+====== Hält die Maschine für gegebenen Input? ======
+Damit eine Maschine überhaupt eine Berechnung ausführen kann, muss diese Maschine irgendwann stoppen, damit das Resultat abgelesen werden kann.
+Die Frage stellt sich, ob eine gegebene Maschine mit gegebenem Input jemals anhält (und damit korrekt funktioniert (oder zumindest könnte)) oder eben nicht (endlos-Schlaufe).
+Wäre es nicht schön, eine Turing Maschine $H$ zu haben, die für eine gegebene Maschine $T$ mit gegebenem Input $I$ entscheidet, ob $T$ mit Eingabe $I$ jemals anhalten wird?
+===== Nummerierung aller Turingmaschinen =====
+Jede TM kann für z.B. unsere universelle TM codiert werden. Dieser Code, im Binärsystem gelesen, entspricht einer grossen natürlichen Zahl.
+So entspricht jeder TM genau eine Zahl. Aber nicht jede Zahl ergibt eine gültige Codierung einer TM (meist nicht).
+Man könnte aber eine TM definieren, die zu einer gegeben Zahl die nächst grösste Zahl bestimmt, die einer gültigen Codierung entspricht. Und damit hätte man eine eins-zu-eins Entsprechnung zwischen natürlichen Zahlen und TMs.
+Auf die gleiche Art und Weise kann der Input als Zahl aufgefasst werden.
+===== Die Haltemaschine $H$ =====
+$H$ ist die Maschine, die als Input die Codierung einer Maschine $T$ und einen zugehörigen Input $I$ entgegennimmt.
+Bei der Ausführung von $H$ mit Input $(T,I)$ gibt drei Möglichkeiten:
+  * $M$ hält mit der Meldung "$T$ hält auf Input $I$"
+  * $M$ hält mit der Meldung "$T$ hält nicht auf Input $I$"
+  * $M$ hält nie.
+Die letzte Möglichkeit möchten wir ausschliessen, weil damit wäre die Maschine $M$ unbrauchbar.
+===== Die Spielverderbermaschine $S$ =====
+Sei $S$ die Maschine, die als Input ebenfalls $(T, I)$ hat und wie folgt funktioniert:
+  * $S$ hält, wenn $H$ auf $(T,I)$ meldet, dass $T$ auf $I$ nicht hält.
+  * $S$ hält nie (endlos Schlaufe), wenn $H$ auf $(T,I)$ meldet, dass $T$ auf $I$ hält.
+===== Der Widerspruch =====
+Sei $I$ ein beliebiger Input. Was macht $H$ mit dem Input $(S,(S,I))$?
+Es gibt folgende zwei Möglichkeiten.
+  * $H$ meldet, dass $S$ auf $(S,I)$ **hält**. Das heisst, dass $H$ auf $(S,(S,I))$ berechnet hat, dass $S$ auf $(S,I)$ nicht hält. Widerspruch.
+  * $H$ meldet, dass $S$ auf $(S,I)$ **nicht hält**. Das heisst, dass $H$ auf $(S,(S,I))$ berechnet hat, dass $S$ auf $(S,I)$ **hält**. Widerspruch.
+Damit kann $H$ nicht existieren.
+Der Grund liegt hier in der möglichen Selbstreferenz von Turingmaschinen. Mit Selbstreferenz lassen sich sehr einfach Widersprüche erzeugen, wie z.B. die Aussage
+  «Diese Aussage ist falsch.»
+{{kurse:ef05a-2021:turingmaschinen:img_20210916_082444378.jpg}}
+===== Konsequenzen =====
+  * Es kann kein allgemeines Programm geben, das die korrekte Funktionsweise eines anderen Programms überprüft.
+    * In sehr eingeschränkten Szenarien ist es aber durchaus möglich, z.B. wurden so schon Fehler in kryptographischen Protokollen gefunden.
+  * Programmieren ist sauschwierig.
+  * Es ist nicht alles berechenbar. Mal abgesehen von den Resourcen gibt auch theoretische Grenzen, was überhaupt prinzipiell berechenbar ist.
+===== Literatur =====
+Roger Penrose, The Emperors new Mind, siehe z.B. https://en.wikipedia.org/wiki/The_Emperor%27s_New_Mind
+Die Bücher können bei Herrn Ivo Blöchliger ausgeliehen werden (vorausgesetzt, er findet die noch).