Método eficaz

En lógica , matemáticas e informática , especialmente en metalógica y teoría de la computabilidad , un método eficaz ^[1] o procedimiento eficaz es un procedimiento para resolver un problema por cualquier medio intuitivamente "efectivo" de una clase específica. ^[2] A veces, un método eficaz también se denomina método o procedimiento mecánico . ^[3]

La definición de un método eficaz implica más que el método en sí. Para que un método se considere eficaz, debe considerarse con respecto a una clase de problemas. Por ello, un método puede ser eficaz con respecto a una clase de problemas y no serlo con respecto a otra clase diferente.

Un método se considera formalmente eficaz para una clase de problemas cuando satisface estos criterios:

• Consiste en un número finito de instrucciones exactas y finitas.
• Cuando se aplica a un problema de su clase:
  • Siempre finaliza ( termina ) después de un número finito de pasos.
  • Siempre produce una respuesta correcta.
• En principio, esto lo puede realizar un ser humano sin más ayuda que material de escritura.
• Sus instrucciones sólo deben seguirse rigurosamente para tener éxito. En otras palabras, no se requiere ingenio para lograrlo. ^[4]

Opcionalmente, también se puede exigir que el método nunca devuelva un resultado como si fuera una respuesta cuando el método se aplica a un problema desde fuera de su clase. Añadir este requisito reduce el conjunto de clases para las que existe un método eficaz.

Un método eficaz para calcular los valores de una función es un algoritmo . Las funciones para las que existe un método eficaz se denominan a veces efectivamente calculables .

Varios esfuerzos independientes para dar una caracterización formal de la calculabilidad efectiva condujeron a una variedad de definiciones propuestas ( funciones recursivas generales , máquinas de Turing , cálculo λ ) que luego demostraron ser equivalentes. La noción capturada por estas definiciones se conoce como computabilidad recursiva o efectiva .

La tesis de Church-Turing afirma que ambas nociones coinciden: cualquier función numérica que sea efectivamente calculable es recursivamente computable . Como no se trata de una afirmación matemática, no se puede demostrar mediante una prueba matemática . ^{[ cita requerida ]}

• Decidibilidad (lógica)
• Problema de decisión
• Problema de función
• Resultados efectivos en teoría de números
• Conjunto recursivo
• Problema indecidible

• SC Kleene (1967), Lógica matemática . Reimpreso, Dover, 2002, ISBN 0-486-42533-9 , pp. 233 y siguientes, esp. p. 231.