Problema de resolubilidad
El problema de solucionabilidad ( decidability problem ) es una pregunta formulada en el marco de algún sistema formal que requiere una respuesta de sí o no, dependiendo posiblemente de los valores de algunos parámetros de entrada [1] .
Por ejemplo, el problema “dados dos números: y ; es divisible por ? es un problema de solución. La respuesta puede ser "sí" o "no" y depende de los valores de y . Un método para resolver un problema de solucionabilidad, presentado en forma de algoritmo, se denomina procedimiento de decisión para este problema. Por lo tanto, el procedimiento de resolución del problema del ejemplo anterior debe determinar el conjunto de acciones que se deben tomar para verificar la divisibilidad de enteros para números dados. Uno de estos algoritmos, la división por una columna , se estudia en la escuela primaria. Un resto igual a cero significa que la respuesta es "sí", de lo contrario, "no". Un problema de resolubilidad para el cual existe un procedimiento de resolución se denomina resoluble.
No todos los problemas matemáticos se pueden formular como problemas de solución. Calcular el producto de dos números, encontrar el algoritmo más rápido para multiplicar números y los problemas de optimización , en particular el clásico problema del viajante de comercio, no son problemas de solución, ya que no se pueden formular de tal manera que la respuesta al problema sea “ si o no".
La investigación en el campo de la teoría de la recursión a menudo se centra en problemas de decidibilidad, ya que muchos problemas pueden reducirse a ellos sin pérdida de generalidad.
Véase también
Notas
- ↑ Tom Stewart. Teoría de la Computación para Programadores . — Litros, 2015-06-24. - S. 329. - 386 pág. — ISBN 9785457831230 .
Literatura
- Maltsev A. I. , Algoritmos y funciones recursivas , Nauka, 1986.
- Daniel Kroening y Ofer Strichman, Procedimientos de decisión , Springer, ISBN 978-3-540-74104-6
- Hartley Rogers, Jr., La teoría de las funciones recursivas y la computabilidad efectiva , MIT Press , ISBN 0-262-68052-1 (rústica), ISBN 0-07-053522-1