Alan Turing - Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem (1937)

Alan Mathison Turing
*23. Juni 1912 †7. Juni 1954

Alan Turing war seinerzeit einer der angesehensten Mathematiker Englands und fiel früh durch seine mathematische Begabung auf. Im Zweiten Weltkrieg arbeitete er in Bletchley Park an einem streng geheimen staatlichen Projekt zur Entschlüsselung der nationalsozialistischen Verschlüsselungsmaschine ENIGMA. Mit der endgültigen Entschlüsselung im Dezember 1942 waren sämtliche deutschen Funksprüche für die Alliierten zugänglich, was eine entscheidende Wende des Krieges und den Untergang der deutschen Marine-Übermacht bedeutete.
Wir behandeln hier den 1937 von Turing veröffentlichten Aufsatz "Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem". Hier entwickelt er das Modell einer Maschine, die später zu den grundlegenden Konzepten der Informatik werden soll.
1952 wurde Alan Turing wegen homosexueller Handlungen zu chemischer Kastration durch eine Hormonbehandlung verurteilt. Infolgedessen erkrankte er an einer Depression und starb 1954 wahrscheinlich durch Suizid durch einen mit Cyanid vergifteten Apfel. Allerdings versäumten es die Ermittler, den Apfel, welcher neben der Leiche gefunden worden war, näher untersuchen zu lassen.
Am 10. September veröffentlichte der britische Premierminister Gordon Brown eine Erklärung, in der er sich im Namen der britischen Regierung bei Turing entschuldigte und ihn für seine Verdienste ehrte.

Zum besseren Verständnis der Turingmaschine wird hier zunächst der Begriff des Algorithmus erklärt. Ein Algorithmus ist ein Lösungsverfahren, das durch präzis formulierte Handlungsanweisungen in endlich vielen Schritten zur Lösung eines Problems führt. Ein Algorithmus setzt sich somit aus einer Folge einzelner Anweisungen zusammen. So kann man beispielsweise im Alltag ein Kochrezept als Algorithmus auffassen, da dieses bei Durchführung der einzelnen Schritte stets zum gleichen Ergebnis führen sollte.


Die Turingmaschine

Die Turingmaschine ist das gedankliche Modell einer Maschine, die mit nur drei Operationen sämtliche Algorithmen simulieren kann. Die Turingmaschine besteht aus einem Speicherband, welches in beide Richtungen unbeschränkt sein muss und in gleich große Felder eingeteilt ist. In jedem Feld ist stets genau ein Symbol gespeichert, wobei wir davon ausgehen, dass ein leeres Feld ein "Leer-Symbol" enthält. Ein Lese-/Schreibkopf kann die Symbole in den Feldern lesen und gegebenfalls überschreiben. Eine Steuereinheit lenkt den Kopf. Sie enthält das Programm der Maschine, welches die jeweiligen Zustände und Arbeitsschritte festlegt.



Beispiel

Zum besseren Verständnis betrachten wir nun ein einfaches Beispiel. Dafür muss zunächst das Programm der Maschine festgelegt werden. Wir benutzen folgende Schreibweise:

[Z1, 1] -> [Z2, 1, R]

[Z1, 1] bedeutet, wir Beginnen in einem Zustand1 Z1. Liest der Kopf im ersten zu lesenden Feld eine 1, so führt die Maschine die Schritte aus, die in der zweiten Klammer angegeben sind: Sie geht über in den Zustand2 Z2, schreibt in das gelesene Feld das Symbol 1 (das Symbol wird also nicht verändert), und bewegt den Kopf ein Feld nach rechts, was durch das R festgelegt ist. Ob nun bei der technischen Umsetzung der Kopf sich nach rechts bewegt oder das Speicherband dementsprechen bewegt wird, ist irrelevant.
Unser festgelegtes Beispielprogramm stellt sich nun in der obigen Schreibweise wie folgt dar:

[Z1, 1] -> [Z2, 1, R]
[Z1, _] -> [Z1, _, R]
[Z2, 1] -> [Z2, 1, R]
[Z2, _] -> [Z2, 1, H]

Wir arbeiten also mit zwei Zuständen Z1 und Z2, zwei Symbolen 1 und _ (welches ein leeres Feld darstellen soll) und zwei Befehlen für die Bewegung des Kopfes R (der Kopf rückt ein Feld nach rechts) und H (der Kopf hält an, die Maschine befindet sich in ihrem Endzustand).
Wir spielen dieses Programm nun an einigen Beispielen durch:

1.) Wir beginnen zunächst im Zustand Z1. Der Kopf liest nun im ersten zu lesenden Feld eine 1. Dies bedeutet, die Maschine geht über in den Zustand Z2, schreibt in das Feld eine 1 und rückt ein Feld nach rechts R. Wir befinden uns nun im Zustand Z2. Ist das nun zu lesende Feld leer, so bleibt die Maschine im Zustand Z2, schreibt in dieses Feld eine 1 und hält an H. Die Zahlenfolge auf dem Band würde folgendermaßen aussehen:

1 1

2.)Wir beginnen erneut im Zustand Z2. Der Kopf liest dieses mal im ersten Feld ein Leer-Symbol _. Also bleibt die Maschine im Zustand Z1, schreibt ein Leer-Symbol _ in das Feld und rückt ein Feld nach rechts R. Wird hier nun eine 1 gelesen, so geht die Maschine über in den Zustand Z2, schreibt in das Feld eine 1 und rückt ein Feld nach rechts R. In diesem Zustand Z2 liest der Kopf nun erneut eine 1, worauf die Maschine im Zustand Z2 bleibt, eine 1 schreibt und ein Feld nach rechts R rückt. Liest der Kopf nun ein Leer-Symbol _, so bleibt die Maschine im Zustand Z2, schreibt in dieses Feld eine 1 und hält an H. Die Zahlenfolge würde nun so aussehen:

_ 1 1 1

Auf diese Art lassen sich wesentlich kompliziertere Algorithmen aufschreiben, die endlich viele Zustände besitzen, und auch andere, endlich viele Symbole enthalten können und nicht nur ein Feld nach rechts rücken können, sondern theoretisch auch mal hundert Felder nach links wandern, wenn das Programm vorher so geschrieben wurde.
Die Turingmaschine arbeitet also ähnlich wie heutige Computer, die auch alle nach algorithmischen Programmen operieren. Mit diesem Modell legte Turing den Grundstein für die spätere theoretische Informatik.


Das Entscheidungsproblem

Im weiteren Text legt Turing die Auswirkungen seines theoretischen Modells auf das so genannte Entscheidungsproblem nieder. Selbiges hängt sehr eng mit dem 1920 von David Hilbert postulierten Hilbertprogramm zusammen, welches darauf abzielt, die Widerspruchsfreiheit der Mathematik mit finiten Methoden nachzuweisen. Entscheidbar wären die Axiome Mathematik, wenn es für jedes Element daraus einen Algorithmus gibt, der entscheiden kann, ob dieses Element den Eigenschaften der Gesamtmenge entspricht. Turing beweist mit Hilfe seines Maschinenmodells, dass die Axiome der Mathematik nicht entscheidbar sind. Die Schritte des Beweises lassen wir hier aus, da sie zu komplex sind, um im Rahmen dieses Blogs nachvollzogen zu werden. Letztendlich besagt die Unentscheidbarkeit, dass die Mathematik nicht in der Lage ist, all ihre Bereiche nur durch sich selbst beweisen zu können.