¿Hay algún lenguaje que pueda expresar su propio compilador Turing-complete?

Un comentario sobre tex.SE me hizo preguntarme. La declaración es esencialmente:

Si puedo escribir un compilador para el lenguaje X en el lenguaje X, entonces X está completo de Turing.

En términos de computabilidad y lenguajes formales, esto es:

Si decide y , entonces . $M$ $L \subseteq L_{\mathrm{TM}}$ $\langle M \rangle \in L$ $F_L = \mathrm{RE}$

Aquí denota el lenguaje de todas las codificaciones máquina de Turing y denota el conjunto de funciones calculadas por máquinas en . $L_{\mathrm{TM}}$ $F_L$ $L$

¿Es esto cierto?

computability turing-completeness Rafael
fuente

cierre, piense / acuerde que debe haber algo parecido a esto, cualquier lenguaje "no trivial" o "suficientemente complejo" que pueda expresar su propio simulador está completo. un compilador generalmente es parte de un simulador. de hecho, es un "patrón de diseño" que se encuentra en muchas pruebas de integridad de TM pero que tal vez no se ha generalizado / formalizado. tal vez un tema para análisis / discusión adicional en Computer Science Chat . sospechoso / conjetura, hay algunos otros temas interesantes algo así como "todo lenguaje no trivial / suficientemente complejo recursivo y recursivamente enumerable puede ser mapeado / reducido a todos los demás".

vzn

Creé un lenguaje esotérico llamado InterpretMe, que no puede hacer nada más que expresar su propio intérprete, por lo que ciertamente no está completo.

Ortografía no contextual

¿Puedes explicar la segunda declaración? ¿Cuál es

? ¿Cómo se relaciona esta declaración con la primera?

⟨ M ⟩

$\langle M \rangle$

reinierpost

@reinierpost

típicamente denota el número de

, dado que algunos (admisible) que codifica. Por lo tanto,

. Por

denoto el conjunto de funciones calculadas por el lenguaje

de las máquinas de Turing.

⟨ M ⟩

$\langle M \rangle$

M

$M$

L_{T M} = {⟨ M ⟩ ∣ M is a Turing machine}

$L_{\mathrm{TM}} = \{ \langle M \rangle \mid M \text{ is a Turing machine}\}$

F_{L}

$F_L$

L

$L$

Raphael

Una mejor manera de expresar el reclamo sería: "Si hay un TM

con

, entonces

M

$M$

⟨ M ⟩ \in L

$\langle M \rangle \in L$

L_{M} = L

$L_M = L$

F_{L} = R E

$F_L = \mathrm{RE}$

Rafael

Respuestas:

La declaración informal no es cierta, como se muestra en el siguiente lenguaje de programación. Cualquier cadena de, digamos, caracteres ASCII es un programa válido y el significado de cada programa es: "Generar un programa que solo genera una copia de su entrada". Por lo tanto, cada programa en este idioma es un compilador para el idioma, pero el idioma no es completo de Turing.

$M$ $2x$ $x$ $\langle M\rangle$ $L$ $M$ $F_L$

$(\phi_i)_{i\geq 0}$ $Q(x,y)$ $p$ $\phi_p$ $y$ $Q(p,y)$ $Q$ $x=y$ $p$ $\phi_p(y) = Q(p,y)$ $\phi_p$ $p$

David Richerby
fuente

¿En qué sentido cada programa en ese idioma es un compilador para ese idioma? Cada programa es un programa que ingresa un programa en ese idioma y genera un programa diferente en ese idioma, sí, pero generalmente los quines no se consideran compiladores.

user253751

c

$c$

c (P) = {x \Rightarrow r e t u r n P}

$c(P) = \{ x \Rightarrow \mathtt{return}\ P \}$

P (x) = P

$P(x) = P$

c

$c$

@immibis (tardíamente) creo que tienes razón. Parece que lo que quise escribir fue que la semántica de cada programa es simplemente "dar salida a su entrada". Eso parece lo suficientemente parecido a lo que escribí que probablemente fue lo que quise decir en primer lugar. O tal vez tuve mucha suerte de que la distancia de edición de mi respuesta incorrecta a la respuesta correcta fuera tan pequeña. :-)

David Richerby

La respuesta ahora dice "ignora su entrada y genera una copia de su entrada", no puede hacer ambas cosas.

user253751

@immibis Volveré de nuevo .

David Richerby