*23. Juni 1912 †7. Juni 1954
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:
Unser festgelegtes Beispielprogramm stellt sich nun in der obigen Schreibweise wie folgt dar:
[Z1, _] -> [Z1, _, R]
[Z2, 1] -> [Z2, 1, R]
[Z2, _] -> [Z2, 1, H]
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:
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.