WikiDer > Turing-Vollständigkeit
In dem Berechenbarkeitstheorie wird ein Programmiersprache, oder ein anderes System zum Ausdrücken von Operationen, Turingkomplett (öfters: Turingkomplett) aufgerufen, wenn es die Aussagekraft von a . hat universelle Turingmaschine. Das heißt grob dass jede programmierbare Rechen- oder Datenoperation auch in diesem System programmiert werden kann.
Das Wort bezieht sich auf den Mathematiker Alan Turing, dass die Turing Maschine als allgemeines Maß für Berechenbarkeit erfunden.
Weitere Beschreibung
Turing-Vollständigkeit bezieht sich auf Systeme, in denen Bilder angegeben werden kann. Ein solches Bild kann als eine Operation betrachtet werden, die eine Eingabe einer bestimmten Form in eine Ausgabe einer bestimmten (möglicherweise unterschiedlichen) Form umwandelt, so dass die Ausgabe bei gegebener Eingabe fest ist.
Turingmaschinen selbst sind ein solches System: Jede Turingmaschine spezifiziert eine Operation auf endlichen Symbolfolgen.
Ein System ist Turing-vollständig, wenn die im System definierbaren Spezifikationen den Betrieb von Turing-Maschinen erlauben simulieren ist. Eine solche Simulation besteht aus drei Bildern:
- eine Abbildung endlicher Symbolketten auf mögliche Eingaben (der Spezifikationen in) des Systems;
- eine Abbildung endlicher Symbolketten auf mögliche Ausgaben (der Spezifikationen in) des Systems;
- ein Abbild von Turing-Maschinen nach Vorgaben im System, so dass für jede Turing-Maschine diese drei nacheinander angewendeten Bilder die gleiche Operation auf Symbolketten spezifizieren wie die Turing-Maschine selbst.
Echte Turing-Vollständigkeit erfordert, dass einem System während der Bearbeitung beliebig viel Arbeitsspeicher zur Verfügung steht. Informell werden Systeme, die nur einen festen Speicherplatz zur Verfügung stellen, auch als Turing-Complete bezeichnet, wenn diese Einschränkung in der Simulation keine Rolle spielt und als Implementierungsdetail betrachtet werden kann.
Beispiele
Das erste Beispiel einer solchen Turing-vollständigen Maschine wäre die Analysegerät von Charles Babbage aber es wurde nie wirklich gebaut. Die erste echte Maschine, die man außer ihrem endlichen Gedächtnis Turing-vollständig nennen konnte, war die Z3 von Konrad Zuse. Diese Maschine wurde bereits 1941 gebaut, aber erst 1998 wurde die Turing-Vollständigkeit nachgewiesen. Die erste Maschine, von der bekannt ist, dass sie vollständig Turing ist, war die ENIAC. Auch alle Heimcomputer sind fertig.
Dass es sich bei diesem Konzept um ein wichtiges Konzept für die Informatik handelt, zeigt sich daran, dass jeder bisher konstruierte (wirklich fertigungsfähige) Computer, Supercomputer und Quantencomputer enthalten, kann von einer Turing-Maschine emuliert werden. Dies gilt auch für einen Computer, der Turing-komplett ist. Im Prinzip kann ein Heimcomputer (abgesehen von Speicherbeschränkungen) alle Berechnungen durchführen, die ein Supercomputer ausführen kann. Natürlich dauert ein Heimcomputer viel länger, und ein gleichwertiges Programm für eine Turing-Maschine zu erstellen wird wahrscheinlich viel schwieriger sein, aber es ist nicht unmöglich.
Theoretisch gibt es Modelle von Computern, die leistungsfähiger sind als die Turing-Maschine, zum Beispiel a Oracle-Maschine, die jeder Entscheidungsproblem antworten kann (wie a Orakel tut, durch 'Glücksspiel'), also auch formal unentscheidbare Probleme wie die Halteproblem. Diese Maschinen oder gleichwertige Maschinen sind jedoch physikalisch nicht realisierbar. Das hat einige Hypothese legen nahe, dass das Universum selbst berechenbar ist, also auf einer Turing-Maschine simuliert werden könnte. Dies würde bedeuten, dass ein leistungsfähigerer Computer als die Turing-Maschine nicht möglich ist, da unter dieser Hypothese eine Turing-Maschine diesen Computer emulieren könnte.
Beispiele für Turing-(Un-)Vollständigkeit
Alle gängigen Programmiersprachen sind fertig. Diese sind zwingende Sprachen wie C, objektorientierte Sprachen wie Java, aber auch funktionale Sprachen wie LISPELN und Haskell und logische Programmiersprachen wie Prolog. Dies bedeutet, dass für jedes Programm in Prolog kann ein äquivalentes Programm darin geschrieben werden C geschrieben werden kann und umgekehrt. Äquivalent ist hier streng formal zu verstehen, die Berechnung des Ergebnisses kann ganz anders sein.
Selbst sehr einfache Sprachen, wie die untypisierte Lambda-Kalkül, die nur wenige Konstruktionen kennen, sind Turing komplett. Einige typisierte Lambda-Kalküle, wie z Lambda-Rechnung zweiter Ordnung, sind nicht vollständig.
Ein Beispiel für eine Sprache, die nicht Turing-vollständig ist, ist a Kalkulationstabelle ohne gegenseitige Abhängigkeiten (d. h. Schleifen) in den Zellen. Ebenfalls Reguläre Ausdrücke sind nicht Turing-vollständig, da sie modelliert werden können durch endliche Automaten, Geräte mit maximal begrenzter Speicherkapazität.
Merkmale der Turing-Vollständigkeit
Ein wichtiges Ergebnis der Berechenbarkeitstheorie ist, dass es im Allgemeinen unmöglich ist zu sagen, ob ein Programm, das in einer Turing-vollständigen Sprache geschrieben ist, einmal stoppt oder ob es unbegrenzt weiterrechnet, das sogenannte Stoppproblem. Methoden, die sicherstellen, dass ein Programm anhält, wie das Stoppen des Programms nach einer bestimmten Zeit oder die Einschränkung der Möglichkeit, Endlosschleifen zu erstellen, führen daher zu Turing-unvollständigen Sprachen.
Ein verwandtes Ergebnis ist, dass es Probleme gibt, die eine Turing-volle Sprache lösen kann, die aber nicht von einer Sprache mit . gelöst werden kann endlich Wiederholungsfähigkeiten – Sprachen, die so garantieren, dass Programme angehalten werden.