Präzisierung des Algorithmusbegriffs

Aus Informatik
Wechseln zu: Navigation, Suche

In früheren Kursen wurde ein intuitiver Algorithmusbegriff erarbeitet:

Ein Algorithmus ist eine Folge von Handlungsanweisungen zur Lösung eines Problems, die folgende Anforderungen erfüllt:
  • Allgemeingültigkeit, d. h. die Anweisungen besitzen Gültigkeit für die Lösung einer ganzen Problemklasse, nicht nur für ein Einzelproblem,
  • Ausführbarkeit, d. h. die Anweisungen sind für den Befehlsempfänger (Mensch oder Maschine) verständlich formuliert und für diesen ausführbar,
  • Eindeutigkeit, d. h. an jeder Stelle ist der Ablauf der Anweisungen eindeutig festgelegt,
  • Endlichkeit, d. h. die Anweisungsfolge ist durch einen endlichen Text beschrieben.

Erwünscht ist außerdem die

  • Terminiertheit, d. h. nach endlich vielen Schritten liefert die Anweisungsfolge eine Lösung des gestellten Problems.
  • Determiniertheit, d. h. bei jeder Ausführung mit gleichen Startbedingungen und Eingaben erhält man das gleiche Ergebnisse.

Wir formulieren nun im Anschluss an die vorigen Überlegungen den präzisen Algorithmusbegriff:

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:

Turingthese

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.

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.

Dies spricht alles dafür, dass im Begriff der Turingmaschine die anschauliche Vorstellung von einem Algorithmus adäquat präzisiert worden ist. 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 Turingthese: Wenn wir die Turingthese akzeptieren, können wir prinzipielle Grenzen des Computers anhand der Grenzen der Turingmaschine nachweisen.