Das Wort A. ist eine Verbalhornung des Namens des arabischen Mathematiker Al Chwarizmi. - Spezielle Algorithmen wurden schon seit der Antike intuitiv verwendet, so der Euklidische Algorithmus zum Auffinden des größten gemeinsamen Teilers zweier natürlicher Zahlen. Strenge Formalisierungen von A. wurden aber erst seit etwa 1932 gefunden: Alan Turings TuringMaschinen, das Gleichungskalkül (Herbrand), Partiell-rekursiven Funktionen (Herbrand / Gödel, Kleene), Lambda-Kalkül (Church, Kleene), Normal-Systeme (Post), Normalalgorithmen (Markow), Logische Schemata von A. (Ljapunow), Graphenschemata (Péter, Kaloujnine). Es zeigte sich, dass all diese Konstrukte dasselbe meinen, wenn auch in unterschiedlichen mathematischen Ausdrucksweisen – ein starkes Indiz (wenn auch kein Beweis) für die Annahme, dass jedes intuitive menschliche Verfahren durch A. beschrieben werden kann (ChurchTuringThese, Künstliche Intelligenz).
Generell bildet ein A. ein System von Regeln, das in eindeutiger, determinierter Weise von Inputwerten zu Outputwerten führt. Ungefähr Synonyme für A. sind effektives Verfahren, Strategie, Methode, Regelsystem, Gebrauchsanweisung, Programm, Rezept - denke beispielsweise an die Anweisungen eines Kochbuchs.
Für einen A. gelten mindestens die folgenden Kriterien:
1) Die Inputwerte des A., die Zutaten, bestehen aus einer Menge diskreter, von einander abgegrenzter Dinge (aus drei Eiern und einer soweit als nötig quantifizierten Menge Mehl beispielweise).
2) Die Anzahl der Befehle, die ein A. enthält, ist endlich und die einzelnen Befehle sind klar voneinander unterscheidbar (”fügen Sie erst das Mehl zum Teig, rühren Sie dann die Eier unter”).
3) Die Ausführung des jeweiligen Befehls kommt stets zu einem determinierten Ergebnis, einem Kuchen etwa; bei gleichen Inputwerten kommt derselbe A. zu den gleichen Outputwerten, beispielsweise zu einem weiteren Kuchen. Dass ein Verfahren „effektiv“ genannt wird, meint ja im besonderen, dass es nicht mal zu einem Ergebnis und mal zu einem anderen oder keinen Ergebnis führen darf.
4) Enthält der A. Befehle zur Bildung weiterer Befehle während seines Verlaufs, die sich auf den Verlauf auswirken, werden diese weiteren Befehle bei gleicher Ausgangskonstellation in völlig gleicher, determinierter Weise gebildet und auch wiederum in gleicher, determinierter Weise zu denselben Outputwerten führen: Untermenüs, etwa das (rechtzeitige) Ein- und Ausschalten des Backofens, ändern nichts am Verlauf eines Programms.
5) Das Ergebnis des A., des effektiven Verfahrens, des Backrezepts muss eindeutig erkennbar sein. Es muss klar sein, wann ein Ergebnis vorliegt und was als Ergebnis vorliegt; beispielsweise ein Kuchen.
Manche Probleme sind wohldefiniert und die Natur ihrer Input- und Outputwerte ist begrifflich klar umrissen, und dennoch ist es nicht möglich einen A. zu finden, der die gewünschte Zuordnung von Input- und Outputwerten leistet. So gibt es zum Beispiel kein Verfahren zur Dreiteilung eines beliebigen Winkels mit Zirkel und Lineal. Auch dem Beweis der Nichtexistenz eines A. kann hoher Wert zukommen.