Puede que el número de ocupados castores con n estados calcularse, o sería necesario analizar todas las máquinas para contar ?
Respuesta
¿Demasiados anuncios?
( Busy beaver es un símbolo de máquina de Turing que se detiene cuando se inicia en una cinta en blanco, y lo hace en un número máximo de pasos entre todos los equipos con el mismo número de estados que detener en el espacio en blanco de la cinta).
Sería extraordinariamente sorprendente si el número de ocupados castores de un tamaño dado, era computable.
Recuerde que no debe ser máquinas donde es independiente de los axiomas (elegir cualquier recursiva conjunto de axiomas que no prueban aritmética falsedades) si la máquina es un castor ocupado o no. Dado que sería muy extraño si los axiomas no obstante determina cómo muchos de ellos no son ... y si no es así, podemos al menos nunca demostrar que cualquier algoritmo dado cuenta de ellos correctamente.
Ya nos estamos metiendo en cuestiones fundamentales aquí, la cuestión no es realmente un sí/no. Hay al menos cuatro imaginable resoluciones:
Sí, esta función es computable, y aquí es un algoritmo concreto que podemos probar que (a partir de una razonable base axiomática) calcula.
La función es computable, y aquí es un no-constructiva prueba de que no debe ser una máquina que calcula. Lo que nunca podemos saber qué equipo es, sin embargo.
Es independiente de (insertar el favorito de su sistema de axiomas aquí) si la función es computable o no.
La función se puede probar no computables.
De estos (1) y (2) me sorprendería, (1) más que (2). Sin embargo, (3) y (4) el sonido plausible -- intuitivamente mi dinero estaría en (3), sin embargo.
