📑 Table of Contents▼

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] Functions for which an effective method exists are sometimes called effectively calculable.

Definition

edit

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

edit

An effective method for calculating the values of a function is called "an algorithm".

Computable functions

edit

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]

See also

edit

References

edit
  1. ^ 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)
  2. ^ 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).
  3. ^ 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.
  4. ^ 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.
  5. ^ The Cambridge Dictionary of Philosophy, effective procedure

📚 Artikel Terkait di Wikipedia

Church–Turing thesis

computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods

Computable function

computable functions, mathematicians often used the informal term effectively calculable. This term has since come to be identified with the computable functions

History of the Church–Turing thesis

development of the study of the nature of functions whose values are effectively calculable; or, in more modern terms, functions whose values are algorithmically

Halting problem

Number Theory", which proposes that the intuitive notion of an effectively calculable function can be formalized by the general recursive functions or

Turing machine

"a computable function": It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process'. We

Church's thesis (constructive mathematics)

functions. The similarly named Church–Turing thesis states that every effectively calculable function is a computable function, thus collapsing the former notion

Entscheidungsproblem

Entscheidungsproblem is impossible, assuming that the intuitive notion of "effectively calculable" is captured by the functions computable by a Turing machine (or

Algorithm characterizations

independently questioned "effectively calculability" and "λ-definability": "We now define the notion . . . of an effectively calculable function of positive