Alan Turing

Alan Turing (1912–1954) war ein britischer Mathematiker und Logiker, der mit seiner Arbeit über „berechenbare Zahlen“ 1936 das theoretische Fundament der Informatik legte. Die darin beschriebene gedachte Maschine, heute Turingmaschine genannt, ist bis heute das Maß dafür, was ein Computer grundsätzlich berechnen kann und was nicht. Im Zweiten Weltkrieg gehörte Turing in Bletchley Park zu den führenden Köpfen bei der Entzifferung der deutschen Enigma-Funksprüche.

Nach dem Krieg entwarf er einen der ersten Computer mit gespeichertem Programm, stellte die Frage, ob Maschinen denken können, und schlug ein mathematisches Modell dafür vor, wie Flecken und Streifen auf Tierfellen entstehen. 1952 wurde Turing wegen seiner Homosexualität verurteilt, zwei Jahre später starb er an einer Zyanidvergiftung. Erst Jahrzehnte danach rehabilitierte ihn der britische Staat; heute ziert sein Porträt die 50-Pfund-Note.

Kindheit und Schulzeit in Sherborne

Alan Mathison Turing kam am 23. Juni 1912 in London zur Welt. Sein Vater gehörte dem britischen Verwaltungsdienst in Indien an; die Eltern lebten überwiegend dort und ließen Alan und seinen älteren Bruder John bei einer Pflegefamilie in St Leonards-on-Sea an der englischen Südküste aufwachsen. Schon als Kind experimentierte Turing mit Chemikalien und las populärwissenschaftliche Bücher.

1926 wechselte er an die Sherborne School in Dorset. Sein erster Schultag fiel in den britischen Generalstreik; weil keine Züge fuhren, legte der 13-Jährige die rund 100 Kilometer von Southampton mit dem Fahrrad zurück. Die Schule legte großen Wert auf Latein und Griechisch, und Turings einseitige Begabung stieß bei den Lehrern eher auf Sorge als auf Begeisterung. Dennoch löste er als Jugendlicher anspruchsvolle Aufgaben, ohne je Differenzialrechnung gelernt zu haben, und mit 16 Jahren arbeitete er sich in Einsteins Relativitätstheorie ein.

Prägend wurde die Freundschaft mit dem ein Jahr älteren Mitschüler Christopher Morcom, der Turings naturwissenschaftliche Interessen teilte. Morcom starb im Februar 1930 an Rindertuberkulose, noch bevor beide nach Cambridge gehen konnten. Der Verlust stürzte Turing in eine tiefe Krise und brachte ihn dazu, über das Verhältnis von Geist und Materie nachzudenken. Diese Frage begleitete ihn bis zu seinen späteren Überlegungen zur Maschinenintelligenz.

Studium in Cambridge und der zentrale Grenzwertsatz

Von 1931 bis 1934 studierte Turing Mathematik am King’s College in Cambridge und schloss mit Auszeichnung ab. Bereits 1935 wählte ihn das College mit 22 Jahren zum Fellow. Grundlage war eine Arbeit, in der er den zentralen Grenzwertsatz der Wahrscheinlichkeitsrechnung bewies, also den Satz, der erklärt, warum sich Summen vieler zufälliger Einflüsse annähernd normalverteilt verhalten. Dass der Finne Jarl Lindeberg das Ergebnis schon 1922 gefunden hatte, wusste Turing nicht; die Leistung wurde trotzdem anerkannt, 1936 erhielt er dafür zusätzlich den Smith’s Prize.

Entscheidend für seinen weiteren Weg war eine Vorlesung des Topologen Max Newman im Frühjahr 1935 über die Grundlagen der Mathematik. Newman stellte darin die Unvollständigkeitssätze von Kurt Gödel vor und eine offene Frage von David Hilbert: das Entscheidungsproblem.

Die Turingmaschine und Hilberts Entscheidungsproblem

Hilberts Frage nach einem allgemeinen Verfahren

Hilbert und sein Mitarbeiter Wilhelm Ackermann hatten 1928 gefragt, ob es ein mechanisches Verfahren gibt, das für jede Aussage der Prädikatenlogik in endlich vielen Schritten entscheidet, ob sie allgemeingültig ist, also aus den logischen Axiomen beweisbar. Gäbe es ein solches Verfahren, könnte man mathematische Fragen im Prinzip durch Rechnen statt durch Nachdenken klären. Gödel hatte 1931 gezeigt, dass jedes widerspruchsfreie, hinreichend starke Axiomensystem Aussagen enthält, die sich darin weder beweisen noch widerlegen lassen. Ob man Beweisbarkeit wenigstens mechanisch entscheiden kann, blieb offen. Um diese Frage verneinen zu können, brauchte man eine genaue Definition dessen, was ein „mechanisches Verfahren“ überhaupt ist. Genau diese lieferte Turing.

Wie eine Turingmaschine funktioniert

Turing ging von einem Menschen aus, der mit Bleistift und Papier rechnet, und reduzierte dessen Tätigkeit auf das Allernötigste. Seine Maschine besteht aus einem unbegrenzt langen Band, das in Felder eingeteilt ist, einem Lese-Schreib-Kopf, der jeweils ein Feld betrachtet, und einem endlichen Vorrat an Zuständen. Eine Tabelle legt fest, was die Maschine im jeweiligen Zustand beim Lesen eines Zeichens tut: ein Zeichen schreiben, ein Feld nach links oder rechts rücken und in einen neuen Zustand wechseln. Mehr kann sie nicht. Und doch reicht das für jede Rechnung, die sich überhaupt als Verfahren beschreiben lässt.

Die universelle Maschine

Turings vielleicht folgenreichste Idee steckt in einem Nebenergebnis: Man kann die Regeltabelle einer beliebigen Turingmaschine selbst als Zeichenfolge auf das Band schreiben. Eine einzige universelle Turingmaschine kann dann diese Beschreibung lesen und das Verhalten jeder anderen Maschine nachahmen. Programm und Daten stehen also im selben Speicher: genau das Prinzip, nach dem heute jeder Computer arbeitet. Turing formulierte es zehn Jahre bevor die ersten elektronischen Rechner mit gespeichertem Programm gebaut wurden.

Grenzen des Berechenbaren: die Unlösbarkeit des Entscheidungsproblems

Mit seinem Modell bewies Turing, dass es Fragen gibt, die keine Maschine beantworten kann. Sein Argument ähnelt dem Diagonalverfahren von Georg Cantor: Gäbe es eine Maschine, die für jede Maschinenbeschreibung entscheidet, ob die beschriebene Maschine sich in einer bestimmten Weise verhält, ließe sich daraus eine neue Maschine bauen, die genau das Gegenteil ihrer eigenen Vorhersage tut. Das ist ein Widerspruch. In heutiger Lehrbuchform heißt das Ergebnis Unentscheidbarkeit des Halteproblems: Kein Programm kann für jedes Programm und jede Eingabe vorhersagen, ob die Rechnung jemals endet. Der Begriff „Halteproblem“ stammt allerdings erst aus den 1950er-Jahren; Turing selbst formulierte das Ergebnis etwas anders.

Daraus folgte, dass Hilberts Entscheidungsproblem keine positive Lösung hat. Nebenbei zeigte Turing, dass zwar Zahlen wie π oder e berechenbar sind, die allermeisten reellen Zahlen aber nicht: Es gibt nur abzählbar viele Maschinen, aber überabzählbar viele reelle Zahlen. Die Arbeit On Computable Numbers, with an Application to the Entscheidungsproblem erschien 1936/37 in den Proceedings of the London Mathematical Society.

Kurz bevor Turing fertig war, veröffentlichte der amerikanische Logiker Alonzo Church in Princeton dasselbe Ergebnis auf anderem Weg, mit dem sogenannten Lambda-Kalkül. Turing ergänzte daraufhin einen Anhang, in dem er die Gleichwertigkeit beider Begriffe bewies. Die Überzeugung, dass Turingmaschinen genau das erfassen, was sich überhaupt algorithmisch berechnen lässt, heißt heute Church-Turing-These. Sie ist kein beweisbarer Satz, sondern eine gut begründete Annahme. Selbst Gödel hielt Turings Analyse für die überzeugendste Definition von Berechenbarkeit.

Promotion in Princeton

Newman vermittelte Turing nach Princeton, wo er 1936 bis 1938 bei Church studierte und 1938 promovierte. In seiner Dissertation über „ordinale Logiken“ untersuchte er, wie weit sich Gödels Unvollständigkeit durch schrittweise Erweiterung von Axiomensystemen auffangen lässt, und führte dabei das Konzept einer „Orakelmaschine“ ein. John von Neumann bot ihm eine Stelle als Assistent am Institute for Advanced Study an; Turing lehnte ab und kehrte nach Cambridge zurück.

Bletchley Park: Turing und die Enigma

Die deutsche Wehrmacht verschlüsselte ihren Funkverkehr mit der Enigma, einer elektromechanischen Maschine mit drehbaren Walzen und einem Steckbrett. Allein die Standardausführung des Heeres mit drei aus fünf Walzen und zehn Steckverbindungen erlaubte rund 159 Trillionen (etwa 1,59 · 10²⁰) Grundeinstellungen. Die Einstellungen wechselten täglich.

Die Grundlagen der Entzifferung stammten aus Polen: Der Mathematiker Marian Rejewski hatte die Enigma bereits Ende 1932 rekonstruiert, und das polnische Chiffrenbüro entwickelte mit der „Bomba“ eine erste Entschlüsselungsmaschine. Im Juli 1939, wenige Wochen vor dem deutschen Überfall, übergaben die Polen ihre Ergebnisse den britischen und französischen Verbündeten. Als die Deutschen ihre Verfahren änderten, reichten die polnischen Methoden jedoch nicht mehr aus.

Turing meldete sich am 4. September 1939 in Bletchley Park, dem Sitz der britischen Code-Knacker nördlich von London. Er entwarf eine neue Maschine, die Bombe. Sie arbeitete mit vermuteten Klartextstücken (etwa einer Wettermeldung, die jeden Morgen gleich begann) und schloss in hohem Tempo Walzenstellungen aus, die zu logischen Widersprüchen führten. Die erste Bombe lief im März 1940; der Mathematiker Gordon Welchman verbesserte das Prinzip entscheidend durch sein „Diagonalbrett“. Bis Kriegsende waren über 200 Bomben in Betrieb.

Turing leitete die Abteilung Hut 8, die für die besonders schwer zu knackende Enigma der Kriegsmarine zuständig war. Deren Funksprüche waren entscheidend für den Kampf gegen die U-Boote im Atlantik. Dafür entwickelte er das statistische Verfahren „Banburismus“ und führte mit „Ban“ und „Deciban“ eigene Maßeinheiten für das Gewicht von Indizien ein, eine frühe Anwendung bayesscher Statistik. Im Oktober 1941 schrieben Turing, Welchman und zwei Kollegen direkt an Premierminister Winston Churchill, weil ihnen Personal fehlte; Churchill ordnete sofortige Abhilfe an.

1942 fand Turing zudem ein Verfahren gegen die Lorenz-Schlüsselmaschine, mit der die deutsche Führung kommunizierte („Turingery“). Von November 1942 bis März 1943 reiste er in die USA, um die Zusammenarbeit mit den amerikanischen Code-Knackern abzustimmen, und traf dabei in den Bell Labs den Informationstheoretiker Claude Shannon. Gegen Kriegsende entwickelte er in Hanslope Park ein Gerät zur Sprachverschlüsselung namens „Delilah“. 1946 wurde er für seine Kriegsverdienste zum Officer of the Order of the British Empire (OBE) ernannt; über die Gründe durfte wegen der Geheimhaltung nicht gesprochen werden.

Wie viel die Arbeit von Bletchley Park zum Kriegsausgang beitrug, ist schwer zu messen. Der Geheimdiensthistoriker Harry Hinsley schätzte, sie habe den Krieg um mindestens zwei Jahre verkürzt. Als Gedankenexperiment bleibt diese Schätzung naturgemäß umstritten.

Computerpionier: ACE und Manchester

Im Oktober 1945 ging Turing an das National Physical Laboratory (NPL) in London. Anfang 1946 legte er dort einen vollständigen Entwurf für einen elektronischen Rechner mit gespeichertem Programm vor, die Automatic Computing Engine (ACE). Der Entwurf war seiner Zeit voraus, doch der Bau verzögerte sich so sehr, dass Turing das NPL enttäuscht verließ. Eine verkleinerte Version, die Pilot ACE, rechnete erst im Mai 1950.

1948 wechselte Turing an die Universität Manchester, wo Frederic Williams und Tom Kilburn im Juni 1948 mit der „Manchester Baby“ den ersten funktionierenden Computer mit gespeichertem Programm in Betrieb genommen hatten. Turing baute die Rechner nicht selbst, wurde aber stellvertretender Leiter des Rechenlabors und schrieb das Programmierhandbuch für den Ferranti Mark 1 (1951), einen der ersten kommerziell gebauten Computer. 1950 nutzte er die Maschine, um Nullstellen der Zetafunktion von Bernhard Riemann zu berechnen: Er bestätigte, dass die ersten 1.104 Nullstellen wie von der Riemannschen Vermutung vorhergesagt auf der kritischen Geraden liegen.

Mit dem Ökonomen David Champernowne entwarf Turing 1948 eines der ersten Schachprogramme, „Turochamp“. Weil kein Computer es ausführen konnte, spielte Turing 1952 eine Partie, indem er den Algorithmus von Hand mit Papier und Bleistift abarbeitete, und verlor gegen seinen Kollegen Alick Glennie. 1951 wurde Turing zum Mitglied der Royal Society gewählt.

Können Maschinen denken? Der Turing-Test

Schon 1948 beschrieb Turing in einem internen Bericht „lernende Maschinen“ aus zufällig verknüpften Schaltelementen, eine frühe Vorstellung künstlicher neuronaler Netze. 1950 veröffentlichte er in der philosophischen Zeitschrift Mind den Aufsatz Computing Machinery and Intelligence, der mit einem berühmten Satz beginnt:

„Ich schlage vor, die Frage zu erwägen: ‚Können Maschinen denken?‘“

Weil sich „Denken“ kaum definieren lässt, ersetzte Turing die Frage durch ein überprüfbares Spiel, das „Imitationsspiel“: Eine Person führt schriftliche Unterhaltungen mit einem Menschen und einer Maschine, ohne zu wissen, wer wer ist. Kann sie die beiden nicht zuverlässig unterscheiden, hat die Maschine bestanden. Turing sagte voraus, dass Rechner um das Jahr 2000 so gut spielen würden, dass ein durchschnittlicher Fragesteller nach fünf Minuten in höchstens 70 Prozent der Fälle richtig liegt. Im selben Aufsatz diskutierte er Einwände gegen denkende Maschinen, darunter den „Einwand der Lady Lovelace“: Ada Lovelace hatte über Charles Babbages Analytical Engine geschrieben, sie könne nichts Neues hervorbringen, sondern nur ausführen, was man ihr befiehlt. Turing hielt dagegen, dass lernende Maschinen ihre Schöpfer durchaus überraschen könnten.

Mathematische Biologie: Wie Muster in der Natur entstehen

In seinen letzten Lebensjahren wandte sich Turing der Biologie zu. In The Chemical Basis of Morphogenesis (1952) fragte er, wie aus einem gleichförmigen Zellhaufen Strukturen wie Flecken, Streifen oder Tentakel entstehen. Seine Antwort war ein System von Reaktions-Diffusions-Gleichungen: Zwei Stoffe reagieren miteinander und breiten sich unterschiedlich schnell aus. Ein Stoff fördert seine eigene Bildung, der andere hemmt sie und verteilt sich rascher. Aus winzigen Zufallsschwankungen wachsen dann stabile, regelmäßige Muster.

Solche Turing-Muster wurden seit den 1990er-Jahren in chemischen Experimenten nachgewiesen und dienen heute als Modell etwa für Fellzeichnungen oder die Anlage von Fingern im Embryo. Turing untersuchte auch die Anordnung von Blättern und Samen in Pflanzen, in der die Zahlen der Fibonacci-Folge auftauchen; diese Arbeiten blieben unvollendet.

Verurteilung 1952 und Tod 1954

Turing ging mit seiner Homosexualität vergleichsweise offen um, obwohl sexuelle Handlungen zwischen Männern in Großbritannien strafbar waren. Im Januar 1952 wurde in sein Haus in Wilmslow eingebrochen. Bei den Ermittlungen gab Turing eine Beziehung zu dem 19-jährigen Arnold Murray zu, dessen Bekannter den Einbruch begangen hatte. Daraufhin wurden beide wegen „grober Unzucht“ nach einem Gesetz von 1885 angeklagt. Nach demselben Paragrafen war 1895 schon Oscar Wilde verurteilt worden.

Am 31. März 1952 bekannte sich Turing schuldig. Statt einer Gefängnisstrafe akzeptierte er eine einjährige Bewährung mit der Auflage einer Hormonbehandlung mit synthetischem Östrogen, oft als „chemische Kastration“ bezeichnet. Die Behandlung hatte körperliche Nebenwirkungen, unter anderem wuchs ihm Brustgewebe. Zudem verlor er seine Sicherheitsfreigabe und konnte nicht mehr für den Nachrichtendienst arbeiten. Wissenschaftlich blieb er dennoch produktiv.

Am 8. Juni 1954 fand seine Haushälterin Turing tot in seinem Bett; er war am Vortag an einer Zyanidvergiftung gestorben. Neben ihm lag ein halb gegessener Apfel, der jedoch nie auf Gift untersucht wurde. Die gerichtliche Leichenschau stellte Selbstmord fest. Sein Biograf Andrew Hodges hält das für die wahrscheinlichste Erklärung; der Turing-Forscher Jack Copeland hat dagegen argumentiert, die Beweisaufnahme sei dürftig gewesen und ein Unfall nicht auszuschließen, denn Turing betrieb in einem Nebenraum Elektrolyse-Experimente mit Kaliumcyanid.

Späte Rehabilitierung: Entschuldigung, Royal Pardon und Turing-Gesetz

Die öffentliche Wahrnehmung Turings wandelte sich erst, als in den 1970er-Jahren die Geheimhaltung um Bletchley Park gelockert wurde und Andrew Hodges 1983 seine Biografie veröffentlichte. Nach einer Online-Petition entschuldigte sich Premierminister Gordon Brown am 10. September 2009 im Namen der Regierung für die „entsetzliche“ Behandlung Turings.

Am 24. Dezember 2013 begnadigte Königin Elisabeth II. Turing posthum auf Antrag des Justizministers Chris Grayling. Dieser sogenannte Royal Pardon beruhte auf dem königlichen Gnadenrecht. Kritiker wandten ein, eine Begnadigung setze ein Vergehen voraus, und sie gelte nur für einen prominenten Einzelfall. Darauf folgte das informell „Alan-Turing-Gesetz“ genannte Regelwerk im Policing and Crime Act 2017: Seit dem 31. Januar 2017 gelten Zehntausende Männer, die nach den aufgehobenen Gesetzen verurteilt worden waren, als posthum begnadigt; Lebende können die Löschung ihrer Verurteilung beantragen.

Die Bank of England stellte am 25. März 2021 eine neue 50-Pfund-Note mit Turings Porträt vor, die an seinem Geburtstag, dem 23. Juni 2021, in Umlauf kam. Sie zeigt unter anderem Zeichnungen der Bombe, ein Foto der Pilot ACE und sein Geburtsdatum im Binärcode.

Zeitleiste: Alan Turings Leben

1. 1912 Geburt am 23. Juni in London
2. 1926 Eintritt in die Sherborne School; Fahrradfahrt während des Generalstreiks
3. 1936 „On Computable Numbers“: Turingmaschine, universelle Maschine, Unlösbarkeit des Entscheidungsproblems
4. 1938 Promotion bei Alonzo Church in Princeton
5. 1939 Beginn in Bletchley Park am 4. September; Entwurf der Bombe
6. 1946 Entwurf der Automatic Computing Engine (ACE); Ernennung zum OBE
7. 1948 Wechsel an die Universität Manchester; Schachprogramm Turochamp
8. 1950 „Computing Machinery and Intelligence“ mit dem Turing-Test
9. 1952 Arbeit zur Morphogenese; Verurteilung wegen „grober Unzucht“
10. 1954 Tod am 7. Juni in Wilmslow an einer Zyanidvergiftung

Bedeutung heute: Wo uns Turings Ideen begegnen

Turings Begriff der Berechenbarkeit ist das Fundament der theoretischen Informatik. Nennt man eine Programmiersprache „Turing-vollständig“, heißt das, sie kann alles berechnen, was eine Turingmaschine kann. Die Komplexitätstheorie (etwa die offene Frage, ob P gleich NP ist) misst Rechenaufwand bis heute in Schritten von Turingmaschinen. Die wichtigste Auszeichnung der Informatik, der seit 1966 vergebene Turing Award der Association for Computing Machinery, trägt seinen Namen.

Auch die Mathematik selbst wurde verändert: Seit Turing lässt sich präzise beweisen, dass bestimmte Probleme algorithmisch unlösbar sind. Der spektakulärste Fall ist Hilberts zehntes Problem über ganzzahlige Lösungen von Gleichungen, dessen Unlösbarkeit 1970 auf Turings Begriffen aufbauend bewiesen wurde. Der Turing-Test ist dagegen ein Dauerthema der Debatte um künstliche Intelligenz. Seit große Sprachmodelle in Studien vereinfachte Varianten bestehen, wird weniger über die Maschinen gestritten als über die Frage, ob der Test überhaupt misst, was Turing „Denken“ nannte. In der Biologie sind Turing-Muster ein Standardmodell der Entwicklungsbiologie.

Turings Leben steht schließlich exemplarisch für das Unrecht, das homosexuellen Menschen angetan wurde. Ein Denkmal in Manchester, die Banknote, zahlreiche Biografien und Filme halten seine Geschichte lebendig. Mehr zum wissenschaftlichen Umfeld bietet der Überblick über die Mathematik des 20. Jahrhunderts.

Häufige Fragen

Quellen und weiterführende Literatur

• Andrew Hodges: Alan Turing: The Enigma. Burnett Books, London 1983 (zahlreiche Neuauflagen).
• Alan M. Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society, Series 2, Band 42 (1936/37), S. 230–265.
• Alan M. Turing: Computing Machinery and Intelligence. In: Mind 59 (1950), S. 433–460.
• B. Jack Copeland (Hrsg.): The Essential Turing. Clarendon Press, Oxford 2004.
• MacTutor History of Mathematics: Alan Mathison Turing (englisch)