 |
Business | Industries | Finance | Tax |
| Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
|
|||||
| First Prev [ 1 2 3 ] Next Last |
It is generally assumed that an algorithm must satisfy the following requirements:
An example of such a method is the Euclidean algorithm for determining the greatest common divisor of two natural numbers.
The notion of algorithm is intuitively clear but is not formally defined since it is not exactly clear what a "simple and precise instruction" is, and what exactly the "required intelligence to execute these instructions" is. (See for example effective results in number theory for cases well beyond the Euclidean algorithm.)
Informally the thesis states that our notion of algorithm can be made precise (in the form of computable function) and computers can run those algorithms. Furthermore any computer can theoretically run any algorithm, that is the theoretic computational power of each computer is the same and it is not possible to build a calculation device which is more powerful than a computer. (Note that this formulation has implicit in it the idea that memory/storage is separate from device; any actual computer has finite memory, but the formulation always assumes that memory can be added at will.)
The thesis may be regarded as a physical law as it cannot be mathematically proven.
The thesis can be stated as
An alternative formulation is
Any computer program can be translated into a Turing machine, and any Turing machine can be translated into any general-purpose programming language, so the thesis is equivalent to saying that any general-purpose programming language is sufficient to express any algorithm.
The thesis is named after mathematicians Alonzo Church and Alan Turing. In his 1936 paper "On Computable Numbers, with an Application to the EntscheidungsproblemThe Entscheidungsproblem ( German: decision problem) is the challenge in symbolic logic to find a general algorithm which decides for given first-order statements whether they are universally valid or not. Alonzo Church and independently Alan Turing showe" Alan Turing tried to capture the notion of algorithm, (than called effective computability), with the introduction of Turing machines. In that paper he showed that the 'Entscheidungsproblem' could not be solved. A few months earlier Alonzo Church had proven a similar result in "A Note on the Entscheidungsproblem" but he used the notions of recursive functionIn mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are "computable" in some intuitive sense. In fact, in computability theory it is shown that the recursive functionss and Lambda-definable functions to formally describe effective computability. Lambda-definable functions were introduced by Alonzo Church and Stephen Kleene (Church 1932, 1936a, 1941, Kleene 1935) and recursive functions by Kurt GödelKurt Godel [ kurˈt godl ], ( April 28, 1906 January 14, 1978) was a logician, mathematician, and philosopher of mathematics, whose biography lists quite a few nations, although he is usually associated with Austria. He was born in Brunn in Austria- and Jacques Herbrand (Gödel 1934, Herbrand 1932). These two formalisms describe the same set of functions, as was shown in the case of functions of positive integers by Church and Kleene (Church 1936a, Kleene 1936). When hearing of Church's proposal, Turing was quickly able to show that his Turing machines in fact describe the same set of functions (Turing 1936, 263ff).
| Politics | Business | Finance |
 |
 |
 |
|