Se sabe que ciertos problemas son indecidibles, pero sin embargo es posible avanzar en su solución. Por ejemplo, el problema de detención es indecidible, pero se puede hacer un progreso práctico en la creación de herramientas para detectar posibles bucles infinitos en su código. Los problemas de mosaico a menudo son indecidibles (p. Ej., ¿Este poliomino mosaico tiene algún rectángulo?) Pero de nuevo es posible avanzar en el estado del arte en esta área.
Lo que me pregunto es si existe algún método teórico decente para medir el progreso en la resolución de problemas indecidibles, que se asemeje al aparato teórico que se ha desarrollado para medir el progreso en problemas NP-difíciles. ¿O parece que estamos atascados con evaluaciones ad hoc, sé-progreso-cuando-lo-veo, de cuánto avances particulares avanzan nuestra comprensión de problemas indecidibles?
Editar : Al pensar en esta pregunta, se me ocurre que quizás la complejidad parametrizada puede ser relevante aquí. Un problema indecidible puede volverse decidible si introducimos un parámetro y fijamos el valor del parámetro. Sin embargo, no estoy seguro de si esta observación es útil.
Respuestas:
En el caso del problema de detención, la respuesta es "todavía no". La razón es que el método lógico estándar para caracterizar cuán difícil es la prueba de terminación de un programa (por ejemplo, análisis ordinal) tiende a perder demasiada estructura combinatoria y / o teórica de números.
Esto significa que no hay una relación clara entre la fuerza teórica de la prueba de la metalogía en la que muestra la terminación (esto es muy importante en la reescritura de la teoría, por ejemplo) y las funciones que las técnicas como la síntesis de función de rango pueden mostrar la terminación para .
Para el cálculo lambda, tenemos una caracterización precisa de la terminación en términos de tipificación: un término lambda se normaliza fuertemente si y solo si se puede escribir bajo la disciplina de tipo intersección. Por supuesto, esto significa que la inferencia de tipo completo para los tipos de intersección es imposible, pero también puede proporcionar una forma de comparar algoritmos de inferencia parcial.
fuente
De una charla memorable de una persona que implementó un algoritmo que resuelve un problema indecidible: "Me toma 2-3 segundos para todas las entradas que probé".
fuente
Esto responde al título de la pregunta más que a su contenido, pero también puede considerar las "aproximaciones" del problema de detención como algoritmos que le darán una respuesta correcta en "casi todos" los programas.
La noción de "casi todos" los programas solo tiene sentido si su modelo de cálculo es óptimo (en el mismo sentido que para la complejidad de Kolmogorov ), para evitar situaciones en las que la mayoría de sus programas son triviales.
fuente