Detaillierte Anweisungen, die einen Rechenprozess definieren (der dann als algorithmisch bezeichnet wird), der mit einer beliebigen Eingabe (aus einer bestimmten Anzahl von Eingaben, die für den gegebenen Algorithmus möglich sind) und mit Anweisungen beginnt, die darauf abzielen, ein Ergebnis (oder eine Ausgabe) zu erhalten, das vollständig durch die Eingabe bestimmt ist. So sind beispielsweise die in der Grundschule gelehrten Regeln für die spaltenweise Addition, Subtraktion, Multiplikation und Division Algorithmen; bei diesen Algorithmen sind die möglichen Ergebnisse nichtnegative, im Dezimalsystem geschriebene ganze Zahlen, während die möglichen Eingaben geordnete Paare solcher Zahlen sind. Im Allgemeinen wird nicht davon ausgegangen, dass das Ergebnis notwendigerweise erzielt wird: Der Prozess der Anwendung eines Algorithmus auf eine mögliche Eingabe (d. h. ein algorithmischer Prozess, der von dieser Eingabe ausgeht) kann auch enden, ohne dass ein Ergebnis erzielt wird (in einem solchen Fall hat man einen ergebnislosen Stopp), oder er kann überhaupt nicht enden. Wenn der Prozess abbricht (nicht abbricht), dann sagt man, dass die Eingabe für den betreffenden Algorithmus geeignet ist (nicht geeignet ist).
Ein wichtiges Ergebnis auf diesem Gebiet ist die Unentscheidbarkeit des sogenannten Halteproblems. Es ist möglich, einen Algorithmus $ \alpha $ so zu konstruieren, dass es keinen Algorithmus gibt, der entscheidet, ob eine beliebige Eingabe, die für $ \alpha $ möglich ist, auch für $ \alpha $ geeignet ist oder nicht. Insbesondere kann man einen solchen Algorithmus $ \alpha $ finden, für den die Menge seiner möglichen Eingaben die Menge der natürlichen Zahlen ist.
Der Begriff des Algorithmus ist einer der zentralen Begriffe in der modernen Mathematik, insbesondere im Bereich des Rechnens. Ein Beispiel dafür ist das folgende. Die numerische Lösung von Gleichungen eines bestimmten Typs zu finden, ist gleichbedeutend mit der Konstruktion eines Algorithmus, der eine beliebige Gleichung dieses Typs und eine beliebige positive rationale Zahl $ \epsilon $ in eine Zahl (oder eine Menge von Zahlen) umwandelt, die sich von der/den Wurzel(n) dieser Gleichung um weniger als $ \epsilon $ unterscheidet. Der Begriff „Rechenvorgang“, wie er im Zusammenhang mit einem Algorithmus verwendet wird, darf jedoch nicht so verstanden werden, dass damit nur numerische Berechnungen gemeint sind: Selbst in der elementaren Algebra werden Berechnungen mit Buchstaben verwendet. Die üblichen arithmetischen Berechnungen beinhalten einige Symbole, die keine Zahlen sind (Klammern, Gleichheitszeichen, Symbole für arithmetische Operatoren). Es ist daher sinnvoll, Algorithmen zu betrachten, die beliebige Symbole und aus Symbolen zusammengesetzte Objekte verwenden. Das einfachste Beispiel für ein solches Objekt ist eine lineare Folge von Symbolen, die ein Wort bilden. Es ist auch möglich, „nicht-lineare“ Objekte zu betrachten – algebraische Matrizen, Ableitungsbäume einer formalen Sprache und allgemeine Graphen. Intuitiv besteht die geringste Anforderung an die Eingaben und Ergebnisse von Algorithmen darin, dass sie konstruktive Objekte sein müssen (vgl. Konstruktives Objekt). Der Begriff des Algorithmus ist also sehr allgemein. Man kann von einem Algorithmus für die Übersetzung von einer Sprache in eine andere sprechen, von einem Algorithmus eines Fluglotsen (der Informationen über die Bewegungen von Flugzeugen nach festen Regeln verarbeitet) und anderen Beispielen für algorithmisch beschriebene Steuerungsprozesse. Folglich ist der Begriff des Algorithmus eine der zentralen Ideen in der Kybernetik und Informatik.
Beispiel für einen Algorithmus.
Sind die möglichen Eingaben und die möglichen Ergebnisse alle möglichen Wörter über dem Alphabet $ \{ a, b \} $. Der Übergang von einem Wort $ X $zu einem Wort $ Y $ist in den folgenden beiden Fällen „zulässig“ (wobei $ P $ein beliebiges Wort bezeichnet): 1) $ X $ist von der Form $ aP $, und $ Y $ist von der Form $ Pb $; oder 2) $ X $ist von der Form $ baP $, während $ Y $von der Form $ Paba $ ist. Die Anweisungen sind wie folgt formuliert: „Bezeichne ein Wort als Eingabe, führe die erlaubten Übergänge aus, bis ein Wort der Form aaP erhalten wird; halte dann an und lasse das Wort P das Ergebnis sein“. Diese Anweisungen bilden einen Algorithmus, der mit $ \mathfrak A $ bezeichnet wird. Nehmen wir das Wort $ babaa $ als Eingabe. Nach einer Transition erhält man $ baaaba $; nach der zweiten erhält man $ aabaaba $. Hier hält der Algorithmus mit $ baaba $ als Ergebnis an. Betrachten Sie eine weitere Eingabe $ baaba $. Man erhält nacheinander $ abaaba, baabab, abababa, bababab, babababa , . . . $. Es kann gezeigt werden, dass dieser Prozess niemals endet (d.h. keines der erzeugten Wörter wird jemals mit $ aa $ beginnen). Nehmen wir nun $ abaab $ als Eingabe. Man erhält $ baabb, abbaba, bbabab $; es sind keine weiteren zulässigen Übergänge möglich, und gleichzeitig ist die Abbruchbedingung nicht erfüllt. Man hat einen ergebnislosen Stop. Die Eingabe $ babaa $ ist also für $ \mathfrak A $ geeignet, die Eingaben $ baaba $ und $ abaab $ sind es nicht.
Die Bedeutung von Algorithmen.
In der Wissenschaft begegnet man Algorithmen überall: Eine „allgemeine“ Lösung eines Problems erfordert einen Algorithmus. Die Fähigkeit des Menschen, Zahlen zu addieren, ist ein Beispiel dafür. Nicht in dem Sinne, dass er früher oder später die Summe zweier beliebiger Zahlen finden kann, sondern in dem Sinne, dass er eine Methode zur eindeutigen Addition zweier beliebiger Zahlen besitzt, die in schriftlicher Form vorliegt, also einen Additionsalgorithmus wie das bekannte spaltenweise Additionsverfahren. „Im Allgemeinen“ wird die Lösung eines Problems als Lösung eines algorithmischen Problems formalisiert. Ein algorithmisches Problem besteht aus einzelnen Problemfällen, für deren Lösung ein einziger Algorithmus gefunden werden muss. Wenn es keinen solchen Algorithmus gibt, ist das algorithmische Problem unlösbar. So sind das Problem der numerischen Lösung von Gleichungen eines bestimmten Typs und das Problem der automatischen Übersetzung algorithmische Probleme. Ihre Problemfälle sind die numerische Lösung einzelner Gleichungen des gegebenen Typs bzw. die Übersetzung einzelner Phrasen. Weitere Beispiele sind die Überprüfung algebraischer Gleichungen in der Algebra und das algorithmische Problem der Erkennung der Ableitbarkeit von Sätzen aus gegebenen Axiomen in der mathematischen Logik. (In der mathematischen Logik ist der Begriff des Algorithmus auch deshalb wichtig, weil er als Grundlage für den Schlüsselbegriff des Kalküls dient, der eine Verallgemeinerung und genauere Form der intuitiven Begriffe „Beweis“ und „Demonstration“ darstellt). Die Feststellung der Unlösbarkeit eines gegebenen algorithmischen Problems (z.B. das Problem der Wahrheitsfindung oder der Beweisbarkeit von Sätzen in einer logisch-mathematischen Sprache) ist wichtig, weil sie zeigt, dass bestimmte Problemfälle dieses Problems prinzipiell nur mit Methoden gelöst werden können, die für jeden einzelnen Problemfall spezifisch sind.
Die wissenschaftliche Bedeutung des Konzepts eines Algorithmus ist seit langem bekannt. Seit den frühesten Zeiten haben die Menschen nach konstruktiven Methoden zur Lösung mathematischer Probleme gesucht. Diese Bemühungen profitierten in der Regel von der neuen Verfügbarkeit geeigneter symbolischer Notationen. Dieser Prozess hat einen bedeutenden Beitrag zu den wissenschaftlichen Erkenntnissen geleistet, insbesondere nachdem klar geworden war, dass einige Probleme von Natur aus unlösbar sind (Quadratur des Kreises usw.). Nachdem man erkannt hatte, dass bestimmte Probleme nicht durch direkte Berechnungen gelöst werden können, wurde im 19. Jahrhundert das theoretische Konzept der Menge geboren. Erst nach einer Periode rasanter Entwicklung dieses Konzepts (die nicht mit Problemen konstruktiver Methoden im modernen Sinne zu tun hatte) war es Mitte des 20. Jahrhunderts möglich, zu konstruktiven Problemen zurückzukehren, aber dies geschah auf einer anderen Ebene, bereichert durch das Konzept eines Algorithmus, das sich inzwischen herauskristallisiert hatte. Dieses Konzept bildet die Grundlage der konstruktiven Strömung in der Mathematik.
Das Wort „Algorithmus“ stammt von dem Wort „algoritmi“ ab, wobei letzteres die lateinische Transliteration des Namens des arabischen Mathematikers Al-Khwarizmi aus dem 9. Ein „Algorithmus“ war im Europa des Mittelalters „das Dezimal-Positionssystem und die Kunst, damit zu rechnen“, da das Positionssystem durch die lateinische Übersetzung (12. Jahrhundert) der Abhandlung von Al-Khwarizmi in Europa eingeführt wurde.
Die Struktur eines algorithmischen Prozesses.
Ein algorithmischer Prozess ist ein Prozess der aufeinanderfolgenden Umwandlung von konstruktiven Objekten durch diskrete „Schritte“, wobei jeder Schritt aus der Ersetzung eines konstruktiven Objekts durch ein anderes besteht. Wendet man also den Algorithmus $ \mathfrak A $ auf das Wort $ baaba $ an, so entstehen nacheinander die Wörter $ baaba, abaaba, baabab $ usw. Wendet man z. B. den Algorithmus der spaltenweisen Subtraktion auf das Zahlenpaar <307, 49 > an, so erhält man nacheinander die folgenden Konstruktionsobjekte:
$$ \begin{array}{rrrr}307 &3 \dot{0} 7 &\dot{3} \dot{0} 7 &\dot{3} \dot{0} 7 \\\\underline{- 49 } &\underline{- 49 } &\underline{- 49 } &\underline{- 49 } \\{} & 8 &58 &258 \\\\end{array}$$
Es sei angemerkt, dass in einer Reihe von aufeinanderfolgenden konstruktiven Objekten jedes aufeinanderfolgende konstruktive Objekt (im Rahmen des gegebenen Algorithmus) vollständig durch das ihm unmittelbar vorangehende konstruktive Objekt bestimmt ist. Im strengeren Ansatz wird auch angenommen, dass der Übergang von einem beliebigen konstruktiven Objekt zu dem unmittelbar folgenden hinreichend „elementar“ ist – in dem Sinne, dass die einstufige Transformation des vorangehenden in das unmittelbar folgende Objekt lokal ist (es ist nicht das gesamte konstruktive Objekt, das transformiert wird, sondern nur sein durch den Algorithmus begrenzter Teil; außerdem wird diese Transformation selbst nicht durch das gesamte vorangehende Objekt bestimmt, sondern nur durch einen begrenzten Teil von ihm).
Dementsprechend hat man nicht nur eine Menge möglicher Eingaben und eine Menge möglicher Ergebnisse, sondern auch eine Menge möglicher Zwischenergebnisse, die das Arbeitsmedium darstellen, in dem sich der algorithmische Prozess entwickelt. Für $ \mathfrak A $ fallen diese drei Mengen zusammen, aber das gilt nicht für den Algorithmus der spaltenweisen Subtraktion – die möglichen Eingaben sind Zahlenpaare, die möglichen Ergebnisse sind Zahlen (alle im Dezimalsystem), während die möglichen Zwischenergebnisse „dreistöckige“ Sätze vom Typ
$$ \begin{array}{r} p \\\\underline{- q } \\\ r \\\\end{array}$$
wobei $ q $der geschriebene Datensatz der Zahl im Dezimalsystem ist, $ r $ein ähnlicher Datensatz oder das leere Wort ist, während $ p $der geschriebene Datensatz einer Zahl im Dezimalsystem ist, mit Punkten über einigen der Ziffern. In der Regel lassen sich mehrere (nicht unabhängige) Parameter unterscheiden, die für einen Algorithmus charakteristisch sind: 1) die Menge der möglichen Eingaben; 2) die Menge der möglichen Ergebnisse; 3) die Menge der möglichen Zwischenergebnisse; 4) die Startregel; 5) die direkte Übergangsregel; 6) die Abbruchregel; und 7) die Regel für die Rückgewinnung des Ergebnisses.
Formalisierung des Konzepts eines Algorithmus.
Das Konzept eines Algorithmus in seiner allgemeinen Form ist ein grundlegendes mathematisches Konzept, das nicht in Form von einfacheren Konzepten definiert werden kann. Streng genommen schränken Formalisierungen des Algorithmusbegriffs diesen sogar etwas ein. In jeder dieser Formalisierungen wird eine genaue Definition einer Klasse gegeben, innerhalb derer jeder der Parameter variieren kann. Die verschiedenen Formalisierungen unterscheiden sich voneinander durch die Auswahl dieser Klassen. Da die Parameter eindeutig einen Algorithmus definieren, bestimmt die Wahl der Parameterdomänen eine Klasse von Algorithmen. Eine solche Wahl kann jedoch nur dann den Anspruch erheben, eine Formalisierung des intuitiven Konzepts des Algorithmus zu sein, wenn man sicher sein kann, dass es für jeden „intuitiven“ Algorithmus einen äquivalenten Algorithmus in der Klasse der Algorithmen gibt, die durch die betrachtete Wahl definiert wird. Diese Forderung wird für jede Formalisierung als fundamentale Hypothese formuliert, die beim gegenwärtigen Wissensstand nicht mathematisch bewiesen werden kann.
Die ersten Formalisierungen dieser Art gehen auf E.L. Post
und auf A.M. Turing zurück, deren Konstruktionen in vielerlei Hinsicht die Ideen vorwegnahmen, auf denen moderne Computer basieren. Es gibt auch Versionen, die von A.A. Markov,
(vgl. Normaler Algorithmus) und von A.N. Kolmogorov , formuliert wurden, der den Ansatz auf konstruktive topologische Komplexe eines bestimmten Typs stützte, was es ermöglicht, die Eigenschaft „lokal“ zu sein einer Transformation genauer auszudrücken. In jeder dieser Formalisierungen steht die Grundhypothese in zufriedenstellender Übereinstimmung mit der Praxis. Ein weiteres Argument für diese Hypothese ist die Tatsache, dass, wie gezeigt werden kann, alle vorgeschlagenen formalen Versionen (der effektiven Berechenbarkeit) äquivalent sind.
Betrachten wir als Beispiel die von Turing vorgeschlagene Formalisierung. In ihrer ursprünglichen Form war dies eine Beschreibung eines theoretischen Computers, bestehend aus 1) einem unendlichen Band, das in aufeinanderfolgende Zellen unterteilt ist, wobei jede Zelle ein Symbol aus dem „Bandalphabet“ der Maschine enthalten kann; und 2) einer „endlichen Steuerung“, die sich zu jedem Zeitpunkt in einem „Zustand“ (aus einer gegebenen endlichen Liste von Zuständen) befindet. Die endliche Steuerung kann sich entlang des Bandes bewegen, eine Zelle nach der anderen, und den Inhalt der Zellen ändern, die sie passiert. Ein Programm, das die Bewegung der endlichen Steuerung überwacht, stellt den Algorithmus für die auf einer solchen Maschine durchgeführten Berechnungen dar (ein „Turing-Algorithmus“). Für eine genauere und detailliertere Beschreibung siehe Turingmaschine. Hier wird eine modernisierte Darstellung von Turings Konstruktion gegeben. Um einen Turing-Algorithmus zu definieren, spezifiziert man a) paarweise disjunkte Alphabete $ B, D, C $, mit einem Unterscheidungsbuchstaben $ \lambda $ in $ D $ und Unterscheidungsbuchstaben $ \alpha $ und $ \omega $ in $ C $; und b) eine Menge von Paaren der Form $ \langle p \xi , \eta Tq \rangle $ mit $ p, q \in C $, $ \xi , \eta \in B \cup D $, während $ T $ eines der drei Symbole $ -, 0, + $ ist; in dieser Menge (die Programm genannt wird) gibt es keine zwei Paare mit der gleichen ersten Koordinate. Die möglichen Eingänge und die möglichen Ausgänge sind Wörter über $ B $, während die möglichen Zwischenergebnisse Wörter über $ B \cup D \cup C $ sind, die nicht mehr als einen Buchstaben von $ C $ enthalten. Die Anfangsregel ist, dass das Anfangswort $ P $ in das Wort $ \lambda \alpha P \lambda $ umgewandelt wird. Die Abbruchregel ist, dass ein Zwischenergebnis, das $ \omega $ enthält, endgültig ist. Die Regel für den Abruf der Ausgabe lautet, dass die Ausgabe die Folge von Buchstaben im endgültigen Zwischenergebnis ist, die auf $ \omega $ folgt und dem ersten nicht zu $ B $ gehörenden Buchstaben vorausgeht. Die Transformationsregel, die $ A $ in $ A ^ \prime $ umwandelt, lautet wie folgt. Der Buchstabe $ \lambda $ wird links und rechts von $ A $ geschrieben; in dem so gebildeten Wort wird der Teil der Form $ \epsilon p \xi $, wobei $ p \in C $, $ \epsilon \xi \in B \cup D $, durch ein Wort $ Q $ gemäß der Regel ersetzt: Im Programm wird ein Paar mit dem ersten Term $ p \xi $ gesucht; der zweite Term dieses Paares sei $ \eta Tq $; ist $ T $ gleich $ – $, ist $ Q = q \epsilon \eta $; ist $ T = 0 $, ist $ Q = \epsilon q \eta $; Ist $ T $ gleich $ + $, so ist $ Q = \epsilon \eta q $. Das durch diesen Austausch erzeugte Wort ist $ A ^ \prime $. Für Referenzen siehe , , , , , , ,
von Algorithmen, Theorie der.
Die oben erwähnte grundlegende Hypothese wird gewöhnlich als Church-Turing-These oder Turing-Hypothese bezeichnet. Diese These besagt, dass das, was nach der eigenen Intuition, was einen effektiven Prozess ausmacht, effektiv berechnet werden kann, auch von einer Turing-Maschine, d.h. einem formal definierten Begriff von Algorithmus, berechnet werden kann. Da es in der Natur der Sache liegt, einen intuitiven informellen Begriff mit einer formalen präzisen Definition zu identifizieren, kann die Church-Turing-These nicht formal bewiesen werden.
Viele Formalisierungen haben sich als gleichwertig erwiesen, und keine Formalisierung hat sich als strikt leistungsfähiger erwiesen. Abgesehen von den oben erwähnten Formalisierungen sind die folgenden Referenzen die gängigsten im Westen: Churchs Formalisierung von Zahlen und berechenbaren Funktionen durch Lambda-Terme, die allgemeinen rekursiven Schemata von Kleene und das von J.C. Shepherdson und H.E. Sturgis vorgeschlagene Registermaschinenmodell, das von S.A. Cook und R.A. Reckhow zu einem realistischeren Computermodell erweitert wurde. Die Versionen von Markov und Kolmogorov sind weniger bekannt. Der Vollständigkeit halber werden auch die Originalverweise auf Turing und Post angegeben.
| A.M. Turing, „On computable numbers, with an application to the Entscheidungsproblem“ Proc. London Math.Soc. Ser. 2 , 42 (1936) pp. 230-265 | |
| A.M. Turing, „Korrekturen zu „On computable numbers, with an application to the Entscheidungsproblem“ “ Proc. London Math.Soc. Ser. 2 , 43 (1937) S. 544-546 | |
| A. Church, „An unsolvable problem of elementary number theory“ Amer. J. Math. , 58 (1936) pp. 345-363 | |
| S.C. Kleene, „General recursive functions of natural numbers“ Math. Ann. , 112 (1936) pp. 727-742 | |
| E.L. Post, „Formal reductions of the general combinatorial decision problem“ Amer. J. Math. , 65 (1943) pp. 197-268 | |
| J.C. Shepherdson, H.E. Sturgis, „Computability of recursive functions“ J. Assoc. Comp. Mach. 10 (1963) pp. 217-255 | |
| S.A. Cook, R.A. Reckhow, „Time-bounded random access machines“ J. Computer and System Sciences , 7 (1973) pp. 354-375 |