In computability theory

Computability theory

Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...

, an effective method (also called an effective procedure) is a procedure

Procedure (term)

A procedure is a sequence of actions or operations which have to be executed in the same manner in order to always obtain the same result under the same circumstances ....

 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:

• 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

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

; 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

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

, Turing machine

Turing machine

A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

s, λ-calculus) that later were shown to be equivalent; the notion captured by these definitions is known as (recursive) computability

Computable function

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...

.

Church's thesis states that the two notions coincide: any number-theoretic function that is effectively calculable is recursively computable

Computable function

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...

. Church's thesis is not a mathematical statement and cannot be proved by a mathematical proof

Mathematical proof

In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...

.

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

Ingenuity

Ingenuity refers to the process of applying ideas to solve problems or meet challenges. The process of figuring out how to cross a mountain stream using a fallen log, build an airplane from a sheet of paper, or start a new company in a foreign culture all involve the exercising of ingenuity...

 from any person or machine executing it.

See also

• Decidability (logic)
  Decidability (logic)
  In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
  
  
• Decision problem
  Decision problem
  In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
  
  
• Function problem
  Function problem
  In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
  
  
• Effective results in number theory
  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...
  
  
• Recursive set
  Recursive set
  In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....
  
  
• Undecidable problem
  Undecidable problem
  In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....