Effective method

From Wikipedia, the free encyclopedia
  (Redirected from Effective procedure)
Jump to: navigation, search

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 mechanical method or procedure.[2]

Definition[edit]

A method is called effective for a class of problems iff

  • it consists of a finite number of exact, finite instructions
  • when applied to a problem from its class, it always finishes (terminates) after a finite number of steps
  • when applied to a problem from its class, 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 be followed rigorously to succeed; in particular, it requires no ingenuity to do.[3]

Optionally, one may require that when an effective method is applied to a problem from outside the class for which it is effective, it may halt without result or diverge, but must not return a result as if it were the answer to the problem. 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]

References[edit]

  1. ^ Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971
  2. ^ Copeland, B.J.; Copeland, Jack and Proudfoot, Diane (June 2000). "The Turing-Church Thesis". AlanTuring.net. Turing Archive for the History of Computing. Retrieved 23 March 2013. 
  3. ^ 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.