In
metalogic
Metalogic is the metatheory of logic. Whereas ''logic'' studies how logical systems can be used to construct valid and sound arguments, metalogic studies the properties of logical systems. Logic concerns the truths that may be derived using a lo ...
,
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
Finite may refer to:
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marked for person and/or tense or aspect
* "Finite", a song by Sara Gr ...
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 function
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as i ...
s,
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)
In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Zeroth-order logic (propositional logic) is decidable, whereas first-order and higher-order logic are not. Logical systems ...
*
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
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the ou ...
*
Model of computation
In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how ...
*
Recursive set
In computability theory, a set of natural numbers is computable (or decidable or recursive) if there is an algorithm that computes the membership of every natural number in a finite number of steps. A set is noncomputable (or undecidable) if it is ...
*
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