Fallout Fallout
 
 
Einführung - Der mathematische Algorithmus

Der Begriff des Algorithmus ist ein grundlegender Begriff der Mathematik. Er ist intuitiv gegeben und gewöhnlich versteht man darunter ein allgemeines Verfahren zur Lösung einer Klasse von Problemen. Ein Algorithmus wird durch eine endliche Menge von Regeln definiert, die nacheinander angewendet und oft nach bestimmten Bedingungen wiederholt werden. Ein klassisches Beispiel sind der Euklidische Algorithmus und das Gaußsche Eliminationsverfahren.
Bereits von den Arabern sind, unter dem Einfluss der Inder, Algorithmen zur Behandlung algebraischer Aufgaben entwickelt worden. Das Wort »Algorithmus« geht auf den Namen des arabischen Mathematikers Mohammed Ibn Musa Alchwarizmi (um 800) zurück, der durch sein (später als »liber algorithmi« zitiertes) Buch über die Behandlung algebraischer Gleichungen wesentlich zur Verbreitung der damals entstandenen Rechenmethoden beigetragen hat.
Descartes entwickelte die analytische Geometrie mit der Absicht, die Geometrie algebraischen Rechenmethoden zugänglich zu machen. Auch von Leibniz ist bekannt, dass ihm eine allumfassende Methode, jedes Problem durch »Rechnen« zu lösen, vorschwebte und er sich daher um die Entwicklung von Algorithmen bemühte. Er war einer der ersten, die den Bau einer Rechenmaschine vorsahen.
Die mangelnde mathematische Genauigkeit in der gängigen Definition eines Algorithmus störte viele Mathematiker und Logiker des 19. und 20. Jahrhunderts. A.A. Markow schuf 1906 eine generelle Theorie stochastischer Prozesse bzw. Zufallsprozesse durch seine sogenannten Markow-Ketten, die 1936 von A. Kolmogorow generalisiert wurde. Der Begriff des algorithmischen Zufalls wurde als ultimative Definition des Zufalls akzeptiert und führte in den 1960er Jahren durch A. Solomonow (»A Formal Theory of Inductive Inference«, 1964), A. Kolmogorow (»Three Approaches to the Quantitative Definition of Information«, 1965) und G. Chaitin (»On the Lenght of Programs for Computing Finite Binary Strings«, publiziert 1966) zur Begründung einer Algorithmischen Informationstheorie, die heute im wesentlichen als Teil der Komplexitätstheorie behandelt wird.
Um Algorithmen zur Lösung möglichst vieler mathematischer Probleme zu haben, versuchte man immer allgemeinere Algorithmen zu finden. Im Bereich der Logik hatte man Kalküle entwickelt, die es gestatten, große Teile der Mathematik mit Hilfe eines solchen Kalküls aus wenigen Axiomen herzuleiten, so z.B. in den Principia Mathematica (1910-1913) von A.N. Whitehead und B. Russel.
Gefragt wurde nun nach einem allgemeinen Algorithmus, der es ermöglicht, alle mathematischen Sätze einer mathematischen Theorie, z.B. der Geometrie, aus Axiomen der Theorie herzuleiten. Mit den Bestrebungen, dieses Problem zu lösen, begann die eigentliche Theorie der Algorithmen und der Begriff des Algorithmus wurde präzis definiert.
Das Problem der Präzisierung des Algorithmenbegriffs ist, historisch wie logisch, eng verknüpft mit der Präzisierung des Begriffs der berechenbaren Funktion: damit eine Funktion berechenbar ist, muss es einen Algorithmus geben, mit dessen Hilfe man für jedes Argument den zugehörigen Funktionswert ausrechnen kann. Diese Untersuchungen begannen mit einer Arbeit von Thoralf Skolem in Jahre 1923. Die von Skolem betrachteten Funktionen sind die primitiv-rekursiven Funktionen. Als Begriff wurden diese Funktionen erst 1931 von Kurt Gödel in seiner Arbeit eingeführt. Das war der Anlass, eine allgemeinere Definition der Berechenbarkeit zu suchen. Um 1934 entwickelten Herbrand und Gödel das Konzept der allgemein-rekursiven Funktion, wobei Gödel noch nicht davon überzeugt war, damit den allgemeinen Begriff der berechenbaren Funktion gefunden zu haben. Erst 1936, als A. Church und S.C. Kleene eine völlig andere Präzisierung des Berechenbarkeitsbegriffes gefunden hatten (die _(lambda)-Definierbarkeit) und sie in Zusammenarbeit mit J.B. Rosser die Äquivalenz dieses Begriffes mit dem von Herbrand und Gödel nachweisen konnten, sprach Church seine berühmte These aus: »Der intuitiv gegebene, allgemein gebräuchliche Begriff der berechenbaren arithmetischen Funktion ist identisch mit dem exakt definierten Begriff der allgemein-rekursiven Funktion''. Obwohl diese These nicht bewiesen werden kann, ist sie durch viele spätere Ergebnisse immer mehr gestärkt worden, so dass heute ihre Gültigkeit allgemein angenommen wird. Als sich herausstellte, dass man auch arithmetische Funktionen zu betrachten hatte, die wie die allgemein-rekursiven Funktionen erklärt werden, jedoch nur mit einer Teilmenge der natürlichen Zahlen als Definitionsbereich, führte man den weiteren Begriff der partiell-rekursiven Funktion ein (Kleene 1938) und verwandte ihn ebenfalls in der Church’schen These.
Ein weiterer, entscheidender Schritt in die Theorie der Berechenbarkeit war die Arbeit von A.M. Turing »On Computable Numbers, with an Application to the Entscheidungsproblem« (1936-37). Hier wird der fundamentale Begriff der automatischen Maschine, heute Turingmaschine genannt, schon vor der technischen Entwicklung von Rechenmaschinen eingeführt. Dieser Begriff ermöglicht einen sehr natürlichen und einfachen Zugang zu einer exakten Definition der berechenbaren Funktion und des Algorithmus. Fast gleichzeitig mit Turing und unabhängig von ihm veröffentlichte E. Post 1937 einen ganz ähnlichen Vorschlag zur Präzisierung des Berechenbarkeitsbegriffs. Turing konstatierte die Äquivalenz der Begriffe der mit einer Turingmaschine berechenbaren Funktion und der im gewöhnlichen Sinne berechenbaren Funktion. Weil Turing 1937 die Gleichwertigkeit seines Berechenbarkeitsbegriffes und der _ (lambda)-Definierbarkeit von Church nachweisen konnte, konnte gezeigt werden, dass die Church’sche und Turing’sche These identisch sind.
Man hatte nun für den Begriff der berechenbaren Funktion drei verschiedene Präzisierungen gefunden und ihre Äquivalenz nachgewiesen. Dabei hat der Begriff der Turing-Berechenbarkeit noch eine besondere Bedeutung. Er liefert nämlich eine Definition der mechanischen Berechenbarkeit. Das erste Problem der klassischen Mathematik, dessen Unlösbarkeit nachgewiesen wurde, ist ein Problem von A. Thue (1914) aus der Theorie der Halbgruppen. Seine Unlösbarkeit wurde gleichzeitig, aber unabhängig von E. Post und A.A. Markov 1947 bewiesen. Aus seiner Unlösbarkeit läßt sich die Unlösbarkeit einer Reihe weiterer, sehr berühmter Probleme der Mathematik folgern, wie z.B. die Unlösbarkeit des Wortproblems der Gruppentheorie oder das Entscheidungsproblem der Prädikatenlogik.
Mit Axel Thue, der 1914 mit seiner Arbeit »Probleme über Veränderungen von Zeichenreihen nach gegebenen Regeln« eine erste genaue Fassung eines algorithmischen Entscheidungsverfahrens lieferte, begann die Entwicklung von Programmiersprachen. Mit Hilfe eines endlichen Alphabets (z.B. sechs Buchstaben) und eines Regelsystems R (z.B. zwei Umformungsregeln) konnte so im Einzelfall festgestellt werden, ob eine vorgegebene Zeichenreihe aus dem gegebenen Alphabet und Regelsystem erzeugt werden könnte. Solche Semi-Thue-Systeme dienten der Entwicklung der Theorie der formalen Sprachen. Noam Chomsky hat in den 1950er Jahren Semi-Thue-Systeme zur Beschreibung grammatikalischer Strukturen natürlicher Sprachen herangezogen. Aufbauend auf den Semi-Thue-Systemen von Chomsky haben John Backus und Peter Naur um 1960 eine formale Notation eingeführt, um die Syntax einer Sprache zu beschreiben woraus sich die erste erfolgreiche Programmiersprache entwickelte: ALGOL 60 (algorithmic language). Alle nachfolgenden Programmiersprachen FORTRAN, COBOL, BASIC, Pascal, C etc. sind ALGOL-ähnlich aufgebaut.