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

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 .$M$$L \subseteq L_{\mathrm{TM}}$$\langle M \rangle \in L$$F_L = \mathrm{RE}$

Hier bezeichnet die Sprache aller Turing-Maschinencodierungen und F L die Menge von Funktionen, die von Maschinen in L berechnet werden .$L_{\mathrm{TM}}$$F_L$$L$

Ist das wahr?

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. ¹ 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  $M$$2x$$x$$\langle M\rangle$$L$$M$aber  ist nicht Turing abgeschlossen.$F_L$

¹ 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 = $(\phi_i)_{i\geq 0}$$Q(x,y)$$p$$\phi_p$$y$$Q(p,y)$$Q$$x=y$und 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$$\phi_p(y) = Q(p,y)$$\phi_p$$p$