Effective Method

From GM-RKB
(Redirected from effective procedure)
Jump to navigation Jump to search

An Effective Method is a procedure that finishes after a finite number of logic steps and produces a correct answer.



References

2017a

  • (Wikipedia, 2017A) ⇒ https://en.wikipedia.org/wiki/Effective_method Retrieved:2017-7-1.
    • 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

      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.
      • 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

2014

  • (Morton & Hughes) ⇒ Morton L. Schagrin, G.E. Hughes (2014). “Formal Logic". Published in Encyclopedia Britannica. http://www.britannica.com/topic/formal-logic
    • QUOTE: In these rules α and β are variables representing arbitrary formulas of PC. They are not themselves symbols of PC but are used in discussing PC. Such variables are known as metalogical variables. It should be noted that the rules, though designed to ensure unambiguous sense for the wffs of PC under the intended interpretation, are themselves stated without any reference to interpretation and in such a way that there is an effective procedure for determining, again without any reference to interpretation, whether any arbitrary string of symbols is a wff or not. (An effective procedure is one that is “mechanical” in nature and can always be relied on to give a definite result in a finite number of steps. The notion of effectiveness plays an important role in formal logic.)

2009

  • (Evans, 2009) ⇒ Evans, D. (2009). Introduction to Computing Explorations in Language, Logic, and Machines. Section: 1.1 Processes, procedures, and computers. Online Open-acess Textbook Link
    • QUOTE: A procedure is a description of a process. A simple process can be described just by listing the steps. The list of steps is the procedure; the act of following them is the process. A procedure that can be followed without any thought is called a mechanical procedure. An algorithm is a mechanical procedure that is guaranteed to eventually finish.

      (...)

      To program computers, we need tools that allow us to describe processes precisely and succinctly. Since the procedures are carried out by a machine, every step needs to be described; we cannot rely on the operator having “common sense” (for example, to know how to fill the coffeemaker with water without explaining that water comes from a faucet, and how to turn the faucet on). Instead, we need mechanical procedures that can be followed without any thinking.

      A computer is a machine that can:

      • Accept input. Input could be entered by a human typing at a keyboard, received over a network, or provided automatically by sensors attached to the computer.
      • Execute a mechanical procedure, that is, a procedure where each step can be executed without any thought.
      • Produce output. Output could be data displayed to a human, but it could also be anything that effects the world outside the computer such as electrical signals that control how a device operates.

  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; 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