Turing-Vollständigkeit

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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. 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. 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, ist die programmgesteuerte Z3 von Konrad Zuse, die 1941 gebaut wurde.[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 von tatsächlich realisierten Computern.

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.

Beispiele[Bearbeiten]

Die gängigen Programmiersprachen sind Turing-vollständig. 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.

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 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.

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, komplexe Operationen mit einem solchen System durchzuführen. Dagegen ist z. B. die Makrosprache VBA für Microsoft Excel ihrerseits Turing-vollständig.

Reguläre Ausdrücke in Programmiersprachen, Editoren oder Systemwerkzeugen (z. B. grep, sed, …), 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.

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), 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[Bearbeiten]

  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[Bearbeiten]

  • 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[Bearbeiten]