Briefmarke des Monats Januar 2005

St. Vincent und Grenadinen 2000

Alan Mathison Turing (1912 - 1954)

Der englische Mathematiker Alan Turing hat sich vor allem als Logiker und Pionier der Informatik einen Namen gemacht. Besonderes Interesse hat er durch seine Arbeit an der Dechiffrierung des deutschen ENIGMA-Codes im Zweiten Weltkrieg auf sich gelenkt - allerdings (aufgrund der Geheimhaltungspolitik) erst durch Veröffentlichungen in jüngster Zeit.

Alan Turing war ein schwieriger und eigensinniger Schüler. Seine mathematischen Leistungen waren hervorragend, aber oft für seine Lehrer zu unkonventionell, um angemessen gewürdigt zu werden. Erst Cambridge, wo er 1931 das Mathematikstudium aufnahm, erwies sich als förderliche Umgebung für seine Fähigkeiten und Interessen. Seit dieser Zeit zogen sich mehrere und unterschiedlich starke mathematische Linien durch Turings Leben: Vorrangig Logik und Grundlagenprobleme der Mathematik sowie die Entwicklung von Computern, aber auch Wahrscheinlichkeitstheorie und Gruppentheorie, und aus der mathematischen Physik Relativitätstheorie und Quantentheorie.

1935 wurde Alan Turing Fellow of King's College in Cambridge, ging aber schon im Jahr darauf nach Amerika und setzte seine Studien an der Princeton University fort. Dort arbeitete der Logiker Alonzo Church, der etwa gleichzeitig mit Turing einen grundlegenden Aufsatz zur Berechenbarkeit von Zahlen und Funktionswerten und zu Entscheidbarkeitsfragen innerhalb logischer Systeme publiziert hatte. Church betreute Turings Studien bis zu dessen Rückkehr nach Cambridge 1938.

Die spannendste Phase in Turings Leben begann mit dem Kriegsausbruch 1939. Er wurde unverzüglich aufgefordert, für die Government Code and Cypher School im südenglischen Bletchley Park zu arbeiten, wo er bis zum Kriegsende seine gesamte Arbeitszeit der Dechiffrierung deutscher Funksprüche widmete. Schon in Princeton hatte Turing erwogen, einen Computer zu konstruieren. In Bletchley fand er Baupläne polnischer Mathematiker (Marian Rejewski u.a.) für Rechenmaschinen ("Bomben") zur Dechiffrierung der Nachrichten vor, die von der deutschen Wehrmacht mit der ENIGMA-Maschine chiffriert worden waren. Turing und sein Kollege William Gordon Welchman entwickelten die "Bomben" weiter und ermöglichten es den Wissenschaftlern in Bletchley, den enormen Rechenaufwand für die Entschlüsselung in vertretbarer Zeit zu leisten. Turings mathematischem Talent, unterstützt durch diese Maschine, verdanken die Alliierten wahrscheinlich zu einem erheblichen Teil den Sieg in diesem Krieg. Besonders wichtig war 1941 der erfolgreiche Einsatz statistischer Methoden bei der Dechiffrierung. Zusätzlich begünstigten andere Faktoren die Arbeit Turings und seiner Kollegen in Bletchley: Etliche ENIGMA-Maschinen aus deutschen Flugzeugen und Schiffen mit den zugehörigen Handbüchern fielen in die Hände der Briten, und die Wehrmacht leistete sich Kunstfehler beim Chiffrieren. Das Team in Bletchley (Tausende (!) von Funkexperten, Datenerfasserinnen, Schreibkräften, Übersetzern, Laufboten, Maschinenoperatoren und Wissenschaftlern) arbeitete im Schichtbetrieb rund um die Uhr in sehr einfach eingerichteten Baracken an der Dechiffrierung des unablässig eingehenden Stroms der abgehörten deutschen Funksprüche, immer im Wettlauf mit der Zeit und unter dem Druck der Kriegsereignisse. Die Arbeit in Bletchley Park - sehr abgeschieden und unter schärfsten Sicherheitsbestimmungen - war Turing wie auf den Leib geschnitten, weil er seine mathematischen Fähigkeiten und seine Ideen zum Einsatz von Rechenmaschinen voll zur Geltung bringen konnte.

      Mehr zu Alan Turing, Marian Rejewski und seinen polnischen Codebreaker-Kollegen: Briefmarke # 110

Nach Kriegsende widmete sich Turing überwiegend der Entwicklung von Computern und Programmcode, ab 1948 an der University of Manchester. Er führte dort auch seine Arbeiten an Fragen der Entscheidbarkeit fort. Gleichzeitig widmete er sich Grundproblemen der künstlichen Intelligenz; Studien zur Neurologie förderten sein Interesse an Analogien zwischen Mensch und Maschine. Ohne Wissen seiner Kollegen an der Universität arbeitete er weiter für die Regierung an geheimen Projekten zur Kryptografie.

Alan Turing war homosexuell und bekannte sich dazu. Dies führte 1952 zu seiner Festnahme und einem Gerichtsprozess mit Schuldspruch. Turing hatte die Wahl zwischen einer Gefängnisstrafe und einer Hormonbehandlung, er entschied sich für letztere. Eine Folge dieser Verurteilung war, dass er als Geheimnisträger zum Sicherheitsrisiko erklärt wurde; er und seine Besucher wurden beschattet. - Nicht lange darauf starb Alan Turing an einem vergifteten Apfel; sehr wahrscheinlich hat er selbst seinem Leben ein Ende gesetzt.


DIE TURING-MASCHINE

1936 schrieb Turing "On Computable Numbers, with an application to the Entscheidungsproblem", einen der meistzitierten und einflussreichsten Beiträge in der Geschichte der Mathematik. In diesem Aufsatz taucht erstmals die Beschreibung einer abstrakten Maschine auf, die (aus unserer heutigen Sicht) wie ein sehr einfacher Computer aufgebaut ist und die später "Turing-Maschine" genannt wurde.

In seinem Aufsatz versuchte Turing, dem Begriff "Algorithmus" eine präzise Definition zu geben. Demnach verwendet ein Algorithmus einen endlichen Zeichensatz, endlich viele Instruktionen und erreicht das Resultat in endlichen vielen Schritten (Turing unterschied dabei nicht zwischen menschlichen und maschinellen Rechnern). Diese Anforderungen führten Turing zum Konzept der Turing-Maschine, die man sich als mechanisches Gerät vorstellen kann, das einen bestimmten mathematischen Algorithmus ausführt. Die Komponenten und die Arbeitsweise der Maschine sind genau definiert. Sie enthält ein Band, das aus einer Folge von nebeneinander stehenden Feldern besteht, die jeweils mit einem Zeichen aus einem endlichen Zeichenvorrat (inklusive "blank") gefüllt sind. Dieses Band ist theoretisch in beiden Richtungen unbeschränkt lang. Die Maschine ist immer auf ein Feld positioniert, dessen Inhalt sie lesen und verändern kann. Die Maschine verfügt außerdem über ein Register, in dem jeweils ein Zustand (von endlich vielen Zuständen) festgehalten wird, von denen ein bestimmter als Anfangszustand definiert ist. Das "Programm" der Maschine ist eine Tabelle, in der für jede Kombination des aktuell gelesenen Zeichens mit dem aktuellen Zustand eine Aktion der Maschine steht. Eine Aktion besteht entweder aus dem Anhalten der Maschine oder aus der Überschreibung des gelesenen Zeichens mit einem neuen Zeichen, der Überschreibung des Registerzustands mit einem neuen Zustand und evtl. einer Bewegung auf das linke oder rechte Nachbarfeld. - Eine Modifikation der beschriebenen Turing-Maschine liest immer  k  benachbarte Felder statt einem einzigen ein; eine Aktion besteht dann aus  k  Einzelschritten.

Nach dieser Beschreibung verhält sich eine Turing-Maschine wie ein speziell konstruierter Computer mit einem festen Programm. Wozu führte Turing die Idee einer solchen Maschine ein? Mit ihrer Hilfe definierte er eine "berechenbare Zahl" ("computable number") als reelle Zahl, für die eine passend programmierte Turing-Maschine jede Dezimalstelle ausgeben kann, ausgehend von einem leeren Band. Turing zeigte, dass die Menge der berechenbaren Zahlen abzählbar ist, und gab auch eine nicht-berechenbare Zahl an.

Turing-Maschinen haben eine wichtige Rolle bei einem Grundlagenproblem der Mathematik und der Informatik gespielt, nämlich beim Problem der "Entscheidbarkeit". Es ist (beweisbar) nicht möglich, eine Turing-Maschine zu konstruieren, die aufgrund der vollständigen Beschreibung einer anderen Turing-Maschine und deren Eingabedaten korrekt vorhersagen kann, ob diese andere Maschine jemals anhalten wird. Auch für das "Entscheidungsproblem" der Prädikatenlogik (Axiomensystem von Bernays-Hilbert-Ackermann) gab Turing eine Lösung an: Keine Turing-Maschine ist in der Lage, für beliebige Aussagen der Prädikatenlogik deren Beweisbarkeit festzustellen.

Zwar haben alle Turing-Maschinen ein festes Programm, aber Alan Turing beschrieb auch die universelle Turing-Maschine. Diese kann jede beliebige spezielle Turing-Maschine simulieren. Dazu kodiert man das Programm der speziellen Turing-Maschine in einer Zeichenkette, die von der universellen Maschine bereits im Anfangszustand auf ihrem Band vorgefunden wird, gefolgt von den Daten auf dem Band der speziellen Maschine im Anfangszustand. Turing zeigte, dass für die universelle Maschine ein Programm existiert, das den gleichen Output wie die jeweils gewählte spezielle Maschine liefert.

1936 lag die Konstruktion eines Universalcomputers jenseits aller praktischen Möglichkeiten. Turings Beschreibung seiner Maschine war in gewisser Weise hellsichtig, denn sie deckt sich im Prinzip mit dem Konzept moderner Rechenautomaten.

Auch heute noch hat das Konzept der Turing-Maschine Bedeutung innerhalb der theoretischen Informatik. Turing und Church stellten die These auf, dass jeder Algorithmus, der von einem Rechner (menschlich oder maschinell) nach der Turing'schen Definition aus dem Aufsatz von 1936 ausgeführt wird, auch von einer Turing-Maschine ausgeführt werden könnte. Dies wird häufig (etwas lax) in der Weise interpretiert, dass jeder real existierende Computer maximal über die Fähigkeiten der universellen Turing-Maschine verfügt (Peripherie, Schnelligkeit oder Bedienungskomfort sollen dabei keine Rolle spielen). Diese Annahme gilt als weitgehend akzeptiert. Andererseits fallen moderne Computer in ihren Fähigkeiten auch nicht hinter die universelle Turing-Maschine zurück und werden daher Turing-vollständig genannt (die - im Gegensatz zur Turing-Maschine - beschränkte Speicherkapazität realer Systeme wird bei dieser Definition ignoriert). Ein formales System, das in der Lage ist, Algorithmen auszuführen, heißt also Turing-vollständig, wenn es mindestens über den gleichen Funktionsumfang verfügt wie die universelle Turing-Maschine. Für erstaunlich viele und sehr unterschiedliche Systeme ist die Turing-Vollständigkeit bewiesen worden (Beispiele). Insbesondere gelten Turings Ergebnisse zu berechenbaren Zahlen und zum Entscheidungsproblem unverändert, wenn man statt der Turing-Maschine einen modernen Computer einsetzt.


DER TURING-TEST

Alan Turing gilt als einer der Väter der künstlichen Intelligenz. Sein Interesse galt Mensch-Maschine-Analogien, lange bevor Roboter, Bild- oder Spracherkennungsprogramme in Sicht kamen. Von ihm stammt eine Idee, wie man einer Maschine (z.B. einem Computer) Intelligenz zuschreiben könnte. Er schlug vor, neutralen Personen zu erlauben, beliebige Fragen zu stellen, die dann von der (verborgenen) Maschine und dem (verborgenen) Menschen beantwortet werden sollten, natürlich auf einem einheitlichen Kanal, etwa per Fernschreiber (um ein Beispiel aus Turings Zeit zu nehmen). Ist es neutralen Personen nicht möglich, aufgrund der Antworten herauszufinden, welche Antworten von der Maschine und welche vom Menschen stammen, so gibt es nach Turings Überzeugung keinen Grund, der Maschine Intelligenz abzusprechen. In diesem Test spiegelt sich Turings Auffassung wider, dass die Beweislast bei der Diskussion über prinzipielle Intelligenzunterschiede zwischen Maschine und Mensch bei den Verfechtern dieser Unterschiede liegt.