Cómo argumentar que si pudiéramos resolver el problema de la parada, entonces podríamos resolver ocupada castor?

Question

Esta es una de las tareas de mi asignación. Tengo una simulación de la máquina de Turing que puede simular un está ocupado castor . He hecho algunas investigaciones en probar este problema, pero todavía no lo entiendo así que supongo que tal vez usted me puede ayudar aquí. Una buena fuente para mí para ir ao ejemplo de cómo argumentar que esto sería bueno.

Answer 1

La función BB se define para ser el número máximo de pasos una máquina de Turing de un tamaño particular puede llevar a cabo y aún detener. (Otra forma de decirlo es que todas las máquinas de Turing de tamaño x o bien se detiene en menos de BB pasos (x), o correr para siempre).

Asumiendo que tiene una máquina de Turing de complejidad x, entonces se podría determinar si sería detener o no dejándola correr para BB (x) pasos de tiempo - si no hubiera detenido a continuación, entonces, por definición nunca lo hará.

Del mismo modo, si se puede resolver el problema de la parada, se puede evaluar todas las posibles máquinas de Turing de tamaño x, eliminar los que no se detenga, y tomar BB (x) siendo el máximo de los tiempos de ejecución de los residuos.

Por supuesto, BB (x) no es computable - y de hecho crece más rápido que cualquier posible función computable puede asignar el nombre -. Por lo que ni siquiera se puede aproximar

Answer 2

Puede encontrar la prueba que busca aquí , por debajo la prueba de que el problema del castor ocupado es incomputable.