En lógica , matemáticas e informática , especialmente en la teoría de la metalógica y la computabilidad , un método eficaz [1] o procedimiento eficaz es un procedimiento para resolver un problema de una clase específica. En ocasiones, un método eficaz también se denomina método o procedimiento mecánico . [2]
Definición
La definición de un método eficaz implica más que el método en sí. Para que un método se considere efectivo, 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 ser efectivo con respecto a una clase diferente.
Un método se llama formalmente efectivo para una clase de problemas cuando satisface estos criterios:
- Consiste en un número finito de instrucciones finitas y exactas.
- Cuando se aplica a un problema de su clase:
- Siempre termina ( termina ) después de un número finito de pasos.
- Siempre produce una respuesta correcta.
- En principio, puede hacerlo un ser humano sin ningún tipo de ayuda, excepto materiales para escribir.
- Sus instrucciones solo deben seguirse rigurosamente para tener éxito. En otras palabras, no se requiere ingenio para tener éxito. [3]
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 desde fuera de su clase. La adición de este requisito reduce el conjunto de clases para las que existe un método eficaz.
Algoritmos
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 .
Funciones computables
Varios esfuerzos independientes para dar una caracterización formal de la calculabilidad efectiva llevaron a una variedad de definiciones propuestas ( recursividad general , máquinas de Turing , cálculo λ ) que luego se demostró que eran equivalentes. La noción capturada por estas definiciones se conoce como computabilidad recursiva o efectiva .
La tesis de Church-Turing establece que las dos nociones coinciden: cualquier función de la teoría de números que sea efectivamente calculable es recursivamente computable . Como no se trata de una afirmación matemática, no puede demostrarse mediante una prueba matemática .
Ver también
Referencias
- ^ Hunter, Geoffrey , Metalogic: Una introducción a la metateoría de la lógica estándar de primer orden , University of California Press, 1971
- ^ Copeland, BJ ; Copeland, Jack; Proudfoot, Diane (junio de 2000). "La tesis de la Iglesia de Turing" . AlanTuring.net . Archivo de Turing para la historia de la informática . Consultado el 23 de marzo de 2013 .
- ^ El Diccionario de Filosofía de Cambridge, procedimiento eficaz
- SC Kleene (1967), lógica matemática . Reimpreso, Dover, 2002, ISBN 0-486-42533-9 , págs. 233 y siguientes, esp. pag. 231.