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:
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 ]