language-design - traducir - traductor de voz
¿Es posible crear una quine en todos los idiomas completos? (4)
Solo quería saber si es 100% posible, si mi idioma está completo, escribir un programa que se imprima por sí mismo (por supuesto, no utilizando una función de lectura de archivos)
Entonces, si el lenguaje tiene las cosas realmente necesarias para que se complete (demostraría que al traducirle el código Brainf * ck), como salida, variables, condiciones y gotos (demonios, gotos), puedo probar escribiendo una quine en ella?
También estoy preguntando esto porque no estoy seguro de que una quine se ajuste directamente a la ley de Turing de que la máquina de turing es capaz de realizar cualquier tarea computacional. Solo quiero saberlo, así que no lo intento por años sin saber que puede ser imposible.
Cualquier lenguaje de programación que esté completo como Turing, y que pueda generar cualquier cadena (mediante una función computable de la cadena como programa, esta es una condición técnica que se cumple en cada lenguaje de programación existente) tiene un programa en quine (y, en De hecho, infinitos programas en quine y muchas curiosidades similares, como sigue el teorema de punto fijo.
Bueno, técnicamente, no siempre. Según la prueba en Wikipedia , el lenguaje de programación debe ser una numeración admisible. Prácticos y sanos lenguajes de programación de Turing complate son todos numeraciones admisibles. Y un lenguaje de programación compilado por Turing es una numeración admisible si es posible traducir entre esa y otra numeración admisible.
Un ejemplo de lenguaje de programación Turing-complete que no es una numeración admisible:
El código fuente siempre contiene una o dos cadenas escapadas con comillas dobles. Si la entrada está vacía, genere la primera cadena si hay dos cadenas, o haga un 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 Python, debemos conocer su comportamiento cuando la entrada está vacía, para traducirla a este idioma. Pero nunca podremos saber si es un bucle infinito, ya que no podemos resolver el problema de la detención. Sin embargo, sabemos que siempre existe una traducción.
Es imposible escribir quines en este idioma.
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 estar limitada a caracteres ASCII de 7 bits con palabras clave de idioma en árabe. Esa es la única excepción que se me ocurre.
Me encontré con este problema hace un par de meses.
Mientras que escribir una quine no prueba necesariamente que un idioma sea Turing Complete, es una sugerencia importante;) En lo que respecta a Turing Completeness, si puede (como usted dijo) proporcionar una traducción válida de su idioma a otro Turing-Complete Idioma, entonces tu idioma es Turing Complete.
Dicho esto, cualquier lenguaje que sea Turing Complete que pueda generar una cadena debe poder generar una quine. Además, desde Wikipedia:
Una quine es un punto fijo de un entorno de ejecución, cuando el entorno de ejecución se ve como una función. Las quines son posibles en cualquier lenguaje de programación que tenga la capacidad de generar cualquier cadena computable, como consecuencia directa del teorema de recursión de Kleene . Para divertirse, los programadores a veces intentan desarrollar la más corta posible en cualquier lenguaje de programación dado.