Método efectivo - Effective method
En lógica , matemáticas e informática , especialmente en la teoría de la metalógica y la computabilidad , un método o procedimiento efectivo es un procedimiento para resolver un problema de una clase específica. Un método eficaz a veces también se denomina método o procedimiento mecánico .
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.
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
- Decidibilidad (lógica)
- Problema de decisión
- Problema de funcionamiento
- Resultados efectivos en teoría de números
- Conjunto recursivo
- Problema indecidible
Referencias
- SC Kleene (1967), lógica matemática . Reimpreso, Dover, 2002, ISBN 0-486-42533-9 , págs. 233 y siguientes, esp. pag. 231.
 |
Este artículo relacionado con la lógica es un fragmento . Puedes ayudar a Wikipedia expandiéndolo . |