Effective method
{{Short description|Problem-solving procedures with certain characteristics}}
{{more references|date=May 2025}}
In metalogic, mathematical logic, and computability theory, an effective method{{Hunter 1996|section=1.7: The notion of effective method in logic and mathematics}} or effective procedure is a finite-time, deterministic procedure for solving a problem from a specific class.Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without the use of continuous methods or analog devices ... carried forward deterministically, without resort to random methods or devices, e.g., dice" (Rogers 1987:2).{{cite journal |last1=Gandy |first1=Robin |title=Church's Thesis and the Principles for Mechanisms |journal=The Kleene Symposium |series=Studies in Logic and the Foundations of Mathematics |date=1980 |volume=101 |pages=123–148 |doi=10.1016/S0049-237X(08)71257-6 |isbn=978-0-444-85345-5 | url=https://doi.org/10.1016/S0049-237X(08)71257-6 |access-date=19 April 2024|url-access=subscription }} An effective method is sometimes also called a mechanical method or procedure.{{cite web|last=Copeland|first=B.J.|title=The Turing-Church Thesis|url=http://www.alanturing.net/turing_archive/pages/reference%20articles/The%20Turing-Church%20Thesis.html|work=AlanTuring.net|publisher=Turing Archive for the History of Computing|date=June 2000|access-date=23 March 2013|author-link=Jack Copeland |author2=Copeland, Jack |author3=Proudfoot, Diane}}
Definition
Formally, a method is called effective to a specific class of problems when it satisfies the following criteria:
- It consists of a finite number of exact, finite instructions.
- When it is applied to a problem from its class:
- It always finishes (terminates) after a finite number of steps.
- It always produces a correct answer.
- In principle, it can be done by a human without any aids except writing materials.
- Its instructions need only to be followed rigorously to succeed. In other words, it requires no ingenuity to succeed.The Cambridge Dictionary of Philosophy, effective procedure
Optionally, it may also be required that the method never returns a result as if it were an answer when the method is applied to a problem from outside its class. Adding this requirement reduces the set of classes for which there is an effective method.
Algorithms
An effective method for calculating the values of a function is an algorithm. Functions for which an effective method exists are sometimes called effectively calculable.
Computable functions
Several independent efforts to give a formal characterization of effective calculability led to a variety of proposed definitions (general recursive functions, Turing machines, λ-calculus) that later were shown to be equivalent. The notion captured by these definitions is known as recursive or effective computability.
The Church–Turing thesis states that the two notions coincide: any number-theoretic function that is effectively calculable is recursively computable. As this is not a mathematical statement, it cannot be proven by a mathematical proof.{{cn|date=February 2024}}
See also
References
{{reflist}}
- S. C. Kleene (1967), Mathematical logic. Reprinted, Dover, 2002, {{ISBN|0-486-42533-9}}, pp. 233 ff., esp. p. 231.
{{Metalogic}}