In
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premise ...
,
mathematics and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, especially
metalogic
Metalogic is the study of 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.Harry GenslerIntroduction to Logic Routledge, ...
and
computability theory, an effective method
[ Hunter, Geoffrey, ''Metalogic: An Introduction to the Metatheory of Standard First-Order Logic'', University of California Press, 1971] or effective procedure is a procedure for solving a problem by any intuitively 'effective' means from a specific class. An effective method is sometimes also called a mechanical method or procedure.
Definition
The definition of an effective method involves more than the method itself. In order for a method to be called effective, it must be considered with respect to a class of problems. Because of this, one method may be effective with respect to one class of problems and ''not'' be effective with respect to a different class.
A method is formally called effective for a class of problems when it satisfies these criteria:
* It consists of a
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* 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 marke ...
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 rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
. 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
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation tha ...
) 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
In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function ''f''(''n'') whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their d ...
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 an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proo ...
.
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 ar ...
*
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 of the input values. An example of a decision problem is deciding by means of an algorithm wheth ...
*
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 o ...
*
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 ...
*
Recursive set
In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly ...
*
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
Computability theory
Theory of computation
{{logic-stub