In der Informatik und Logik , ein formales System wird gesagt, dass im Sinne der Turing vollständige oder Turing-vollständig (nach der englischen Tracing Turing-vollständig ) , wenn sie eine hat Ausdruckskraft zumindest äquivalent zu derjenigen von Turing Maschinen . In einem solchen System ist es daher möglich, jede beliebige Turingmaschine zu programmieren .
Dieser Begriff wird durch die These von Church relevant , die die Existenz eines natürlichen Begriffs der Berechenbarkeit postuliert. Damit deckt sich die Ausdruckskraft von Turing-Maschinen mit der von rekursiven Funktionen , Lambda-Kalkülen oder gar Zählmaschinen .
Obwohl einige Berechnungsmodelle, Hypercomputer genannt , strikt ausdrucksstärker sind als Turing-Maschinen, sind diese Modelle Spekulationsobjekte (z ob sie physikalisch machbar sind. Unter diesen Bedingungen vermutet Churchs These die Universalität des Turing-Maschinen-Rechenmodells: Jedes Turing-vollständige System wäre tatsächlich Turing-Maschinen äquivalent.
Wie ein Rechenmodell wird eine Computersprache als Turing-vollständig bezeichnet, wenn alle berechenbaren Funktionen im Sinne von Turing und Church dargestellt werden können (ungeachtet der Endlichkeit des Computerspeichers).
Einige Autoren verwenden diese Eigenschaft für die Definition einer Programmiersprache , aber es können auch andere Definitionen gewählt werden.
Die gängigen Programmiersprachen ( C , Java …) sind Turing-vollständig, weil sie alle notwendigen Zutaten für die Simulation einer universellen Turing-Maschine haben (zählen, vergleichen, lesen, schreiben, etc.). Die Sprache C++ ist ebenfalls Turing-vollständig, und die Untermenge, die eine generische Programmierung ( Templates ) ermöglicht, ist ebenfalls .
Die ursprünglich im Sinne von Turing unvollständige SQL- Sprache wurde es mit dem SQL:1999-Standard, der es ihr erlaubt, rekursive Abfragen zu schreiben .
Die Sprache LaTeX (von TeX ), die für die Dokumenterstellung gedacht ist, ist ebenfalls Turing-komplett.
Die Sprache HTML allein ist nicht Turing-vollständig, obwohl nachgewiesen wurde, dass die Sprache CSS (Version 3) es erlaubt, den elementaren zellulären Automatencode 110 (siehe Regel 110 (in) ) aufzubauen, der im Sinne von Turing als universell bekannt ist . Diese beiden Sprachen sind oft untrennbar, wir können daraus schließen, dass HTML + CSS Turing-vollständig ist und diese Assoziation es daher theoretisch zu einer Programmiersprache macht.
Eine Turing-vollständige Sprache erbt die Eigenschaften einer Turing-Maschine. Zum Beispiel das Herunterfahren Problem ist unentscheidbar , so dass es unmöglich ist , ein Programm zu schreiben , das sagt , ob ein beliebiges Programm , um es gegeben endet oder nicht.
Einige Sprachen, die sich mit bestimmten Problemen befassen, sind nicht Turing-vollständig. System F , ein Lambda-Kalkül-Formalismus, ist ein Beispiel. Darüber hinaus sind – per Design – totale Sprachen (en) , bei denen alle Berechnungen notwendigerweise enden (wie die Gallina- Sprache des Coq- Beweisassistenten ), auch nicht Turing-vollständig. Letztere sind jedoch in der Lage, alles zu berechnen, was von Interesse ist, dh sie können alle Funktionen ausführen, die wir im praktischen Leben benötigen; die Berechnungen, die ihnen entgehen, haben entweder eine Komplexität jenseits des Vorstellbaren und Realisierbaren oder enden nicht. Die Kompilierung muss dann die Beendigung der Programme demonstrieren oder für einige Demonstrationen die Interaktion mit dem Programmierer erfordern, aber dies ist der Preis für die konstruktionsbedingt korrekte Codequalität.
Einige Spiele und Software sind zufällig Turing-komplett, ohne dass ihre Autoren dies wollten oder in Betracht ziehen:
„ Dass alle Standard-Programmiersprachen genau die Klasse der partiellen rekursiven Funktionen ausdrücken, wird oft mit der Aussage zusammengefasst, dass alle Programmiersprachen Turing-vollständig sind. "
„ Eine Programmiersprache ist eine Sprache, die für den Ausdruck von Computerprogrammen bestimmt ist und die in der Lage ist, jedes Computerprogramm auszudrücken. Dies ist keine vage Vorstellung. Es gibt einen präzisen theoretischen Weg, um zu bestimmen, ob eine Computersprache verwendet werden kann, um ein Programm auszudrücken, nämlich indem man zeigt, dass sie einer universellen Turing-Maschine entspricht. "