Die universelle Turing-Maschine

Ob Smartphone, Notebook oder Supercomputer – all diese Rechner funktionieren nach dem gleichen Grundprinzip: Ihre Hardware liefert die elektronische Grundlage, die Software aber bestimmt, welche Aufgaben der Rechner gerade bearbeitet – ob beispielsweise mathematische Kalkulationen, Textverarbeitung oder das Rendern einer Grafik. Eine Hardware kann – je nach Software – daher ganz verschiedenen Zwecken dienen. Diese Zweiteilung ist es letztlich, die den Computer zu einem so universellen Werkzeug macht.

Portrait von Alan Turing, aufgenommen 1951 © National Portrait Gallery, London

Ein Band, ein Programm und ein Schreib-Lese-Kopf

Erdacht hat dieses Prinzip kein anderer als der britische Mathematiker Alan Turing. Mit seiner „Universellen Turing-Maschine“ entwickelte er es bereits 1936 – zu einer Zeit, als Computer im heutigen Sinne noch nicht einmal ansatzweise existierten. Turing stützte sich bei seinem Konzept allein auf Logik und Mathematik und ersann die erste Idee einer programmierbaren Maschine. Seine Turing-Maschine besteht im Prinzip aus nichts anderem als einem Schreib-Lese-Kopf, einem endlos langen Speicherband mit einzelnen, jeweils ein Zeichen enthaltenden Feldern und einer Arbeitsanweisung.

„Das Band läuft durch die Maschine und ist in klare Sektionen geteilt, jede kann ein Symbol enthalten. Zu jeder Zeit ist aber immer nur ein Feld in der Maschine und wird gescannt“, erklärt Turing in seiner Veröffentlichung „On computable Numbers“. Die Arbeitsanweisung gibt dem Schreibkopf die Anweisung, ob er sich ein Feld vor oder zurück bewegen soll. Sie bestimmt auch, ob er das im aktiven Feld stehende Zeichen auf dem Band löschen, stehen lassen oder es durch ein anders ersetzen soll. „Der Fortschritt der Arbeit und der Status des Computers ist zu jeder Zeit allein durch die Arbeitsanweisung und die Symbole auf dem Band bestimmt“, schreibt Turing.

Schema einer Turing-Maschine: Die Felder enthalten jeweils ein Symbol, das vom Lese-Schreib-Kopf gelesen und verändert werden kann. Die Arbeitsanweisung sagt dem Kopf, ob und wie er sich bewegen soll und ob er das Symbol ändern,löschen oder stehen lassen soll. © gemeinfrei

Eine Maschine für alle Aufgaben

„Damit verkörperte diese Maschine bereits das essenzielle Prinzip eines Computers: einer einzigen Maschine die jede definierte Aufgabe übernehmen kann, indem sie ein entsprechendes Programm erhält“, erklärt Andrew Hodges, Mathematiker der University of Oxford und Autor der bisher umfassensten Biografie Turings. Und ähnlich wie bei heutigen Computern sieht Turing bereits vor, dass komplexere Symbole und Aufgaben über eine Abfolge von einfachen, grundlegenden Schritten dargestellt werden können.

Ausgehend von dieser Idee entwickelt zehn Jahre später der Mathematiker John von Neumann die Rechnerarchitektur, auf der heute so gut wie alle modernen Computer beruhen: Das Programm und die von ihm verarbeiten Daten liegen binär kodiert im selben Speicher. Die Arbeitsanweisungen können dadurch im laufenden Rechenvorgang verändert werden. „Die Worte, die die Anweisungen kodieren, werden im Speicher wie Zahlen behandelt“, erklärt von Neumann 1945.

Der Prototyp von Turings Automatic Computing Engine (ACE), 1950 am britischen National Physical Laboratory fertiggestellt © Philafrenzy/CC-by-sa 2.0

EDVAC und ACE – die ersten elektronischen Turing Maschinen

Von Neumann beginnt damals gerade damit, im Auftrag des US-Militärs eine elektronische Version von Turings universeller Maschine zu konstruieren, den „Electronic Discrete Variable Automatic Computer“ (ECVAC). Mit diesem Rechner kommt er Turings eigener Konstruktion, der Automatic Computing Engine (ACE) knapp zuvor. Turing hat das Konzept für die ACE zwar bereits 1946 fertig, die Konstruktion des Prototyps dauert jedoch bis 1950. Dann allerdings ist seine Version der universellen Turing Maschine mit einem Megahertz Taktrate für kurze Zeit der schnellste Rechner der Welt.

Seither sind mehr als 60 Jahre vergangen, aber noch immer steckt in jedem unserer Rechner die von Neumann modifizierte Turing-Maschine. „Jeder, der heute auf einer Computertastatur tippt, eine Tabellenkalkulation oder ein Word-Dokument öffnet, arbeitet auf einer Reinkarnation einer Turing-Maschine“, schrieb das Time Magazine im Jahr 1999, das Alan Turin unter die 100 wichtigsten Menschen des 20. Jahrhunderts wählte.

Nadja Podbregar
Stand: 22.06.2012