This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0000006854 Reproduction Date:
In computability theory, the Church–Turing thesis (also known as the Turing–Church thesis,^{[1]} the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis ("thesis") about the nature of computable functions. In simple terms, the Church–Turing thesis states that a function on the natural numbers is computable in an informal sense (i.e., computable by a human being using a pencil-and-paper method, ignoring resource limitations) if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and his Ph.D. student, the British mathematician Alan Turing.
Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods. In the 1930s, several independent attempts were made to formalize the notion of computability:
Church ^{[2]} and Turing ^{[3]} proved that these three formally defined classes of computable functions coincide: a function is λ-computable if and only if it is Turing computable if and only if it is general recursive. This has led mathematicians and computer scientists to believe that the concept of computability is accurately characterized by these three equivalent processes.
On the other hand, the Church–Turing thesis states that the above three formally defined classes of computable functions coincide with the informal notion of an effectively calculable function. Since, as an informal notion, the concept of effective calculability does not have a formal definition, the thesis, although it has near-universal acceptance, cannot be formally proven.
J. B. 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 method' 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".^{[4]} 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".^{[5]}^{[6]}
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 "definitions" given in a footnote in his 1939 Ph.D. thesis Systems of Logic Based on Ordinals, supervised by Church, are virtually the same:
The thesis can be stated as follows:
Turing stated it this way:
One of the important problems for logicians in the 1930s was David Hilbert's Entscheidungsproblem, which asked whether 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.^{[9]} But from the very outset Alonzo Church's attempts began with a debate that continues to this day.^{[10]} 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").
In the course of studying the problem, Church and his student Stephen Kleene 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.^{[11]} The debate began when Church proposed to 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".^{[12]} 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 Gödel had detailed in his 1934 lectures in Princeton NJ (Kleene and Rosser transcribed the notes). But "he did not think that the two ideas could be satisfactorily identified "except heuristically".^{[14]}
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").^{[15]}
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".^{[16]} 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".^{[17]}
A hypothesis leading to a natural law?: In late 1936 Alan Turing's paper (also proving that the Entscheidungsproblem is unsolvable) was delivered orally, but had not yet appeared in print.^{[18]} On the other hand, Emil Post's 1936 paper had appeared and was certified independent of Turing's work.^{[19]} 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".^{[21]} This idea was "sharply" criticized by Church.^{[22]}
Thus Post in his 1936^{[13]} paper 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.^{[13]}
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"^{[18]} appeared. In it he stated 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.^{[23]}
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.^{[24]} 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";^{[25]} neither framed their statements 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":
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:
An attempt to understand the notion of "effective computability" better led Robin Gandy (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."^{[31]} 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."^{[32]} 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.^{[33]} ".
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".^{[34]} 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:
The matter remains in active discussion within the academic community.^{[36]}^{[37]}
The thesis can be viewed as nothing but an ordinary mathematical definition. Comments by Gödel on the subject suggest this view, e.g. "the correct definition of mechanical computability was established beyond any doubt by Turing".^{[38]} The case for viewing the thesis as nothing more than a definition is made explicitly by Robert I. Soare in ^{[39]} where it is also argued that Turing's definition of computability is no less likely to be correct than the epsilon-delta definition of a continuous function.
Other formalisms (besides recursion, the λ-calculus, 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 S_{1}" of Kurt Gödel 1936, and Emil Post's (1943, 1946) "canonical [also called normal] systems".^{[40]} 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 algorithms. 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."^{[41]}
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 S_{1}":
Proofs in computability theory often invoke^{[43]} 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^{[44]}) 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 success of the Church–Turing thesis prompted variations of the thesis to be proposed. For example, the Physical Church–Turing thesis (PCTT) states:
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.^{[46]} 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^{[47]} 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:^{[48]}
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.^{[49]} 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.^{[50]}
If BQP is shown to be a strict superset of BPP, it would invalidate the Complexity-Theoretic Church–Turing Thesis. In other words, there would be efficient quantum algorithms that perform tasks that do not have efficient probabilistic algorithms. This would not however invalidate the original Church–Turing thesis, since a quantum computer can always be simulated by a Turing machine, but it would invalidate the classical Complexity-Theoretic Church–Turing thesis for efficiency reasons. Consequently, the Quantum Complexity-Theoretic Church–Turing thesis states:^{[48]}
Eugene Eberbach and Peter Wegner^{[51]} 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 they call super-Turing computation.
Philosophers have interpreted the Church–Turing thesis as having implications for the philosophy of mind; however, many of the philosophical interpretations of the Thesis involve basic misunderstandings of the thesis statement.^{[52]} 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.^{[53]} 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.
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 machine 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 states that this function cannot be effectively computed by any method.
Several computational models allow for the computation of (Church-Turing) non-computable functions. These are known as hypercomputers. Mark Burgin^{[56]} argues that super-recursive algorithms 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.
Quantum mechanics, Hava Siegelmann, Alan Turing, Computation, Computable function
Computer Science, Logic, Artificial intelligence, University of Cambridge, Bletchley Park
Alan Turing, Computer science, Logic, Turing machine examples, Mathematics
Computer science, Mathematics, Mathematical logic, Set theory, Logic
Mathematical logic, Parallel computing, Computer science, Category theory, Linguistics
Alan Turing, Alonzo Church, Stephen Cole Kleene, Kurt Gödel, David Hilbert
Lambda calculus, Programming language, Turing machine, Computability theory, Church–Turing thesis
Computer science, Logic, Alan Turing, Turing machine, Drakon
Mathematics, Mathematical logic, Number theory, Turing machine, Game theory
Computer science, David Hilbert, Alan Turing, Foundations of mathematics, Mathematics