Turingmaschine als Rechner

Die letzten Beispiele haben gezeigt, dass die Turingmaschine in der Lage ist Berechnungen auf Binärzahlen durchzuführen.

Der Graph der hier gegebenen Turingmaschine teilt die auf dem Band stehende Binärzahl durch 2.

Eine Funktion f heißt Turing-berechenbar, wenn es eine TM gibt, die f wie folgt berechnet:

• im Startzustand mit dem Eingabewort w beginnend
• durch definierte Zustandsübergänge in einem Endzustand hält und
• das Wort v auf das Band geschrieben hat.

Die Division einer Binärzahl durch 2 ist also Turing-berechenbar. Eine Berechnung ist eine schrittweise, nach bestimmten Regeln durchgeführte Manipulationen der Zeichen auf dem Band. Die Zeichen können Codierungen von Zahlen oder Zeichen darstellen. Damit beschreibt eine Turingmaschine eine Funktion = Programm = Algorithmus, die nach bestimmten Regeln Eingaben auf dem Band in Ausgaben auf das Band abbildet. 

Church-Turing-These

Alonzo Church und Alan Turing stellten eine These auf, die von den meisten Informatikern akzeptiert wird: 

„Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.“

Das Modell der Turingmaschine mathematisiert damit die Begriffe Algorithmus und Berechenbarkeit.

Ein Algorithmus ist nicht anderes als eine intuitiv berechenbare Funktion und somit eine Turingmaschine. Somit wird aus der "Verarbeitungsvorschrift, die aus einer endlichen Folge von eindeutig ausführbaren Anweisungen besteht, mit der eine Vielzahl gleichartiger Aufgaben gelöst werden können und die Eigenschaften Endlichkeit, Ausführbarkeit, Terminiertheit, Eindeutigkeit und Allgemeingültigkeit hat" das mathematische Modell Turingmaschine, kurz: Programm = Algorithmus = Turingmaschine.

Verhältnis von berechenbaren Funktionen (Turingmaschinen/Algorithmen) zu definierbaren Funktionen 

Wie viele Funktionen kann man eigentlich definieren und wie viele davon berechnen? Beide Mengen sind unendlich groß. Lasst uns da mal zuerst über Unendlichkeit reden.

• kurzer Clip (ca 1,5 Minute):
• langer Clip (ca. 10 Minuten):

Man kann mithilfe des systematischen Durchzählens beweisen, dass die Menge der berechenbaren Funktionen - also der Turingmaschinen - abzählbar unendlich groß ist. Die Menge der definierbaren Funktionen ist beweisbar überabzählbar unendlich groß. Damit ergibt sich die Konsequenz, dass es definierbare Funktionen gibt, die nicht berechenbar sind und demzufolge sich nicht mit Hilfe einer Turingmaschine lösen lassen.

Es gibt definierbare Funktionen, die nicht algorithmisch lösbar sind. 

Vertiefung: 

• Inf-Schule: Aufzählung aller Turingmaschinen 
• Inf-Schule: Existenz nichtberechenbarer Funktionen

Beispiel für eine nicht berechenbare Funktion - das Halteproblem

Lothar Collatz stellte 1937 folgendes Problem vor. Endet die Folge

stets auf 1 für beliebige natürliche Zahlen a₀?

Beispiele:

• a₀ = 23: 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
• a₀ = 49: 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
• a₀ = 75: 75, 226, 113, 340, 170, 85, 256, 128, 64, 32, 16, 8, 4, 2, 1

Aufgabe: Entwickeln Sie unter Verwendung des Struktogramms ein Programm zur Berechnung der Collatz-Folge für beliebige Startwerte. Untersuchen Sie, ob der Algorithmus für verschiedene Startwerte stoppt.

Stopp-Tester

Die entwickelte Software untersucht letztlich stets eine endliche Menge von Eingaben und prüft, ob die Folge auf Eins endet. Bisher hat man dies für alle Zahlen bis 20·2⁵⁸ (lt. Spiegel 2011) positiv beantworten können. Dennoch könnte schon die nächste Zahl das Programm in eine Endlosschleife führen. Sinnvoll wäre ein Programm, mit dessen Hilfe man für jedes beliebige Programm entscheiden kann, ob es mit jeder beliebigen Eingabe nach endlich vielen Schritten abbricht oder nicht?

Dies dürfte kein Problem sein, da jedes Programm als eine Zeichenkette dargestellt werden kann und damit als Eingabe für das Stopp-Test-Programm dienen kann. Man könnte sogar für Testzwecke das Stopp-Programm selbst als Eingabe nutzen. Die Informatiker nennen dies "Selbstanwendbarkeitsproblem".

Wie kann so ein Algorithmus aussehen?
Sicherlich ist ein bestimmter Programmvorbau notwendig. Da jedoch zum Ende des Algorithmus die Ausgabe der Entscheidung ansteht, hat das - verbal beschrieben - Programm sicherlich folgende Gestalt, wobei stopp eine boolesche Variable ist, die vorher berechnet wurde.

BEGIN
  {...}
  IF (stopp)
  THEN Ausgabe: "Das Programm ist selbststoppend."
  ELSE Ausgabe: "Das Programm ist nicht selbststoppend."
END.

Wenn dieses Programm existiert, dann könnte ein Programmierer den Quelltext aber auch ändern und so das Programm SELTSAM erschaffen:

BEGIN
  {...}
  IF (stopp)
  THEN Ausgabe: "Das Programm ist selbststoppend."
       WHILE (true) DO //nichts
  ELSE Ausgabe: "Das Programm ist nicht selbststoppend."
END.

Ist Seltsam selbststoppend oder nicht?

Angenommen es ist selbststoppend. Startet man nun das Programm SELTSAM und gibt ihm seinen Quelltext als Eingabe, so wird der gleiche Algorithmus abgearbeitet, wie beim Stopp-Test und damit die Variable stopp auf true gesetzt. Das Programm gibt nun aus, dass es selbststoppend ist, bleibt aber dann in der Endlosschleife hängen, ist also nicht selbststoppend. Damit steht es im Widerspruch zur Annahme.

Angenommen es ist nicht selbststoppend. Auch hier wird das Programm SELTSAM wie oben beschrieben abgearbeitet und die Variable stopp erhält den Wert false. Der Algorithmus gibt nun aus "Das Programm ist nicht selbststoppend", hält aber anschließend. Damit ist aber wieder ein Widerspruch zur Annahme vorhanden.

Da SELTSAM weder die Eigenschaft "selbststoppend" noch deren logische Negation besitzt, kann es nach den Gesetzen der Logik nicht existieren. Da es formal aus dem ersten Programm entwickelt wurde, kann es aber auch kein Programm Stopp-Tester geben.

Resümee:

Es ist nicht möglich von einem beliebigen Programm zu sagen, ob es nach endlich vielen Schritten stoppt oder nicht! Damit wurde (beweisbar) ein Problem gefunden, dass nicht mit Hilfe des Computers gelöst werden kann.

Vertiefung/Visualisierung: 

• Florian Dalwigk:
• Udiprod: Proof that computer can't do everything