In diesem kleinen Garten in der Nähe des Institute of Science and Technology der Universität Manchester finden Sie eine Bronzestatue des britischen Denkers Alan Turing.
Turing sitzt auf einer bronzenen Parkbank, in der einen Hand einen Apfel, den Hemdkragen geöffnet und die Krawatte gelockert. Zu seinen Füßen befindet sich eine Tafel mit dem Text: »Father of Computer Science, Mathematician, Logician, Wartime Codebreaker, Victim of Prejudice« (frei übersetzt etwa »Vater der Informatik, Mathematiker, Logiker, Codeknacker in Kriegszeiten, Opfer von Vorurteilen«). Am bekanntesten ist Turing wohl für seine Arbeit bei der Entschlüsselung der Enigma-Chiffre während des Zweiten Weltkriegs (siehe Kapitel 40). Doch Turings Vermächtnis ist wesentlich größer – ihm verdanken wir zu großen Teilen die Computertechnik, wie wir sie heute kennen.
Turing erfand einen theoretischen Computer, der heute als Turingmaschine bekannt ist. Eine Turingmaschine ist ein sehr einfacher Computer mit vier wichtigen Komponenten. Die erste ist ein in Quadrate (sogenannte Zellen) unterteiltes Band. Die Turingmaschine kann in jedem Quadrat ein Symbol ihres Zeichen-Alphabets speichern. Symbole können mit dem Kopf der Turingmaschine vom Band gelesen und geschrieben werden. Dabei bewegte sich entweder der Kopf oder das Band, so dass der Kopf jede Zelle lesen oder in diese schreiben konnte (Abbildung 66.1). Die Turingmaschine verwendete eine Tabelle mit Instruktionen, auf deren Grundlage dann entschieden wurde, was zu tun war – sie konnte solche Aktionen durchführen wie den Kopf um eine Zelle bewegen, das Symbol unter dem Kopf einlesen, ein neues Symbol schreiben oder ein Symbol vom Band löschen. Zusätzlich gab es noch ein »Statusregister«, das der Maschine Informationen darüber lieferte, an welcher Stelle der Instruktionstabelle sie sich befand.
Das Halteproblem
Bei Turings Halteproblem wird die folgende Frage formuliert: »Ist es möglich, ein Computerprogramm zu schreiben, das bestimmt, ob ein anderes Computerprogramm für immer läuft?« Turing zeigte, das die Antwort nein lautet – es ist nicht möglich. Um dies zu beweisen, nutzte Turing eine in der Mathematik gängige Technik: die Cantor-Diagonalisierung, die auch als Cantor’sches Diagonalverfahren bezeichnet wird (siehe Kasten in Kapitel 47).
Bei diesem Beweis geht man zunächst von einer Menge aller möglichen Computerprogramme aus und nummeriert sie mit 1, 2, 3, und so weiter. So kann man jedes Computerprogramm über seine Nummer identifizieren. Das Gleiche geschieht mit den Eingaben des Programms, d.h. alle möglichen Eingaben werden mit 1, 2, 3 und so weiter durchnummeriert.
Das Halteproblem selbst kann als mathematische Funktion beschrieben werden, die 1 ist, wenn ein Programm für eine gegebene Eingabe anhält, und 0, wenn dies nicht der Fall ist (Gleichung 66.1).
Das Halteproblem lässt sich dann wie folgt formulieren: »Gibt es ein Programm, das die Haltefunktion h(p,i) berechnen kann?« Hierfür nutzte Turing eine zweite mathematische Funktion, die für einige Werte undefiniert war (was dem »Nicht-Halt« eines Computerprogramms entsprach) und für andere 0 (Gleichung 66.2).
g(i) besitzt nur einen Parameter, die Zahl i. Sie wird von h(i,i) verwendet, um sowohl das Programm mit der Nummer i als auch die Eingabe mit der Nummer i zu finden. Und g(i) ist 0, wenn das Programm i mit der Eingabe i nicht anhält, anderenfalls ist g(i) undefiniert. Nun kommen wir zu dem Teil, der wirklich Kopfzerbrechen bereitet. Nehmen wir an, es gibt ein Computerprogramm für h(p,i). Man kann zwei Dinge leicht erkennen:
- Es muss ein Programm für g(i) geben, weil es über h(p,i) definiert ist.
- g(i) wird durch die Programmnummer j für irgendeine Zahl j berechnet.
Was geschieht nun also, wenn Sie versuchen, g(j) zu berechnen? Was passiert, wenn Sie g(j) an sich selbst übergeben?
- Wenn g(j) 0 ist, dann ist h(j,j) auch 0, was bedeutet, dass das Programm j bei der Eingabe j nicht anhält. Doch das Programm j ist das Programm für g(j), von dem wir gerade gesagt haben, dass es 0 ist. Das ist ein Widerspruch und daher kann g(j) niemals 0 sein.
- Ist g(j) undefiniert, dann ist h(j,j) gleich 1, d.h. das Programm j hält bei der Eingabe j an. Aber das Programm j ist das Programm für g(j), das wir gerade als undefiniert (hält nicht an) bezeichnet haben. Ein weiterer Widerspruch.
Diese Argumentation führt zu Widersprüchen und bedeutet, dass die ursprüngliche Annahme falsch ist: es gibt kein Programm, um h(p,i) zu berechnen. Das Halteproblem war wichtig, weil es zeigte, dass Turings Maschinen nicht in der Lage waren, wichtige ungelöste mathematische Probleme zu lösen.
Es zeigte außerdem, dass kein Computer in der Lage ist vorherzusagen, ob ein Programm aufhört, zu reagieren. Also sind wir Menschen immerhin nicht ganz außen vor, wenn es um das Debugging geht.
Das Band entspricht dem Speicher eines modernen Computers. Der Kopf wurde durch den elektronischen Zugriff auf den Speicher ersetzt und die Instruktionstabelle ist einfach das Programm. Turing beschrieb seine Turingmaschine in den späten 1930ern, während seines Studiums an der Universität von Cambridge. Das zugrundeliegende Prinzip wird bei Computern bis heute genutzt.
Turing erfand die Maschine wegen seines Interesses an einem mathematischen Puzzle, dem sogenannten Entscheidungsproblem. Mathematiker des frühen 20. Jahrhundert (und auch einige frühere große Mathematiker wie Leibnitz) waren an der Entwicklung einer Maschine für die Mathematik interessiert. Bei dem Entscheidungsproblem geht es um die Frage, ob es möglich ist, einen Algorithmus zu finden, dem man ein mathematisches Problem (in einer geeigneten mathematischen Sprache) übergeben kann, und der dann entsprechend Wahr oder Falsch zurückliefert. Falls ein solcher Algorithmus existiert, könnte er mit ungelösten mathematischen Problemen gefüttert werden, um dann die Antwort Wahr oder Falsch zu erhalten. Turings Beitrag bestand darin zu zeigen, dass das Halteproblem mittels einer Turingmaschine nicht gelöst werden konnte (siehe Kasten).
Nach seiner Arbeit als Codeknacker während des Zweiten Weltkriegs arbeitete Turing an einigen der ersten elektronischen Computer, einschließlich des ACE (des ersten britischen Computers mit einem darin gespeicherten Programm), und später am Manchester Mark I der Universität von Manchester. 1950 schrieb Turing über künstliche Intelligenz und schlug einen Test vor, um zu entscheiden, ob ein Computer wirklich denken kann. Für diesen Test, den wir heute Turingtest nennen, werden zwei Personen A und B sowie ein Computer C benötigt. A kommuniziert nun mit B (der Person) und C (dem Computer) nur über eine Tastatur und einen Bildschirm. Die Aufgabe von A besteht nun darin herauszufinden, ob B oder C menschlich ist. Wenn dies nicht möglich ist, wird C als »denkend« eingestuft.
Sackville Street Gardens liegt in der Nähe der Canal Street, die am Rochdale-Kanal entlang führt und seit den 1960ern das Zentrum der Schwulenszene Manchesters war. Alan Turing war homosexuell und wurde 1952 wegen »grober Unzucht« angeklagt. Um dem Gefängnis zu entgehen, akzeptierte Turing eine »Behandlung« der Homosexualität mit Östrogenspritzen. Dadurch verlor er jedoch seine Sicherheitseinstufung und durfte für die britische Regierung nicht mehr im Bereich der Kryptographie arbeiten. Zwei Jahre später wurde Turing tot in seinem Haus aufgefunden. Er hatte offensichtlich einen mit Zyanid vergifteten Apfel gegessen und sich so das Leben genommen.
Ein Turing-Geheimnis bleibt. In die Bank eingraviert sind die Zeichen IEKYF ROMSI ADXUO KVKZC GUBJ, deren Entschlüsselung FOUNDER OF COMPUTER SCIENCE (Begründer der Informatik) lauten soll. Doch professionelle Codeknacker haben darauf hingewiesen, dass das U in COMPUTER dann als U in ADXUO hätte verschlüsselt werden müssen. Dies ist aber unmöglich, weil die Enigma niemals einen Buchstaben mit sich selbst verschlüsselt. Die genaue Dekodierung ist immer noch unbekannt.
Der Park ist aufgrund seiner Nähe zur Canal Street (und Sackville Street), zur Universität und zum Kanal leicht zu finden. (Die Canal Street selbst ist eine beliebte Gegend zum Ausgehen.) Wissenschaftlich interessierte Besucher sollten ihren Besuch mit einem Abend im Café Scientifique verbinden, das zum Manchester Museum gehört. Hier finden öffentliche Vorträge und Wissenschaftsdemonstrationen der Universität von Manchester statt. Details finden Sie unter http://www.cafescientifique.manchester.ac.uk/.