kurse:ef05a-2021:turingmaschinen:halting_problem [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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).