[ < ] [ globaleÜbersicht ] [ Kapitelübersicht ] [Stichwortsuche ] [ > ]
Ist für eine Problemklasse ein Algorithmus bekannt, so braucht für die Lösung eines Problems dieser Klasse keine schöpferische Arbeit mehr geleistet werden. Jedes Problem der betreffenden Klasse kann durch rein schematisches Befolgen der algorithmischen Vorschrift gelöst werden.
In der Mathematik bemühte man sich jarhhunderte lang um die Aufstellung möglichst allgemeiner Algorithmen, und noch Leibnitz war der Ansicht, daß jedes mathematische Problem durch einen Algorithmus lösbar sei. Diese Ansicht wurde jedoch später immer mehr angezweifelt, als immer weitere Probleme auftraten, deren algorithmische Lösung nicht gelang.
Hat man ein allgemeines Lösungsverfahren gefunden, so kann manleicht nachprüfen, ob es die charakteristischen Eigenschaften des intuitiven Algorithmusbegriffs besitzt. Eine negative Aussage der Form "Es gibt nachweisbar keinen Algorithmus zur Lösung eines bestimmten Problems" bedarf dagegen grundsätzlich einer exakten, präzisen Definition des Begriffs Algorithmus.
Beispiel - Beweisbarkeit zahlentheoretischer Formeln
Die ersten Präzisierungen des Algorithmusbegriffs wurden um 1936 vorgeschlagen.
Sie entstanden vor allem durch Arbeiten von A. Church, K.Gödel, S.C. Kleene,
A.M. Turing und A.A. Markov. Man kennt heute eine Vielzahl verschiedener
Möglichkeiten, den Begriff Algorithmus zu präzisieren, z.b. durch den Mechanismus
der Turingmaschine (vgl. Appelrath, Ludewieg[32]) oder der Registermaschine,
durch 
-rekursive
Funktionen, durch Formelsysteme der Logik usw. Diese und auch alle übrigen
Präzisierungendes intuitiven Algorithmusbegriffs sind zueinander in dem
Sinne äquivalent,daß die zu ihnen gehörige Klasse von berechenbaren Funktionen(
siehe Abschnitt 4.3.2 ) immer dieselbe ist (die partiell-rekursiven
Funktionen).
Die Äquivalenz der verschiedenen Algorithmuspräzisierungen legt die Vermutung nahe, daß durch sie der intuitive Algorithmusbegriff gut erfaßt wird, dh., daß sie adäquate Abstraktionen fürdie intuitiven Vorstellungen sind. Diese Vermutung wurde zuerst um 1936 von A. Church ausgesprochen und wird heute als Churchsche These bezeichnet: "Jede im intuitiven Sinne berechenbare Funktion ist Turing-berechenbar. "Anschaulich bedeutet diese These, daß man zu jedem in irgendeinerForm aufgeschriebenen algorithmischen Verfahren eine Turingmaschine (einspezielles mathematisches Modell von Geräten, die Informationen verarbeiten) finden kann, die die gleiche Funktion berechnet.
Die Theorie der Berechenbarkeit ist jener Teil der Algorithmentheorie, der sich mit berechenbaren Funktionen auseinandersetzt. Die Frage nachder Existenz numerischer Algorithmen und Programme ist äquivalent zur Frage nach der Existenz berechenbarer Funktionen, da jedes Programm P als eine Funktion von der Menge der Eingabedaten E indie Menge der Ausgabedaten A
P : E -> A
angesehen werden kann. Eine Funktion f nennt man berechenbar,
wenn es einen Algorithmus gibt, der für jeden Eingabewert 
,
für den f definiert ist, nach endlich vielen Schritten anhält und
als Ergebnis a = f(e) liefert. In allen Fällen, in denen f(e)
nicht definiert ist, bricht der Algorithmus nicht ab.
Eine berechenbare Funktion f, die für jedes
definiert ist, nennt man auch rekursiveFunktion. Berechenbare Funktionen,
die nur auf einer echten Teilmenge von E definiert sind, heißen
partiell-rekursive Funktionen.
Als reine Existenzaussage kann folgende Feststellung getroffen werden: Es gibt nur abzählbar unendlich viele berechenbare Funktionen, aber es gibt überabzählbar viele nicht-berechenbare Funktionen, dh., die Berechenbarkeit einer Funktion kann als eine Ausnahme angesehen werden. Dies kann man sich durch Abzählung überlegen: Alle Algorithmen werden mit einer endlichen Beschreibung über einem endlichen Alphabet formuliert. Die Menge aller möglichen Formulierungen von Algorithmen ist daher abzählbar. Andererseits gibt es überabzählbar viele Funktionen f : E -> A, falls E eine unendliche und A eine mindestens zweielementige Menge ist (Cantorsches Diagonalverfahren).
Nicht-berechenbare Funktionen können durch kein Verfahren auf einemComputer nachvollzogen werden.
Beispiel & Beweis - Halteproblem
Für viele konkrete Algorithmen ist es möglich, zu entscheiden, ob sie terminieren werden. Die Nicht-Berechenbarkeit von fH besagt, daß es aber kein allgemeines Verfahren gibt, eine derartige Untersuchung für beliebige Algorithmen durchzuführen. Daraus folgt auch: Es gibt kein automatisches Verfahren, mit dem man für jedes Programm entscheiden kann, ob es eine Wiederholung enthält, deren Ausführung nie abbricht ("Endlosschleife"), oder nicht.
Eine Konsequenz dieser Tatsache ist die prinzipielle Unmöglichkeit,dieKorrektheit eines Programms automatisch überprüfen zu können.Jeder Beweis, daß ein Programm auf Eingabewerte immer mit den erwartetenAusgabewerten reagiert, muß daher zwangsläufig (jedenfalls teilweise)manuell erfolgen.
Beispiel - Ungelöste Terminierungsfrage