Church–Turing thesis
Encyclopedia
In computability theory, the Church–Turing thesis (also known as the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a combined hypothesis
("thesis") about the nature of functions whose values are effectively calculable; in more modern terms, algorithmically
computable. In simple terms, it states that "everything algorithmically computable is computable by a Turing machine
."
Several attempts were made in the first half of the 20th Century to formalize the notion of computability:
All three computational processes (recursion, the λ-calculus, and the Turing machine) were shown to be equivalent—all three approaches define the same class of functions. This has led mathematicians and computer scientists to believe that the concept of computability is accurately characterized by these three equivalent processes. Informally the Church–Turing thesis states that if some method (algorithm
) exists to carry out a calculation, then the same calculation can also be carried out by a Turing machine (as well as by a recursively
-definable function, and by a λ-function
).
The Church–Turing thesis is a statement that characterizes the nature of computation and cannot be formally proven. Even though the three processes mentioned above proved to be equivalent, the fundamental premise behind the thesis—the notion of what it means for a function to be "effectively calculable" (computable)—is "a somewhat vague intuitive one". Thus, the "thesis" remains an hypothesis.
Despite the fact that it cannot be formally proven, the Church–Turing thesis now has near-universal acceptance.
" is here used in the rather special sense of a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps". Thus the adverb-adjective "effective" is used in a sense of "1a: producing a decided, decisive, or desired effect", and "capable of producing a result".
In the following, the words "effectively calculable" will mean "produced by any intuitively 'effective' means whatsoever" and "effectively computable" will mean "produced by a Turing-machine or equivalent mechanical device". Turing's 1939 "definitions" are virtually the same:
The thesis can be stated as follows:
Turing stated it this way:
Entscheidungsproblem
, which asked if there was a mechanical procedure for separating mathematical truths from mathematical falsehoods. This quest required that the notion of “algorithm” or “effective calculability” be pinned down, at least well enough for the quest to begin. But from the very outset Alonzo Church
's attempts began with a debate that continues to this day. Was the notion of “effective calculability” to be (i) an "axiom or axioms" in an axiomatic system, or (ii) merely a definition that “identified” two or more propositions, or (iii) an empirical hypothesis to be verified by observation of natural events, or (iv) or just a proposal for the sake of argument (i.e. a "thesis").
introduced the notion of λ-definable functions
, and they were able to prove that several large classes of functions frequently encountered in number theory were λ-definable. The debate began when Church proposed to Kurt Gödel
that one should define the "effectively computable" functions as the λ-definable functions. Gödel, however, was not convinced and called the proposal "thoroughly unsatisfactory". Rather in correspondence with Church (ca 1934–5), Gödel proposed axiomatizing the notion of "effective calculability"; indeed, in a 1935 letter to Kleene, Church reported that:
But Gödel offered no further guidance. Eventually, he would suggest his (primitive) recursion, modified by Herbrand's suggestion, that he (Gödel) had detailed in his 1934 lectures in Princeton NJ (Kleene and another student J. B. Rosser transcribed the notes.). But "he did not think that the two ideas could be satisfactorily identified "except heuristically".
Next, it was necessary to identify and prove the equivalence of two notions of effective calculability. Equipped with the λ-calculus and "general" recursion, Stephen Kleene
with help of Church and J. B. Rosser produced proofs (1933, 1935) to show that the two calculi are equivalent. Church subsequently modified his methods to include use of Herbrand–Gödel recursion and then proved (1936) that the Entscheidungsproblem
is unsolvable: There is no generalized "effective calculation" (method, algorithm) that can determine whether or not a formula in either the recursive- or λ-calculus is "valid" (more precisely: no method to show that a well formed formula has a "normal form").
Many years later in a letter to Davis (ca 1965), Gödel would confess that "he was, at the time of these [1934] lectures, not at all convinced that his concept of recursion comprised all possible recursions". By 1963–4 Gödel would disavow Herbrand–Gödel recursion and the λ-calculus in favor of the Turing machine as the definition of “algorithm” or “mechanical procedure” or “formal system”.
An hypothesis leading to a natural law?: In late 1936 Alan Turing
’s paper (also proving that the Entscheidungsproblem
is unsolvable) had not yet appeared. On the other hand, Emil Post's 1936 paper had appeared and was certified independent of Turing's work. Post strongly disagreed with Church’s “identification” of effective computability with the λ-calculus and recursion, stating:
Rather, he regarded the notion of “effective calculability” as merely a "working hypothesis" that might lead by inductive reasoning
to a "natural law
" rather than by “a definition or an axiom”. This idea was "sharply" criticized by Church.
Thus Post in his 1936 was also discounting Kurt Gödel
's suggestion to Church in 1934–5 that the thesis might be expressed as an axiom or set of axioms.
Turing adds another definition, Rosser equates all three: Within just a short time, Turing's 1936–37 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" appeared. In it he asserted another notion of "effective computability" with the introduction of his a-machines (now known as the Turing machine
abstract computational model). And in a proof-sketch added as an "Appendix" to his 1936–37 paper, Turing showed that the classes of functions defined by λ-calculus and Turing machines coincided.
In a few years (1939) Turing would propose, like Church and Kleene before him, that his formal definition of mechanical computing agent was the correct one. Thus, by 1939, both Church (1934) and Turing (1939), neither having knowledge of the other’s efforts, had individually proposed that their "formal systems" should be definitions of "effective calculability"; neither framed their assertions as theses.
Rosser (1939) formally identified the three notions-as-definitions:
Kleene proposes Church's Thesis: This left the overt expression of a "thesis” to Kleene. In his 1943 paper Recursive Predicates and Quantifiers Kleene proposed his "THESIS I":"Since a precise mathematical definition of the term effectively calculable (effectively decidable) has been wanting, we can take this thesis ... as a definition of it..."
Kleene goes on to note that:
Kleene's Church–Turing Thesis: A few years later (1952) Kleene would overtly name, defend, and express the two "theses" and then "identify" them (show equivalence) by use of his Theorem XXX:
(Turing's student and friend) in 1980 to analyze machine computation (as opposed to human-computation acted out by a Turing machine). Gandy's curiosity about, and analysis of, "cellular automata", "Conway's game of life
", "parallelism" and "crystalline automata" led him to propose four "principles (or constraints) ... which it is argued, any machine must satisfy." His most-important fourth, "the principle of causality" is based on the "finite velocity of propagation of effects and signals; contemporary physics rejects the possibility of instantaneous action at a distance." From these principles and some additional constraints—(1a) a lower bound on the linear dimensions of any of the parts, (1b) an upper bound on speed of propagation (the velocity of light), (2) discrete progress of the machine, and (3) deterministic behavior—he produces a theorem that "What can be calculated by a device satisfying principles I–IV is computable. ".
In the late 1990s Wilfried Sieg analyzed Turing's and Gandy's notions of "effective calculability" with the intent of "sharpening the informal notion, formulating its general features axiomatically, and investigating the axiomatic framework". In his 1997 and 2002 Sieg presents a series of constraints on the behavior of a computor—"a human computing agent who proceeds mechanically"; these constraints reduce to:"(B.2) (Boundedness) There is a fixed bound on the number of internal states a computor can be in.
"(L.1) (Locality) A computor can change only elements of an observed symbolic configuration.
"(L.2) (Locality) A computor can shift attention from one symbolic configuration to another one, but the new observed configurations must be within a bounded distance of the immediately previously observed configuration.
"(D) (Determinacy) The immediately recognizable (sub-)configuration determines uniquely the next computation step (and id [instantaneous description] )"; stated another way: "A computor's internal state together with the observed configuration fixes uniquely the next computation step and the next internal state."
The matter remains in active discussion within the academic community.
, and the Turing machine
) have been proposed for describing effective calculability/computability . Stephen Kleene
(1952) adds to the list the functions "reckonable in the system S1" of Kurt Gödel
1936, and Emil Post's (1943, 1946) "canonical [also called normal] systems". In the 1950s Hao Wang and Martin Davis
greatly simplified the one-tape Turing-machine model (see Post–Turing machine). Marvin Minsky
expanded the model to two or more tapes and greatly simplified the tapes into "up-down counters", which Melzak and Lambek
further evolved into what is now known as the counter machine
model. In the late 1960s and early 1970s researchers expanded the counter machine model into the register machine
, a close cousin to the modern notion of the computer
. Other models include combinatory logic
and Markov algorithm
s. Gurevich adds the pointer machine
model of Kolmogorov and Uspensky (1953, 1958): "...they just wanted to ... convince themselves that there is no way to extend the notion of computable function."
All these contributions involve proofs that the models are computationally equivalent to the Turing machine; such models are said to be Turing complete. Because all these different attempts at formalizing the concept of "effective calculability/computability" have yielded equivalent results, it is now generally assumed that the Church–Turing thesis is correct. In fact, Gödel (1936) proposed something stronger than this; he observed that there was something "absolute" about the concept of "reckonable in S1":
Dirk van Dalen (in Gabbay 2001:284) gives the following example for the sake of illustrating this informal use of the Church–Turing thesis:
(Emphasis added). In order to make the above example completely rigorous, one would have to carefully construct a Turing Machine, or λ-function, or carefully invoke recursion axioms, or at best, cleverly invoke various theorems of computability theory. But because the computability theorist believes that Turing computability correctly captures what can be computed effectively, and because an effective procedure is spelled out in English for deciding the set B, the computability theorist accepts this as proof that the set is indeed recursive.
As a rule of thumb, the Church–Turing thesis should only be invoked to simplify proofs in cases where the writer would be capable of, and expects the readers also to be capable of, easily (but not necessarily without tedium) producing a rigorous proof if one were demanded
The Church–Turing thesis says nothing about the efficiency with which one model of computation can simulate another. It has been proved for instance that a (multi-tape) universal Turing machine
only suffers a logarithmic slowdown factor in simulating any Turing machine. No such result has been proved in general for an arbitrary but reasonable model of computation. A variation of the Church–Turing thesis that addresses this issue is the Feasibility Thesis or (Classical) Complexity-Theoretic Church–Turing Thesis (SCTT), which is not due to Church or Turing, but rather was realized gradually in the development of complexity theory
. It states:
The word 'efficiently' here means up to polynomial-time reductions. This thesis was originally called Computational Complexity-Theoretic Church–Turing Thesis by Ethan Bernstein and Umesh Vazirani
(1997). The Complexity-Theoretic Church–Turing Thesis, then, posits that all 'reasonable' models of computation yield the same class of problems that can be computed in polynomial time. Assuming the conjecture that probabilistic polynomial time (BPP) equals deterministic polynomial time (P
), the word 'probabilistic' is optional in the Complexity-Theoretic Church–Turing Thesis. A similar thesis, called the Invariant Thesis, was introduced by Cees F. Slot and Peter van Emde Boas. It states: "Reasonable" machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space. The thesis originally appeared in a paper at STOC'84, which was the first paper to show that polynomial-time overhead and constant-space overhead could be simultaneously achieved for a simulation of a Random Access Machine
on a Turing machine.
If production-scale quantum computers can be built, they could invalidate the Complexity-Theoretic Church–Turing Thesis, since it is also conjectured that quantum polynomial time (BQP
) is larger than BPP. In other words, there are efficient quantum algorithms that perform tasks that are not known to have efficient probabilistic algorithms; for example, factoring integers. They would not however invalidate the original Church–Turing thesis, since a quantum computer can always be simulated by a Turing machine, but they would invalidate the classical Complexity-Theoretic Church–Turing thesis for efficiency reasons. Consequently, the Quantum Complexity-Theoretic Church–Turing thesis states:
Eugene Eberbach and Peter Wegner claim that the Church-Turing thesis is sometimes interpreted too broadly,
stating "the broader assertion that algorithms precisely capture
what can be computed is invalid". They claim that forms of computation not captured by the thesis are relevant today,
terms which the call super-Turing computation
.
; however many of the philosophical interpretations of the Thesis involve basic misunderstandings of the thesis statement. B. Jack Copeland
states that it's an open empirical question whether there are actual deterministic physical processes that, in the long run, elude simulation by a Turing machine; furthermore, he states that it is an open empirical question whether any such processes are involved in the working of the human brain. 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:
There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.
with n states can print before halting, when run with no input. Finding an upper bound on the busy beaver function is equivalent to solving the halting problem
, a problem known to be unsolvable by Turing machines. Since the busy beaver function cannot be computed by Turing machines, the Church–Turing thesis asserts that this function cannot be effectively computed by any method. For more information see the article busy beaver
.
Several computational models allow for the computation of (Church-Turing) non-computable functions. These are known as
hypercomputers
.
Mark Burgin
argues that super-recursive algorithm
s such as inductive Turing machines disprove the Church–Turing thesis. His argument relies on a definition of algorithm broader than the ordinary one, so that non-computable functions obtained from some inductive Turing machines are called computable. This interpretation of the Church–Turing thesis differs from the interpretation commonly accepted in computability theory, discussed above. The argument that super-recursive algorithms are indeed algorithms in the sense of the Church–Turing thesis has not found broad acceptance within the computability research community.
Hypothesis
A hypothesis is a proposed explanation for a phenomenon. The term derives from the Greek, ὑποτιθέναι – hypotithenai meaning "to put under" or "to suppose". For a hypothesis to be put forward as a scientific hypothesis, the scientific method requires that one can test it...
("thesis") about the nature of functions whose values are effectively calculable; in more modern terms, algorithmically
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
computable. In simple terms, it states that "everything algorithmically computable is computable by a Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
."
Several attempts were made in the first half of the 20th Century to formalize the notion of computability:
- British mathematician Alan TuringAlan TuringAlan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
created a theoretical model for a machine, now called a universal Turing machineUniversal Turing machineIn computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
, that could carry out calculations from inputs, - Alonzo ChurchAlonzo ChurchAlonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem.-Life:Alonzo Church...
, along with mathematician Stephen KleeneStephen Cole KleeneStephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
and logician J.B. Rosser created a formal definition of a class of functions whose values could be calculated by recursionRecursionRecursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
.
All three computational processes (recursion, the λ-calculus, and the Turing machine) were shown to be equivalent—all three approaches define the same class of functions. This has led mathematicians and computer scientists to believe that the concept of computability is accurately characterized by these three equivalent processes. Informally the Church–Turing thesis states that if some method (algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
) exists to carry out a calculation, then the same calculation can also be carried out by a Turing machine (as well as by a recursively
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
-definable function, and by a λ-function
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
).
The Church–Turing thesis is a statement that characterizes the nature of computation and cannot be formally proven. Even though the three processes mentioned above proved to be equivalent, the fundamental premise behind the thesis—the notion of what it means for a function to be "effectively calculable" (computable)—is "a somewhat vague intuitive one". Thus, the "thesis" remains an hypothesis.
Despite the fact that it cannot be formally proven, the Church–Turing thesis now has near-universal acceptance.
Formal statement
Rosser 1939 addresses the notion of "effective computability" as follows: "Clearly the existence of CC and RC (Church's and Rosser's proofs) presupposes a precise definition of "effective". "Effective methodEffective method
In computability theory, an effective method is a procedure that reduces the solution of some class of problems to a series of rote steps which, if followed to the letter, and as far as may be necessary, is bound to:...
" is here used in the rather special sense of a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps". Thus the adverb-adjective "effective" is used in a sense of "1a: producing a decided, decisive, or desired effect", and "capable of producing a result".
In the following, the words "effectively calculable" will mean "produced by any intuitively 'effective' means whatsoever" and "effectively computable" will mean "produced by a Turing-machine or equivalent mechanical device". Turing's 1939 "definitions" are virtually the same:
- "†We shall use the expression "computable function" to mean a function calculable by a machine, and we let "effectively calculable" refer to the intuitive idea without particular identification with any one of these definitions."(cf. the footnote † in Turing 1939 (his Ordinals paper) in Davis 1965:160).
The thesis can be stated as follows:
- Every effectively calculable function is a computable function.
Turing stated it this way:
- "It was stated ... that 'a function is effectively calculable if its values can be found by some purely mechanical process.' We may take this literally, understanding that by a purely mechanical process one which could be carried out by a machine. The development ... leads to ... an identification of computability † with effective calculability" († is the footnote above, ibid).
History
One of the important problems for logicians in the 1930s was David Hilbert'sDavid Hilbert
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
Entscheidungsproblem
Entscheidungsproblem
In mathematics, the is a challenge posed by David Hilbert in 1928. The asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either "True" or "False" according to whether the statement is true or false...
, which asked if there was a mechanical procedure for separating mathematical truths from mathematical falsehoods. This quest required that the notion of “algorithm” or “effective calculability” be pinned down, at least well enough for the quest to begin. But from the very outset Alonzo Church
Alonzo Church
Alonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem.-Life:Alonzo Church...
's attempts began with a debate that continues to this day. Was the notion of “effective calculability” to be (i) an "axiom or axioms" in an axiomatic system, or (ii) merely a definition that “identified” two or more propositions, or (iii) an empirical hypothesis to be verified by observation of natural events, or (iv) or just a proposal for the sake of argument (i.e. a "thesis").
Circa 1930–1952
In the course of studying the problem, Church and his student Stephen KleeneStephen Cole Kleene
Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
introduced the notion of λ-definable functions
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, and they were able to prove that several large classes of functions frequently encountered in number theory were λ-definable. The debate began when Church proposed to Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
that one should define the "effectively computable" functions as the λ-definable functions. Gödel, however, was not convinced and called the proposal "thoroughly unsatisfactory". Rather in correspondence with Church (ca 1934–5), Gödel proposed axiomatizing the notion of "effective calculability"; indeed, in a 1935 letter to Kleene, Church reported that:
- "His [Gödel's] only idea at the time was that it might be possible, in terms of effective calculability as an undefined notion, to state a set of axioms which would embody the generally accepted properties of this notion, and to do something on that basis".
But Gödel offered no further guidance. Eventually, he would suggest his (primitive) recursion, modified by Herbrand's suggestion, that he (Gödel) had detailed in his 1934 lectures in Princeton NJ (Kleene and another student J. B. Rosser transcribed the notes.). But "he did not think that the two ideas could be satisfactorily identified "except heuristically".
Next, it was necessary to identify and prove the equivalence of two notions of effective calculability. Equipped with the λ-calculus and "general" recursion, Stephen Kleene
Stephen Cole Kleene
Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
with help of Church and J. B. Rosser produced proofs (1933, 1935) to show that the two calculi are equivalent. Church subsequently modified his methods to include use of Herbrand–Gödel recursion and then proved (1936) that the Entscheidungsproblem
Entscheidungsproblem
In mathematics, the is a challenge posed by David Hilbert in 1928. The asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either "True" or "False" according to whether the statement is true or false...
is unsolvable: There is no generalized "effective calculation" (method, algorithm) that can determine whether or not a formula in either the recursive- or λ-calculus is "valid" (more precisely: no method to show that a well formed formula has a "normal form").
Many years later in a letter to Davis (ca 1965), Gödel would confess that "he was, at the time of these [1934] lectures, not at all convinced that his concept of recursion comprised all possible recursions". By 1963–4 Gödel would disavow Herbrand–Gödel recursion and the λ-calculus in favor of the Turing machine as the definition of “algorithm” or “mechanical procedure” or “formal system”.
An hypothesis leading to a natural law?: In late 1936 Alan Turing
Alan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
’s paper (also proving that the Entscheidungsproblem
Entscheidungsproblem
In mathematics, the is a challenge posed by David Hilbert in 1928. The asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either "True" or "False" according to whether the statement is true or false...
is unsolvable) had not yet appeared. On the other hand, Emil Post's 1936 paper had appeared and was certified independent of Turing's work. Post strongly disagreed with Church’s “identification” of effective computability with the λ-calculus and recursion, stating:
- "Actually the work already done by Church and others carries this identification considerably beyond the working hypothesis stage. But to mask this identification under a definition . . . blinds us to the need of its continual verification."
Rather, he regarded the notion of “effective calculability” as merely a "working hypothesis" that might lead by inductive reasoning
Inductive reasoning
Inductive reasoning, also known as induction or inductive logic, is a kind of reasoning that constructs or evaluates propositions that are abstractions of observations. It is commonly construed as a form of reasoning that makes generalizations based on individual instances...
to a "natural law
Natural law
Natural law, or the law of nature , is any system of law which is purportedly determined by nature, and thus universal. Classically, natural law refers to the use of reason to analyze human nature and deduce binding rules of moral behavior. Natural law is contrasted with the positive law Natural...
" rather than by “a definition or an axiom”. This idea was "sharply" criticized by Church.
Thus Post in his 1936 was also discounting Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
's suggestion to Church in 1934–5 that the thesis might be expressed as an axiom or set of axioms.
Turing adds another definition, Rosser equates all three: Within just a short time, Turing's 1936–37 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" appeared. In it he asserted another notion of "effective computability" with the introduction of his a-machines (now known as the Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
abstract computational model). And in a proof-sketch added as an "Appendix" to his 1936–37 paper, Turing showed that the classes of functions defined by λ-calculus and Turing machines coincided.
In a few years (1939) Turing would propose, like Church and Kleene before him, that his formal definition of mechanical computing agent was the correct one. Thus, by 1939, both Church (1934) and Turing (1939), neither having knowledge of the other’s efforts, had individually proposed that their "formal systems" should be definitions of "effective calculability"; neither framed their assertions as theses.
Rosser (1939) formally identified the three notions-as-definitions:
- "All three definitions are equivalent, so it does not matter which one is used."
Kleene proposes Church's Thesis: This left the overt expression of a "thesis” to Kleene. In his 1943 paper Recursive Predicates and Quantifiers Kleene proposed his "THESIS I":
- "This heuristic fact [general recursive functions are effectively calculable]...led Church to state the following thesis(22). The same thesis is implicit in Turing's description of computing machines(23).
- "THESIS I.
- "(22) references Church 1936
- "(23) references Turing 1936–7
Kleene goes on to note that:
- "...the thesis has the character of an hypothesis—a point emphasized by Post and by Church(24). If we consider the thesis and its converse as definition, then the hypothesis is an hypothesis about the application of the mathematical theory developed from the definition. For the acceptance of the hypothesis, there are, as we have suggested, quite compelling grounds."
-
- "(24) references Post 1936 of Post and Church's Formal definitions in the theory of ordinal numbers, Fund. Math. vol 28 (1936) pp.11–21 (see ref. #2, Davis 1965:286).
-
Kleene's Church–Turing Thesis: A few years later (1952) Kleene would overtly name, defend, and express the two "theses" and then "identify" them (show equivalence) by use of his Theorem XXX:
- "Heuristic evidence and other considerations led Church 1936 to propose the following thesis.
- Thesis I. Every effectively calculable function (effectively decidable predicate) is general recursive.
- Theorem XXX: "The following classes of partial functions are coextensive, i.e. have the same members: (a) the partial recursive functions, (b) the computable functions. . . ".
- Turing's thesis: "Turing's thesis that every function which would naturally be regarded as computable is computable under his definition, i.e. by one of his machines, is equivalent to Church's thesis by Theorem XXX."
Later developments
An attempt to understand the notion of "effective computability" better led Robin GandyRobin Gandy
Robin Oliver Gandy was a British mathematician and logician.He was a friend, student, and associate of Alan Turing, having been supervised by Turing during his PhD at the University of Cambridge , where they worked together.Educated at Abbotsholme, Robin Gandy took two years of the Mathematical...
(Turing's student and friend) in 1980 to analyze machine computation (as opposed to human-computation acted out by a Turing machine). Gandy's curiosity about, and analysis of, "cellular automata", "Conway's game of life
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
", "parallelism" and "crystalline automata" led him to propose four "principles (or constraints) ... which it is argued, any machine must satisfy." His most-important fourth, "the principle of causality" is based on the "finite velocity of propagation of effects and signals; contemporary physics rejects the possibility of instantaneous action at a distance." From these principles and some additional constraints—(1a) a lower bound on the linear dimensions of any of the parts, (1b) an upper bound on speed of propagation (the velocity of light), (2) discrete progress of the machine, and (3) deterministic behavior—he produces a theorem that "What can be calculated by a device satisfying principles I–IV is computable. ".
In the late 1990s Wilfried Sieg analyzed Turing's and Gandy's notions of "effective calculability" with the intent of "sharpening the informal notion, formulating its general features axiomatically, and investigating the axiomatic framework". In his 1997 and 2002 Sieg presents a series of constraints on the behavior of a computor—"a human computing agent who proceeds mechanically"; these constraints reduce to:
- "(B.1) (Boundedness)
The matter remains in active discussion within the academic community.
Success of the thesis
Other formalisms (besides recursion, the λ-calculusLambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, and the Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
) have been proposed for describing effective calculability/computability . Stephen Kleene
Stephen Cole Kleene
Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
(1952) adds to the list the functions "reckonable in the system S1" of Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
1936, and Emil Post's (1943, 1946) "canonical [also called normal] systems". In the 1950s Hao Wang and Martin Davis
Martin Davis
Martin David Davis, is an American mathematician, known for his work on Hilbert's tenth problem . He received his Ph.D. from Princeton University in 1950, where his adviser was Alonzo Church . He is Professor Emeritus at New York University. He is the co-inventor of the Davis-Putnam and the DPLL...
greatly simplified the one-tape Turing-machine model (see Post–Turing machine). Marvin Minsky
Marvin Minsky
Marvin Lee Minsky is an American cognitive scientist in the field of artificial intelligence , co-founder of Massachusetts Institute of Technology's AI laboratory, and author of several texts on AI and philosophy.-Biography:...
expanded the model to two or more tapes and greatly simplified the tapes into "up-down counters", which Melzak and Lambek
Joachim Lambek
Joachim Lambek is Peter Redpath Emeritus Professor of Pure Mathematics at McGill University, where he earned his Ph.D. degree in 1950 with Hans Julius Zassenhaus as advisor. He is called Jim by his friends.- Scholarly work :...
further evolved into what is now known as the counter machine
Counter machine
A counter machine is an abstract machine used in formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines...
model. In the late 1960s and early 1970s researchers expanded the counter machine model into the register machine
Register machine
In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine...
, a close cousin to the modern notion of the computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
. Other models include combinatory logic
Combinatory logic
Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming...
and Markov algorithm
Markov algorithm
In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a general model of computation and can represent any...
s. Gurevich adds the pointer machine
Pointer machine
In theoretical computer science a pointer machine is an "atomistic" abstract computational machine model akin to the Random access machine....
model of Kolmogorov and Uspensky (1953, 1958): "...they just wanted to ... convince themselves that there is no way to extend the notion of computable function."
All these contributions involve proofs that the models are computationally equivalent to the Turing machine; such models are said to be Turing complete. Because all these different attempts at formalizing the concept of "effective calculability/computability" have yielded equivalent results, it is now generally assumed that the Church–Turing thesis is correct. In fact, Gödel (1936) proposed something stronger than this; he observed that there was something "absolute" about the concept of "reckonable in S1":
- "It may also be shown that a function which is computable ['reckonable'] in one of the systems Si, or even in a system of transfinite type, is already computable [reckonable] in S1. Thus the concept 'computable' ['reckonable'] is in a certain definite sense 'absolute', while practically all other familiar metamathematical concepts (e.g. provable, definable, etc.) depend quite essentially on the system to which they are defined"
Informal usage in proofs
Proofs in computability theory often invoke the Church–Turing thesis in an informal way to establish the computability of functions while avoiding the (often very long) details which would be involved in a rigorous, formal proof. To establish that a function is computable by Turing machine, it is usually considered sufficient to give an informal English description of how the function can be effectively computed, and then conclude "By the Church–Turing thesis" that the function is Turing computable (equivalently partial recursive).Dirk van Dalen (in Gabbay 2001:284) gives the following example for the sake of illustrating this informal use of the Church–Turing thesis:
- EXAMPLE: Each infinite RE set contains an infinite recursive set.
- Proof: Let A be infinite RE. We list the elements of A effectively, n0, n1, n2, n3, ...
- From this list we extract an increasing sublist: put m0=n0, after finitely many steps we find an nk such that nk > m0, put m1=nk. We repeat this procedure to find m2 > m1, etc. this yields an effective listing of the subset B={m0,m1,m2,...} of A, with the property mi < mi+1.
- Claim. B is decidable. For, in order to test k in B we must check if k=mi for some i. Since the sequence of mi's is increasing we have to produce at most k+1 elements of the list and compare them with k. If none of them is equal to k, then k not in B. Since this test is effective, B is decidable and, by Church's thesis, recursive.
(Emphasis added). In order to make the above example completely rigorous, one would have to carefully construct a Turing Machine, or λ-function, or carefully invoke recursion axioms, or at best, cleverly invoke various theorems of computability theory. But because the computability theorist believes that Turing computability correctly captures what can be computed effectively, and because an effective procedure is spelled out in English for deciding the set B, the computability theorist accepts this as proof that the set is indeed recursive.
As a rule of thumb, the Church–Turing thesis should only be invoked to simplify proofs in cases where the writer would be capable of, and expects the readers also to be capable of, easily (but not necessarily without tedium) producing a rigorous proof if one were demanded
Variations
The success of the Church–Turing thesis prompted variations of the thesis to be proposed. For example, the Physical Church–Turing thesis (PCTT) states:-
- "According to Physical CTT, all physically computable functions are Turing-computable"
The Church–Turing thesis says nothing about the efficiency with which one model of computation can simulate another. It has been proved for instance that a (multi-tape) universal Turing machine
Universal Turing machine
In computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
only suffers a logarithmic slowdown factor in simulating any Turing machine. No such result has been proved in general for an arbitrary but reasonable model of computation. A variation of the Church–Turing thesis that addresses this issue is the Feasibility Thesis or (Classical) Complexity-Theoretic Church–Turing Thesis (SCTT), which is not due to Church or Turing, but rather was realized gradually in the development of complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. It states:
- "A probabilistic Turing machineProbabilistic Turing machineIn computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point according to some probability distribution....
can efficiently simulate any realistic model of computation."
The word 'efficiently' here means up to polynomial-time reductions. This thesis was originally called Computational Complexity-Theoretic Church–Turing Thesis by Ethan Bernstein and Umesh Vazirani
Umesh Vazirani
Umesh Virkumar Vazirani is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. Vazirani was himself a Ph.D. student at Berkeley, receiving his Ph.D. in 1986 under the...
(1997). The Complexity-Theoretic Church–Turing Thesis, then, posits that all 'reasonable' models of computation yield the same class of problems that can be computed in polynomial time. Assuming the conjecture that probabilistic polynomial time (BPP) equals deterministic polynomial time (P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
), the word 'probabilistic' is optional in the Complexity-Theoretic Church–Turing Thesis. A similar thesis, called the Invariant Thesis, was introduced by Cees F. Slot and Peter van Emde Boas. It states: "Reasonable" machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space. The thesis originally appeared in a paper at STOC'84, which was the first paper to show that polynomial-time overhead and constant-space overhead could be simultaneously achieved for a simulation of a Random Access Machine
Random access machine
In computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...
on a Turing machine.
If production-scale quantum computers can be built, they could invalidate the Complexity-Theoretic Church–Turing Thesis, since it is also conjectured that quantum polynomial time (BQP
BQP
In computational complexity theory BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances...
) is larger than BPP. In other words, there are efficient quantum algorithms that perform tasks that are not known to have efficient probabilistic algorithms; for example, factoring integers. They would not however invalidate the original Church–Turing thesis, since a quantum computer can always be simulated by a Turing machine, but they would invalidate the classical Complexity-Theoretic Church–Turing thesis for efficiency reasons. Consequently, the Quantum Complexity-Theoretic Church–Turing thesis states:
- "A quantum Turing machineQuantum Turing machineA quantum Turing machine , also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a particular quantum...
can efficiently simulate any realistic model of computation."
Eugene Eberbach and Peter Wegner claim that the Church-Turing thesis is sometimes interpreted too broadly,
stating "the broader assertion that algorithms precisely capture
what can be computed is invalid". They claim that forms of computation not captured by the thesis are relevant today,
terms which the call super-Turing computation
Hypercomputation
Hypercomputation or super-Turing computation refers to models of computation that are more powerful than, or are incomparable with, Turing computability. This includes various hypothetical methods for the computation of non-Turing-computable functions, following super-recursive algorithms...
.
Philosophical implications
The Church–Turing thesis has some profound implications for the philosophy of mindPhilosophy of mind
Philosophy of mind is a branch of philosophy that studies the nature of the mind, mental events, mental functions, mental properties, consciousness and their relationship to the physical body, particularly the brain. The mind-body problem, i.e...
; however many of the philosophical interpretations of the Thesis involve basic misunderstandings of the thesis statement. B. Jack Copeland
Jack Copeland
Brian Jack Copeland is Professor of Philosophy at the University of Canterbury, Christchurch, New Zealand.Copeland received a BPhil and DPhil from the University of Oxford in philosophy, where he undertook research on modal and non-classical logic.He is the Director of the Turing Archive for the...
states that it's an open empirical question whether there are actual deterministic physical processes that, in the long run, elude simulation by a Turing machine; furthermore, he states that it is an open empirical question whether any such processes are involved in the working of the human brain. There are also some important open questions which cover the relationship between the Church–Turing thesis and physics, and the possibility of hypercomputation
Hypercomputation
Hypercomputation or super-Turing computation refers to models of computation that are more powerful than, or are incomparable with, Turing computability. This includes various hypothetical methods for the computation of non-Turing-computable functions, following super-recursive algorithms...
. When applied to physics, the thesis has several possible meanings:
- The universe is equivalent to a Turing machine; thus, computing non-recursive functionsRecursion (computer science)Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science....
is physically impossible. This has been termed the Strong Church–Turing thesis and is a foundation of digital physicsDigital physicsIn physics and cosmology, digital physics is a collection of theoretical perspectives based on the premise that the universe is, at heart, describable by information, and is therefore computable...
. - The universe is not equivalent to a Turing machine (i.e., the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a hypercomputerHypercomputationHypercomputation or super-Turing computation refers to models of computation that are more powerful than, or are incomparable with, Turing computability. This includes various hypothetical methods for the computation of non-Turing-computable functions, following super-recursive algorithms...
. For example, a universe in which physics involves real numbers, as opposed to computable realComputable numberIn mathematics, particularly theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers or the computable reals, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm...
s, might fall into this category. - The universe is a hypercomputerHypercomputationHypercomputation or super-Turing computation refers to models of computation that are more powerful than, or are incomparable with, Turing computability. This includes various hypothetical methods for the computation of non-Turing-computable functions, following super-recursive algorithms...
, 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 mechanicalQuantum mechanicsQuantum mechanics, also known as quantum physics or quantum theory, is a branch of physics providing a mathematical description of much of the dual particle-like and wave-like behavior and interactions of energy and matter. It departs from classical mechanics primarily at the atomic and subatomic...
events are Turing-computable, although it is known that rigorous models such as quantum Turing machines are equivalent to deterministic Turing machines. (They are not necessarily efficiently equivalent; see above.) John LucasJohn Lucas (philosopher)- Overview :John Lucas was educated at Winchester College and Balliol College, Oxford, where he studied first mathematics, then Greats , obtaining first class honors, and proceeding to an MA in Philosophy in 1954. He spent the 1957-58 academic year at Princeton University, deepening his...
and, more famously, Roger PenroseRoger PenroseSir Roger Penrose OM FRS is an English mathematical physicist and Emeritus Rouse Ball Professor of Mathematics at the Mathematical Institute, University of Oxford and Emeritus Fellow of Wadham College...
have suggested that the human mind might be the result of some kind of quantum-mechanically enhanced, "non-algorithmic" computation, although there is no scientific evidence for this proposal.
There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.
Non-computable functions
One can formally define functions that are not computable. A well known example of such a function is the Busy Beaver function. This function takes an input n and returns the largest number of symbols that a Turing machineTuring machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
with n states can print before halting, when run with no input. Finding an upper bound on the busy beaver function is equivalent to solving the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
, a problem known to be unsolvable by Turing machines. Since the busy beaver function cannot be computed by Turing machines, the Church–Turing thesis asserts that this function cannot be effectively computed by any method. For more information see the article busy beaver
Busy beaver
In computability theory, a busy beaver is a Turing machine that attains the maximum "operational busyness" among all the Turing machines in a certain class...
.
Several computational models allow for the computation of (Church-Turing) non-computable functions. These are known as
hypercomputers
Hypercomputation
Hypercomputation or super-Turing computation refers to models of computation that are more powerful than, or are incomparable with, Turing computability. This includes various hypothetical methods for the computation of non-Turing-computable functions, following super-recursive algorithms...
.
Mark Burgin
argues that super-recursive algorithm
Super-recursive algorithm
In computability theory, super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines. The term was introduced by Mark Burgin, whose book "Super-recursive algorithms" develops their theory and presents several mathematical...
s such as inductive Turing machines disprove the Church–Turing thesis. His argument relies on a definition of algorithm broader than the ordinary one, so that non-computable functions obtained from some inductive Turing machines are called computable. This interpretation of the Church–Turing thesis differs from the interpretation commonly accepted in computability theory, discussed above. The argument that super-recursive algorithms are indeed algorithms in the sense of the Church–Turing thesis has not found broad acceptance within the computability research community.
See also
- Church's thesis in constructive mathematicsChurch's thesis (constructive mathematics)In constructive mathematics, Church's thesis is the mathematical assertion that all total functions are recursive. It gets its name after the informal Church–Turing thesis, which states that every algorithm is in fact a recursive function, but the constructivist version is formal and much...
- Computability logicComputability logicIntroduced by Giorgi Japaridze in 2003, computability logic is a research programme and mathematical framework for redeveloping logic as a systematic formal theory of computability, as opposed to classical logic which is a formal theory of truth...
- Computability theory
- DecidabilityDecidability (logic)In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
- History of the Church–Turing thesis
- Hypercomputer
- Super-recursive algorithmSuper-recursive algorithmIn computability theory, super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines. The term was introduced by Mark Burgin, whose book "Super-recursive algorithms" develops their theory and presents several mathematical...
- Church–Turing–Deutsch principleChurch–Turing–Deutsch principleIn computer science and quantum physics, the Church–Turing–Deutsch principle is a stronger, physical form of the Church–Turing thesis formulated by David Deutsch in 1985. The principle states that a universal computing device can simulate every physical process. The principle was originally...
, which states that every physical process can be simulated by a universal computing device
External links
.- Computation in Physical Systems A comprehensive philosophical treatment of relevant issues.