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 Manipulation der Zeichen auf dem Band. Die Zeichen können Codierungen von Zahlen oder Zeichen darstellen. Eine Turingmaschine kann einen Algorithmus modellieren. Führt sie eine Berechnung durch, bildet sie eine Eingabe auf eine Ausgabe ab und berechnet damit eine Funktion. 

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.

Die Church-Turing-These besagt vereinfacht: Alles, was sich überhaupt algorithmisch berechnen lässt, kann auch von einer Turingmaschine berechnet werden. Damit liefert die Turingmaschine ein grundlegendes Modell für die Begriffe Algorithmus und Berechenbarkeit. 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.

nur für den LK: 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 Probleme, für die kein Algorithmus existiert. 

Vertiefung: 

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

Das Halteproblem

Dass ein Programm sehr lange rechnet, bedeutet noch nicht, dass es niemals anhalten wird.

Hält ein Algorithmus immer an?

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. Springer 2025) positiv beantworten können. Dennoch könnte schon die nächste Zahl das Programm in eine Endlosschleife führen.

Kann ein Algorithmus für ein beliebiges Programm P und eine beliebige Eingabe E entscheiden, ob P mit E nach endlich vielen Schritten anhält?

Angenommen, es gäbe einen Stopp-Tester. Diesem übergeben wir ein beliebiges Programm und eine zugehörige Eingabe. Der Stopp-Tester soll stets nach endlich vielen Schritten entscheiden, ob dieses Programm mit dieser Eingabe anhält oder endlos weiterläuft.

Da ein Programm als Zeichenfolge gespeichert werden kann, kann auch der Programmtext selbst eine Eingabe sein. Wir können einen Stopp-Tester deshalb insbesondere fragen, ob ein Programm anhält, wenn es seinen eigenen Programmtext als Eingabe erhält. Ein Programm nennen wir hier selbststoppend, wenn es anhält, sobald sein eigener Programmtext als Eingabe verwendet wird.

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 ...
       WHILE (true) DO //nichts
  ELSE ...
END.

Ist Seltsam selbststoppend oder nicht?

Fall 1: Der Stopp-Tester sagt voraus, dass SELTSAM anhält.

Dann führt SELTSAM absichtlich eine Endlosschleife aus. Es hält also nicht. Die Vorhersage ist falsch.

Fall 2: Der Stopp-Tester sagt voraus, dass SELTSAM nicht anhält.

Dann beendet sich SELTSAM. Es hält also doch. Auch diese Vorhersage ist falsch.

In beiden Fällen entsteht ein Widerspruch. Der Fehler kann nicht in der Konstruktion von SELTSAM liegen, sondern nur in unserer ursprünglichen Annahme: Ein Stopp-Tester, der für jedes beliebige Programm und jede beliebige Eingabe korrekt entscheidet, ob das Programm anhält, kann nicht existieren.

Resümee:

Es gibt keinen Algorithmus, der für jedes beliebige Programm und jede beliebige Eingabe entscheiden kann, ob das Programm nach endlich vielen Schritten anhält. Das Halteproblem ist damit algorithmisch nicht entscheidbar. Es zeigt eine prinzipielle Grenze der Berechenbarkeit und damit auch der Turingmaschine. Damit haben wir ein Problem gefunden, das grundsätzlich nicht durch einen Algorithmus für alle möglichen Eingaben gelöst werden kann.

Vertiefung/Visualisierung: 

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