Gibt es eine Sprache, die ihren eigenen Turing-Compiler vollständig ausdrücken kann?

12

Ein Kommentar zu tex.SE ließ mich staunen . Die Aussage ist im Wesentlichen:

Wenn ich einen Compiler für Sprache X in Sprache X schreiben kann, ist X Turing-vollständig.

In Bezug auf die Berechenbarkeit und die formalen Sprachen ist dies:

Wenn entscheidet L L T M und M L , dann F L = R E .MLLTMMLFL=RE

Hier bezeichnet die Sprache aller Turing-Maschinencodierungen und F L die Menge von Funktionen, die von Maschinen in L berechnet werden .LTMFLL

Ist das wahr?

Raphael
quelle
Schließen, denken / stimmen Sie zu, es muss einen Real Thm geben, der diesem ähnlich ist. Jede "nichttriviale" oder "ausreichend komplexe" Sprache, die ihren eigenen Simulator ausdrücken kann, ist TM-vollständig. Ein Compiler ist in der Regel Teil eines Simulators. es ist in der Tat ein "Entwurfsmuster", das in vielen TM-Vollständigkeitsnachweisen zu finden ist, aber möglicherweise nicht verallgemeinert / formalisiert wurde. Vielleicht ein Thema für weitere Analysen / Diskussionen im Computer Science Chat . Verdacht / Vermutung gibt es einige andere interessante Thems wie "jede nichttriviale / ausreichend komplexe rekursive und rekursiv aufzählbare Sprache kann auf jede andere abgebildet / reduziert werden".
VZN
1
Ich habe eine esoterische Sprache namens InterpretMe erstellt, die nichts anderes kann , als ihren eigenen Interpreter auszudrücken. Es ist also mit Sicherheit nicht vollständig.
Nicht-kontextuelle Rechtschreibung
Können Sie die zweite Aussage erklären? Was ist ? In welcher Beziehung steht diese Aussage zur ersten? M
Reinierpost
@reinierpost bezeichnet üblicherweise die Anzahl von M , da einige (zulässig) kodiert. Daher L T M = { M | M  ist eine Turingmaschine } . Mit F L bezeichne ich die Menge von Funktionen, die durch die Sprache L von Turing-Maschinen berechnet werden. MMLTM={MM is a Turing machine}FLL
Raphael
Ein besserer Weg , um die Forderung zu erklären wäre: „Wenn es ein TM mit M L und L M = L , dann F L = R E .MMLLM=LFL=RE
Raphael

Antworten:

13

Die informelle Aussage ist nicht wahr, wie die folgende Programmiersprache zeigt. Eine beliebige Zeichenfolge von beispielsweise ASCII-Zeichen ist ein gültiges Programm, und die Bedeutung jedes Programms lautet: "Ein Programm ausgeben, das nur eine Kopie seiner Eingabe ausgibt." Somit ist jedes Programm in dieser Sprache ein Compiler für die Sprache, aber die Sprache ist nicht vollständig.

Ich bin mir nicht sicher, ob Ihre "computability theory version" äquivalent ist, aber es ist auch nicht wahr. Nach Kleenes zweitem Rekursionssatz gibt es für jede Codierung von Turing-Maschinen ein TM, das seine eigene Codierung akzeptiert und alle anderen ablehnt. 1 Diese Maschine ist ein Gegenbeispiel zum Satz. Konkreter können wir das Ergebnis erzielen, indem wir eine Kodierung wählen. Lassen Sie beispielsweise jede ungerade Zahl die Maschine codieren, die  durch "Wenn meine Eingabe ungerade ist, akzeptieren Sie sie, andernfalls verwerfen" definiert ist, und lassen Sie die Zahl  2 x die Maschine codieren, die durch  x in Ihrem eigenen bevorzugten Codierschema für Turing-Maschinen codiert ist. M  ist in der Sprache  L lassener  MM2xxMLMaber  ist nicht Turing abgeschlossen.FL


1 Kleenes zweiter Rekursionssatz besagt, dass es für jede Aufzählung der partiellen rekursiven Funktionen (dh für jede Codierung von Programmen als ganze Zahlen) und für jede partielle rekursive Funktion  Q ( x , y ) eine gibt Ganzzahl  p, so dass ϕ p  die Funktion ist, die y auf Q ( p , y ) abbildet . Insbesondere sei Q also die Funktion, die akzeptiert, wenn x = y ist(ϕi)i0Q(x,y)pϕpyQ(p,y)Qx=yund lehnt sonst ab. Nach dem Satz gibt es eine ganze Zahl  , die das Programm ϕ p ( y ) = Q ( p , y ) codiert . Das heißt, ϕ p akzeptiert seine eigene Codierung  p und weist alle anderen Eingaben zurück.pϕp(y)=Q(p,y)ϕpp

David Richerby
quelle
1
Inwiefern ist jedes Programm in dieser Sprache ein Compiler für diese Sprache? Jedes Programm ist ein Programm, das ein Programm in dieser Sprache eingibt und ein anderes Programm in dieser Sprache ausgibt, ja, aber Quines werden im Allgemeinen nicht als Compiler betrachtet.
user253751
1
Ich denke, @immibis hat einen Punkt: Ihr Compiler ist c ( P ) = { x r e t u r n P }, wohingegen alle Programme in der Sprache P ( x ) = P sind , so dass c eindeutig nicht in der Sprache ist . Vermisse ich etwas? cc(P)={xreturn P}P(x)=Pc
Raphael
1
@immibis Ich (verspätet) denke, du hast recht. Es scheint, als wollte ich schreiben, dass die Semantik jedes Programms nur "Ihre Eingaben ausgeben" soll. Das scheint nah genug an dem zu sein, was ich geschrieben habe, dass es wahrscheinlich das war, was ich eigentlich sagen wollte. Oder vielleicht hatte ich das große Glück, dass die Bearbeitungsentfernung von meiner falschen Antwort zur richtigen Antwort so gering war. :-)
David Richerby
1
Die Antwort lautet jetzt "ignoriert die Eingabe und gibt eine Kopie der Eingabe aus" - Sie können nicht beides tun.
user253751
@immibis Ich komme wieder rein .
David Richerby