Turingvollständigkeit

Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Bitte entferne erst danach diese Warnmarkierung.

Turing-Vollständigkeit bezeichnet 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. Der Name ist abgeleitet von dem englischen Mathematiker Alan Turing, der das Modell der universellen Turingmaschine eingeführt hat^[1].

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^[2]. Die erste Maschine, von der die Turing-Vollständigkeit sicher bekannt ist, erschien 1941: die programmgesteuerte Z3 von Konrad Zuse^[3]. Die Universalität dieses Rechners war jedoch in der Zeit seiner Entstehung noch unbekannt und wurde erst später bewiesen^[4]. 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.

Turing-Vollständigkeit ist insofern wichtig, als jedes plausible Design einer Rechenmaschine (sogar Quantencomputer) von einer Turing-Maschine emuliert werden kann. Daher kann eine Maschine, die Turing-vollständig ist, jede Berechnung, die irgendein Computer ausführen kann, ebenfalls ausführen (in anderen Worten, sie ist universal programmierbar). Dadurch wird allerdings nichts über den Aufwand ausgesagt, ein bestimmtes Programm zu schreiben, noch über die Zeit, die ein Programm zur Ausführung benötigt.

Siehe Berechenbarkeitstheorie für eine längere Liste von Turing-vollständigen Systemen, sowie manchen Systemen, die weniger berechnen können.

Beispiele

Alle gängigen Programmiersprachen sind Turing-vollständig. Dies umfasst konventionelle prozedurale Sprachen wie C und objekt-orientierte Sprachen wie C++ und Java. Auch Sprachen, die nach weniger gängigen Paradigmen entworfen wurden, unter anderem funktionale Programmiersprachen wie LISP und Haskell und Sprachen für Logikprogrammierung wie Prolog sind Turing-vollständig.

Es ist schwierig, Beispiele für nicht Turing-vollständige Sprachen zu finden, da diese Sprachen sehr eingeschränkt wären. Einige Autoren basieren ihre Definition des Begriffs „Programmiersprache“ auf Turing-Vollständigkeit.^[5] Eine Folge von Formeln in einer Tabellenkalkulation ohne Schleife ist nicht Turing-vollständig, obwohl es möglich ist, viele interessante Operationen mit so einem System zu erzeugen. Die Makrosprache in Excel (VBA) ist jedoch Turing-vollständig. Ein anderes bekanntes Beispiel sind reguläre Ausdrücke, die von endlichen Automaten erzeugt werden. Eine mächtigere, aber immer noch nicht Turing-vollständige Erweiterung von endlichen Automaten sind formale Sprachen. 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 auch nicht über Schleifen. Da die Relationale Algebra und SQL gleich mächtig sind, ist auch SQL nicht Turing-vollständig.

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

Ein weiteres Theorem stammt aus der Berechenbarkeitstheorie: Mit einer Maschine, die nur endliche Schleifen bietet (z. B. Sprachen, die garantieren, dass jedes Programm irgendwann anhält), können nicht alle Probleme gelöst werden, die von einer Turing-Maschine gelöst werden können.

Der untypisierte Lambda-Kalkül ist Turing-vollständig, aber viele typbehaftete Kalküle, u. a. 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.

Literatur

1. ↑ Turing "On Computable Numbers, with an Application to the Entscheidungsproblem" Proc. London Math. Soc..1937; s2-42: 230-265 Nachdruck
2. ↑ Fuegi, J.; Francis, J.;"Lovelace & Babbage and the creation of the 1843 'notes'"Annals of the Seiten16 - 26 doi:10.1109/MAHC.2003.1253887
3. ↑ Rojas, R.; "Konrad Zuse's legacy: the architecture of the Z1 and Z3" Annals of the History of Computing, IEEE Bd.19, Nr.2, April-Juni 1997 Seiten 5 - 16 doi:10.1109/85.586067
4. ↑ Rojas, R.; "How to make Zuse's Z3 a universal computer" Annals of the History of Computing, IEEE Bd.20, Nr.3, Juli-Sept. 1998 Seiten 51 - 54 doi:10.1109/85.707574
5. ↑ So etwa Bruce MacLennan: Principles of Programming Languages, S. 1. Oxford University Press, New York 1999, ISBN 0-19-511306-3

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley.