Turing-Vollständigkeit

Mit Turing-Vollständigkeit eines Systems wird seine universelle Programmierbarkeit beschrieben. Für die Adjektivform turing-vollständig wird synonym häufig auch turingmächtig verwendet. Der Name ist abgeleitet vom englischen Mathematiker Alan Turing, der das Modell der universellen Turingmaschine eingeführt hat.^[1][2]

Definition und Anwendung des Begriffs

Exakt ausgedrückt bezeichnet Turing-Vollständigkeit in der Berechenbarkeitstheorie die Eigenschaft einer Programmiersprache oder eines anderen logischen Systems, sämtliche Funktionen berechnen zu können, die eine universelle Turingmaschine berechnen kann. Anders ausgedrückt, das System und eine universelle Turingmaschine können sich gegenseitig emulieren.

Obwohl solche Maschinen physikalisch unmöglich sind, da sie unbegrenzten Speicherplatz besitzen müssten, wird der Begriff Turing-vollständig bei gängigen Programmiersprachen und Computern angewandt, die universell wären, wenn sie unbegrenzten Speicher besäßen. Charles Babbages Analytical Engine wäre in diesem Sinne Turing-vollständig gewesen, wenn sie jemals gebaut worden wäre.^[3] Die erste Maschine, von der die Turing-Vollständigkeit sicher bekannt ist, die programmgesteuerte Z3 von Konrad Zuse, wurde 1941 gebaut.^[4] Die Universalität dieses Rechners war jedoch in der Zeit seiner Entstehung noch unbekannt und wurde erst später bewiesen.^[5] Alle modernen Computer sind ebenfalls im weiteren Sinne Turing-vollständig. Im Jahre 1954 veröffentlichte Hans Hermes als einer der ersten einen Beweis für die Turing-Vollständigkeit von von-Neumann-Rechenmaschinen, also tatsächlich realisierter Computer.

Eine Maschine, welche 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.

Beispiele

Die gängigen Programmiersprachen sind Turing-vollständig. Dies schließt konventionelle prozedurale Sprachen wie C und objekt-orientierte 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.

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 prozess-orientierte von vorn herein 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 das – Internet-Nutzern zumindest dem Namen und der Nutzung nach bekannte – HTML (HyperText Markup Language): 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 in diesem Artikel diskutierten Sprachen stellt die Tatsache dar, dass HTML in sich nicht aktiv sein kann; erst in Ergänzung um eine aktive Komponente (z. B. JavaScript) oder durch den ausführenden Browser, in welchem das Konstrukt verarbeitet wird, ergibt sich die Steuerbarkeit und verfolgbare zeitliche und hierarchische Abhängigkeit. Da HTML jedoch vor allem für spezielle Segmente wie Muster-Bibliotheken, Platzhalter für dynamisch erzeugte Inhalte, als passive Listung für im Browser vorgezeichnete Routinen, für Formulare und zur Kapselung von Prozessen eingesetzter Scripte genutzt wird, ist HTML eher wie die zuvor an zweiter Stelle erwähnten prozess-orientierten Sprachen, nämlich die Stapel-Verarbeitungen und Stacking-Coda, zu betrachten.

Einige Autoren definieren den Begriff „Programmiersprache“ auf Basis der Turing-Vollständigkeit.^[6] Eine Folge von Formeln in einer Tabellenkalkulation ohne Schleife ist nicht Turing-vollständig, obwohl es möglich ist, viele interessante Operationen mit einem solchen System zu erzeugen. Die Makrosprache in Excel (VBA) ist jedoch Turing-vollständig. Ein weiteres bekanntes Beispiel sind reguläre Ausdrücke in Programmiersprachen, Editoren oder Systemwerkzeugen (z. B. grep, sed, …), wo sie vor allem zum Pattern Matching verwendet werden. In vielen Implementierungen werden reguläre Ausdrücke um Konstrukte wie Rückwärtsreferenzen (engl. backreferences) erweitert, wodurch sie nicht mehr von endlichen Automaten erzeugt werden können. Sie sind jedoch weiterhin Turing-unvollständig. Ein weiteres Beispiel für eine nicht-Turing-vollständige Sprache ist die Relationale Algebra, da es nicht möglich ist, die transitive Hülle zu berechnen. Außerdem verfügt die Relationale Algebra eben nicht über Schleifen.

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 sind jedoch strikt nicht-Turing-vollständig. Dieses Resultat wurde z. B. von Brainerd und Landweber von PL und PL-{GOTO}-Sprachen abgeleitet.

Ein weiteres Theorem stammt aus der Berechenbarkeitstheorie: Mit einer Maschine, die nur endliche Schleifen bietet (zum Beispiel LOOP) 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.

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.

Einzelnachweise

1. ↑ Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society. Bd. s2-42, Nr. 1, 1937, S. 230–265 (PDF).
2. ↑ Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction. In: Proceedings of the London Mathematical Society. Bd. s2-43, Nr. 1, 1938, S. 544–546 (PDF).
3. ↑ J. Fuegi, J. Francis: Lovelace & Babbage and the creation of the 1843 “notes”. In: Annals of the History of Computing. Bd. 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. Bd. 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. Bd. 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.

Literatur

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

Weblinks

• Turingseite der Fachhochschule Gießen-Friedberg