En lógica , matemáticas e informática , especialmente metalógica y teoría de la computabilidad , un método efectivo [1] o procedimiento efectivo es un procedimiento para resolver un problema por cualquier medio intuitivamente 'eficaz' de una clase específica. [2] Un método eficaz a veces 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. Debido a esto, un método puede ser efectivo con respecto a una clase de problemas y no serlo con respecto a una clase diferente.
Un método se considera formalmente eficaz para una clase de problemas cuando satisface estos criterios:
Opcionalmente, también puede ser necesario que el método nunca devuelva un resultado como si fuera una respuesta cuando el método se aplica a un problema externo a su clase. Agregar 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 a veces se denominan 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 las dos nociones coinciden: cualquier función de teoría de números que sea efectivamente calculable es recursivamente computable . Como esta no es una afirmación matemática, no puede probarse mediante una prueba matemática . [ cita necesaria ]