¿Qué es?
El número de Busy Beaver, o castor ocupado, es una función que da la máxima cantidad de pasos o símbolos que una máquina de Turing con un número fijo de estados puede ejecutar antes de detenerse, si se limita a operar en cinta blanca. Cada valor define el comportamiento más ‘productivo’ posible para máquinas de ese tamaño.
Complejidad
Para cada número de estados, el valor correspondiente de la función Busy Beaver crece más rápido que cualquier función computable. Esta función es no computable: no existe un algoritmo general que determine su valor para cualquier número de estados, lo que refleja límites fundamentales en la teoría de la computación.
Curiosidades
Los números Busy Beaver son conocidos sólo para máquinas de muy pocos estados. Para valores mayores, su magnitud aumenta de forma explosiva. El estudio de esta función ofrece ejemplos de números colosales que emergen de problemas simples.