Escriba un programa mental de no más de 256 caracteres que tome tantos pasos como sea posible, pero que no se repita infinitamente. El programa no puede tomar ninguna entrada.
Más específicamente:
- Asume un número infinito de celdas a la derecha.
- A
<cuando en la celda más a la izquierda no hace nada. - A
-cuando el valor de la celda es cero, establece la celda en255. +-<>.Todas las instrucciones cuentan como un paso cuando se ejecutan.- Cuando se encuentra un
[o], cuenta como un paso. Sin embargo, si la condición es verdadera y el flujo de control salta, el correspondiente]o[qué no de nuevo contará como un paso. - La solución que da más pasos gana.
- Si hay algún tipo de patrón en su solución,
nse agradece dar una función de cuántos pasos tomaría un programa de duración similar, pero no es obligatorio. - Para contar las instrucciones, puede usar este intérprete modificado :
Ejemplo:
++[-]
Las instrucciones encontradas son ++[-]-], y el programa se ejecutó durante 7 pasos.
code-challenge
brainfuck
busy-beaver
Anton Golov
fuente
fuente
floato lasdoubleprimitivas utilizadas para la informática general diaria. (En ese momento, la computadora solo está manipulando cadenas que representan la ecuación)Respuestas:
Aquí hay un programa de 41 caracteres que finalmente se detiene, dejando más de 10 ↑ (10 ↑ 28) celdas contiguas establecidas igual a 1 (por lo que el número de instrucciones ejecutadas es mucho mayor que eso):
Si no me equivoco, esa es una traducción correcta del siguiente programa en el lenguaje variante BF que utiliza un solo bit para cada celda de memoria (es decir, contenido de celda 0..1 en lugar de 0..255, entonces '+' actúa simplemente para voltear el valor de bit):
El valor exacto (el número de 1 bits adyacentes) producido por este último programa es
El programa anterior inicializa y calcula una función que crece como 2 ↑↑ x (en notación de flecha hacia arriba de Knuth ). Una conversión similar de un programa BF variante que inicializa y calcula una función que crece como 2 ↑ 23 x proporciona el siguiente programa de 256 caracteres:
que finalmente se detiene, dejando más de 2 ↑ 23 6 celdas adyacentes establecidas igual a 1 (por lo que el número de pasos es enormemente mayor que eso).
NB-1 : 2 ↑ 23 6 es un número "inconcebiblemente grande"; por ejemplo, incluso 2 ↑ 4 6 = 2 ↑↑↑↑ 6 ya supera el primer término (3 ↑↑↑↑ 3) en la secuencia utilizada para calcular el número de Graham .
NB-2 : Creo que es probable que 256 caracteres sean suficientes para que un programa BF inicialice y calcule una función con una salida mucho mayor que el número de Graham ; si encuentro tiempo, tal vez intente escribir uno.
NB-3 : en caso de que alguien esté interesado en el origen de los programas anteriores, aquí hay algunos recursos de programación para "Brainf * ck F" , con varios programas escritos en Python. ("Brainf * ck F", o simplemente "F", es lo que llamé una variante completa de Turing de Smallf * ck esolanguage.) Acabo de subir estos archivos, que han estado fuera de línea durante varios años, y por ahora el la página web vinculada es solo un "gabinete de archivos" - vea el archivo Busy_Beavers.txt para una discusión detallada relevante a los programas anteriores.
fuente
Aquí hay un bonito personaje de 39:
Básicamente hace un 'trineo' de 3 espacios que se mueve hacia la derecha y disminuye en uno. Completado en 31,919,535,558 instrucciones, con el bucle más interno ejecutándose 256 ^ 3 veces. Todavía tengo mucho espacio para extender esto bastante lejos a una velocidad de 14 caracteres a otro orden de magnitud para el tiempo de ejecución.
Funciona en cualquier intérprete con memoria ilimitada o con memoria envolvente.
Le dejo un ejercicio al lector para determinar cuándo terminará la versión mejorada por 2 bucles:
Ahora se ha ejecutado durante la noche y tiene más de 3,000,000,000 de pasos. Todavía no ha pasado por una sola iteración del bucle externo. Apenas ha superado el 15% del segundo ciclo.
fuente
Este programa funciona en un número infinito de celdas. Al principio se inician dos valores con valores ascii 255. El primer valor en la primera rotación del bucle principal se divide en 255 celdas y se inicializan con 255 cada uno, en la segunda rotación del bucle principal cada valor en 255 celdas se divide nuevamente hasta 255 * 255 celdas, de la misma manera para la rotación 255 del bucle principal, las celdas totales inicializadas serán 255 ^ 255. El segundo valor determina cuántas veces se repetirá el bucle principal.
fuente
Este programa es casi igual que mi programa anterior, la diferencia es que el valor que determina el bucle externo permanece fijo en una celda particular, por lo que se puede aumentar tanto el número de celdas inicializadas como los pasos totales al final del programa
células inicializadas al final del programa 255 ^ 255
celdas inicializadas al final del programa 255 ^ 255 ^ 3
Lo modifiqué aún más para que se ejecute para más cantidad de pasos.
Inicializa 255 ^ 255 celdas durante la primera rotación de las celdas principales 255 ^ (255 ^ 255 * 255) durante la segunda rotación del bucle principal 255 ^ {255 ^ (255 ^ 255 * 255) * 255} celdas durante la tercera rotación del bucle principal en de esta manera el bucle se repite 255 veces
fuente