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 prem ...
,
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 Applied science, practical discipli ...
, 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
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 sinc ...
, 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 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 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 alg ...
s,
λ-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
In 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) is a thesis about the nature of co ...
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 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 pr ...
.
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 of the input values. An example of a decision problem is deciding by means of an algorithm whe ...
*
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 ...
*
Effective results in number theory
*
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
Computability theory
Theory of computation
{{logic-stub