¿Cómo podría "resolver" el problema de detención si, hipotéticamente, los números de castor ocupados eran "pequeños"?

Question

Leí que si BB (N) no creció más rápido que todas las secuencias computables de enteros, podría resolver el problema detener y contradictar el teorema de Turing.

Estoy tratando de averiguar cómo podrías hacer esto específicamente.Una posibilidad obvia es construir una máquina de Turing de N-State que busque una solución a un problema indecidible, y simplemente esperando que pase las transiciones BB (N).Esto debería ser factible ya que BB (N), en este escenario, es pequeño y supera que demostraría que la máquina se bucea para siempre.

Pero esta no es una respuesta satisfactoria porque seguramente la decidibilidad no se trata de lo factible en la práctica, pero si es decidible en la teoría, y si las computadoras fueran lo suficientemente poderosas como para poder implementar esto en nuestro universo actual dondeBb (n) es muy grande?¿No deberíamos suponer que la máquina es independiente de la teoría del número?

Answer 1

Para seguir la estrategia que describe, debemos confiar en a priori que tenemos un límite superior en $ bb (n) $ . Más Snappily, si $ f $ es cualquier función con $ f (n) \ ge bb (n) $ , luego de $ f $ podemos calcular el problema de detención: dado un $ n $ máquina de estado , ejecutelo para $ f (n) $ -many pasos.

Dado que el problema de detención no es computable, esto significa que no hay tal $ f $ es computable; Este es un fenómeno "global". No particular valor de $ bb $ es demasiado grande para ser usado, pero más bien la tasa de crecimiento de $ bb (n) $ nos impide tener una secuencia completa de límites superiores, uno para cada $ n $ . Como analogía de bajo nivel:

No hay una función polinomial que esté siempre por encima de $ exp (n)= 2 ^ n $ . Por supuesto, esto no se debe a que los valores individuales de $ Exp $ son demasiado grandes, pero más bien debido al comportamiento general de la función en todas las entradas .

Answer 2

Pero esta no es una respuesta satisfactoria porque seguramente la decidibilidad no se trata de lo factible en la práctica, pero si es decidible en la teoría, y si las computadoras fueran lo suficientemente poderosas como para poder implementar esto en nuestro universo actual dondeBb (n) es muy grande?

El problema no es tanto que BB (N) es muy grande, el problema es que no es computable.Su supuesto procedimiento de decisión no funcionaría porque no sabría si hemos superado las transiciones BB (N) o no.