In
computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a
thesis
A thesis ( : theses), or dissertation (abbreviated diss.), is a document submitted in support of candidature for an academic degree or professional qualification presenting the author's research and findings.International Standard ISO 7144 ...
about the nature of
computable functions. It states that a
function on the
natural numbers can be calculated by an
effective method if and only if it is computable by a
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...
. The thesis is named after American mathematician
Alonzo Church and the British mathematician
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical ...
. 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
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is clo ...
:
* In 1933,
Kurt Gödel, with
Jacques Herbrand, formalized the definition of the class of
general recursive functions: the smallest class of functions (with arbitrarily many arguments) that is closed under
composition,
recursion
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematic ...
, and
minimization, and includes
zero,
successor, and all
projections.
* In 1936,
Alonzo Church created a method for defining functions called the
λ-calculus. Within λ-calculus, he defined an encoding of the natural numbers called the
Church numerals
In mathematics, Church encoding is a means of representing data and operators in the lambda calculus. The Church numerals are a representation of the natural numbers using lambda notation. The method is named for Alonzo Church, who first encoded ...
. A function on the natural numbers is called
λ-computable if the corresponding function on the Church numerals can be represented by a term of the λ-calculus.
* Also in 1936, before learning of Church's work,
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical ...
created a theoretical model for machines, now called Turing machines, that could carry out calculations from inputs by manipulating symbols on a tape. Given a suitable encoding of the natural numbers as sequences of symbols, a function on the natural numbers is called
Turing computable
Computable functions are the basic objects of study in recursion theory, computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm, algorithms, in the sense that a function is computable if there ex ...
if some Turing machine computes the corresponding function on encoded natural numbers.
Church,
Kleene, and Turing proved that these three formally defined classes of computable functions coincide: a function is λ-computable if and only if it is Turing computable, and 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. Other formal attempts to characterize computability have subsequently strengthened this belief (see
below
Below may refer to:
*Earth
* Ground (disambiguation)
*Soil
*Floor
* Bottom (disambiguation)
*Less than
*Temperatures below freezing
*Hell or underworld
People with the surname
*Ernst von Below (1863–1955), German World War I general
*Fred Below ...
).
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. Although the thesis has near-universal acceptance, it cannot be formally proven, as the concept of effective calculability is only informally defined.
Since its inception, variations on the original thesis have arisen, including statements about what can physically be realized by a computer in our universe (
physical Church-Turing thesis
Physical may refer to:
* Physical examination, a regular overall check-up with a doctor
* ''Physical'' (Olivia Newton-John album), 1981
** "Physical" (Olivia Newton-John song)
* ''Physical'' (Gabe Gurnsey album)
* "Physical" (Alcazar song) (2004)
* ...
) and what can be efficiently computed (
Church–Turing thesis (complexity theory)). These variations are not due to Church or Turing, but arise from later work in
complexity theory and
digital physics. The thesis also has implications for the
philosophy of mind
Philosophy of mind is a branch of philosophy that studies the ontology and nature of the mind and its relationship with the body. The mind–body problem is a paradigmatic issue in philosophy of mind, although a number of other issues are add ...
(see
below
Below may refer to:
*Earth
* Ground (disambiguation)
*Soil
*Floor
* Bottom (disambiguation)
*Less than
*Temperatures below freezing
*Hell or underworld
People with the surname
*Ernst von Below (1863–1955), German World War I general
*Fred Below ...
).
Statement in Church's and Turing's words
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". 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 "definitions" given in a footnote in his 1938 Ph.D. thesis ''
Systems of Logic Based on Ordinals
''Systems of Logic Based on Ordinals'' was the PhD dissertation of the mathematician Alan Turing.
Turing's thesis is not about a new type of formal logic, nor was he interested in so-called ‘ranked logic’ systems derived from ordinal or rela ...
'', supervised by Church, are virtually the same:
We shall use the expression "computable function" to mean a function calculable by a machine, and let "effectively calculable" refer to the intuitive idea without particular identification with any one of these definitions.
The thesis can be stated as: ''Every effectively calculable function is a computable function''.
Church also stated that "No computational procedure will be considered as an algorithm unless it can be represented as a Turing Machine".
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 quoted above.ref name="Turing_1938_thesis_p8"/>
History
One of the important problems for logicians in the 1930s was the
Entscheidungsproblem of
David Hilbert and
Wilhelm Ackermann, 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. But from the very outset
Alonzo Church's attempts began with a debate that continues to this day. the notion of "effective calculability" to be (i) an "axiom or axioms" in an axiomatic system, (ii) merely a ''definition'' that "identified" two or more propositions, (iii) an ''empirical hypothesis'' to be verified by observation of natural events, or (iv) 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 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. 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". Rather, in correspondence with Church (c. 1934–1935), 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 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".
Next, it was necessary to identify and prove the equivalence of two notions of effective calculability. Equipped with the λ-calculus and "general" recursion, Kleene with help of Church and
J. Barkley 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 algorithm that can determine whether a
well formed formula has a
beta normal form
In the lambda calculus, a term is in beta normal form if no ''beta reduction'' is possible. A term is in beta-eta normal form if neither a beta reduction nor an ''eta reduction'' is possible. A term is in head normal form if there is no ''beta-rede ...
.
Many years later in a letter to Davis (c. 1965), Gödel said that "he was, at the time of these
934lectures, not at all convinced that his concept of recursion comprised all possible recursions". By 1963–1964 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".
A hypothesis leading to a natural law?: In late 1936
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical ...
's paper (also proving that the
Entscheidungsproblem is unsolvable) was delivered orally, but had not yet appeared in print.
[.] 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
Natural law ( la, ius naturale, ''lex naturalis'') is a system of law based on a close observation of human nature, and based on values intrinsic to human nature that can be deduced and applied independently of positive law (the express enacte ...
" rather than by "a definition or an axiom". This idea was "sharply" criticized by Church.
Thus Post in his 1936 paper was also discounting
Kurt Gödel's suggestion to Church in 1934–1935 that the thesis might be expressed as an axiom or set of axioms.
[Sieg 1997:160.]
Turing adds another definition, Rosser equates all three: Within just a short time, Turing's 1936–1937 paper "On Computable Numbers, with an Application to the Entscheidungsproblem"
appeared. In it he stated another notion of "effective computability" with the introduction of his a-machines (now known as the
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...
abstract computational model). And in a proof-sketch added as an "Appendix" to his 1936–1937 paper, Turing showed that the classes of functions defined by λ-calculus and Turing machines coincided. Church was quick to recognise how compelling Turing's analysis was. In his review of Turing's paper he made clear that Turing's notion made "the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately".
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) had individually proposed that their "formal systems" should be ''definitions'' of "effective calculability"; neither framed their statements as ''theses''.
Rosser (1939) formally identified the three notions-as-definitions:
Kleene proposes ''Thesis I'': This left the overt expression of a "thesis" to Kleene. In 1943 Kleene proposed his "Thesis I":
[ in . Footnotes omitted.]
The Church–Turing Thesis: Stephen Kleene, in ''Introduction To Metamathematics'', finally goes on to formally name "Church's Thesis" and "Turing's Thesis", using his theory of recursive realizability. Kleene having switched from presenting his work in the terminology of Church-Kleene lambda definability, to that of Gödel-Kleene recursiveness (partial recursive functions). In this transition, Kleene modified Gödel's general recursive functions to allow for proofs of the unsolvability of problems in the Intuitionism of E. J. Brouwer. In his graduate textbook on logic, "Church's thesis" is introduced and basic mathematical results are demonstrated to be unrealizable. Next, Kleene proceeds to present "Turing's thesis", where results are shown to be uncomputable, using his simplified derivation of a Turing machine based on the work of Emil Post. Both theses are proven equivalent by use of "Theorem XXX".
Kleene, finally, uses for the first time the term the "Church-Turing thesis" in a section in which he helps to give clarifications to concepts in Alan Turing's paper "The Word Problem in Semi-Groups with Cancellation", as demanded in a critique from William Boone.
Later developments
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 (including
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 work 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) There is a fixed bound on the number of symbolic configurations a computor can immediately recognize.
*"(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
nstantaneous 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.
The thesis as a definition
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". The case for viewing the thesis as nothing more than a definition is made explicitly by
Robert I. Soare,
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
In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in val ...
.
Success of the thesis
Other formalisms (besides recursion, the
λ-calculus, and the
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...
) have been proposed for describing effective calculability/computability. 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''
lso 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
Marvin Lee Minsky (August 9, 1927 – January 24, 2016) was an American cognitive and computer scientist concerned largely with research of artificial intelligence (AI), co-founder of the Massachusetts Institute of Technology's AI laboratory ...
expanded the model to two or more tapes and greatly simplified the tapes into "up-down counters", which Melzak and
Lambek
Joachim "Jim" Lambek (5 December 1922 – 23 June 2014) was a German-born Canadian mathematician. He was Peter Redpath Emeritus Department of Mathematics and Statistics, McGill University, Professor of Pure Mathematics at McGill University, wher ...
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
A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations ( computation) automatically. Modern digital electronic computers can perform generic sets of operations known as programs. These prog ...
. Other models include
combinatory logic
Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of com ...
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."
All these contributions involve proofs that the models are computationally equivalent to the Turing machine; such models are said to be
Turing complete
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical ...
. 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":
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 gives the following example for the sake of illustrating this informal use of the Church–Turing thesis:
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.
Variations
The success of the Church–Turing thesis prompted variations of the thesis to be proposed. For example, the physical Church–Turing thesis states: "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 only suffers a logarithmic slowdown factor in simulating any Turing machine.
A variation of the Church–Turing thesis addresses whether an arbitrary but "reasonable" model of computation can be efficiently simulated. This is called the feasibility thesis, also known as the (classical) complexity-theoretic Church–Turing thesis or the extended Church–Turing thesis, which is not due to Church or Turing, but rather was realized gradually in the development of
complexity theory. It states:
"A
probabilistic Turing machine can efficiently simulate any realistic model of computation." The word 'efficiently' here means up to
polynomial-time reduction
In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming ...
s. 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 invariance 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
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
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite sequ ...
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:
"A
quantum Turing machine
A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algori ...
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 "Though
..Turing machines express the behavior of algorithms, 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.
Philosophical implications
Philosophers have interpreted the Church–Turing thesis as having implications for the
philosophy of mind
Philosophy of mind is a branch of philosophy that studies the ontology and nature of the mind and its relationship with the body. The mind–body problem is a paradigmatic issue in philosophy of mind, although a number of other issues are add ...
.
B. Jack Copeland states that it is 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:
#The universe is equivalent to a Turing machine; thus, computing
non-recursive functions is physically impossible. This has been termed the strong Church–Turing thesis, or
Church–Turing–Deutsch principle, and is a foundation of
digital physics.
#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
hypercomputer. For example, a universe in which physics involves random
real numbers, as opposed to
computable reals, would 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 is known that rigorous models such as
quantum Turing machine
A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algori ...
s are equivalent to deterministic Turing machines. (They are not necessarily efficiently equivalent; see above.)
John Lucas and
Roger Penrose have suggested that the human mind might be the result of some kind of quantum-mechanically enhanced, "non-algorithmic" computation.
There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.
Philosophical aspects of the thesis, regarding both physical and biological computers, are also discussed in Odifreddi's 1989 textbook on recursion theory.
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 machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...
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
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a ...
, 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 argues that
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" dev ...
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
*
Abstract machine
*
Church's thesis in constructive mathematics
*
Church–Turing–Deutsch principle, which states that every
physical process can be simulated by a universal computing device
*
Computability logic
Computability logic (CoL) is a research program 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. It was introduced and so named by Gi ...
*
Computability theory
*
Decidability
*
Hypercomputation
*
Model of computation
*
Oracle (computer science)
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a s ...
*
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" dev ...
*
Turing completeness
Footnotes
References
*
*
*
*
*
*
*
*
*
*
*
* Includes original papers by Gödel, Church, Turing, Rosser, Kleene, and Post mentioned in this section.
*
*
*
*
*
*
* Cited by .
*
*
*
*
*
*
* Reprinted in
''The Undecidable'', p. 255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p. 274); he would later repeat this thesis (in ) and name it "Church's Thesis" (i.e., the
Church thesis).
*
*
*
*
*
*
*
*
*
*
*
* and (See also: )
*
External links
* .
* —a comprehensive philosophical treatment of relevant issues.
*
*
special issue(Vol. 28, No. 4, 1987) of the ''
Notre Dame Journal of Formal Logic
The ''Notre Dame Journal of Formal Logic'' is a quarterly peer-reviewed scientific journal covering the foundations of mathematics and related fields of mathematical logic, as well as philosophy of mathematics. It was established in 1960 and is pub ...
'' was devoted to the Church–Turing thesis.
{{DEFAULTSORT:Church-Turing Thesis
Computability theory
Alan Turing
Theory of computation
Philosophy of computer science