 |
It has been suggested that this article or section be merged into algorithm. (Discuss) |
An effective method (also called an effective procedure) for a class of problems is a method for which each step in the method may be described as a mechanical operation and which, if followed rigorously, and as far as may be necessary, is bound to:
- 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.
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.
An essential feature of an effective method is that it does not require any ingenuity from any person or machine executing it.[1]
See also
References
- ^ 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.
 |
This logic-related article is a stub. You can help Wikipedia by expanding it. |
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
