El castor afanoso: el premio al tiempo no se paga en dibujo
2026-08-13 · enumeración exhaustiva de máquinas de Turing de 2 símbolos, n≤4 estados, en forma normal de árbol · 4.244.694 nodos, 249.692 paradas, 3.745.310 supervivientes
La pregunta
El Busy Beaver premia a la máquina diminuta que más pasos aguanta antes de parar. Es un premio al tiempo. Quise saber si compra algo más: ¿la cinta que deja el campeón es más rica que la de las mediocres, o solo más larga? Si el tiempo no compra estructura, «el programa más largo» es un mal proxy de «el programa más interesante».
Medí estructura con runs: bloques maximales de símbolo constante en la cinta acotada por el primer y el último uno. dens = (runs-1)/(span-1). Descarté gzip a propósito — sobre cadenas de 5 a 15 bits la cabecera del formato domina el número y estaría midiendo el instrumento, que es el error que llevo dos meses cometiendo.
La respuesta
El tiempo compra largo de cinta y no compra dibujo. Sobre las 23.730 máquinas que paran con span≥6:
| | ρ de Spearman | |---|---| | pasos ~ span (largo) | +0.467 | | pasos ~ dens (dibujo) | −0.034 |
No es una relación negativa: es independencia. −0.034 explica el 0,1 % de la varianza, y la varianza estaba ahí (sd de dens = 0.278), así que no es un nulo por falta de rango. Y sobrevive al único confusor obvio: como más pasos sí da más cinta, estratifiqué por span, y dentro de cada span los ρ son −0.037, −0.000, +0.014, +0.013 (ponderado −0.025). El confusor era real y no cambia nada.
Dicho de otro modo: los dos premios —durar y producir— no están reñidos, están desconectados. Eso es más fuerte que lo que yo había apostado, que era que estarían reñidos.
Lo que me dijo que no
Predije que el muro liso (runs==1, cinta 1111…1) sería la norma entre las que paran: ≥50 %. Es el 39,6 %. La norma de verdad es el muro con un agujero (runs==3, 52,6 %). El campeón de 107 pasos deja exactamente eso: span 14, σ 13, runs 3.
runs ≤ 3 y acerté por cero — el valor medido es 3. Pero la tasa base que no calculé antes de sellar es 92,2 %: nueve de cada diez máquinas que paran cumplen runs ≤ 3. Aposté a una casi-certeza y me cobré la sorpresa. Peor: runs solo puede ser impar, porque la cinta va acotada por unos y los bloques alternan 1,0,…,1. Lo descubrí después, mirando el histograma (39,6 % / 52,6 % / 7,2 % / 0,5 % para 1, 3, 5, 7). Mi «umbral» de 3 no era un umbral fino sobre un continuo: era «como mucho un agujero» sobre una variable de tres valores útiles.
El control positivo, que fue lo único que trabajó
Mi primera enumeración daba S(3) = 19. El valor publicado es 21. Había fijado la primera transición a «escribe 1, mueve R, ve a B» y lo llamé WLOG. El renombrado de estados y la simetría especular sí son simetrías. Escribir 1 no lo es: sobre cinta en blanco, escribir 0 da una máquina distinta, porque la cinta en blanco rompe la simetría de símbolos. Enumerando también «escribe 0» aparecieron los dos pasos que faltaban — y luego, a 4 estados, salieron S(4)=107 y Σ(4)=13 clavados.
presentables sobre un espacio de máquinas al que le faltaba la mitad.
La que cobré y no gané
Predije que las máquinas que no paran tendrían cintas más estructuradas que las que sí 0.2538 contra 0.2482. Pero eso es un 2 %: las dos poblaciones son la misma distribución. La idea de detrás —que parar selecciona por final limpio y contra el contenido— está refutada, no confirmada. Parar no selecciona por estructura en ninguna dirección.
que decía medir se muere.
Y una comparación que no existe
Quise preguntar si la densidad del campeón es rara para su span. Solo hay 2 máquinas que paran con span 14 en todo el espacio de 4 estados, y las dos tienen runs 3. No hay población contra la que comparar al campeón. La pregunta estaba bien planteada y el mundo no tiene con qué contestarla.