¿Resolver el problema de detención para *casi* todas las máquinas?

Question

Según tengo entendido, la prueba de la indecidibilidad del problema de parada es conceptualmente bastante sencilla. Se postula una máquina $h(m, x)$ que (1) siempre se detiene y (2) devuelve 1 si $m$ se detiene con la entrada $x$ 0 en caso contrario. Usando esto, se construye una máquina $g(m)$ que gira eternamente si $h(m, m) = 1$ y se detiene si $h(m, m) = 0$ . Entonces, $g(g)$ crea una contradicción: si se detiene, entonces $h(g, g) = 1$ y $g(g)$ debe girar para siempre; y del mismo modo, si gira para siempre, debe detenerse.

Así que mi pregunta es: ¿dice esto algo sobre el problema de detención de las máquinas que no sea los que resuelven el problema de detención o utilizan máquinas que lo resuelven? Es decir, ¿no se podría seguir construyendo una máquina $h’(m, x)$ que resuelve el problema de detención para cualquier máquina excepto $h$ , $h'$ y cualquier máquina que incluya $h$ o $h'$ ? Con esa restricción, no se puede evaluar $g(g)$ y la contradicción desaparece. Parece que una máquina así seguiría siendo extremadamente potente.

¿O es que las matemáticas que hay detrás de mi escasa comprensión de la prueba de indecidibilidad lo impiden? Una forma en la que podría imaginar que esto ocurriera es si se pudiera demostrar que la definición precisa de "excepto cualquier máquina " es no-desaliente, en cuyo caso la respuesta a mi pregunta es básicamente que la existencia (¿o definición?) de $h'$ no es decidible.

No soy super no estoy muy versado en esta rama de las matemáticas, así que una respuesta del tipo "explícalo como si tuviera 5 años" sería muy apreciada.

---

(Disculpas si esto es un dup; he buscado otras preguntas de problemas de detención y no he podido encontrar una respuesta, aunque no estoy seguro de qué añadir para centrar la búsqueda. Esto parece similar a, pero diferente de, esta pregunta .)

Answer 1

El teorema dice que no existe ningún algoritmo que resuelva el problema de detención para todo Máquinas de Turing. Ciertamente hay algoritmos que resuelven el problema de parada para algunas subclases de máquinas. Sin embargo, su criterio no está bien expuesto. Hay otros problemas para los que se sabe que no existen algoritmos, por ejemplo, el problema de la palabra para grupos, o la existencia de soluciones de ecuaciones diofantinas. La interrupción de las máquinas de Turing que buscan soluciones a estos problemas también es indecidible.

Answer 2

No voy a responder a la pregunta, porque no sé cuál es la respuesta correcta. Sólo intento reformularla para que pueda recibir una respuesta precisa de alguien. El término "incluir" en la pregunta original puede carecer de la precisión necesaria para que la pregunta tenga una respuesta definitiva.

La prueba habitual de que el problema de detención es irresoluble emplea una forma de diagonalización: suponemos la existencia de la máquina H que resuelve el problema y luego construimos otra máquina D para la que H no siempre funcionará; la cuestión es que D se construye por referencia a la propia H: D está definida de tal manera que H, cuando se le alimenta con el código de D, tendría que comportarse de forma distinta a como se comporta con esa entrada. D se define de tal manera que sus cálculos están lógicamente relacionados con los de H.

Supongamos que queremos restringirnos a considerar sólo aquellos cálculos que no están relacionados con el comportamiento de H en el sentido de que no pueden ser definidos en términos del comportamiento de H. Para este problema limitado, la prueba clásica no se cumple. Entonces surge la pregunta: ¿puede existir un H que tenga éxito para todos los cálculos en el rango restringido aunque no funcione para todos los cálculos posibles?

Una respuesta afirmativa implicaría quizás que los cálculos pueden acomodarse en una jerarquía de niveles tal que para cualquier nivel n, existe una máquina algunos de cuyos cálculos son de nivel mayor que n y que resuelve el Problema de Parada para todos los cálculos de nivel n.

No estoy seguro de que mis propios términos ("puede definirse en términos de") sean más precisos que el "incluye" original, pero quizás lo sean.

Answer 3

Se puede demostrar que ni $h(g,g)$ o $g(g)$ detener. Por lo tanto, se puede resolver $g(g)$ construyendo una segunda máquina de parada $h'$ que devuelve $0$ si la entrada es $(g,g)$ y llama $h$ De lo contrario. No tengo una prueba, pero creo que en general, para cualquier programa y cualquier entrada, siempre se puede construir una máquina $M$ que indica si se detiene o no. Sin embargo, siempre habrá algún programa y alguna entrada para los que $M$ bucles. Para resolver el problema, intenta construir una máquina de parada diferente $M'$ . Dado un programa concreto y una entrada, lo más difícil, por supuesto, es averiguar qué máquina de parada va a resolverlo. Para algunos casos, es bastante obvio, pero la mayoría de los casos siguen siendo difíciles de resolver, aunque no imposibles.