¿El problema de detención es computable para entradas / supuestos particulares?

Según tengo entendido, la prueba de que detener el problema no es computable, este problema no es computable porque si tenemos un programa P (x) que calcula si el programa x se detiene o no, tenemos una paradoja al dar P como entrada al mismo P, que tiene: P (P), tratando de decidir si P se detiene o no usa P en sí.

Entonces, mi pregunta es: ¿el programa P puede calcular el problema de detención para todos los demás programas utilizados como entrada, pero P en sí mismo? En otras palabras: ¿el problema de detención no es computable solo en este caso especial o la prueba es más general y me falta algo?

Si es una función computable, entonces , definida como$f$$g$

también es computable, para cualquier elección de .$k,v$

Básicamente, si tiene un programa que calcula para todos los ' s excepto para , puede "arreglar" ese caso (por ejemplo, usando un ) y obtener otro programa P que calcula g ( n ) para todos n . g ( n ) n n = $P'$$g(n)$$n$$n=k$if then else$P$$g(n)$$n$

Por lo tanto, si pudiera calcular la función de detención "a excepción de un caso", también podría calcular la función de detención (sin excepciones). De eso, puede obtener una contradicción como de costumbre.

Conclusión: no, no puede decidir el problema de detención "excepto un caso" (ni "excepto muchos casos").

¿El problema P es computable por el programa P para todos los demás programas utilizados como entrada pero P en sí mismo?

No. Considere la secuencia infinita de programas , donde P i es "Mueva la cabeza i  cuadra hacia la derecha, luego i  cuadra hacia la izquierda, luego haga exactamente lo que P haría". Cada uno de estos programas produce exactamente la misma salida que  P para cada entrada (incluido el bucle para siempre si P se  repite para siempre), pero todos son programas diferentes.$P_1, P_2, \dots$$P_i$$i$$i$$P$$P$$P$

Y no puede evitar esto si solo requiere que trabaje en programas que no son funcionalmente equivalentes a sí mismos, ya que esa propiedad también es indecidible. Quizás el problema sería decidible cuando se restringiera a esas instancias (aunque sospecho que no lo haría), pero el conjunto de instancias es indecidible, por lo que no podría realizar la restricción.$P$

Hay algoritmos para mostrar que ciertas clases de programas se detienen o no. Por ejemplo,

• Es posible determinar algorítmicamente si un programa que modela una máquina de estado finito se detiene.
• Es posible determinar aritméticamente si una máquina de turing con límites lineales se detiene
• Si sabe en qué clase de complejidad se encuentra un programa, entonces sabe que el programa se detiene por entradas finitas.

Si bien no existe un algoritmo para determinar si un programa arbitrario se detiene, la mayoría del código se diseñó para detenerse (como la mayoría de las subrutinas) o no (como un bucle infinito para manejar eventos), y es posible determinar algorítmicamente cuál es cuál. En otras palabras, puede tener un algoritmo que responda ya sea "se detiene", "no se detiene" o "No sé", y dicho algoritmo puede diseñarse para cubrir suficientes programas que serían útiles.

Las pruebas por contradicción no tienen que ser exhaustivas , un solo contraejemplo es suficiente. La prueba de que el problema de detención es indecidible le proporciona un ejemplo de P para el que no se puede decidir la propiedad de detención. Esta prueba no indica que P es el único programa de este tipo, de hecho, puede haber pruebas independientes que construyen clases de P. completamente diferentes.

La prueba es de hecho más general: el problema de detención es un caso especial del teorema de Rice , que establece

$\Phi$

$A$$B$$\Phi(A)$$\Phi(B)$

$x$$x$

Usted puede obtener algunos resultados, restringiendo el espacio de programas que desea trabajar, a pesar de estas restricciones tienen que ser bastante drástico. Por ejemplo, si tiene la garantía de que el programa que recibe se detiene dentro de 100 pasos o se ejecuta para siempre, decidir si se detiene se vuelve fácil.

$N$$k$$BB(k)$

Sea R un conjunto recursivamente enumerable pero no recursivo. Hay infinitos conjuntos de este tipo. Sea T una máquina de Turing que se detiene en la entrada k si y solo si k está en R. Tal T existe para cualquier conjunto recursivamente enumerable. Es imposible escribir un programa que pueda resolver el problema de detención de esta T. Esto se debe a que cualquier algoritmo para determinar si T se detiene produciría un algoritmo para determinar la pertenencia a R, lo cual es imposible si R no es recursivo. Dado que hay infinitamente tales R, cada una de las cuales proporciona diferentes máquinas de Turing, hay infinitas máquinas de Turing en las que cualquier intento de detener el programa P podría fallar.