Effective method

In metalogic, mathematical logic, and computability theory, an effective method^[1] or effective procedure is a finite-time, deterministic procedure for solving a problem from a specific class.^[2]^[3] An effective method is sometimes also called a mechanical method or procedure.^[4]

Definition

Formally, a method is called effective to a specific class of problems when it satisfies the following 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.^[5]

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. 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 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.^{[citation needed]}

References

^ Hunter, Geoffrey (1996) [1971]. "1.7: The notion of effective method in logic and mathematics". Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press (published 1973). ISBN 9780520023567. OCLC 36312727. (accessible to patrons with print disabilities)
^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without the use of continuous methods or analog devices ... carried forward deterministically, without resort to random methods or devices, e.g., dice" (Rogers 1987:2).
^ Gandy, Robin (1980). "Church's Thesis and the Principles for Mechanisms". The Kleene Symposium. Studies in Logic and the Foundations of Mathematics. 101: 123–148. doi:10.1016/S0049-237X(08)71257-6. ISBN 978-0-444-85345-5. Retrieved 19 April 2024.
^ 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