In
metalogic,
mathematical logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
, and
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
, an effective method or effective procedure is a finite-time, deterministic procedure for
solving a problem from a specific class. An effective method is sometimes also called a mechanical method or procedure.
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
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
. 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 machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
s,
λ-calculus
In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computation based on function abstraction and application using variable binding and substitution. Untyped lambda calculus, the topic ...
) that later were shown to be equivalent. The notion captured by these definitions is known as
recursive or effective computability.
The
Church–Turing thesis
In Computability theory (computation), computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's 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
A mathematical proof is a deductive reasoning, deductive Argument-deduction-proof distinctions, argument for a Proposition, mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use othe ...
.
See also
*
Decidability (logic)
*
Decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
*
Effective results in number theory
For historical reasons and in order to have application to the solution of Diophantine equations, results in number theory have been scrutinised more than in other branches of mathematics to see if their content is effectively computable. Where it ...
*
Function problem
*
Model of computation
*
Recursive set
*
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an ...
References
* S. C. Kleene (1967), ''Mathematical logic''. Reprinted, Dover, 2002, , pp. 233 ff., esp. p. 231.
{{Metalogic
Metalogic
Computability theory
Theory of computation