In logic and mathematics – especially metalogic and computability theory – an effective method (also called an effective procedure) is a procedure which takes some class of problems and reduces the solution to a set of steps which:
- always give some answer rather than ever give no answer;
- always give the right answer and never give a wrong answer;
- always be completed in a finite number of steps, rather than in an infinite number;
- work for all instances of problems of the class.
An effective method for calculating the values of a function is an algorithm; functions with an effective method are sometimes called effectively calculable.
Several independent efforts to give a formal characterization of effective calculability led to a variety of proposed definitions (general recursion, Turing machines, λ-calculus) that later were shown to be equivalent; the notion captured by these definitions is known as (recursive) computability.
The Church–Turing thesis states that the two notions coincide: any number-theoretic function that is effectively calculable is recursively computable. This is not a mathematical statement and cannot be proven by a mathematical proof.
Optionally, one may require that when an effective method is applied to a problem from outside the class for which it is effective, it may halt without result or continue forever without halting, but must not return a result as if it were the answer to the problem (c.f. divergence).
 See also
- Decidability (logic)
- Decision problem
- Function problem
- Effective results in number theory
- Recursive set
- Undecidable problem
- Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971
- The Cambridge Dictionary of Philosophy, effective procedure
- S. C. Kleene (1967), Mathematical logic. Reprinted, Dover, 2002, ISBN 0-486-42533-9, pp. 233 ff., esp. p. 231.
- Copeland, B.J. (2000), "The Turing-Church Thesis", AlanTuring.net (Turing Archive for the History of Computing), retrieved March 23, 2013
|This logic-related article is a stub. You can help Wikipedia by expanding it.|