Tenga en cuenta: por su naturaleza, las especificaciones para este desafío son difíciles de entender. Probablemente requiere al menos un curso de primer año en teoría de la computabilidad, o una lectura de fondo equivalente. Además, el desafío en sí es bastante difícil. Para contestarla, deberá escribir un intérprete completo para un subconjunto de su idioma de elección, y no solo eso, sino que el intérprete tendrá que tener la forma de una especie de quine. Si su respuesta no está haciendo todo esto, es casi seguro que no cumpla con las especificaciones.
No necesita resolver el problema de detención (incluso parcialmente) para resolver este desafío. Sin embargo, es casi seguro que necesite escribir un intérprete (del idioma que está usando, escrito en el mismo idioma que interpreta), aunque no es necesario que esté completo. Es esto lo que hace de este un desafío interesante.
Prometí otorgar una recompensa de 500 puntos a la primera respuesta que cumpla con las especificaciones, y esto se otorgará a la respuesta BF de Jo King .
El reto
Una versión aproximada y simplificada de la prueba de Alan Turing de la insolubilidad del problema de detención es algo así:
Supongamos que he escrito un programa Fdestinado a resolver el programa de detención. Es decir, Ftoma el código fuente de otro programa como entrada, y F(G)se supone que devuelve 1si se Gdetiene, y de lo 0contrario.
Pero si le doy mi programa, Fentonces puede construir otro programa Hque ejecute mi programa Hcomo entrada. Si F(H)regresa, 0entonces Hregresa 0, pero de lo contrario entra deliberadamente en un bucle infinito. Esto lleva a una paradoja, y tenemos que concluir que Fno puede resolver el problema de detención después de todo.
Su tarea es escribir el programa H, pero con un giro: no voy a darle mi programa. En cambio, su programa recibirá el código fuente de mi programa como entrada. Es decir:
Su programa recibirá mi programa como entrada, en forma de código fuente. (Por ejemplo, como un archivo o como entrada de línea de comando, los detalles dependen de usted).
Mi programa se escribirá en el mismo idioma que su programa, y también recibe información en forma de una cadena de código fuente.
Si mi programa regresa
0cuando se le da su programa como entrada, su programa debería detenerse (y regresar0) cuando se le da mi programa como entrada. (El significado exacto de "retroceder0" depende de usted).Si mi programa no se detiene, o si devuelve algo que no sea
0cuando se le dio su programa como entrada, su programa debería seguir ejecutándose indefinidamente.
El giro es que, solo para hacerlo mucho más difícil, debes obedecer las siguientes reglas:
No puede utilizar ningún tipo de función incorporada
execo deevaltipo.No puede utilizar ningún método de "trampa" para obtener el código fuente de su propio programa. (Por ejemplo, no puede decir "guardar esto en un archivo llamado 'programa'" y luego tenerlo
open(program)en su programa).
Esto significa que su programa tiene que ser algún tipo de súper quine loco que no solo puede reproducir su propio código fuente en forma de cadena, sino que también es capaz de analizar e interpretar correctamente el lenguaje en el que está escrito.
Para hacerlo un poco menos increíblemente difícil, puede usar solo un subconjunto (completo de Turing) de su idioma elegido. Entonces, si su programa está escrito en Python y solo funcionará si mi programa solo contiene ifs y whilebucles y operaciones básicas de cadena, entonces está bien siempre que su programa solo use esas cosas también. (¡Esto significa que no tiene que preocuparse por implementar la biblioteca estándar completa de su idioma elegido!) Sin embargo, su programa realmente tiene que ejecutarse: no puede inventar su propio idioma.
Este es un concurso de popularidad , por lo que gana la respuesta con más votos. Sin embargo, como se mencionó anteriormente, es un gran desafío solo cumplir con las especificaciones, por lo que otorgaré una recompensa de 500 puntos a la primera respuesta que lo haga de acuerdo a mi juicio.
tenga en cuenta: sin duda, hay muchas formas en que puede "engañar" en este desafío, dada la redacción exacta que he usado. Sin embargo, realmente espero respuestas que entren en el espíritu de la pregunta. El desafío según lo previsto es muy difícil pero posible, y realmente espero ver soluciones genuinas para él. No otorgaré la recompensa a una respuesta que me parezca engañosa a mi juicio.
Nota: este desafío se publicó originalmente como un concurso de popularidad , pero se cerró en 2016 debido a que no tenía un "criterio de objetivo ganador", y lo cambié a código de golf para reabrirlo. Sin embargo, descubrí que, a partir de enero de 2018, los concursos de popularidad no están prohibidos en PPCG (siendo esta la meta discusión más reciente), por lo que cerrarlo en primer lugar fue contrario a la política del sitio. Entiendo que los popcons no son populares en estos días, pero este es un viejo desafío, y su naturaleza lo hace realmente inadecuado para el código de golfsistema de puntuación. Si alguien todavía siente firmemente que no debería permitirse, entonces tengamos una meta discusión antes de que se empiecen a emitir votos cerrados. Finalmente, en el caso de que alguien haya pasado el último año intentando jugar golf su solución, tenga la seguridad de que será tan competitivo en este desafío y tan digno de la recompensa, como lo habría sido en el código golf. versión.
fuente
Fa un archivo e ingresarloimport? ; 3Respuestas:
brainfuck ,
601348774376 bytesEditar: -1136 bytes. Se cambió a una mejor forma de generar los datos para la quine
Edit2: -501 bytes. Volví a visitar mi autointerpretador y lo reduje a un par de cientos de bytes.
Pruébalo en línea! La entrada aquí es un simple programa cat (
,[.,]) que imprimirá el programa en sí.El "retorno 0" se define al finalizar el programa en una celda con valor 0.
Una combinación impía de dos programas que he escrito en el pasado, un quine y un auto-intérprete. La primera sección es la parte quine, que toma los datos y llena la cinta con la generación de datos seguida del código fuente. El siguiente es el autointerpretador, que toma su programa y lo ejecuta. Esto es más o menos una copia sin cambios de un autointerpretador normal, excepto que en lugar de recibir información directamente, obtiene información desde el comienzo de la sección de datos, configurando la celda a 0 si no hay más información. Finalmente, finalice en la celda actual de su programa y ejecútelo
[]. Si el valor devuelto fue 0, mi programa finalizará en cero. Si es algo más, ejecutará un bucle infinito. Si su programa se ejecuta para siempre,Mi programa se ejecutará para siempre.Cómo funciona:
Parte 1: generación de datos
Esta parte constituye la sección de datos de la quine, y es, con mucho, la mayoría del código en 3270 bytes. El comienzo
-es un marcador para el comienzo de los datos. Cada uno>+++representa un carácter del código después de esta sección.Parte 2: generar la sección de datos utilizando los datos
Esto utiliza los datos de la primera parte para agregar los caracteres que se utilizan para generar los datos a la sección de código. Agrega una
>al final de la sección de código y el valor de esa celda tiene muchas más ventajas.Parte 3: generar el resto del código utilizando los datos
Destruye la sección de datos y agrega el resto del código fuente a la sección de código.
Parte 4: Obtenga un programa ingresado
Obtiene el programa ingresado. Elimina los personajes que no son una mierda mental y representa cada personaje con un número:
Representa el final del programa con
255.Parte 5: Interpretar la entrada
Interpreta el programa. La única diferencia con respecto a una normal es que la entrada se toma desde el comienzo de la sección de código en lugar de la entrada.
Parte 6: Detener si el retorno no es 0
Navegue a la celda final de su programa y ejecute un ciclo infinito si el retorno no es 0. Si es 0, salga del ciclo y termine en ese mismo 0.
Entradas de prueba:
Siempre devuelve 0 (se detiene y devuelve 0)
Siempre devuelve 1 (se ejecuta para siempre)
Devuelve todas las entradas agregadas juntas, mod 256 (devuelve 211, por lo que se ejecuta para siempre)
Devuelve 0 si los dos últimos caracteres de un código son un bucle infinito (
[]) ( su programa devuelve 0 cuando se le da mi programa , por lo tanto, mi programa se detiene)Dato curioso para aquellos que todavía están leyendo
Si la entrada para este programa es el código fuente de este programa, comenzará a recurrir, creando repetidamente autointerpretadores que ejecutan este programa y luego le dan el mismo programa nuevamente. Esto me da algunas ideas interesantes sobre la creación de programas recursivos reales en brainfuck. En lugar de verificar el valor de retorno y comenzar un ciclo infinito como en esta pregunta, el valor de retorno se puede guardar y actuar sobre él. Un ejemplo simple sería un programa factorial que va
Por supuesto, esta es una forma completamente loca de codificar brainfuck, dado que ejecutar autointerpretadores recurrentes aumentará el tiempo de ejecución exponencialmente.
fuente
.. Aunque dado que esto ya no es una pregunta de código de golf, puede ser más impresionante admitir todo el lenguaje.