¿Pero cuánto más difícil? En 1962, el matemático Tibor Radó inventó una nueva forma de explorar esta pregunta a través de lo que llamó el juego de castor ocupado. Para jugar, comience por elegir un número específico de reglas: presente ese número norte. Tu objetivo es encontrar el norte-Contratando la máquina que funciona más tiempo antes de detenerse. Esta máquina se llama Beaver ocupado y el número de castor ocupado correspondiente, BB (norte), es el número de pasos que se toma.
En principio, si desea encontrar el castor ocupado para cualquier nortesolo necesitas hacer algunas cosas. Primero, enumere todo lo posible norte-Contratación de turing. A continuación, use un programa de computadora para simular la ejecución de cada máquina. Busque signos reveladores de que las máquinas nunca se detengan; por ejemplo, muchas máquinas caerán en bucles repetitivos infinitos. Deseche todas estas máquinas no halcas. Finalmente, registre cuántos pasos tomó cualquier otra máquina antes de detenerse. El que tiene el tiempo de ejecución más largo es su castor ocupado.
En la práctica, esto se vuelve complicado. Para empezar, el número de posibles máquinas crece rápidamente con cada nueva regla. Analizarlos a todos individualmente sería desesperado, por lo que deberá escribir un programa de computadora personalizado para clasificar y descartar máquinas. Algunas máquinas son fáciles de clasificar: se detienen rápidamente o caen en bucles infinitos fácilmente identificables. Pero otros corren durante mucho tiempo sin mostrar ningún patrón obvio. Para estas máquinas, el problema de detención merece su temible reputación.
Cuantas más reglas agregue, más potencia informática necesitará. Pero la fuerza bruta no es suficiente. Algunas máquinas funcionan durante tanto tiempo antes de detenerse que simularlas paso a paso es imposible. Necesitas trucos matemáticos inteligentes para medir sus tiempos de ejecución.
“Las mejoras tecnológicas definitivamente ayudan”, dijo Shawn Ligockiun ingeniero de software y un cazador de castores ocupado desde hace mucho tiempo. “Pero solo ayudan hasta ahora”.
Final de una época
Los cazadores de Beaver ocupados comenzaron a atribuir el problema de BB (6) en serio en los años 90 y 2000, durante un punto muerto en la caza de BB (5). Entre ellos estaban Shawn Ligocki y su padre, Terry, un matemático aplicado que dirigió su programa de búsqueda en las horas libres en poderosas computadoras en el Laboratorio Nacional de Lawrence Berkeley. En 2007, encontraron una máquina Turing de seis reglas que rompió el récord del tiempo de ejecución más largo: la cantidad de pasos que tomó antes de detenerse tenía casi 3.000 dígitos. Ese es un número colosal por cualquier medida ordinaria. Pero no es demasiado grande para escribir. En una fuente de 12 puntos, esos 3.000 dígitos cubrirán casi una sola hoja de papel.
Tres años más tarde, un estudiante de informática de pregrado eslovaco llamado Pavel Kropitz decidió abordar la caza de BB (6) como un proyecto de tesis senior. Escribió su propio programa de búsqueda y lo estableció en segundo plano en una red de 30 computadoras en un laboratorio universitario. Después de un mes, encontró una máquina que duró mucho más que la descubierta por los Ligockis, un nuevo “campeón”, en la jerga de los cazadores de castores ocupados.
“Tuve suerte, porque la gente en el laboratorio ya se quejaba del uso de mi CPU y tuve que reducir un poco”, escribió Kropitz en un intercambio de mensajes directos sobre el Servidor de discordia de Beaver Beaver. Después de otro mes de búsqueda, rompió su propio récord con una máquina cuyo tiempo de ejecución tenía más de 30,000 dígitos, suficientes para llenar unas 10 páginas.