Método eficaz

En metalógica , lógica matemática y teoría de la computabilidad , un método efectivo ^{[ 1 ]} o procedimiento efectivo es un procedimiento determinista de tiempo finito para resolver un problema de una clase específica. ^{[ 2 ]}^{[ 3 ]} Un método efectivo también se denomina a veces método o procedimiento mecánico . ^{[ 4 ]} Las funciones para las que existe un método efectivo se denominan a veces calculables de manera efectiva .

Definición

Formalmente, un método se considera eficaz para una clase específica de problemas cuando cumple los siguientes criterios:

Consiste en un número finito de instrucciones exactas y finitas.
Cuando se aplica a un problema de su clase:
- Siempre termina ( finaliza ) después de un número finito de pasos.
- Siempre produce una respuesta correcta.
En principio, puede hacerlo un ser humano sin más ayuda que los materiales de escritura.
Para tener éxito, basta con seguir sus instrucciones rigurosamente . En otras palabras, no requiere ingenio para tener éxito. ^{[ 5 ]}

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

Algoritmos

Un método eficaz para calcular los valores de una función se denomina " algoritmo ".

funciones computables

Diversos esfuerzos independientes por caracterizar formalmente la computabilidad efectiva dieron lugar a varias definiciones propuestas ( funciones recursivas generales , máquinas de Turing , cálculo lambda ) que posteriormente demostraron ser equivalentes. El concepto que abarcan estas definiciones se conoce como computabilidad recursiva o efectiva .

La tesis de Church-Turing afirma que ambas nociones coinciden: cualquier función de la teoría de números que sea efectivamente calculable es recursivamente computable .

Véase también

Referencias

↑ Hunter, Geoffrey (1996) [1971]. " 1.7 : La noción de método efectivo en lógica y matemáticas". Metalogic: An Introduction to the Metatheory of Standard First-Order Logic . University of California Press (publicado en 1973). ISBN 9780520023567OCLC 36312727 ( Accesible para usuarios con discapacidades visuales )
↑ Es discutible si un proceso con procesos internos aleatorios (sin incluir la entrada) constituye o no un algoritmo. Rogers opina que: "un cálculo se lleva a cabo de forma discreta y gradual, sin utilizar métodos continuos ni dispositivos analógicos... se realiza de forma determinista, sin recurrir a métodos o dispositivos aleatorios, como los dados" (Rogers 1987:2).
↑ Gandy, Robin (1980). «La tesis de Church y los principios de los mecanismos» . Simposio Kleene . Estudios en lógica y fundamentos de las matemáticas. 101 : 123–148 . doi : 10.1016/S0049-237X(08)71257-6 . ISBN 978-0-444-85345-5Consultado el 19 de abril de 2024 .
↑ Copeland, BJ ; Copeland, Jack; Proudfoot, Diane (junio de 2000). "La tesis de Turing-Church" . AlanTuring.net . Archivo Turing para la Historia de la Computación . Consultado el 23 de marzo de 2013 .
↑ Diccionario de Filosofía de Cambridge, procedimiento efectivo