Como seguimiento al programa de terminación más corto cuyo tamaño de salida excede el número de Graham y Golf un número mayor que TREE (3) , presento un nuevo desafío.
El número del cargador es un número muy grande, que es un poco difícil de explicar (ya que fue el resultado de un ejercicio de golf de código con un objetivo flexible). Hay una definición y explicación aquí , pero a los efectos de autocontención, que intentará explicar más adelante en este post también.
¡El algoritmo utilizado por Ralph Loader produce uno de los números más grandes de cualquier algoritmo (computable) jamás escrito! De hecho, el número de Loader es el número "computable" más grande en el Wiki de Googología. (Por número "computable", significan un número definido en términos de un cálculo). Eso significa que si la respuesta produce un número mayor que el número de Loader de una manera interesante (es decir, no solo el número de Loader + 1), podría bajar en Historia de la googología! Dicho esto, los programas que producen algo como el número + 1 de Loader son definitivamente respuestas válidas y contendientes a esta pregunta; Simplemente no esperes ninguna fama.
Su trabajo es crear un programa de terminación que produzca un número mayor que el número de Loader. Esto es código golf , por lo que gana el programa más corto.
- No está permitido tomar aportes.
- Su programa finalmente debe terminar de manera determinista, pero puede suponer que la máquina tiene memoria infinita.
- Puede suponer que el tipo de número de su idioma puede contener cualquier valor finito, pero necesita explicar cómo funciona exactamente en su idioma (por ejemplo: ¿un flotador tiene una precisión infinita?)
- No se permiten infinitos como salida.
- El flujo inferior de un tipo de número produce una excepción. No se envuelve.
- Debe proporcionar una explicación de por qué su número es tan grande y una versión no codificada de su código para verificar si su solución es válida (ya que no hay una computadora con suficiente memoria para almacenar el número de Loader).
Así que aquí hay una explicación del número de Loader. Consulte http://googology.wikia.com/wiki/Loader%27s_number y los enlaces en él para obtener detalles más precisos. En particular, contiene un programa que produce el número de Loader exactamente (por definición).
El cálculo de las construcciones es esencialmente un lenguaje de programación con propiedades muy particulares.
En primer lugar, cada programa sintácticamente válido finaliza. No hay bucles infinitos. Esto será muy útil, porque significa que si ejecutamos un programa de cálculo de construcciones arbitrario, nuestro programa no se atascará. El problema es que esto implica que el cálculo de las construcciones no está completo.
En segundo lugar, entre los idiomas completos que no son de Turing, es uno de los más poderosos. Esencialmente, si puede probar que una máquina de Turing se detendrá en cada entrada, puede programar una función en el cálculo de construcciones que la simule. (Esto no hace que el proceso sea completo, porque hay máquinas de detención que no puede probar que se están deteniendo).
El número del cargador es esencialmente un número de castor ocupado para el cálculo de construcciones, que es posible calcular ya que todos los programas coc terminan.
En particular, loader.c define una función llamada D. Aproximadamente, D(x)itera sobre todas las cadenas de bits inferiores ax , las interpreta como programas coc, ejecuta las sintácticamente válidas y concatena los resultados (que también serán cadenas de bits). Devuelve esta concatenación.
El número del cargador es D(D(D(D(D(99))))).
Una copia más legible del código de la wiki de googolología
int r, a;
P(y,x){return y- ~y<<x;}
Z(x){return r = x % 2 ? 0 : 1 + Z (x / 2 );}
L(x){return x/2 >> Z(x);}
S(v,y,c,t){
int f = L(t);
int x = r;
return f-2 ? f>2 ? f-v ? t-(f>v)*c : y : P(f,P(S(v,y,c,L(x)), S(v+2,t=S(4,13,-4,y),c,Z(x)))) : A(S(v,y,c,L(x)),S(v,y,c,Z(x)));
}
A(y,x){return L(y)-1 ? 5<<P(y,x) : S(4,x,4,Z(r));}
D(x)
{
int f;
int d;
int c=0;
int t=7;
int u=14;
while(x&&D(x-1),(x/=2)%2&&(1)){
d = L(L(D(x))),
f = L(r),
x = L(r),
c - r||(L(u)||L(r)-f||(x/=2)%2&&(u=S(4,d,4, r),t=A(t,d)),f/2&(x/=2)%2&&(c=P(d,c),t=S(4,13,-4,t),u=S(4,13,-4,u))),
c&&(x/=2)%2&&(t=P(~u&2|(x/=2)%2&&(u=1<<P(L(c),u)),P(L(c),t)),c=r)
u/2&(x/=2)%2&&(c=P(t,c),u=S(4,13,-4,t),t=9);
}
return a = P( P( t, P( u, P( x, c)) ),a);
}
main(){return D(D(D(D(D(99)))));}
fuente
Respuestas:
JavaScript, D ^ 6 (9) (
508501495492487485481 bytes)Este es un código codificado.
Código decodificado:
Código descodificado y descodificado (las condiciones y las cosas se guardan de loader.c):
En esto, se supone que es:
NumberNumberAlgoritmo de codificación / decodificación:
La codificación se realiza de la siguiente manera:
El algoritmo de decodificación:
La compresión se realizó con este código , marque solo la última casilla. Como esto codificará el mayor ahorro primero, no es la compresión más eficiente, pero tampoco sé cómo hacerlo más pequeño.
JavaScript, (339 caracteres )
Este código tomará la cadena de 16 bits como a, la convertirá en una cadena de 8 bits con el mismo binario (BE) y la
evalconvertirá.El código decodificado es el código codificado anterior.
Prueba de que D ^ 6 (9)> D ^ 5 (99)
Para esto, compararíamos D (9) y 99.
Al ejecutar manualmente el código, D (9) se encuentra igual a
(15*2^14849+1)*2^((15*2^14849+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^929+1)*2^((15*2^929+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^((15*2^59+1)*2^(15*2^59+1)))))))))))))))))))))))))))))))), e incluso D (0) es igual a8646911284551352321.Entonces, D (9) >>> 99, y debido a que D está aumentando estrictamente, D ^ 6 (9)> D ^ 5 (99).
D(D(D(D(D(99)))))aD(D(D(D(D(D(9)))))). También eso barajó las letras.&&(1)paraD(x)la condición del bucle./2s a>>1s porqueNumberfor...inafor...of.evalparaD, eliminarreturn.fuente
Python 3, D ^ 6 (9) (
608600599 bytes)Este es un código codificado. Extraído:
En esto, se supone que es:
Esto es básicamente un puerto de mi respuesta de JavaScript . Para más detalles, verifique eso.
La compresión se hizo con esto .
No estoy muy bien informado en Python, por lo que ciertamente hay lugares para guardar bytes.
Creo que sub-600 es posible.Sub-600 ha sido probado.Sreducir paréntesisu/2en la tercera última línea de la definición deDau>>1, salvando un byte de comprimirlo a un carácter con otro>>1s.fuente
Ruby, D ^ 6 (9) (553 bytes)
Este es un código codificado. Extraído:
Este código es el número del cargador con D 6 (9) en su lugar.
En esto, se supone que es:
Esto es básicamente un puerto de mi respuesta de JavaScript y la respuesta de Python 3 . Para más detalles, verifíquelos.
La compresión se realizó con esto (puede aparecer ya que no existe).
Soy un principiante en Ruby, así que tal vez menos de 512 es posible, pero lo dudo.
fuente