Im Abschnitt Grundlagen der Programmierung wurde der Begriff Algorithmus intuitiv definiert. Für eine präzise Definition genügt diese jedoch nicht.
Mit Hilfe der Turingmaschine kann ein präziserer Begriff formuliert werden:
Definition: Algorithmus
Unter einem Algorithmus versteht man ein Verfahren, das von einer Turingmaschine ausführbar ist.
… oder …
Ein Algorithmus ist eine Turingmaschine.
Wir fragen nun, in welchen Zusammenhang dieser Algorithmusbegriff mit dem bisher geläufigen steht. Eine Aussage dazu macht die folgende von Alan T. Turing formulierte These, die als Turingthese bezeichnet wird:
Definition: Turing-These
Der intuitive Begriff des Algorithmus (allgemeines, ausführbares, eindeutiges, endliches Verfahren) und der präzise Begriff des Algorithmus (Turingmaschine) stimmen überein.
… bzw. …
Jedes Problem, das überhaupt maschinell lösbar ist, kann von einer Turingmaschine gelöst werden.
Diese These ist wegen unklarer Begriffe wie ausführbar oder Verfahren nicht beweisbar. Sie wird aber allgemein akzeptiert, denn es gibt gute Argumente, die für ihre Gültigkeit sprechen. Einige davon sind:
- Jedes von einer Turingmaschine ausführbare Verfahren ist natürlich ein Algorithmus im intuitiven Sinn.
- Umgekehrt wurde noch nie ein Algorithmus im intuitiven Sinn gefunden, der nicht auch im Prinzip für eine Turingmaschine formulierbar wäre.
- Komplexer aufgebaute Maschinenmodelle, z. B. solche mit mehreren Bändern oder mehreren Lese-/Schreibköpfen, sind nachweisbar nicht leistungsfähiger als die Turingmaschine.
- Es wurden verschiedene andere Präzisierungen des Algorithmusbegriffs von anderen Mathematikern gefunden, die alle als äquivalent nachgewiesen wurden. Eine dieser Präzisierungen ist der auf Alonzo Church zurückgehende \lambda-Kalkül.
- Aus den verschiedenen Präzisierungen haben sich verschiedene Typen von Programmiersprachen entwickelt, aus dem Maschinenmodell von Turing die imperativen Sprachen wie FORTRAN, ALGOL und Pascal, und aus dem \lambda-Kalkül von Church die funktionalen Sprachen wie LISP. Es gibt Compiler von jeder Sprache in jede andere.
Erstaunlicherweise stellte sich heraus, dass die unabhängig voneinander erdachten und unterschiedlichen Definitionen gleichwertig sind. Das heißt: Wenn etwas durch einen Algorithmus berechnet werden kann, der sich im sog. \lambda-Kalkül darstellen lässt, so auch durch eine Turingmaschine – und umgekehrt.
Neben dem \lambda-Kalkül gibt es weitere Rechenmodelle, die sich gegenseitig simulieren können: z. B. Registermaschine, GOTO-Programm oder WHILE-Programme.
Definition: Turing-vollständig
Alle Rechenmodelle (und die daraus folgenden Algorithmenbegriffe), die gleichmächtig zur Turingmaschine sind, bezeichnet man als Turing-vollständig. Alle diese Rechenmodelle lassen sich daher gegenseitig simulieren.
Das folgt unmittelbar die Church-Turing-These:
Alle bisher entwickelten Präzisierungen des intuitiven Algorithmusbegriffs sind äquivalent, und jede vernünftige Definition der Berechenbarkeit, die irgendwann einmal aufgestellt wird, ist mit den derzeit bekannten Definitionen äquivalent.
… oder …
Jede (im intuitiven Sinn) berechenbare Funktion ist auch Turing-berechenbar.
Diese These ist nicht beweisbar, da der intuitive Berechenbarkeitsbegriff eben nicht formal mathematisch erfasst werden kann. Allerdings könnte man sie sofort widerlegen, indem man einen Berechenbarkeitsbegriff angibt, der eben nicht durch Turingmaschinen simuliert werden kann – das aber wurde in den vergangenen Jahrzehnten (die historisch ersten Definitionen von Turing und Church gehen auf 1936 zurück) immer wieder versucht, allerdings bis heute vergeblich, so dass man heute allgemein von der Richtigkeit der These ausgeht.
Welch intellektuelle Leistung dies darstellt, können wir uns vielleicht besser klar machen, wenn wir uns an einen der zentralen Begriffe aus der Mathematik erinnern. Der intuitive Begriff der stetigen Funktion nach Leonhard Euler („aus freier Hand zu zeichnen“) und der präzise Begriff nach Augustin L. Cauchy (\epsilon–\delta-Definition) stimmen nicht überein. Dies stört den Mathematiker jedoch nicht. Er verwendet bei Stetigkeits- und Unstetigkeitsbeweisen nur den präzisen Begriff. Der Informatiker hingegen kommt in der Praxis meist mit dem intuitiven Algorithmusbegriff aus. Wenn er zeigen will, dass ein Problem algorithmisch lösbar ist, so tut er dies durch konkrete Angabe eines Algorithmus. Dafür reicht der intuitive Begriff. Wenn er jedoch zeigen will, dass es keinen Algorithmus zur Lösung eines bestimmten Problems gibt, dann muss er eine Aussage über alle möglichen Algorithmen machen. Um sie zu begründen, muss er die Annahme der Existenz eines solchen Algorithmus zum Widerspruch führen. Hierfür ist der präzise Begriff erforderlich.
Wir werden sehen, dass es tatsächlich exakt formulierbare Problemstellungen gibt, die nicht von einer Turingmaschine gelöst werden können und damit prinzipiell algorithmisch nicht lösbar sind.
Und darin liegt die Bedeutung der Church-Turing-These: Wenn wir die These akzeptieren, können wir prinzipielle Grenzen des Computers anhand der Grenzen der Turingmaschine nachweisen.
