¿Es posible crear una quine en cada idioma completado de Turing?

Question

Solo quería saber si es 100% posible, si mi idioma es Turing-Complete, escribir un programa que se imprima (por supuesto, no usa una función de lectura de archivos)

Entonces, si el lenguaje solo tiene las cosas realmente necesarias para completarlo (probaría que al traducir el código Brainf*ck), como salida, variables, condiciones y gotos (demonios, sí, gotos), ¿puedo intentarlo? ¿Escribir una quine en él?

También estoy preguntando esto porque no estoy seguro de que una quina se ajuste directamente a la ley de Turing que la máquina Turing es capaz de cualquier tarea computacional. Solo quiero saber para no intento durante años sin saber que puede ser imposible.

Answer 1

Cualquier lenguaje de programación que esté completo, y que sea capaz de generar cualquier cadena (mediante una función computable de la cadena como programa: esta es una condición técnica que se satisface en cada lenguaje de programación que existe) tiene un programa Quine (y, en De hecho, infinitamente muchos programas de quine y muchas curiosidades similares) como sigue el teorema de punto fijo.

Mira aquí

Answer 2

Me encontré con este problema hace un par de meses.

Si bien escribir un quine no necesariamente prueba que un idioma está completo, es una sugerencia fuerte;) en lo que respecta a la integridad de Turing, si puede (como usted dijo) proporcionar una traducción válida de su idioma a otro Turing-Complete Lenguaje, entonces su idioma está completo.

Dicho esto, cualquier idioma que esté completo que pueda generar una cadena debería poder generar una quine. Además, de Wikipedia:

Una quina es un punto fijo de un entorno de ejecución, cuando el entorno de ejecución se ve como una función. Las quinas son posibles en cualquier lenguaje de programación que tenga la capacidad de generar cualquier cadena computable, como consecuencia directa de Teorema de recursión de Kleene. Para diversión, los programadores a veces intentan desarrollar la quina más corta posible en cualquier lenguaje de programación dado.

Answer 3

Es posible tener un lenguaje de programación que no pueda imprimir todos los símbolos en su representación. Por ejemplo, la E/S puede limitarse a los caracteres ASCII de 7 bits con palabras clave del lenguaje en árabe. Esa es la única excepción en la que puedo pensar.

Answer 4

Bueno, técnicamente, no siempre. De acuerdo con la Prueba en Wikipedia, el lenguaje de programación tiene que ser una numeración admisible. Los lenguajes de programación prácticos y sensatos que completan son numeraciones admisibles. Y un lenguaje de programación que completa con Turing es una numeración admisible si es posible traducir entre eso y otra numeración admisible.

Un ejemplo de lenguaje de programación de Turing-Complete que no es una numeración admisible:

El código fuente siempre contiene una o dos cadenas escapadas de doble cita. Si la entrada está vacía, salga la primera cadena si hay dos cadenas o bucle para siempre si hay una. De lo contrario, evalúe la última cadena en Python, utilizando la entrada original como entrada.

No es una numeración admisible porque, dado un programa de Python, tenemos que saber su comportamiento cuando la entrada está vacía, para traducirla a este idioma. Pero es posible que nunca sepamos si es un bucle infinito, ya que no podemos resolver el problema de detención. Sin embargo, sabemos que siempre existe una traducción.

Es imposible escribir Quines en este idioma.