Una variante de la función de castor ocupado

Al leer esta pregunta " Problemas naturales indecidibles de RE pero no completos de Turing ", me vino a la mente el siguiente lenguaje:

Si es la función de castor ocupado (puntaje máximo alcanzable entre todas las máquinas Turing de 2 símbolos de estado n detenidas del tipo descrito anteriormente, cuando se inicia en una cinta en blanco), defina la función:$\Sigma(\cdot)$

Ahora defina el idioma:

$L = \{ \langle M \rangle \; | \; \langle M \rangle \mbox{ halts and } BB(\langle M \rangle) = 0 \}$

¿Es recursivamente enumerable? (debería ser re: simplemente simule en paralelo M con todas las TM de la misma longitud, y si M se detiene y otra M 'se detiene con una puntuación más alta, agregue M a la enumeración).$L$$M$$M'$

¿Podemos reducir el problema de detención a ? (parece que no puede "capturar" la detención de los castores ocupados)$L$

No puedo creer que no haya visto esto antes, pero sí, con un oráculo para puedes resolver el problema. Obviamente, un oráculo para L nos da 'recursivamente' todas las máquinas de detención que no son Busy Beaver, por lo que la pregunta es '¿podemos descubrir recursivamente en L cuáles son los castores ocupados?'. Defina Σ 2 ( n ) como la función de conteo del 'segundo castor más ocupado'; es decir, el segundo puntaje más alto posible entre todos los TM de dos símbolos n- estados que se detienen. El truco aquí es que hay una función recursiva f ( ) tal que Σ ( n ) ≤ Σ $L$$L$$L$$\Sigma_2(n)$$n$$f()$ (es casi seguro que f ( n ) = n + 1 hará el truco, de hecho, pero eso requiere saber que la función BB está aumentando estrictamente): dada una máquina M de tamaño n que imprime Σ ( M ) 1s en su cinta y luego se detiene, hay algunasmáquinas c > 1 y dos de tamaño ≤ c n que imprimen exactamente Σ ( M ) 1s y exactamente Σ ( M $\Sigma(n)\leq\Sigma_2(f(n))$$f(n)=n+1$$M$$n$$\Sigma(M)$$c\gt 1$$\leq cn$$\Sigma(M)$ 1s, respectivamente, en sus cintas, y esto es válido para una máquina de 'castor ocupado' M a pesar de que no conocemos M explícitamente. Esto significa que tener un límite en la función 'segundo castor ocupado' para f ( n ) da un límite para la función de castor ocupado en n ; pero haciendo esto, es fácil de resolver el problema de la parada por un TM M de tamaño n - si ⟨ M ⟩ ∈ L luego decir que M se detiene; de lo contrario, encuentre la máquina de mayor duración de tamaño f ( n ) en$\Sigma(M)+1$$M$ $M$$f(n)$$n$$M$$n$$\langle M\rangle\in L$$M$$f(n)$$L$(lo que se puede hacer de forma recursiva ya que solo hay muchas máquinas finitas de tamaño ) y simulan M para todos los pasos que la máquina debe detener. Si M no se detiene dentro de ese tiempo, entonces M no puede detenerse.$\leq f(n)$$M$$M$$M$

Esta es una versión reelaborada de la buena respuesta de Steven, con una reducción explícita del problema de detención.

Dada acumulación M ' que se ejecuta M en w y si se detiene va a la derecha de la cinta, escribe un 0 y alto.$\langle M \rangle, w$$M'$$M$$w$

$M'$$BB(M')=0$$L$$M$$w$$M$$w$$M' \in L$

... resultó que la pregunta es realmente trivial :-)