Turing Vollständigkeit

Turing Vollstä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.

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • Turing — ist der Familienname von: Alan Turing, britischer Logiker, Mathematiker und Kryptoanalytiker Turing steht auch für: Turingmaschine, ein grundlegendes mathematisches Modell der Informatik um eine Klasse von berechenbaren Funktionen zu bilden… …   Deutsch Wikipedia

  • Turing-mächtig — 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… …   Deutsch Wikipedia

  • Turing-Maschine — Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie gehört zu den grundlegenden Konzepten der Informatik. Das Modell wurde im Rahmen des von… …   Deutsch Wikipedia

  • Turing Award — Der nach Alan Turing benannte A. M. Turing Award wird jährlich von der Association for Computing Machinery (ACM) an Personen verliehen, die sich besonders um die Entwicklung der Informatik verdient gemacht haben. Er gilt als höchste Auszeichnung… …   Deutsch Wikipedia

  • Turing-Award — Der nach Alan Turing benannte und mit 250.000 US Dollar dotierte Turing Award (offizielle Bezeichnung: A. M. Turing Award) wird jährlich von der Association for Computing Machinery (ACM) an Personen verliehen, die sich besonders um die… …   Deutsch Wikipedia

  • Turing-Preis — Der nach Alan Turing benannte und mit 250.000 US Dollar dotierte Turing Award (offizielle Bezeichnung: A. M. Turing Award) wird jährlich von der Association for Computing Machinery (ACM) an Personen verliehen, die sich besonders um die… …   Deutsch Wikipedia

  • Turingmächtig — 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… …   Deutsch Wikipedia

  • Turingmächtigkeit — 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… …   Deutsch Wikipedia

  • Turingvollständig — 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… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”