Turing-Vollständigkeit

aus Wikipedia, der freien Enzyklopädie

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 leitet sich vom Mathematiker Alan Turing her, der das Modell der universellen Turingmaschine eingeführt hat.

Obwohl solche Maschinen physikalisch unmöglich sein dürften, 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. Die erste tatsächliche Implementation erschien 1941: Die programmgesteuerte Z3 von Konrad Zuse. Die erste Maschine, von der die Turing-Vollständigkeit sicher bekannt ist, war die ENIAC. Die Universalität dieser Rechner war jedoch in der Zeit ihrer Entstehung noch unbekannt. 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.

Es existiert die Hypothese, dass das Universum Turing-vollständig ist (siehe Church-Turing-These).

Siehe Berechenbarkeitstheorie für eine längere Liste von Turing-vollständigen Systemen, sowie manchen Systemen, die weniger berechnen können, sowie manchen, die sogar leistungsfähiger als eine universelle Turingmaschine sind.

[Bearbeiten] Beispiele

Alle gängigen Programmiersprachen sind Turing-vollständig. Dies umfasst konventionelle imperative 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. Ein Beispiel wäre eine Folge von Formeln in einer Tabellenkalkulation ohne Schleifen. Obwohl es möglich ist, viele interessante Operationen mit so einem System zu erzeugen, ist es nicht Turing-vollständig, da keine Schleifen gebildet werden können. Die Makrosprache in Excel 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 unmöglich ist, über ein Programm, das in einer Turing-vollständigen Programmiersprache geschrieben wurde, auszusagen, 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 überraschendes 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.

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

[Bearbeiten] Literatur

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley.
• Turing completeness aus der englischen Wikipedia. Abgerufen 28. Juni 2005.