Effective method
 | This article needs additional citations for verification. (May 2025) |
In metalogic, mathematical logic, and computability theory, an effective method[1] or effective procedure is a finite-time, deterministic procedure for solving a problem from a specific class.[2][3] An effective method is sometimes also called a mechanical method or procedure.[4]
Definition
[edit | edit source]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.[5]
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
[edit | edit source]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
[edit | edit source]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.[citation needed]
See also
[edit | edit source]- Decidability (logic)
- Decision problem
- Effective results in number theory
- Function problem
- Model of computation
- Recursive set
- Undecidable problem
References
[edit | edit source]- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value). (accessible to patrons with print disabilities)
- ^ 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).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ The Cambridge Dictionary of Philosophy, effective procedure
- S. C. Kleene (1967), Mathematical logic. Reprinted, Dover, 2002, Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value)., pp. 233 ff., esp. p. 231.