Turingmaschine als Berechnungsmodell

Eine Zwischenbilanz

Ausgangspunkt war das Ziel, den Algorithmusbegriff zu präzisieren, um nachweisbare Aussagen über die algorithmische Lösbarkeit von Problemen zu ermöglichen.

Ein erster Versuch zur Präzisierung des Algorithmusbegriffs wurde 1936 vom britischen Mathematiker Alan Turing unternommen - interessanterweise bevor es die ersten realen Computer gab. Turing entwickelte einen einfachen Modellrechner (der heute Turingmaschine genannt wird), mit dem er den Begriff der (algorithmischen) Berechenbarkeit erfasste.

Es zeigt sich, dass die gängigen algorithmischen Rechenverfahren (z.B. zur Addition, Subtraktion, Multiplikation, Division, ... natürlicher Zahlen) alle von der Turingmaschine ausgeführt werden können.

Mit geeigneten Codierungen gelingt es auch, komplexere Probleme mit einer Turingmaschine zu lösen.

Das Turingmaschinenmodell ist sogar in der Lage, Programmierbarkeit zu simulieren. Es weist demnach sehr viele Eigenschaften auf, die man von einem Computer als programmierbarer Verarbeitungseinheit erwartet.

Aber reicht das?

Ausblick

Wir wollen noch einen Schritt weiter gehen, indem wir folgende Frage aufwerfen: Ist das Berechnungsmodell Turingmaschine so mächtig, dass es alle denkbaren Algorithmen (in geeignet codierter Form) ausführen kann? Die Klärung dieser Frage wird uns im folgenden Abschnitt beschäftigen.