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 premis ...
,
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 (includin ...
, especially
metalogic 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 ...
, 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
Traditionally, a finite verb (from la, fīnītus, past partici ...
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 algor ...
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 Inference, inferential Argument-deduction-proof distinctions, argument for a Proposition, mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previo ...
.
See also
*
Decidability (logic)
*
Decision problem
*
Function problem
*
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 ...
References
* S. C. Kleene (1967), ''Mathematical logic''. Reprinted, Dover, 2002, , pp. 233 ff., esp. p. 231.
Metalogic
Computability theory
Theory of computation
{{logic-stub