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 by any intuitively 'effective' means from a specific class.^[2] An effective method is sometimes also called a mechanical method or procedure.^[3]

YouTube Encyclopedic

1/3
Views:
239 390
22 844
63 305

Transcription

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.^[4]

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, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971
^ Gandy, Robin (1980). "Church's Thesis and the Principles for Mechanisms". The Kleene Symposium. 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

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

v t e Metalogic and metamathematics
Cantor's theorem Entscheidungsproblem Church–Turing thesis Consistency Effective method Foundations of mathematics of geometry Gödel's completeness theorem Gödel's incompleteness theorems Soundness Completeness Decidability Interpretation Löwenheim–Skolem theorem Metatheorem Satisfiability Independence Type–token distinction Use–mention distinction

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

This page was last edited on 19 April 2024, at 20:06

From Wikipedia, the free encyclopedia