Turing-Vollständigkeit

Exakt ausgedrückt bezeichnet Turing-Vollständigkeit in der Berechenbarkeitstheorie die Eigenschaft einer Programmiersprache oder eines anderen logischen Systems, sämtliche (Turing)-berechenbaren Funktionen auch berechnen zu können. Eine universelle Turingmaschine kann alle berechenbaren Funktionen berechnen.

Anders ausgedrückt: ein Turing-vollständiges System und eine universelle Turingmaschine können sich gegenseitig emulieren.

Noch vor der Prägung des Begriffs wurde der erste turingmächtige mathematische Formalismus von Kurt Gödel im Jahre 1931 in seiner Arbeit zum Unvollständigkeitssatz veröffentlicht.

Obwohl solche Maschinen physikalisch unmöglich sind, da sie unbegrenzten Speicherplatz besitzen müssten, werden gängige Programmiersprachen und Computer, die universell wären, wenn sie unbegrenzten Speicher besäßen, als Turing-vollständig bezeichnet. Die in den 30er Jahren des 19. Jahrhunderts von Charles Babbage entworfene Analytical Engine hätte in diesem Sinne Turing-Vollständigkeit besessen, wäre sie jemals gebaut worden.[3]

Die Zuse Z3 wurde 1941 gebaut, sie war nicht turingmächtig konstruiert und wurde auch nicht dafür genutzt.[4] Wie Raúl Rojas im Jahr 1998 herausfand, ist sie über zwei Tricks (begrenzte Rechengenauigkeit und Zusammenkleben des Lochstreifens zu einer Schleife) dennoch Turing-vollständig, wird dabei aber sehr langsam.[5]

Im Jahre 1954 veröffentlichte Hans Hermes als einer der Ersten einen Beweis für die Turing-Vollständigkeit von Von-Neumann-Rechenmaschinen, also von tatsächlich realisierten Computern. Alle modernen Computer sind ebenfalls im weiteren Sinne Turing-vollständig.

Eine Maschine, die Turing-vollständig ist, kann jede Berechnung, die irgendein Computer ausführen kann, ebenso ausführen und wird daher auch als universell programmierbar bezeichnet. Hierdurch ergibt sich jedoch weder eine Aussage über den Aufwand, ein bestimmtes Programm auf einer solchen Maschine zu implementieren, noch über die Zeit, die zur Ausführung benötigt werden würde.

Die Berechenbarkeitstheorie befasst sich damit, welche Probleme mit Hilfe einer Maschine, insbesondere mit einer Turingmaschine, lösbar sind.

Die gängigen Programmiersprachen sind Turing-vollständig. Einige Autoren definieren den Begriff „Programmiersprache“ sogar auf Basis der Turing-Vollständigkeit.[6] Dies schließt konventionelle prozedurale Sprachen wie C und objektorientierte Sprachen wie C++ und Java ein. Auch Sprachen, die nach weniger geläufigen Paradigmen entworfen wurden, unter anderem funktionale Programmiersprachen wie LISP und Haskell und Sprachen für Logikprogrammierung wie Prolog, sind Turing-vollständig. Ebenfalls Turing-vollständig sind die in der Berechenbarkeitstheorie verwendeten, minimalistischen Programmiersprachen GOTO und WHILE.

Beispiele für nicht Turing-vollständige Programmiersprachen zu finden, fällt Fachleuten schwer, da diese die Sprachen nach Funktionalität filtern und strukturelle Sprachen und rein prozessorientierte von vornherein als sehr eingeschränkt erachten und sie gar nicht erst in die Betrachtung aufnehmen. Ein häufig diskutiertes Beispiel sind SGML-Dialekte und -Derivate wie beispielsweise HTML, die Auszeichnungssprache zur Darstellung von Webseiten. Diese Struktur-Sprache ist bei Einsatz aller gegebenen Attribute durchaus in der Lage, universelle Beschreibungen für Prozesse zu halten. Auch die zeit-diskrete Steuerung bzw. die zeitliche Abfolge lässt sich mit Hilfe der Relationalen beschreiben. Alle Instrumentale, die nötig wären, sind im Sprachschatz vorhanden. Einziges Hindernis zur Aufnahme in die Reihe der Turing-vollständigen Sprachen stellt die Tatsache dar, dass HTML in sich nicht aktiv sein kann. Erst in Ergänzung um eine aktive Komponente, wie z. B. JavaScript, oder durch den ausführenden Webbrowser ergibt sich die Steuerbarkeit und verfolgbare zeitliche und hierarchische Abhängigkeit.

Eine Folge von Formeln in einer Tabellenkalkulation ohne Schleife ist nicht Turing-vollständig, obwohl es möglich ist, komplexe Operationen mit einem solchen System durchzuführen. Dagegen ist z. B. die Programmiersprache VBA für Microsoft Excel ihrerseits Turing-vollständig.

Reguläre Ausdrücke in Programmiersprachen, Editoren oder Systemwerkzeugen (z. B. grep), wo sie vor allem zum Pattern Matching verwendet werden, sind nicht Turing-vollständig, auch wenn in vielen Implementierungen reguläre Ausdrücke um Konstrukte wie Rückwärtsreferenzen (engl. backreferences) erweitert werden, die nicht mehr von endlichen Automaten erzeugt werden können.

Die relationale Algebra ist nicht Turing-vollständig, da es innerhalb dieser nicht möglich ist, die transitive Hülle zu bilden. Außerdem verfügt die Relationale Algebra nicht über Schleifen.

Turing-vollständig sind μ-rekursive Funktionen (daher kommt auch die Bezeichnung rekursiv für entscheidbare Mengen).

Der untypisierte Lambda-Kalkül ist Turing-vollständig, aber viele typbehaftete Kalküle, unter anderem System F, sind es nicht. Der Vorteil von typbehafteten Systemen ist ihre Möglichkeit, die meisten typischen Computerprogramme darzustellen, dabei aber mehr Fehler entdecken zu können.

Eine wichtige Schlussfolgerung aus der Berechenbarkeitstheorie ist, dass es keinen Algorithmus geben kann, der über jedes in einer bestimmten Turing-vollständigen Programmiersprache geschriebene Programm aussagen kann, ob es in endlicher Zeit abbricht oder für immer in einer Schleife bleibt (siehe Halteproblem). Eine Methode, dieses Problem zu umgehen, ist das Abbrechen eines Programmablaufs nach einer fixen Zeitspanne oder das Herabsetzen der Mächtigkeit von Kontroll-Anweisungen. Solche Systeme gelten jedoch strikt als nicht Turing-vollständig. Dieses Resultat wurde z. B. von Landweber abgeleitet.

Ein weiteres Theorem stammt aus der Berechenbarkeitstheorie. Mit einer Maschine, die nur endliche Schleifen bietet (zum Beispiel LOOP oder die dazu äquivalenten primitiv-rekursiven Funktionen), ist garantiert, dass jedes Programm irgendwann anhält. Mit dieser Maschine können jedoch nicht alle Probleme gelöst werden, die von einer Turing-Maschine gelöst werden können, z. B. die Ackermann-Funktion.

• Walter S. Brainerd, Lawrence H. Landweber: Theory of Computation. Wiley, New York NY u. a. 1974, ISBN 0-471-09585-0.

1. Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society. Band s2-42, Nr. 1, 1937, S. 230–265, doi:10.1112/plms/s2-42.1.230 (PDF).
2. Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction. In: Proceedings of the London Mathematical Society. Band s2-43, Nr. 1, 1938, S. 544–546, doi:10.1112/plms/s2-42.1.230 (PDF).
3. J. Fuegi, J. Francis: Lovelace & Babbage and the creation of the 1843 “notes”. In: Annals of the History of Computing. Band 25, Nr. 4. IEEE, Oktober 2003, ISSN 1058-6180, S. 16–26, doi:10.1109/MAHC.2003.1253887.
4. Raúl Rojas: Konrad Zuse’s Legacy: The Architecture of the Z1 and Z3. In: IEEE Annals of the History of Computing. Band 19, Nr. 2, 1997, ISSN 1058-6180, S. 5–16 (PDF).
5. Raúl Rojas: How to make Zuse’s Z3 a universal computer. In: Annals of the History of Computing. Band 20, Nr. 3. IEEE, 1998, ISSN 1058-6180, S. 51–54, doi:10.1109/85.707574 (PDF Scan, PDF, HTML).
6. So etwa Bruce MacLennan: Principles of Programming Languages. Oxford University Press, New York 1999, ISBN 0-19-511306-3, S. 1.