Insbesondere in der Mathematik und Logik hat man schon seit langem versucht, die entwickelten Berechnungs- und Schlußverfahren möglichst präzise zu beschreiben4.4. Dort spricht man statt von Verfahren häufig auch von Algorithmen4.5. Der Begriff des Algorithmus wurde erst im 20. Jahrhundert soweit präzisiert, daß auch mechanische Apparaturen einen Algorithmus ausführen können. Ein Algorithmus ist eine endliche Menge von Regeln, die uns genau angeben, was in jedem Moment der Ausführung eines solchen Algorithmus zu tun ist, um eine bestimmte Klasse von Aufgaben oder Problemen zu lösen.4.6 Wenn ein Algorithmus zur Lösung einer Klasse K von Problemen gegeben ist, so ist jedermann dazu in der Lage, jedes einzelne Problem dieser Klasse K zu lösen. Vorausgesetzt, er ist in der Lage die einzelnen Operationen, die der Algorithmus vorschreibt, auszuführen. Die einzelnen Operationen werden durch die Regeln, aus denen sich der Algorithmus zusammensetzt, bestimmt. So kann beispielsweise ein Schuljunge den euklidischen Algorithmus4.7 erlernen und ihn richtig anwenden, ohne dabei zu verstehen, warum der Algorithmus zu einer richtigen Antwort führt.
Ein Mensch, der einen Algorithmus anwendet, benutzt dafür bestimmte Daten. Darunter fallen die Regeln des Algorithmus, die er im Kopf hat und die übrigen Daten, die er verwendet und die außerhalb seines Kopfes festgehalten sind - zum Beispiel auf Papier niedergeschrieben. Man kann also davon ausgehen, daß Speichermedien benutzt werden, um einerseits Daten, die vor der Ausführung eines Algorithmus vorliegen, zu speichern. Dazu zählen die Regeln des Algorithmus selbst und die Beschreibung des zu lösenden Problems. Andererseits wird ein Speichermedium benötigt, um Zwischenergebnisse zu speichern, die im Laufe der Ausführung eines Algorithmus entstehen. Zweitens muß dieser Mensch eine festumrissene Menge von elementaren Operationen ausführen können. Nämlich genau diejenigen Operationen, die in den verschiedenen Regeln des Algorithmus vorkommen. Als drittes ist zu beachten, daß die Reihenfolge und die Auswahl der Regeln und der in ihnen beinhalteten Operationen richtig durchgeführt wird.
Von diesen drei Aufgaben ist die zweite Aufgabe, die richtige Ausführung von elementaren Operationen, sicherlich am einfachsten technisch zu realisieren - insbesondere, wenn die elementaren Operationen hinreichend einfach gehalten werden. Die erste Aufgabe, das Speichern von Daten - insbesondere des Algorithmus - erscheint schon schwieriger, da es auch nicht so offensichtlich ist, wie die allgemeine Form einer algorithmischen Regel aussieht. Die dritte Aufgabe, die Regeln des Algorithmus in der richtigen Reihenfolge auszuwählen, muß ebenfalls für beliebige Algorithmen gelöst werden. Sie muß also auch für beliebige Regelmengen richtig funktionieren.
Wenn man die
praktische Realisierung von Rechenmaschinen betrachtet, so ist die
dritte Aufgabe in Form eines sogenannten Steuerwerks
realisiert.
Die zweite Aufgabe übernimmt eine sogenannte
arithmetisch-logische Einheit.
Bei der ersten Aufgabe wurde bei den
frühen Entwicklungen von Computern der Algorithmus außerhalb des
Einflußbereichs der
Maschine durch externe Knöpfe eingestellt. In späteren
Entwicklungen von
Rechenmaschinen wurde der Algorithmus zusammen mit den
Zwischenergebnissen, die bei der Ausführung des Algorithmus entstehen, in
einem elektrischen oder elektronischen Speicher abgelegt.
Dies ist eine grobe Beschreibung des architektonischen Prinzips der meisten
heutigen Computer, die von Neumann-Architektur (Abbildung 3.1).
Der Begriff des Algorithmus war bis in die dreißiger Jahre dieses Jahrhunderts eher vage. Was beispielsweise eine Regel ist, die mechanisch interpretiert werden kann und ohne zusätzliche Hintergrundannahmen korrekt von einer mehr oder weniger einfachen Maschine ausgeführt werden kann, ist zunächst unklar. Zu diesem Zweck wird in jedem Fall eine spezifische Sprache benötigt, die einerseits hinreichend ausdrucksstark sein muß, um in ihr die Regeln des Algorithmus ausdrücken zu können, und andererseits darf es bei deren Interpretation keine Zweifelsfälle und Mehrdeutigkeiten geben. So gelangt man von dem Problem, den Begriff eines Algorithmus zu explizieren, zu zwei ähnlich schwierigen Problemen: Es muß eine `mechanische' Sprache zusammen mit einer Maschine definiert werden, die in der Lage ist, die Sätze der mechanischen Sprache eindeutig und korrekt zu interpretieren. Die Maschine muß geeignete elementare Operationen ausführen. Zu diesem Zweck könnte man eine große Zahl von Algorithmen sammeln und sie auf ihre Gemeinsamkeiten hin untersuchen. Hierbei ist es allerdings nicht klar, wie eine solch induktive Vorgehensweise zu einer zufriedenstellenden Abstraktion von den konkret betrachteten Algorithmen führen soll.
Alan M. Turing Turing[Tur37] betrachtete Algorithmen, die von Menschen korrekt durchgeführt werden können. Dadurch kam er zu einer Reihe von elementaren Operationen, die mit Sicherheit von einem mechanischen Apparat richtig ausgeführt werden können. Andererseits reichten sie dafür aus, auch die schwierigsten Algorithmen, die Menschen ausführen können, durch einen mechanischen Apparat ausführen zu lassen. Turings elementare Operationen können zu komplexeren Operationen zusammengesetzt werden. Dabei benötigt man nur entsprechend mehr Anweisungsregeln, also einen entsprechend längeren Algorithmus und mehr Speicherplatz für die entstehenden Zwischenergebnisse. Wenn eine solch elementare Maschine erst einmal konzipiert ist, dann ist es nicht mehr schwierig eine passende Sprache zu entwerfen, in der sich Regeln formulieren lassen, die von der Maschine eindeutig interpretiert werden können.
Wenn man sich einen Menschen vorstellt, der auf einem in Quadrate unterteiltem Stück Papier eine Berechnung durchführt, so spielen die folgenden Dinge dabei eine wesentliche Rolle:
Was diesen Vorgang mechanisch macht, sind die beiden folgenden Eigenschaften:
Entsprechend dem ersten Prinzip hängt die Entscheidung, welcher Berechnungsschritt als nächster durchgeführt wird, nur von den Symbolen auf den abgegrenzten Kästchen auf dem Papier und dem gegenwärtigen `Geisteszustand' ab. Wenn eine Berechnung gemäß einem vorgegebenen Algorithmus durchgeführt wird, so muß der Algorithmus für jede Situation, in die der Berechnende während der Berechnung gelangt, angeben, was zu tun ist. Eine solche Situation wird dabei durch die Symbole, die in den betrachteten Kästchen auf dem Papier stehen und durch den spezifischen `Geisteszustand' in dem sich der Berechnende befindet, charakterisiert.
Der hier benutzte Begriff `Geisteszustand' bedarf dabei einer genaueren
Erklärung. Zunächst soll zur größeren Klarheit die Wahrnehmung
des Berechnenden eines Algorithmus ohne Verlust der Allgemeinheit in
zwei getrennte Teile unterteilt werden:
Der eine Teil seien die visuellen Wahrnehmungen,
das
heißt, genau die Symbole, die der Berechnenden auf denjenigen Kästchen
seines Papierstückes sieht, die seinem momentanem Augenmerk gelten. Der
andere Teil seiner momentanen Wahrnehmungen bezieht sich auf
seinen inneren Sinn. Dazu
gehören sicherlich auch viele irrelevante Dinge. Beispielsweise
könnte er
feststellen, daß sein Magen knurrt; dies sollte jedoch keinerlei
Einfluß darauf haben, welcher Berechnungsschritt als Nächstes
durchgeführt wird. Vielmehr können wir davon ausgehen, daß die für die korrekte
Ausführung eines Algorithmus relevanten Wahrnehmungen
durch den inneren Sinn
sich ausschließlich darauf beziehen,
welche Berechnungsschritte
bisher bereits durchgeführt wurden.
Damit kann das, was als `Geisteszustand' bezeichnet wurde, wie folgt präzisiert werden: Es handelt sich um eine eindeutige Disposition, auf bestimmte Symbole, die auf dem Papier in den betrachteten Kästchen stehen, in genau festgelegter Weise zu reagieren; also den nächsten Berechnungsschritt auszuwählen. In dem `Geisteszustand' soll also lediglich gespeichert werden, an welcher Stelle des gesamten Berechnungsverfahrens sich der Berechnende augenblicklich befindet.
Gemäß dem oben genannten Prinzip der Endlichkeit soll davon ausgegangen werden, daß der Berechnende nur in der Lage ist, eine endliche Anzahl von verschiedenen `Geisteszuständen' in obigem Sinne einzunehmen. Gleichermaßen wird davon ausgegangen, daß der Berechnende lediglich in der Lage ist, zu jedem Zeitpunkt eine endliche Zahl von unterschiedlichen Zeichen in den Kästchen auf dem Papier wahrzunehmen. Ja, man kann sogar davon ausgehen, daß sowohl die Zahl der verschiedenen `Geisteszustände', als auch die Zahl der unterschiedlichen Zeichen, die wahrgenommen werden können, eine feste Obergrenze haben. Die Obergrenze für die unterschiedlichen Symbole auf dem Papier wird verhältnismäßig klein sein, während die Obergrenze für die Zahl der verschiedenen `Geisteszustände' wesentlich größer sein wird. Daraus folgt unmittelbar, daß der Berechnende zu jedem Zeitpunkt auch nur eine endliche Zahl von Kästchen auf dem Papier überblicken kann. Wenn es notwendig ist, mehr Kästchen in Betracht zu ziehen, so muß dies in mehreren Schritten zeitlich nacheinander geschehen.
Aus den obigen Erörterungen folgt, daß die Zahl der unterschiedlichen Zeichen, die in ein Kästchen geschrieben werden können, endlich ist. Dies folgt einerseits aus der endlichen Zahl von eindeutigen Dispositionen, den `Geisteszuständen' und andererseits hat es bei der Ausführung eines Algorithmus wenig Sinn, Zeichen auf das Papier zu schreiben, die anschließend nicht mehr eindeutig klassifiziert werden können. Man kann sich zwar vorstellen, prinzipiell unendlich lange Zeichenketten zu schreiben, dies würde aber wiederum zeitlich nacheinander durch wiederholtes Schreiben einzelner Zeichen aus einer endlichen Auswahl von Zeichen geschehen. Nun soll das Prinzip der Endlichkeit noch auf die Zahl der Operationen angewendet werden, die in jedem Rechenschritt durchgeführt werden können. Wie oben bereits erwähnt, besteht ein solcher Rechenschritt aus dreierlei Typen von Operationen:
Zusammenfassend kann man also davon ausgehen, daß der Berechnende zu jedem Zeitpunkt der Berechnung immer nur genau ein Kästchen auf dem eindimensionalen Band betrachtet. Als Berechnungsoperationen nur den Inhalt genau dieses Kästchens verändert und das Augenmerk im Anschluß daran entweder auf dem gleichen Kästchen beläßt, oder aber es auf das Kästchen ein Feld links bzw. rechts von dem alten Kästchen bewegt. Außerdem geht er eventuell in einen anderen `Geisteszustand' über. Als Konsequenz davon bleiben nur noch zwei quantitative Unbekannte übrig:
Die Zahl der zu benutzenden unterschiedlichen Zeichen und die Zahl der verschiedenen `Geisteszustände' bzw. Berechnungsdispositionen. Wenn die Zahl der unterschiedlichen Zeichen kleiner wird, im Extremfall nur noch zwei unterschiedliche Zeichen, so wird man dementsprechend mehr unterschiedliche Berechnungsdispositionen benötigen. Reduziert man hingegen die Zahl von verschiedenen Berechnungsdispositionen, so muß zum Ausgleich die Zahl der verschiedenen Zeichen, die in ein einzelnes Kästchen geschrieben werden können, erhöht werden.
Für die formale Beschreibung eines Algorithmus werden sogenannte
Turingtabellen verwendet, die die Operationen
einer zugehörigen Turingmaschine beschreiben.
(Siehe Abbildung 3.2.) In einer Turingtabelle wird
für jeden der möglichen `Geisteszustände' und jedes
mögliche Zeichen in dem Kästchen dem das Augenmerk gilt,
die drei auszuführenden
Operationstypen angegeben.
Durch eine solche Turingtabelle zusammen mit der Auszeichnung eines
Start- und Endzustandes ist ein Algorithmus vollständig beschrieben.
Ein solcher Algorithmus bzw. eine solche Turingmaschine berechnet
für jede mögliche Eingabe auf dem Band, einen bestimmten Ausgabewert
A(e) oder aber rechnet endlos und gibt somit keinen Wert aus.
Mithin kann man sagen, die Turingmaschine berechnet eine bestimmte
(eventuell partielle) Funktion.
