¿Es posible crear un quine en cada idioma turing-complete?
Solo quería saber si es 100% posible, si mi lenguaje es turing-complete, escribir un programa en él que se imprima (por supuesto, no usando una función de lectura de archivos)
Entonces, si el lenguaje solo tiene las cosas realmente necesarias para que turing sea completo (lo probaría traduciendo el código Brainf*ck a él), como salida, variables, condiciones y gotos (diablos, gotos), ¿puedo intentar escribir un quine en él?
También estoy preguntando esto porque no estoy seguro que un quine encaja directamente en la ley de Turing que la máquina de Turing es capaz de cualquier tarea computacional. Solo quiero saber para no intentarlo durante años sin saber que puede ser imposible.
4 answers
Cualquier lenguaje de programación que sea Turing completa, y que es capaz de salida de cualquier cadena (por un computable función de la cadena como programa - esta es una condición técnica que es satisfecho en cada programación idioma en existencia) tiene un quine programa (y, de hecho, infinitamente programas quine, y muchos similares curiosidades) como sigue por el teorema de punto fijo.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-04-02 17:15:39
Me encontré con este problema hace un par de meses.
Si bien escribir un quine no necesariamente prueba que un idioma está Turing Completo, es una fuerte sugerencia ;) En cuanto a la Integridad de Turing, si puedes (como dijiste) proporcionar una traducción válida de tu idioma a otro idioma Turing Completo, entonces tu idioma está Turing Completo.
Dicho esto, cualquier lenguaje que esté Turing Completo que pueda generar una cadena debería ser capaz de generar un quine. También, de Wikipedia:
Un quine es un punto fijo de un entorno de ejecución, cuando el entorno de ejecución es visto como una función. Los 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 diversión, los programadores a veces intentan desarrollar el quine más corto posible en cualquier lenguaje de programación dado.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-04-02 17:22:12
Es posible tener un lenguaje de programación que no puede 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 del idioma en árabe. Es la única excepción que se me ocurre.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-04-02 19:17:03
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 Turing-complate prácticos y cuerdos son todos numberings admisibles. Y un lenguaje de programación Turing-complate 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:
La fuente el código siempre contiene una o dos cadenas de escape doublequoted. Si la entrada está vacía, muestra la primera cadena si hay dos cadenas, o loop forever si hay una. De lo contrario, evalúe la última cadena en Python, usando la entrada original como entrada.
No es una numeración admisible porque, dado un programa Python, tenemos que conocer su comportamiento cuando la entrada está vacía, para traducirla a este lenguaje. Pero puede que nunca sepamos si es un bucle infinito, ya que no podemos resolver la detención problema. Sin embargo, sabemos que siempre existe una traducción.
Es imposible escribir quines en este idioma.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-06-01 11:41:02