|
In computability theory the Church-Turing thesis, Church's thesis, Church's conjecture or Turing's thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. The thesis claims that any calculation which is possible, can be performed by an algorithm running on a computer, provided that sufficient time and storage space are available. Computability theory is that part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. ...
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who was responsible for some of the foundations of theoretical computer science. ...
Alan Turing is often considered the father of modern computer science. ...
A hypothesis (= assumption in ancient Greek) is a proposed explanation for a phenomenon. ...
Flowcharts are often used to represent algorithms. ...
It is generally assumed that an algorithm must satisfy the following requirements:
- The algorithm consists of a finite set of simple and precise instructions that are described with a finite number of symbols.
- The algorithm will always produce the result in a finite number of steps.
- The algorithm can in principle be carried out by a human being with only paper and pencil.
- The execution of the algorithm requires no intelligence of the human being except that which is needed to understand and execute the instructions.
An example of such a method is the Euclidean algorithm for determining the greatest common divisor of two natural numbers. The Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. ...
In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers. ...
Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...
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.) For historical reasons and in order to have application to the solution of Diophantine equations, results in number theory have been scrutinised more than in other branches of mathematics to see if their content is effectively computable. ...
Informally the thesis states that our notion of algorithm can be made precise (in the form of computable functions) 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.) In computability theory computable functions or Turing computable functions are the basic objects of study. ...
The thesis may be regarded as a physical law as it cannot be mathematically proven. A physical law or a law of nature is a scientific generalization based on empirical observations. ...
Church-Turing thesis
The thesis, in Turing's own words, can be stated as: - Every 'function which would naturally be regarded as computable' can be computed by a Turing machine.
Due to the vagueness of the concept of a "function which would naturally be regarded as computable", the thesis cannot formally be proven. Disproof would be possible only if humanity found ways of building hypercomputers whose results should "naturally be regarded as computable". In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). ...
In computability theory computable functions or Turing computable functions are the basic objects of study. ...
The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ...
Hypercomputation is the law of methods for the computation of non-computable functions. ...
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. A programming language or computer language is a standardized communication technique for expressing instructions to a computer. ...
Various variations of the thesis exist; for example, the Physical Church-Turing thesis (PCTT) states:
- Every function that can be physically computed can be computed by a Turing machine.
This stronger statement may have been proven false in 2002 when Willem Fouché discovered that a Turing machine cannot effectively approximate any of the values of one-dimensional Brownian motion at rational points in time almost surely (with respect to Wiener measure; see reference below). 2002 is a common year starting on Tuesday of the Gregorian calendar. ...
An example of 1000 simulated steps of Brownian motion in two dimensions. ...
In mathematics, the Wiener process, so named in honor of Norbert Wiener, is a continuous-time Gaussian stochastic process with independent increments used in modelling Brownian motion and some random phenomena observed in finance. ...
Another variation is the Strong Church-Turing thesis (SCTT), which states (cf. Bernstein, Vazirani 1997):
- Any 'reasonable' model of computation can be efficiently simulated on a probabilistic Turing machine.
History The thesis is named after mathematicians Alonzo Church and Alan Turing. In his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" Alan Turing tried to capture the notion of algorithm (then 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 functions 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ödel 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). Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who was responsible for some of the foundations of theoretical computer science. ...
Alan Turing is often considered the father of modern computer science. ...
1936 was a leap year starting on Wednesday (link will take you to calendar). ...
The 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. ...
In 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. ...
The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
Stephen Cole Kleene (January 5, 1909 - January 25, 1994) was an American mathematician whose work at the University of Wisconsin-Madison helped lay the foundations for theoretical computer science. ...
Kurt Gödel Kurt Gödel [kurt gøËdl], (April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher of mathematics. ...
Jacques Herbrand (February 12, 1908 - July 27, 1932) was a French mathematician who was born in Paris, France and died in La Bérarde, Isère, France. ...
Success of the thesis Since that time many other formalisms for describing effective computability have been proposed, including recursive functions, the lambda calculus, register machines, Post systems, combinatory logic, and Markov algorithms. All these systems have been shown to compute essentially the same functions as Turing machines; systems like this are called Turing-complete. Because all these different attempts of formalizing the concept of algorithm have yielded equivalent results, it is now generally assumed that the Church-Turing thesis is correct. However, the thesis is a definition and not a theorem, and hence cannot be proven true. It could, however, be disproven if a method could be exhibited which is universally accepted as being an effective algorithm but which cannot be performed on a Turing machine. In 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. ...
The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
In theoretical computer science a register machine is an abstract machine used to study decision problems, similar to how a Turing machine is used. ...
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post. ...
This article is about a topic in theoretical computer science, and is not to be confused with combinatorial logic, a topic in electronics. ...
A Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. ...
In computability theory a programming language or any other logical system is called Turing-complete if it has a computational power equivalent to a universal Turing machine. ...
A theorem is a proposition that has been or is to be proved on the basis of explicit assumptions. ...
In the early twentieth century, mathematicians often used the informal phrase effectively computable, so it was important to find a good formalization of the concept. Modern mathematicians instead use the well-defined term Turing computable (or computable for short). Since the undefined terminology has faded from use, the question of how to define it is now less important. Computability theory is that part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. ...
The success of the Church–Turing thesis prompted supertheses that extend the thesis, including the conjecture that there is a polynomial transformation from the representation of computable functions in one formalization to their representation in another, and the conjecture that every model of computation can be step-by-step simulated by a Turing machine.
Philosophical implications The Church-Turing thesis has some profound implications for the philosophy of mind. There are also some important open questions which cover the relationship between the Church-Turing thesis and physics, and the possibility of hypercomputation. When applied to physics, the thesis has several possible meanings: Philosophy of mind is the philosophical study of the nature of the mind, mental events, mental functions, mental properties, and consciousness. ...
Hypercomputation refers to methods for the computation of non-computable functions. ...
- The universe is equivalent to a Turing machine (and thus, computing non-recursive functions is physically impossible). This has been termed the strong Church-Turing thesis and is assumed in digital physics.
- The universe is not a Turing machine (ie, the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a hypercomputer. For example, a universe in which physics involves real numbers, as opposed to computable reals, might fall into this category.
- The universe is a hypercomputer, and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all quantum mechanical events are Turing-computable, although it has been proved that any system built out of qubits is (at best) Turing-complete. John Lucas (and famously, Roger Penrose) have suggested that the human mind might be the result of quantum hypercomputation, although there is little scientific evidence for this theory.
There are actually many technical possibilities which fall outside or between these three categories, but these should serve to illustrate the concept. In theoretical physics, digital physics holds the basic premise that the entire history of our universe is computable, that is, the output of a (presumably short) computer program. ...
Hypercomputation refers to methods for the computation of non-computable functions. ...
Please refer to Real vs. ...
In mathematics, theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers, are the subset of the real numbers consisting of the numbers which can be computed by a finite, terminating algorithm. ...
Hypercomputation refers to methods for the computation of non-computable functions. ...
Fig. ...
A quantum bit, or qubit is a unit of quantum information. ...
John Randolph Lucas (born 18 June 1929) is a philosopher. ...
Sir Roger Penrose, is a member of the faculty of Oxford University Sir Roger Penrose OM (born August 8, 1931) is an English scientist and academician. ...
Additional reading - Hofstadter, Douglas R., Gödel, Escher, Bach: an Eternal Golden Braid, Chapter 17.
Douglas Richard Hofstadter (born February 15, 1945) is an American academic. ...
References - Church, A., 1932, "A set of Postulates for the Foundation of Logic", Annals of Mathematics, second series, 33, 346-366.
- Church, A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics, 58, 345-363.
- Church, A., 1936, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
- Church, A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University Press.
- Gödel, K., 1934, "On Undecidable Propositions of Formal Mathematical Systems", lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven.
- Herbrand, J., 1932, "Sur la non-contradiction de l'arithmetique", Journal fur die reine und angewandte Mathematik, 166, 1-8.
- Kleene, S.C., 1935, "A Theory of Positive Integers in Formal Logic", American Journal of Mathematics, 57, 153-173, 219-244.
- Kleene, S.C., 1936, "Lambda-Definability and Recursiveness", Duke Mathematical Journal 2, 340-353.
- Markov, A.A., 1960, "The Theory of Algorithms", American Mathematical Society Translations, series 2, 15, 1-14.
- Turing, A.M., 1936, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp.230-265.
- Pour-El, M.B. & Richards, J.I., 1989, Computability in Analysis and Physics, Springer Verlag.
- Willem Fouché, Arithmetical representations of Brownian motion, J. Symbolic Logic 65 (2000) 421-442
- E. Bernstein, U. Vazirani, Quantum complexity theory, SIAM Journal on Computing 26(5) (1997) 1411?1473
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who was responsible for some of the foundations of theoretical computer science. ...
Jacques Herbrand (February 12, 1908 - July 27, 1932) was a French mathematician who was born in Paris, France and died in La Bérarde, Isère, France. ...
Stephen Cole Kleene (January 5, 1909 - January 25, 1994) was an American mathematician whose work at the University of Wisconsin-Madison helped lay the foundations for theoretical computer science. ...
Andrey Andreyevich Markov (Андрей Андреевич Марков) (June 14, 1856 N.S. - July 20, 1922) was a Russian mathematician. ...
Alan Turing, on the steps of the bus, with members of the Walton Athletic Club, 1946. ...
The Springer-Verlag (pronounced SHPRING er FAIR lahk) was a worldwide publishing company base in Germany. ...
External links - Detailed info on the Church-Turing Hypothesis (Stanford Encyclopedia of Philosophy)
See also |
Feeds |
Contact