- published: 17 Feb 2012
- views: 171508
In computability theory, an effective method (also called an effective procedure) is a procedure that reduces the solution of some class of problems to a series of rote steps which, if followed to the letter, and as far as may be necessary, is bound to:
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.
Church's thesis states that the two notions coincide: any number-theoretic function that is effectively calculable is recursively computable. Church's thesis is not a mathematical statement and cannot be proved by a mathematical proof.
A further elucidation of the term "effective method" may include the requirement that, when given a problem from outside the class for which the method is effective, the method may halt or loop forever without halting, but must not return a result as if it were the answer to the problem.