Diskussion:Turing-Vollständigkeit
aus Wikipedia, der freien Enzyklopädie
fachlich und sprachlich weniger guter Artikel.
Inhaltsverzeichnis |
[Bearbeiten] 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)
[Bearbeiten] 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.
[Bearbeiten] 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).
[Bearbeiten] 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.
[Bearbeiten] 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)
