# Effective method

In logic, mathematics and computer science, especially metalogic and computability theory, an **effective method**^{[1]} or **effective procedure** is a procedure for solving a problem from a specific class. An effective method is sometimes also called a **mechanical** method or procedure.^{[2]}

## Definition[edit]

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.

- It always finishes (
- 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.
^{[3]}

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[edit]

An effective method for calculating the values of a function is an algorithm. Functions for which an effective method exists are sometimes called **effectively calculable**.

## Computable functions[edit]

Several independent efforts to give a formal characterization of effective calculability led to a variety of proposed definitions (general recursion, Turing machines, λ-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 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.

## See also[edit]

- Decidability (logic)
- Decision problem
- Function problem
- Effective results in number theory
- Recursive set
- Undecidable problem

## References[edit]

**^**Hunter, Geoffrey,*Metalogic: An Introduction to the Metatheory of Standard First-Order Logic*, University of California Press, 1971**^**Copeland, B.J.; Copeland, Jack; Proudfoot, Diane (June 2000). "The Turing-Church Thesis".*AlanTuring.net*. Turing Archive for the History of Computing. Retrieved 23 March 2013.**^**The Cambridge Dictionary of Philosophy,*effective procedure*

- S. C. Kleene (1967),
*Mathematical logic*. Reprinted, Dover, 2002, ISBN 0-486-42533-9, pp. 233 ff., esp. p. 231.

This logic-related article is a stub. You can help Wikipedia by expanding it. |