Mètode efectiu
En lògica, matemàtiques i informàtica, especialment metalògica i teoria de la computabilitat, un mètode efectiu[1] o procediment efectiu és un procediment per resoldre un problema per qualsevol mitjà intuïtivament "efectiu" d'una classe específica.[2] Un mètode efectiu de vegades també s'anomena mètode o procediment mecànic.[3]
Definició
[modifica]Cal distingir entre efectivitat i eficàcia.
La definició d'un mètode efectiu implica més que el mètode en si. Perquè un mètode es pugui dir efectiu, s'ha de considerar respecte a una classe de problemes. Per això, un mètode pot ser efectiu respecte a una classe de problemes i no ser efectiu respecte a una classe diferent.
Un mètode s'anomena formalment efectiu per a una classe de problemes quan compleix aquests criteris:
- Consisteix en un nombre finit d'instruccions exactes i finites.
- Quan s'aplica a un problema de la seva classe:
- Sempre s'acaba després d'un nombre finit de passos.
- Sempre produeix una resposta correcta.
- Per principi, pot fer-ho un humà sense cap tipus d'ajuda excepte material d'escriptura.
- Només cal seguir amb rigor les seves instruccions per tenir èxit. En altres paraules, no requereix enginy per tenir èxit.[4]
Opcionalment, també es pot requerir que el mètode no retorni mai un resultat com si fos una resposta quan el mètode s'aplica a un problema des de fora de la seva classe. Afegir aquest requisit redueix el conjunt de classes per a les quals hi ha un mètode efectiu.
Algorismes
[modifica]Un mètode efectiu per calcular els valors d'una funció és un algorisme. Les funcions per a les quals existeix un mètode efectiu s'anomenen de vegades efectivament calculables.
Funcions computables
[modifica]Diversos esforços independents per donar una caracterització formal de la calculabilitat efectiva van conduir a una varietat de definicions proposades (funcions recursives generals, màquines de Turing, càlcul λ) que més tard es van demostrar que eren equivalents. La noció encapsulada en aquestes definicions es coneix com a computabilitat recursiva o efectiva.
La tesi Church-Turing afirma que les dues nocions coincideixen: qualsevol funció teòrica dels nombres que sigui efectivament calculable és computable recursivament. Com que aquesta no és una afirmació matemàtica, no es pot demostrar amb una demostració matemàtica.
Vegeu també
[modifica]Referències
[modifica]- ↑ Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971
- ↑ Gandy, Robin The Kleene Symposium, 1980 [Consulta: 19 abril 2024].
- ↑ Copeland, Jack. «The Turing-Church Thesis» (en anglès). Turing Archive for the History of Computing, 01-06-2000. [Consulta: 23 març 2013].
- ↑ The Cambridge Dictionary of Philosophy, effective procedure
Bibliografia complementària
[modifica]- SC Kleene (1967), Lògica matemàtica . Reimprès, Dover, 2002,ISBN 0-486-42533-9, pàgs. 233 ss. , esp. pàg. 231.