Diskussion:Turing-Vollständigkeit

fachlich und sprachlich weniger guter Artikel.

Tatbestandsmerkmale?

Mir ist nach der Lektüre des Artikels noch immer nicht wirklich klar, wie ich ganz konkret die Turing-Vollständigkeit insbesondere einer Programmiersprache nachweisen oder widerlegen kann. Also was sind ganz konkret die Voraussetzungen, die ich durchprüfen muss, wenn ich wissen will, ob eine Programmiersprache turing-vollständig ist? Es werden bloß nicht näher begründete Beispiele von turing- bzw. nicht-turing-vollständigen Sprachen aufgezählt. Weiter irritiert mich als Laien der Informatik folgender Satz: »Alle gängigen Programmiersprachen sind Turing-vollständig.« Sosnt höre ich immer nur, dass die Turing-Vollständigkeit eine Voraussetzung sei, um überhaupt von einer Programmiersprache sprechen zu können (deswegen etwa sei HTML keine Programmiersprache). Wie ist es denn nun richtig? Ich fände es gut, wenn diese Fragen hier etwas diskutiert würden... --Teutates 14:03, 11. Mai 2006 (CEST)

Man kann nicht einfach so beweisen, ob irgendein Kalkül Turing-vollständig ist oder nicht, dazu benötigt man unter Umständen äußert komplizierte mathematische Beweise. Ein gutes Beispiel ist die Sprache der Wolfram-2,3-Turingmaschine, von der m. W. bis heute nicht bewiesen werden konnte, ob sie Turing-vollständig ist oder nicht. Prinzipiell muss man "nur" beweisen, dass jede Turing-berechenbare Funktion auch innerhalb des zu untersuchenden Kalküls berechenbar ist. Eine Funktion ist Turing-berechenbar, wenn sie µ-rekursiv oder WHILE-berechenbar ist oder wenn es eine Turing-Maschine gibt, die die Funktion berechnet (diese drei Bedingungen sind äquivalent). Wenn man sich die Definition der WHILE-Berechenbarkeit anschaut (siehe WHILE-Programm, wird einem auch schnell klar, wieso nahezu alle praktisch verwendeten Programmiersprachen Turing-vollständig sind: Die Anforderungen sind einfach nicht besonders hoch. Man braucht lediglich Variablen, Zuweisung, Addition, Subtraktion und eine Schleife der Form while(x != 0) do ... end. Das hat halt jede Programmiersprache (Bei funktionalen Sprachen gibt es zwar keine Zuweisungen, allerdings kann man deren Turing-Vollständigkeit meist leicht auf µ-Rekursion zurückführen). Was die Frage anbelangt, ob eine nicht Turing-vollständige Sprache den Namen "Programmiersprache" verdient, so bräuchte man dafür erstmal eine wasserdichte Definition von Programmiersprache. Im Wikipedia-Artikel zum Thema Programmiersprache heißt es: "Eine Programmiersprache ist eine Notation für Computerprogramme;". Schlägt man unter "Computerprogramm" nach, so heißt es: "Das [...] Programm ist eine Folge von Befehlen, welche auf einem Computer zur Ausführung gebracht werden können, um damit eine bestimmte Funktionalität [..] zur Verfügung zu stellen.". Wenn man das als Grundlage nimmt, so schließt das selbstverständlich auch nicht Turing-vollständige Sprachen ein, wie z. B. Sieve. Hier ist es ganz klar gegeben, dass es sich um eine Folge von Befehlen handelt, welche eine bestimmte Funktionalität bereitstellt, nämlich das Filtern von Mails. Ähnlich sieht es bei SQL aus, welches ebenfalls nicht Turing-vollständig ist.

Mir ging es ähnlich wie Teutates beim lesen des Artikel. So ähnlich wie in deiner Antwort es steht auch in jedem Lehrbuch zu dem Thema. Das sollte m.M. unbedingt ergänzt werden.

Ich bitte um Entschuldigung, wenn ich bisher bei der Diskussion über die Stränge geschlagen habe. Ich bin der Meinung, dass wir uns den Sachverhalt gemeinschaftlich auf der Diskussionsseite erarbeiten sollten (mit Quellenzitaten). Daraufhin sollten wir den Sachverhalt gut und genau erklärend im Artikel texten. Wobei wir sehen können, was von dem bisherigen erhalten bleibt.--84.157.242.85 17:47, 28. Jun. 2008 (CEST)

Wäre eine Maschine, die einen integer-Datentyp hat, Addition und Substraktion kann, Überläufe erkennt, und einen Vergleichsoperator für bedingte Sprünge hat, turing-vollständig? Irgendwas davon überflüssig? --129.13.72.198 12:50, 11. Jan. 2012 (CET)

System F?

was hat das damit am Hut?

Ich denke, hier ist voreilig eine Weiterleitungsseite angelegt worden. In der englischen Wikipedia ist das System F korrekt als das Lambdakalkül 2. Ordnung eingetragen.

Formale Sprachen

Also das hier kann ich nicht ganz glauben: "Eine mächtigere, aber immer noch nicht Turing-vollständige Erweiterung von endlichen Automaten sind formale Sprachen." Jede Programmiersprache kann als formale Sprache angesehen werden, und da gibt es definitiv touring-vollständige. Genaueres zu touring-vollständigen formalen Sprachen ist relativ einfach hier nachzulesen Chomsky-Hierarchie. Die Chomsky-Hierarchie ist ja genau eine Hierarchie formaler Sprachen (bzw. eine Hierarchie formaler Grammatiken die formale Sprachen definieren/erzeugen) und (wenn ich nicht irre) sind fast alle Programmiersprachen vom Chomsky-Typ 2 (und somit auch vom Typ 0 und 1).

Die Passage ist in der Tat falsch (und nehm ich 'raus). Eine richtige (aber sinnlose) Formulierung wäre: "Eine mächtigere, aber immer noch nicht Turing-vollständige Erweiterung von endlichen Automaten sind der Kellerautomat und der linear beschränkte Automat." Sinnlos ist diese Formulierung, weil die Eigenschaft "Turing-unvollständig" (weniger mächtig als die TM) direkt aus deren Konstruktion bzw. der Chomsky-Hierarchie folgt. Ein sinnvolles Beispiel lässt sich daraus nicht ableiten.
NB: Mit Deiner Aussage "fast alle Programmiersprachen vom Chomsky-Typ 2" irrst Du allerdings. Die Aussage "Programmiersprachen sind Turing-vollständig" entspricht (wie im Artikel richtig beschrieben) der Aussage "Programmiersprachen sind Chomsky-Typ 0". Diese Aussage bezieht sich auf die (Mächtigkeit der) Programme, die man in der Sprache schreiben kann. Allerdings ist die Sprache (Grammatik), die die Programmierprache selbst beschreibt (geschieht üblicherweise in BNF-Notation) vom Typ 2. Entsprechende Grammatiken schließen den Chomsky-Typ 3 (reguläre Ausdrücke, endliche Automaten, weil weniger mächtig) mit ein, nicht aber Typ 0 oder 1.--Sarge 16:08, 10. Nov. 2009 (CET)

Beispiele für Sprachen die nicht Turing vollständig sind

Jede Sprache die zu Beginn oder bei Beendigung eine feste Ausgabe macht ist nicht Turing vollständig, da sie zum Beispiel keinen leeren String ausgeben kann. Dies ist für viele interpretierte Sprachen der Fall. Ebenso sind viele Sprachen die bereits im Sprachstandard die Größe des Heaps und des Stacks begrenzen nicht Turing vollständig.

Welche sollen das sein? Sind diese relevant? --RokerHRO 23:05, 30. Mär. 2008 (CEST)

Ich würde sagen, das Brainfuck nicht Turing-Vollständig ist; allerdings bin ich mir auch nicht sicher, ob man brainfuck als Programmiersprache bezeichnen kann. ich würde es eher einen Verschlüsselungscode nennen... --212.202.247.146 11:58, 30. Sep. 2008 (CEST)

Was du sagen würdest, ist irrelevant. Brainfucks ist eine Programmiersprache und seine Turing-Vollständigkeit wurde bereits bewiesen. --RokerHRO 14:29, 30. Sep. 2008 (CEST)

das angeführte Beispiel sed (Unix) ist falsch, da sed durchaus eine Turing-äquivalente Spache ist - steht übrigens so auch im Artikel. Ich habe es deshalb entfernt. --bakunin (Diskussion) 00:41, 25. Nov. 2014 (CET)

reale nicht vernetzte Computer sind _nicht_ Turing-vollständig

Es sollte IMHO mehr Wert darauf gelegt werden, dass kein real existierender, nicht vernetzter, Digitalrechner Turing-vollständig sein kann, aufgrund der Endlichkeit seines Speichers und somit Endlichkeit seines Zustandsraumes. Vielleicht existiert ja eine Definition für "quasi Turing-vollständig", wenn der Zustandsraum des Rechners größer ist, als für ein konkretes Problem nötig ist. Mir ist so eine Definition aber leider nicht bekannt. --RokerHRO 10:58, 13. Feb. 2007 (CET)

Wer lesen kann, ist klar im Vorteil. Im Artikel heißt es explizit "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.". Das ist völlig ausreichend, zumal das einem denkenden Menschen sowieso klar sein sollte. Zu dieser Spezies scheinst Du aber nicht zu gehören, sonst wäre Dir eventuell aufgefallen, dass der Speicher auch bei einem vernetzten Rechner noch immer endlich ist.

Es ist ein Unterschied, ob man einen klassischen, nicht vernetzten Computer mit eben stets endlichem Speicher und damit endlichem Zustandsraum betrachtet, oder ein System, dessen Zustandsraum sich jederzeit beliebig erweitern lässt. Auf ersterem lässt sich eben nur eine Turingmaschine mit einem endlichem Band (dessen Länge sich nach Zusammenbau des Computers nicht mehr ändern lässt) simulieren, auf letzterem kann man die Simulation anhalten, wenn der verfügbare Speicher erschöpft ist, und weitermachen, sobald sich mehr Rechner mit mehr Speicher zum Netzwerk hinzugesellt haben und das - zumindest theoretisch - unendlich oft.

Natürlich spielt diese Unterscheidung in der Praxis kaum eine Rolle. Aber das Thema Turing-Vollständigkeit kommt ja auch eher aus der theoretischen Informatik. Und da halte ich diese Unterscheidung für durchaus relevant. --RokerHRO 22:56, 30. Mär. 2008 (CEST)

Falsch, RokerHRO. Wie oben steht, wird der Begriff der Turing-Vollständigkeit bereits "bei gängigen Programmiersprachen und Computern angewandt, die universell wären, wenn sie unbegrenzten Speicher besäßen". Im Übrigen lässt sich auch bei unvernetzten Rechnern stets eine externe Festplatte anstöpseln, andererseits ist auch die Rechen- und Speicherkapazität des Internetzes endlich groß und auch nicht beliebig vergrößerbar. Im Sinne der Turing-Vollständigkeit besteht zwischen vernetzten und stand alone Rechnern deshalb kein Unterschied. --2003:D4:C702:6701:F196:9D1D:1CE3:56D5 11:55, 18. Sep. 2021 (CEST)

SQL

SQL ist nicht turing-vollständig? Ich kenne leider nur einen Dialekt ganz gut und das ist MySQL, welcher turin-vollständig sein dürfte, da er IF und WHILE kennt (sofern man eine Datenbank benutzt, die theoretisch unendlich groß werden kann - was aber von dem Dialekt MySQL unabhängig ist).

Keine Ahnung wer den Artikel pflegt. Ich habe eine Modifikation gemacht, die den Wahrheitsgehalt des Artikels nicht wesentlch verändert. Da scheint jemand seine Beweisidee negativ formuliert zu haben.

Die Modelle der theo. Inf. sind nur endlicher Text, oder etwas äquivalentes, die man einige Zeit etwas Semantik aussetzt. Was soll es - das Universum könnte endlich sein und meine Geduld auf ein Ergebnis zu warten auch. Die Turingmaschine braucht einen Informationsträger, wie beispielsweise ein Papierband, oder moderner vielleicht Tesa-Band. Wo im Universum soll man das herbekommen. Der Satz von Rice sagt, alle nicht-triviale Aussagen über Turings-Brainer sind Mupets. Die Berechenbarkeitstheorie fürt sich selbst ad absurdum. Wer glaubt "Rice" kann man essen, ist ein Praktiker. Generalisiert man Rice's Satz ist sowieso nichts größeres berechenbar. Gefühlsmäsig widerspreche ich Rice. Ein Widerspruch mehr in den Diskussionen der wp, was soll's--84.157.213.134 14:50, 23. Jun. 2008 (CEST)

Die Aussage, dass relationale Algebra und SQL äquivalent sind ist Quatsch. SQL ist eine Sprache die diverse Operationen aus der relationalen Algebra kennt. Allerdings ist bereits die Tatsache dass das Ergebnis einer SQL-Abfrage eine Reihenfolge besitzt und Duplikate besitzen kann eine Verallgemeinerung der Relationenalgebra. Damit sind diese offensichtlich NICHT äquivalent. In SQL hat man durch das Konzept der rekursiven Vereinigung mit UNION ALL die Möglichkeit, transitive Hüllen zu berechnen. Daher ist SQL turingvollständig. Und dass die Datenbank dazu unendlich groß sein muss ist absoluter Quatsch! Gruß Thomas 93.131.158.208 19:25, 14. Dez. 2008 (CET)

Sogar Quantencomputer?

Ist es wirklich sicher, dass Quantencomputer "nur" turing-vollständig sind? Wo steht das?

Gibt es nicht eine Diskussion darum, ob es eine "hyperberechenbare" Oberklasse der Turing-Vollständigkeit geben könnte, also eine Klasse von Maschinen, welche von einer Turing-Maschine nicht simuliert werden kann? 130.83.30.182 13:45, 15. Aug. 2008 (CEST)

Seit zwei Jahren hat sich niemand dazu geäußert. Ich nehme den Satz "Die Turing-Vollständigkeit ist insofern von Relevanz, als jedes plausible Design einer Rechenmaschine (auch Quantencomputer) von einer Turing-Maschine emuliert werden können muss." jetzt vorläufig aus dem Artikel raus, bis jemand eine Quelle dafür findet. --130.83.244.131 15:03, 23. Sep. 2010 (CEST)

Mir (Nicht-Informatiker) kam gerade die gleiche Frage: "Eine Maschine, die Turing-vollständig ist, kann jede Berechnung, die irgendein Computer ausführen kann, ebenso ausführen und wird daher auch als universell programmierbar bezeichnet." heißt, dass normale Computer Q-Computer emulieren können, oder? (nicht signierter Beitrag von 84.178.238.229 (Diskussion) 22:22, 21. Dez. 2019 (CET))

Rechtschreibung

Ist eigentlich Turing-vollständig das einzige Adjektiv, dass man großschreibt?--178.24.70.200 18:41, 10. Okt. 2010 (CEST)

Offenbar nicht, siehe z.B. Lipschitz-stetig. --Phrood 20:08, 10. Okt. 2010 (CEST)

Turing-Vollständigkeit und Turing-Äquivalenz

"Exakt ausgedrückt bezeichnet Turing-Vollständigkeit 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." Ist das was der hintere Satz besagt nicht etwas stärkeres, nämlich die Turing-Äquivalenz? (nicht signierter Beitrag von 93.134.91.189 (Diskussion) 00:39, 21. Feb. 2015 (CET))