church turing thesis tutorialspoint

• Selected Reading
• UPSC IAS Exams Notes
• Developer's Best Practices
• Questions and Answers
• Effective Resume Writing
• HR Interview Questions
• Computer Glossary

What is The Church-Turing Thesis in TOC?

The Church-Turing thesis says that every solvable decision problem can be transformed into an equivalent Turing machine problem.

It can be explained in two ways, as given below −

The Church-Turing thesis for decision problems.

The extended Church-Turing thesis for decision problems.

Let us understand these two ways.

The Church-Turing thesis for decision problems

There is some effective procedure to solve any decision problem if and only if there is a Turing machine which halts for all input strings and solves the problem.

The extended Church-Turing thesis for decision problems

A decision problem Q is said to be partially solvable if and only if there is a Turing machine which accepts precisely the elements of Q whose answer is yes.

A proof by the Church-Turing thesis is a shortcut often taken in establishing the existence of a decision algorithm.

For any decision problem, rather than constructing a Turing machine solution, let us describe an effective procedure which solves the problem.

The Church-Turing thesis explains that a decision problem Q has a solution if and only if there is a Turing machine that determines the answer for every q ϵ Q. If no such Turing machine exists, the problem is said to be undecidable.

Related Articles

• What is Turing Machine in TOC?
• What are the Turing machine variations in TOC?
• Explain the universal Turing machine in TOC
• Explain Multi tape Turing Machine in TOC?
• What is a Thesis Statement?
• How to use Turing machines to recognize languages in TOC?
• What is the decision problem in TOC?
• What is the Halting Problem in TOC?
• What is Decidability in TOC?
• What is Inductive Hypothesis in TOC?
• What is unambiguous grammar in TOC?
• What is NP-completeness in TOC?
• What is Kleene’s Theorem in TOC?
• Witch hunts and the Catholic Church
• What is a Derivation tree in TOC?

Kickstart Your Career

Get certified by completing the course

• Engineering Mathematics
• Discrete Mathematics
• Operating System
• Computer Networks
• Digital Logic and Design
• C Programming
• Data Structures
• Theory of Computation
• Compiler Design
• Computer Org and Architecture

Church’s Thesis for Turing Machine

In 1936, A method named as lambda-calculus was created by Alonzo Church in which the Church numerals are well defined, i.e. the encoding of natural numbers. Also in 1936, Turing machines (earlier called theoretical model for machines) was created by Alan Turing, that is used for manipulating the symbols of string with the help of tape.

Church Turing Thesis :

Turing machine is defined as an abstract representation of a computing device such as hardware in computers. Alan Turing proposed Logical Computing Machines (LCMs), i.e. Turing’s expressions for Turing Machines. This was done to define algorithms properly. So, Church made a mechanical method named as ‘M’ for manipulation of strings by using logic and mathematics. This method M must pass the following statements:

• Number of instructions in M must be finite.
• Output should be produced after performing finite number of steps.
• It should not be imaginary, i.e. can be made in real life.
• It should not require any complex understanding.

Using these statements Church proposed a hypothesis called

Church’s Turing thesis

that can be stated as: “The assumption that the intuitive notion of computable functions can be identified with partial recursive functions.”

Or in simple words we can say that “Every computation that can be carried out in the real world can be effectively performed by a Turing Machine.”

In 1930, this statement was first formulated by Alonzo Church and is usually referred to as Church’s thesis, or the Church-Turing thesis. However, this hypothesis cannot be proved. The recursive functions can be computable after taking following assumptions:

• Each and every function must be computable.
• Let ‘F’ be the computable function and after performing some elementary operations to ‘F’, it will transform a new function ‘G’ then this function ‘G’ automatically becomes the computable function.
• If any functions that follow above two assumptions must be states as computable function.

Please Login to comment...

Similar reads, improve your coding skills with practice.

What kind of Experience do you want to share?

Church-Turing Thesis

The Church-Turing thesis (formerly commonly known simply as Church's thesis) says that any real-world computation can be translated into an equivalent computation involving a Turing machine . In Church's original formulation (Church 1935, 1936), the thesis says that real-world calculation can be done using the lambda calculus , which is equivalent to using general recursive functions .

The Church-Turing thesis encompasses more kinds of computations than those originally envisioned, such as those involving cellular automata , combinators , register machines , and substitution systems . It also applies to other kinds of computations found in theoretical computer science such as quantum computing and probabilistic computing.

There are conflicting points of view about the Church-Turing thesis. One says that it can be proven, and the other says that it serves as a definition for computation. There has never been a proof, but the evidence for its validity comes from the fact that every realistic model of computation, yet discovered, has been shown to be equivalent. If there were a device which could answer questions beyond those that a Turing machine can answer, then it would be called an oracle .

Some computational models are more efficient, in terms of computation time and memory, for different tasks. For example, it is suspected that quantum computers can perform many common tasks with lower time complexity , compared to modern computers, in the sense that for large enough versions of these problems, a quantum computer would solve the problem faster than an ordinary computer. In contrast, there exist questions, such as the halting problem , which an ordinary computer cannot answer, and according to the Church-Turing thesis, no other computational device can answer such a question.

The Church-Turing thesis has been extended to a proposition about the processes in the natural world by Stephen Wolfram in his principle of computational equivalence (Wolfram 2002), which also claims that there are only a small number of intermediate levels of computing power before a system is universal and that most natural systems are universal.

This entry contributed by Todd Rowland

Explore with Wolfram|Alpha

More things to try:

• Bernoulli B(16)
• n-complete graph

Referenced on Wolfram|Alpha

Cite this as:.

Rowland, Todd . "Church-Turing Thesis." From MathWorld --A Wolfram Web Resource, created by Eric W. Weisstein . https://mathworld.wolfram.com/Church-TuringThesis.html

Subject classifications

• Collectibles

The Church-Turing Thesis Explained: A Deep Dive into the Foundations of Computation

• by history tools
• March 28, 2024

The Church-Turing thesis is a fundamental tenet of computer science that provides the very definition of what it means to be "computable." In essence, it claims that any function that is intuitively "computable" by an effective procedure can be computed by a Turing machine. While this may sound simple, the implications are profound, touching everything from the limits of logical proof to the nature of human cognition.

As a digital technology expert, I find the Church-Turing thesis endlessly fascinating, both for its elegance as an idea and its relevance to the technology we use every day. Far from an archaic piece of mathematical trivia, it remains the beating heart of theoretical computer science nearly a century after its inception. Let‘s dive in and explore the origins, meaning, and implications of this landmark idea in the history of human knowledge.

Origins of Computability Theory in the 1930s

Independently, a young British mathematician named Alan Turing was exploring similar questions. In 1936, Turing published a groundbreaking paper introducing what he called "a-machines," later known as Turing machines.[^3] A Turing machine is an abstract device that can perform any computation that can be done by a human following a finite set of explicit instructions. It consists of:

• An infinite tape divided into cells that can each hold a symbol from a finite alphabet
• A read/write head that can move left or right on the tape and read or write symbols
• A finite set of states the machine can be in, with transition rules that specify how the state and tape contents change based on the current state and symbol being read

Turing showed that any function computable by a Turing machine was also expressible in the lambda calculus, and vice versa. This established the equivalence of the two formalisms and led Church to propose what became known as "Church‘s thesis" or the "Church-Turing thesis":

"A function is effectively calculable if and only if it is computable by a Turing machine or expressible in the lambda calculus." (adsbygoogle = window.adsbygoogle || []).push({});

While Church and Turing could not prove that their formalisms captured all possible notions of computability, the thesis has stood the test of time remarkably well. In the 85 years since it was proposed, no one has found a convincing counterexample of a function that is intuitively computable but not Turing computable. The Church-Turing thesis has become a foundational axiom of computer science.

Computable and Uncomputable Functions

To get a concrete sense of what the Church-Turing thesis means, let‘s look at some examples of computable and uncomputable functions. A classic computable function is primality testing: given a natural number n, determine whether n is prime (i.e. evenly divisible only by 1 and itself). Here‘s a simple Python program that implements a primality test:

This function takes a number n as input, checks if it‘s evenly divisible by any number between 2 and its square root, and returns True if no such divisor is found (meaning n is prime) or False otherwise. It‘s easy to see that this function is computable by a Turing machine: we can specify a finite set of rules for updating the machine‘s state and tape contents to implement the same logic as the Python code. Primality testing is a computable problem.

Turing‘s proof is a clever use of diagonalization and self-reference. Suppose a halting solver Turing machine H existed. We could then construct a machine M that takes a program P as input and does the following:

• Run H on P and P itself as input
• If H says P halts on itself, go into an infinite loop; otherwise, halt immediately

Now, what happens if we run M on itself? If M halts on itself, then H would have determined that M does not halt on itself, in which case the second step would cause M to halt. But if M doesn‘t halt on itself, then H would have determined that M halts on itself, in which case the second step would cause M to go into an infinite loop! This contradiction means our original assumption that H exists must have been false. The halting problem is uncomputable.

This kind of self-referential paradox crops up often in computability theory. It‘s reminiscent of Gödel‘s incompleteness theorems, and in a sense, establishes a fundamental limit on what can be algorithmically decided. Not every well-defined mathematical question has a computable solution.

Variations and Extensions to the Church-Turing Thesis

While the Church-Turing thesis is widely accepted, there have been various philosophical and mathematical challenges to it over the years. Some researchers have proposed notions of "hypercomputation" that go beyond the limits of Turing machines, such as:

• Oracle machines: Turing machines equipped with a black box "oracle" that can magically solve the halting problem or other uncomputable tasks
• Analog computers: Machines that perform computation using continuous physical quantities like voltages or fluid pressures instead of discrete symbols
• Quantum computers: Devices that harness quantum superposition and entanglement to perform computations, potentially offering exponential speedups over classical computers for certain problems

Personally, I find the Church-Turing thesis compelling both as a mathematical foundation and an empirical claim. The fact that nearly a century of research has failed to produce a convincing counterexample suggests that Turing machines really do capture something fundamental about the nature of computation. At the same time, I‘m excited by theoretical and technological developments that probe the boundaries of the computable, and I try to keep an open mind about the potential for new computational models.

The Computational Lens on Mind and Universe

Beyond its central role in computer science, the Church-Turing thesis provides a powerful conceptual framework for viewing the world at large through a computational lens. The notion that any effective procedure can be realized by a Turing machine suggests a kind of universal computability to the cosmos. And if the universe itself is a computer, might the human mind simply be an embodied subprogram?

The strong form of this view is that human cognition is Turing-computable – that everything from perception to reasoning to consciousness can in principle be implemented by a sufficiently advanced AI system. If this is true, then the Church-Turing thesis places ultimate limits on the nature of intelligence. No matter how sophisticated our technology becomes, the space of possible minds will be constrained by the space of Turing-computable functions.

As a computer scientist, I lean towards a computational view of mind, but I also recognize the difficulty of reducing something as complex and subjective as human experience to the cut-and-dried formalisms of Turing machines. While I believe artificial general intelligence is possible in principle, I suspect the Church-Turing thesis alone is too crude a tool to fully delineate the space of possible minds. We likely need a richer theory of computation that can account for context, embodiment, and interaction with the environment.

This connects to perhaps the grandest application of the Church-Turing lens: viewing the physical universe itself as a computation. Digital physics, as championed by thinkers like Konrad Zuse, Edward Fredkin, and Stephen Wolfram, models the cosmos as a giant (quantum) computer, with the physics constrained by the Church-Turing thesis.[^12] In this view, spacetime is the hardware, particles are the software, and the speed of light is the clock rate.

While a compelling metaphor, digital physics remains highly speculative. We have no empirical evidence that the universe is discretized at the Planck scale or that physical dynamics are bounded by Turing computability. In fact, some have argued that a discrete, computable universe would violate locality and Lorentz invariance.[^13] For now, digital physics is more of a philosophical stance than a scientific theory.

The Church-Turing thesis is a profound and enduring idea that has shaped the foundations of computer science and our philosophical understanding of the nature of mind and cosmos. By precisely defining what it means for a function to be "computable," Church and Turing gave us a powerful mathematical framework for reasoning about the limits of algorithmic problem-solving.

While the thesis remains unproven in a formal sense, its remarkable resilience over nearly a century attests to its conceptual power. No one has yet found a convincing example of an intuitively computable function that is not Turing computable. The Church-Turing thesis has become a bedrock assumption of modern computability theory.

At the same time, the thesis raises deep questions about the nature of computation in the physical universe and human minds. Are there forms of hypercomputation that transcend the Church-Turing limit? Is the brain itself bounded by Turing computability? Might the universe be a vast digital computer constrained by the laws of Church and Turing? These are heady philosophical questions that have inspired much debate and speculation.

As our digital technologies continue to advance at a dizzying pace, it‘s worth reflecting on the Church-Turing foundations that make it all possible. The smartphones in our pockets and the supercomputers in the cloud are all in a sense instantiations of Turing‘s original vision – an astoundingly general model of mechanical computation. Every time you run a program, send an email, or do a web search, you‘re implicitly relying on the Church-Turing thesis. That is the mark of a truly deep idea.

Moving forward, I believe the Church-Turing thesis will remain a vital touchstone for anyone seeking to understand the nature of computation – in silicon, in carbon, and in the cosmos. While it may not be the final word on computability, it is a crucial piece of the puzzle, and one that will continue to inspire and inform our thinking about the algorithmic universe we inhabit. As a digital technology expert, I find that an endlessly exciting prospect.

Related posts:

• Hello Reader, Here is the Complete Guide to Understanding the Turing Test
• The Origins and Evolution of STEM Education: An Exploration of Its History, Significance and Future
• Unlocking the Power of Z-Scores: An Essential Guide for the Tech-Savvy Data Analyst
• Precision vs Recall: Understanding the Key Differences
• The Complete Guide to Cybernetics
• A Complete History of Code-Breaking and Cryptanalysis
• Converting Between Celsius and Fahrenheit: A Digital Technology Perspective
• Hashing 101: A Comprehensive Guide to Understanding Hash Functions

The Church-Turing Thesis

There are various equivalent formulations of the Church-Turing thesis. A common one is that every effective computation can be carried out by a Turing machine. The Church-Turing thesis is often misunderstood, particularly in recent writing in the philosophy of mind.

The Thesis and its History

Misunderstandings of the thesis, some key remarks by turing, bibliography, other internet resources, related entries.

The Church-Turing thesis concerns the notion of an effective or mechanical method in logic and mathematics. ‘Effective’ and its synonym ‘mechanical’ are terms of art in these disciplines: they do not carry their everyday meaning. A method, or procedure, M, for achieving some desired result is called ‘effective’ or ‘mechanical’ just in case

• M is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols);
• M will, if carried out without error, produce the desired result in a finite number of steps;
• M can (in practice or in principle) be carried out by a human being unaided by any machinery save paper and pencil;
• M demands no insight or ingenuity on the part of the human being carrying it out.

A well-known example of an effective method is the truth table test for tautologousness. In practice, of course, this test is unworkable for formulae containing a large number of propositional variables, but in principle one could apply it successfully to any formula of the propositional calculus, given sufficient time, tenacity, paper, and pencils.

Statements that there is an effective method for achieving such-and-such a result are commonly expressed by saying that there is an effective method for obtaining the values of such-and-such a mathematical function. For example, that there is an effective method for determining whether or not any given formula of the propositional calculus is a tautology -- e.g. the truth table method -- is expressed in function-speak by saying that there is an effective method for obtaining the values of a function, call it T, whose domain is the set of formulae of the propositional calculus and whose value for any given formula x, written T(x), is 1 or 0 according to whether x is, or is not, a tautology.

The notion of an effective method is an informal one, and attempts to characterise effectiveness, such as the above, lack rigour, for the key requirement that the method demand no insight or ingenuity is left unexplicated. One of Turing's achievements in his paper of 1936 was to present a formally exact predicate with which the informal predicate ‘can be calculated by means of an effective method’ may be replaced. Church did the same (1936a). The replacement predicates that Turing and Church proposed were, on the face of it, very different from one another, but they turned out to be equivalent, in the sense that each picks out the same set of mathematical functions. The Church-Turing thesis is the assertion that this set contains every function whose values can be obtained by a method satisfying the above conditions for effectiveness. (Clearly, if there were functions of which the informal predicate, but not the formal predicate, were true, then the latter would be less general than the former and so could not reasonably be employed to replace it.) When the thesis is expressed in terms of the formal concept proposed by Turing, it is appropriate to refer to the thesis also as ‘Turing's thesis’; and mutatis mutandis in the case of Church.

The formal concept proposed by Turing is that of computability by Turing machine . He argued for the claim (Turing's thesis) that whenever there is an effective method for obtaining the values of a mathematical function, the function can be computed by a Turing machine. The converse claim is easily established, for a Turing machine program is itself a specification of an effective method: without exercising any ingenuity or insight, a human being can work through the instructions in the program and carry out the required operations. If Turing's thesis is correct, then talk about the existence and non-existence of effective methods can be replaced throughout mathematics and logic by talk about the existence or non-existence of Turing machine programs.

Turing stated his thesis in numerous places, with varying degrees of rigour. The following formulation is one of the most accessible.

Turing's thesis : LCMs [logical computing machines: Turing's expression for Turing machines] can do anything that could be described as "rule of thumb" or "purely mechanical". (Turing 1948:7.)

This is sufficiently well established that it is now agreed amongst logicians that "calculable by means of an LCM" is the correct accurate rendering of such phrases. (1948: 7.)

Turing introduced this thesis in the course of arguing that the Entscheidungsproblem, or decision problem, for the predicate calculus - posed by Hilbert (Hilbert and Ackermann 1928) -- is unsolvable. Here is Church's account of the Entscheidungsproblem:

By the Entscheidungsproblem of a system of symbolic logic is here understood the problem to find an effective method by which, given any expression Q in the notation of the system, it can be determined whether or not Q is provable in the system. (Church 1936b: 41.)

The truth table test is such a method for the propositional calculus. Turing showed that, given his thesis, there can be no such method for the predicate calculus. He proved formally that there is no Turing machine which can determine, in a finite number of steps, whether or not any given formula of the predicate calculus is a theorem of the calculus. So, given his thesis that if an effective method exists then it can be carried out by one of his machines, it follows that there is no such method to be found.

Church had arrived at the same negative result a few months earlier, employing the concept of lambda-definability in place of computability by Turing machine. (A function of positive integers is said to be lambda-definable if the values of the function can be calculated by a process of repeated substitution.) Church and Turing discovered the result quite independently of one another. Turing's method of obtaining it is rather more satisfying than Church's, as Church himself acknowledged in a review of Turing's work:

computability by a Turing machine ... has the advantage of making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately. (1937a: 43.)

(Another aspect in which their approaches differ is that Turing's concerns were rather more general than Church's, in that the latter considered only functions of positive integers (see below), whereas Turing described his work as encompassing "computable functions of an integral variable or a real or computable variable, computable predicates, and so forth" (1936: 230). He intended to pursue the theory of computable functions of a real variable in a subsequent paper, but in fact did not do so.)

Church used the (informal) expression ‘effectively calculable’ to indicate that there is an effective method for calculating the values of the function. He proposed that we

define the notion ... of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers (or of a lambda-definable function of positive integers). (1936a: 356.)

The concept of a lambda-definable function is due to Church and Kleene (Church 1932, 1936a, 1941, Kleene 1935) and the concept of a recursive function to Gödel and Herbrand (Gödel 1934, Herbrand 1932). The class of lambda-definable functions and the class of recursive functions are identical. This was established in the case of functions of positive integers by Church and Kleene (Church 1936a, Kleene 1936). After learning of Church's proposal, Turing quickly established that the apparatus of lambda-definability and his own apparatus of computability are equivalent (1936: 263ff). Thus, in Church's proposal, the words ‘recursive function of positive integers’ can be replaced by the words ‘function of positive integers computable by Turing machine’.

Post referred to Church's identification of effective calculability with recursiveness as a "working hypothesis", and quite properly criticised Church for masking this hypothesis as a definition.

[T]o mask this identification under a definition ... blinds us to the need of its continual verification. (Post 1936: 105.)

This, then, is the "working hypothesis" that, in effect, Church proposed:

Church's thesis : A function of positive integers is effectively calculable only if recursive.

The reverse implication, that every recursive function of positive integers is effectively calculable, is commonly referred to as the converse of Church's thesis (although Church himself did not so distinguish, bundling both theses together in his ‘definition’). If attention is restricted to functions of positive integers then Church's thesis and Turing's thesis are equivalent, in view of the previously mentioned results by Church, Kleene and Turing.

The term ‘Church-Turing thesis’ seems to have been first introduced by Kleene, with a small flourish of bias in favour of Church:

So Turing's and Church's theses are equivalent. We shall usually refer to them both as Church's thesis , or in connection with that one of its ... versions which deals with ‘Turing machines’ as the Church-Turing thesis . (Kleene 1967: 232.)

Much evidence has been amassed for the ‘working hypothesis’ proposed by Church and Turing in 1936. One of the fullest surveys is to be found in chapters 12 and 13 of Kleene (1952). In summary: (1) Every effectively calculable function that has been investigated in this respect has turned out to be computable by Turing machine. (2) All known methods or operations for obtaining new effectively calculable functions from given effectively calculable functions are paralleled by methods for constructing new Turing machines from given Turing machines. (3) All attempts to give an exact analysis of the intuitive notion of an effectively calculable function have turned out to be equivalent in the sense that each analysis offered has been proved to pick out the same class of functions, namely those that are computable by Turing machine. Because of the diversity of the various analyses the latter is generally considered strong evidence. For example, apart from the analyses already mentioned in terms of lambda-definability and recursiveness, there are analyses in terms of register machines (Shepherdson and Sturgis 1963), Post's canonical and normal systems (Post 1943, 1946), combinatory definability (Schönfinkel 1924, Curry 1929, 1930, 1932), Markov algorithms (Markov 1960), and Gödel's notion of reckonability (Gödel 1936, Kleene 1952).

While there have from time to time been attempts to call the Church-Turing thesis into question (for example by Kalmar (1959); Mendelson (1963) replies), the summary of the situation that Turing gave in 1948 is no less true today: "it is now agreed amongst logicians that ‘calculable by means of an LCM’ is the correct accurate rendering" (of the informal notion in question).

A myth seems to have arisen concerning Turing's paper of 1936, namely that he there gave a treatment of the limits of mechanism and established a fundamental result to the effect that the universal Turing machine can simulate the behaviour of any machine. The myth has passed into the philosophy of mind, generally to pernicious effect. For example, the Oxford Companion to the Mind states: "Turing showed that his very simple machine ... can specify the steps required for the solution of any problem that can be solved by instructions, explicitly stated rules, or procedures" (Gregory 1987: 784). Dennett maintains that "Turing had proven - and this is probably his greatest contribution - that his Universal Turing machine can compute any function that any computer, with any architecture, can compute" (1991: 215); also that every "task for which there is a clear recipe composed of simple steps can be performed by a very simple computer, a universal Turing machine, the universal recipe-follower" (1978:. xviii). Paul and Patricia Churchland assert that Turing's "results entail something remarkable, namely that a standard digital computer, given only the right program, a large enough memory and sufficient time, can compute any rule-governed input-output function. That is, it can display any systematic pattern of responses to the environment whatsoever" (1990: 26). These various quotations are typical of current writing on the foundations of the computational theory of mind. It seems on the surface unlikely that these authors mean to restrict the general notions of ‘explicitly stated rule’, ‘instruction’, ‘clear recipe composed of simple steps', ‘computer with any architecture’, ‘rule-governed function’ and ‘systematic pattern’ so as to apply only to things that can be obeyed, simulated, calculated, or produced by a machine that implements ‘effective’ methods in Turing's original sense. But unless these notions are restricted in this way from the start, we should reject such claims.

Turing did not show that his machines can solve any problem that can be solved "by instructions, explicitly stated rules, or procedures", nor did he prove that the universal Turing machine "can compute any function that any computer, with any architecture, can compute". He proved that his universal machine can compute any function that any Turing machine can compute; and he put forward, and advanced philosophical arguments in support of, the thesis here called Turing's thesis. But a thesis concerning the extent of effective methods -- which is to say, concerning the extent of procedures of a certain sort that a human being unaided by machinery is capable of carrying out -- carries no implication concerning the extent of the procedures that machines are capable of carrying out, even machines acting in accordance with ‘explicitly stated rules’. For among a machine's repertoire of atomic operations there may be those that no human being unaided by machinery can perform.

The further proposition, very different from Turing's own thesis, that a Turing machine can compute whatever can be computed by any machine working on finite data in accordance with a finite program of instructions, is sometimes also referred to as (a version of) the Church-Turing thesis or Church's thesis. For example, Smolensky says:

connectionist models ... may possibly even challenge the strong construal of Church's Thesis as the claim that the class of well-defined computations is exhausted by those of Turing machines. (Smolensky 1988: 3.)

This loosening of established terminology is unfortunate, for neither Church nor Turing endorsed, or even formulated, this further proposition. There are numerous examples of this extended usage in the literature. The following are typical.

That there exists a most general formulation of machine and that it leads to a unique set of input-output functions has come to be called Church's thesis . (Newell 1980: 150.) [T]he work of Church and Turing fundamentally connects computers and Turing machines. The limits of Turing machines, according to the Church-Turing thesis, also describe the theoretical limits of all computers. (McArthur 1991: 401.) [I]t is difficult to see how any language that could actually be run on a physical computer could do more than Fortran can do. The idea that there is no such language is called Church's thesis. (Geroch and Hartle 1986: 539.)

Also (more distant still from anything that Church or Turing actually wrote):

I can now state the physical version of the Church-Turing principle: "Every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means." This formulation is both better defined and more physical than Turing's own way of expressing it. (Deutsch 1985: 99.)

This formulation may be ‘more physical’ than Turing's own, but it is scarcely ‘better defined’. The notion of an effective method played an important role in early debates about the foundations of mathematics, and it was sufficiently clear to allow Turing, Church, and others to recognize that different formal accounts gave alternative modellings of the notion. Their notion was certainly not that of a ‘finitely realizable physical system’.

Gandy (1980) is one of the few writers to distinguish explicitly between Turing's thesis and the stronger proposition that whatever can be calculated by a machine can be calculated by a Turing machine. Borrowing Gandy's terminology, I will call the stronger proposition ‘Thesis M’. I will use expressions such as ‘the Church-Turing thesis properly so-called’ for the proposition that Church and Turing themselves endorsed.

Thesis M : Whatever can be calculated by a machine (working on finite data in accordance with a finite program of instructions) is Turing-machine-computable.

Thesis M itself admits of two interpretations, according to whether the phrase "can be generated by a machine" is taken in the narrow, this-worldly, sense of "can be generated by a machine that conforms to the physical laws (if not to the resource constraints) of the actual world", or in a wide sense that abstracts from the issue of whether or not the notional machine in question could exist in the actual world. Under the latter interpretation, thesis M is false. It is straightforward to describe notional machines, or ‘hypercomputers’ ( Copeland and Proudfoot (1999a)) that generate functions not Turing-machine-computable (see e.g. Abramson (1971), Copeland (2000), Copeland and Proudfoot (2000), Stewart (1991)). It is an open empirical question whether or not the narrow this-worldly version of thesis M is true. Speculation that there may be physical processes -- and so, potentially, machine-operations -- whose behaviour conforms to functions not computable by Turing machine stretches back over at least five decades; see, for example, da Costa and Doria (1991), (1994), Doyle (1982), Geroch and Hartle (1986), Hogarth (1994), Kreisel (1967), (1974), (1982), Pour-El and Richards (1979), (1981), Scarpellini (1963), Siegelmann and Sontag (1994), and Stannett (1990). (Copeland and Sylvan (1999) is a survey; see also Copeland and Proudfoot (1999b).)

The literature on the computational theory of the mind contains numerous endorsements of propositions equivalent or similar to thesis M that are supported by nothing more than a nod toward Turing or Church (as is illustrated by a number of the quotations given earlier). Perhaps some writers are simply misled by the terminological practice whereby a thesis concerning which there is little real doubt, the Church-Turing thesis properly so called, and a different thesis of unknown truth-value, are referred to indiscriminately as Church's thesis or the Church-Turing thesis -- albeit with accompanying hedges like ‘strong form’ and ‘physical version’. Other writers may maintain thesis M (or some equivalent or near equivalent) on the spurious grounds that the various, and prima facie very different, attempts -- by Turing, Church, Post, Markov, and others -- to characterise in precise terms the informal notion of an effective procedure have turned out to be equivalent to one another. This is evidence concerning the extent of effective procedures, and not evidence concerning the extent of what can be calculated by machine.

The error of confusing the Church-Turing thesis properly so-called with thesis M has led to some remarkable claims in the foundations of psychology. For example, one frequently encounters the view that psychology must be capable of being expressed ultimately in terms of the Turing machine (e.g. Fodor 1981: 130; Boden 1988: 259). To one who makes the error, conceptual space will seem to contain no room for mechanical models of the mind that are not equivalent to Turing machines.Yet it is certainly possible that psychology will find the need to employ models of human cognition that transcend Turing machines.

Note that in some cases, an author's apparent endorsement of M is merely apparent. In this connection, it is important to remember that in the technical literature the word ‘computable’ is often tied by definition to effective calculability. Thus a function is said to be computable if and only if there is an effective procedure for determining its values. Accordingly, a common formulation of the Church-Turing thesis in the technical literature and in textbooks is:

All computable functions are computable by Turing machine.

Corollaries such as the following are sometimes offered:

certain functions are uncomputable in an absolute sense: uncomputable even by [Turing machine], and, therefore, uncomputable by any past, present, or future real machine. (Boolos and Jeffrey 1980: 55.)

Given the definition of ‘computable’ as ‘effectively calculable’, the Church-Turing thesis does entail that if a function f is not computable by Turing machine then it is not computable by any machine. However, to a casual reader of the technical literature, such statements may appear to say more than they in fact do. (Of course, the decision to tie the term ‘computable’ and its cognates to the concept of effectiveness does not settle the truth-value of thesis M. Those who abide by this terminological decision are simply prevented from describing a machine that falsifies thesis M as computing the function that it generates.)

The word ‘mechanical’, too, in technical usage, is tied to effectiveness and, as already remarked, ‘mechanical’ and ‘effective’ are used interchangeably. (Gandy (1988) outlines the history of this usage of the word ‘mechanical’.) Thus statements like the following are to be found in the technical literature:

Turing proposed that a certain class of abstract machines could perform any ‘mechanical’ computing procedure. (Mendelson 1964: 229.)

Understood correctly, this remark attributes to Turing not thesis M but the Church-Turing thesis. This usage of ‘mechanical’ tends to obscure the possibility that there may be machines, or biological organs, that calculate (or compute, in a broad sense) functions that are not Turing-machine-computable. For the question ‘Can a machine execute a procedure that is not mechanical?’ may appear self-answering, yet this is precisely what is asked if thesis M is questioned.

Thesis M is not the only problematic thesis that is linked to the Church-Turing thesis. An error which, unfortunately, is common in modern writing on computability and the brain is to hold that Turing's results somehow entail that the brain, and indeed any biological or physical system whatever, can be simulated by a Turing machine. For example, the entry on Turing in the recent A Companion to the Philosophy of Mind contains the following claims: "we can depend on there being a Turing machine that captures the functional relations of the brain", for so long as "these relations between input and output are functionally well-behaved enough to be describable by ... mathematical relationships ... we know that some specific version of a Turing machine will be able to mimic them" (Guttenplan 1994: 595). Searle writes in a similar fashion:

Can the operations of the brain be simulated on a digital computer? ... The answer seems to me ... demonstrably ‘Yes’ ... That is, naturally interpreted, the question means: Is there some description of the brain such that under that description you could do a computational simulation of the operations of the brain. But given Church's thesis that anything that can be given a precise enough characterization as a set of steps can be simulated on a digital computer, it follows trivially that the question has an affirmative answer. (Searle 1992: 200.)

So too Johnson-Laird, and the Churchlands:

If you assume that [consciousness] is scientifically explicable ... [and] [g]ranted that the [Church-Turing] thesis is correct, then ... [i]f you believe [functionalism] to be false ... then ... you [should] hold that consciousness could be modelled in a computer program in the same way that, say, the weather can be modelled ... [and if] you accept functionalism ... you should believe that consciousness is a computational process. (Johnson-Laird 1987: 252.)

Church's Thesis says that whatever is computable is Turing computable. Assuming, with some safety, that what the mind-brain does is computable, then it can in principle be simulated by a computer. (Churchland and Churchland 1983: 6.)

As previously mentioned, Churchland and Churchland seem to believe, erroneously, that Turing's "results entail ... that a standard digital computer, given only the right program, a large enough memory and sufficient time, can ... display any systematic pattern of responses to the environment whatsoever" (1990: 26). (They do not explicitly restrict talk of ‘systematic patterns’ to ones that are effectively calculable.) This no doubt explains why they think they can assume "with some safety" that what the mind-brain does is computable, for on their understanding of matters this is to assume only that the mind-brain exhibits a systematic pattern of responses, or is characterised by a ‘rule-governed’ (1990: 26) input-output function.

The Church-Turing thesis does not entail that the brain (or the mind, or consciousness) can be modelled by a Turing machine program, not even in conjunction with the belief that the brain (or mind, etc.) is scientifically explicable, or exhibits a systematic pattern of responses to the environment, or is ‘rule-governed’ (etc.). Each of the authors quoted seems to be assuming the truth of a close cousin of thesis M, which I will call

Thesis S: Any process that can be given a mathematical description (or that is scientifically describable or scientifically explicable) can be simulated by a Turing machine.

As with thesis M, neither the Church-Turing thesis properly so-called nor any result proved by Turing or Church entails thesis S. This is so even when the thesis is taken narrowly, as concerning processes that conform to the physics of the real world. (Thesis S taken in the wide sense is known to be false; see the references given earlier re the wide version of thesis M.) Any device or organ whose internal processes can be described completely by means of effectively calculable functions can be simulated exactly by a Turing machine program (provided that the input into the device or organ is itself Turing-machine-computable, which is to say, is either finite or expressible as a computable number, in Turing's sense (which is explained below)); but any device or organ whose mathematical description involves functions that are not effectively calculable cannot be so simulated. As Turing showed, there are uncountably many such functions. (Examples from logic are Turing's famous halting function (described in the entry on Turing machines) and the function D whose domain is the set of well-formed formulae of the predicate calculus and whose values, D(x), are 1 or 0 according to whether x is, or is not, derivable from the Bernays-Hilbert-Ackermann axioms for predicate logic.) It is an open question whether a completed neuroscience will employ functions that are not effectively calculable.

Turing introduces his machines with the intention of providing an idealised description of a certain human activity, the tedious one of numerical computation , which until the advent of automatic computing machines was the occupation of many thousands of people in business, government, and research establishments. He prefaces his first description of a Turing machine with the words:

We may compare a man in the process of computing a ... number to a machine. (Turing 1936: 231.)

The Turing machine is a model, idealised in certain respects, of a human being calculating in accordance with an effective procedure. Wittgenstein put this point in a striking way:

Turing's "Machines". These machines are humans who calculate. (Wittgenstein 1980, 1096.)

It is a point that Turing was to emphasise, in various forms, again and again. For example:

A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine. (Turing 1948: 9.)

The electronic stored-program digital computers for which the universal Turing machine was a blueprint are, each of them, computationally equivalent to a Turing machine, and so they too are, in a sense, models of human beings engaged in computation. Turing chose to emphasise this when explaining these electronic machines in a manner suitable for an audience of uninitiates:

The idea behind digital computers may be explained by saying that these machines are intended to carry out any operations which could be done by a human computer. (Turing 1950a: 436).

He makes the point a little more precisely in the technical document containing his preliminary design for the Automatic Computing Engine or ACE. (The ACE was an electronic stored-program computer built at the National Physical Laboratory, London. A pilot version first ran in 1950 and at the time was the fastest computer in the world. The commercial model was called the DEUCE.)

The class of problems capable of solution by the machine [the ACE] can be defined fairly specifically. They are [a subset of] those problems which can be solved by human clerical labour, working to fixed rules, and without understanding. (Turing 1946: 38-9.)

(Turing went on to characterise the subset in terms of the amount of paper and time available to the human clerk.) It was presumably because he considered the point under discussion to be essential for understanding the nature of the new electronic machines that he chose to begin his Programmers' Handbook for Manchester Electronic Computer with this explanation:

Electronic computers are intended to carry out any definite rule of thumb process which could have been done by a human operator working in a disciplined but unintelligent manner. (Turing 1950b: 1.)

It was not some deficiency of imagination that led Turing to model his computing machines on what could be achieved by a human computer. The purpose for which the Turing machine was invented demanded it. The Entscheidungsproblem is the problem of finding a humanly executable procedure of a certain sort, and Turing's aim was precisely to show that there is no such procedure in the case of predicate logic. He proved that no Turing machine can compute the values of the function D that I described earlier, and he argued that his model of human computation is sufficiently general, in the sense that there are no intuitively computable (i.e. effectively calculable) functions that Turing machines are incapable of computing.

The latter claim is, of course, Turing's thesis. Here are two additional formulations of the thesis, from his paper of 1936.

[T]he "computable numbers" [the numbers whose decimal representations can be generated progressively by a Turing machine] include all numbers which would naturally be regarded as computable. (Turing 1936: 249.)

It is my contention that these operations [the primitive operations of a Turing machine] include all those which are used in the computation of a number. (Turing 1936: 232.)

(As Turing explains: "Although the subject of this paper is ostensibly the computable numbers, it is almost equally easy to define and investigate computable functions ... I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique" (1936: 230).)

To understand these assertions as Turing intended them it is essential to keep in mind that when he uses the words ‘computer’, ‘computable’ and ‘computation’ he employs them not in their modern sense as pertaining to machines but as pertaining to human calculators. Many passages make this obvious.

Computers always spend just as long in writing numbers down and deciding what to do next as they do in actual multiplications, and it is just the same with ACE ... [T]he ACE will do the work of about 10,000 computers ... Computers will still be employed on small calculations ... (Turing 1947: 116, 120.)

Thus when Turing maintains that every number or function that "would naturally be regarded as computable" can be calculated by a Turing machine he is asserting not thesis M but a thesis concerning the extent of the effectively calculable numbers and functions. Similarly, when Church writes (in a review of Post (1936)):

To define effectiveness as computability by an arbitrary machine, subject to restrictions of finiteness, would seem to be an adequate representation of the ordinary notion (Church 1937b: 43),

he is to be understood not as entertaining some form of thesis M but as endorsing the identification of the effectively calculable functions with those functions that can be calculated by an arbitrary machine whose principles of operation are such as to mimic the actions of a human computer. (There is much that is ‘arbitrary’ about the machines described (independently, in the same year) by Turing and Post, for example the one-dimensional arrangement of the squares of the tape (or in Post's case, of the ‘boxes’), the absence of a system of addresses for squares of the tape, the choice between a two-way and a one-way infinite tape, and, in Post's case, the restriction that a square admit of only two possible conditions, blank or marked by a single vertical stroke.)

It is equally important to note also that when Turing uses the word ‘machine’ he often means not machine-in-general but, as we would now say, Turing machine. At one point he explicitly draws attention to this idiosyncratic usage:

The expression "machine process" of course means one which could be carried out by the type of machine I was considering [in Turing (1936)]. (Turing 1947: 107.)

Thus when, a few pages later, he asserts that "machine processes and rule of thumb processes are synonymous" (1947: 112), he is to be understood as advancing the Church-Turing thesis (and its converse), not a version of thesis M. Unless his intended usage is borne in mind, misunderstanding is certain to ensue. Especially liable to mislead are statements like the following, which a casual reader might easily mistake for a formulation of thesis M:

The importance of the universal machine is clear. We do not need to have an infinity of different machines doing different jobs. A single one will suffice. The engineering problem of producing various machines for various jobs is replaced by the office work of "programming" the universal machine to do these jobs. (Turing 1948: 7.)

In context it is perfectly clear that these remarks concern machines equivalent to Turing machines (the passage is embedded in a discussion of LCMs).

Whether or not Turing would, if queried, have assented to thesis M is unknown. There is certainly no textual evidence in favour of the common belief that he did so assent.

• Abramson, F.G. 1971. ‘Effective Computation over the Real Numbers’. Twelfth Annual Symposium on Switching and Automata Theory . Northridge, Calif.: Institute of Electrical and Electronics Engineers.
• Boden, M.A. 1988. Computer Models of Mind . Cambridge: Cambridge University Press.
• Boolos, G.S., Jeffrey, R.C. 1980. Computability and Logic . 2nd edition. Cambridge: Cambridge University Press.
• Church, A. 1932. ‘A set of Postulates for the Foundation of Logic’. Annals of Mathematics , second series, 33, 346-366.
• –––. 1936a. ‘An Unsolvable Problem of Elementary Number Theory’. American Journal of Mathematics , 58, 345-363.
• –––. 1936b. ‘A Note on the Entscheidungsproblem’. Journal of Symbolic Logic , 1, 40-41.
• –––. 1937a. Review of Turing 1936. Journal of Symbolic Logic , 2, 42-43.
• –––. 1937b. Review of Post 1936. Journal of Symbolic Logic , 2, 43.
• –––. 1941. The Calculi of Lambda-Conversion . Princeton: Princeton University Press.
• Churchland, P.M., Churchland, P.S. 1983. ‘Stalking the Wild Epistemic Engine’. Nous , 17, 5-18.
• –––. 1990. ‘Could a Machine Think?’. Scientific American , 262 (Jan.), 26-31.
• Copeland, B.J. 1998. ‘Turing's O-machines, Penrose, Searle, and the Brain’. Analysis , 58, 128-138.
• –––. 2000. ‘Narrow Versus Wide Mechanism’. Journal of Philosophy , 97, 5-32.
• –––., Proudfoot, D. 1999a. ‘Alan Turing's Forgotten Ideas in Computer Science’. Scientific American , 280 (April), 76-81.
• –––., Proudfoot, D. 1999b. ‘The Legacy of Alan Turing’. Mind , 108, 187-195.
• –––., Proudfoot, D. 2000. ‘What Turing Did After He Invented the Universal Turing Machine’. Journal of Logic, Language, and Information , 9, 491-509.
• –––., Sylvan, R. 1999. ‘Beyond the Universal Turing Machine’. Australasian Journal of Philosophy , 77, 46-66.
• Curry, H.B. 1929. ‘An Analysis of Logical Substitution’. American Journal of Mathematics , 51, 363-384.
• –––. 1930. ‘Grundlagen der kombinatorischen Logik’. American Journal of Mathematics , 52, 509-536, 789-834.
• –––. 1932. ‘Some Additions to the Theory of Combinators’. American Journal of Mathematics , 54, 551-558.
• da Costa, N.C.A., Doria, F.A. 1991. ‘Classical Physics and Penrose's Thesis’. Foundations of Physics Letters , 4, 363-374.
• –––. 1994. ‘Undecidable Hopf Bifurcation with Undecidable Fixed Point’. International Journal of Theoretical Physics , 33, 1913-1931.
• Dennett, D.C. 1991. Consciousness Explained . Boston: Little, Brown.
• –––. 1978. Brainstorms: Philosophical Essays on Mind and Psychology . Brighton: Harvester.
• Deutsch, D. 1985. ‘Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer’. Proceedings of the Royal Society , Series A, 400, 97-117.
• Doyle, J. 1982. ‘What is Church's Thesis? An Outline.’ Laboratory for Computer Science, MIT.
• Fodor, J.A. 1981. ‘The Mind-Body Problem’. Scientific American , 244 (Jan.), 124-32.
• Gandy, R. 1980. ‘Church's Thesis and Principles for Mechanisms’. In Barwise, J., Keisler, H.J., Kunen, K. (eds) 1980. The Kleene Symposium . Amsterdam: North-Holland.
• –––. 1988. ‘The Confluence of Ideas in 1936’. In Herken, R. (ed.) 1988. The Universal Turing Machine: A Half-Century Survey . Oxford: Oxford University Press.
• Geroch, R., Hartle, J.B. 1986. ‘Computability and Physical Theories’. Foundations of Physics , 16, 533-550.
• Gödel, K. 1934. ‘On Undecidable Propositions of Formal Mathematical Systems’. Lecture notes taken by Kleene and Rosser at the Institute for Advanced Study. Reprinted in Davis, M. (ed.) 1965. The Undecidable . New York: Raven.
• –––. 1936. ‘Über die Lange von Beweisen’. Ergebnisse eines mathematischen Kolloquiums , 7, 23-24.
• Gregory, R.L. 1987. The Oxford Companion to the Mind . Oxford: Oxford University Press.
• Guttenplan, S. 1994. A Companion to the Philosophy of Mind . Oxford: Blackwell.
• Hogarth, M.L. 1994. ‘Non-Turing Computers and Non-Turing Computability’. PSA 1994 , vol.1, 126-138.
• Herbrand, J. 1932. ‘Sur la non-contradiction de l'arithmetique’. Journal fur die reine und angewandte Mathematik , 166, 1-8.
• Hilbert, D., Ackermann, W. 1928. Grundzüge der Theoretischen Logik . Berlin: Springer.
• Johnson-Laird, P. 1987. ‘How Could Consciousness Arise from the Computations of the Brain?’. In Blakemore, C., Greenfield, S. (eds) 1987. Mindwaves . Oxford: Basil Blackwell.
• Kalmar, L. 1959. ‘An Argument Against the Plausibility of Church's Thesis’. In Heyting, A. (ed.) 1959. Constructivity in Mathematics . Amsterdam: North-Holland.
• Kleene, S.C. 1935. ‘A Theory of Positive Integers in Formal Logic’. American Journal of Mathematics , 57, 153-173, 219-244.
• –––. 1936. ‘Lambda-Definability and Recursiveness’. Duke Mathematical Journal , 2, 340-353.
• –––. 1952. Introduction to Metamathematics . Amsterdam: North-Holland.
• –––. 1967. Mathematical Logic . New York: Wiley.
• Kreisel, G. 1967. ‘Mathematical Logic: What Has it Done For the Philosophy of Mathematics?’. In R. Schoenman (ed.) 1967. Bertrand Russell: Philosopher of the Century . London: George Allen and Unwin.
• –––. 1974. ‘A Notion of Mechanistic Theory’. Synthese , 29, 11-26.
• –––. 1982. Review of Pour-El and Richards. Journal of Symbolic Logic , 47, 900-902.
• Markov, A.A. 1960. ‘The Theory of Algorithms’. American Mathematical Society Translations , series 2, 15, 1-14.
• Mendelson, E. 1963. ‘On Some Recent Criticism of Church's Thesis’. Notre Dame Journal of Formal Logic , 4, 201-205.
• –––. 1964. Introduction to Mathematical Logic . New York: Van Nostrand.
• Newell, A. 1980. ‘Physical Symbol Systems’. Cognitive Science , 4, 135-183.
• Post, E.L. 1936. ‘Finite Combinatory Processes - Formulation 1’. Journal of Symbolic Logic , 1, 103-105.
• –––. 1943. ‘Formal Reductions of the General Combinatorial Decision Problem’. American Journal of Mathematics , 65, 197-215.
• –––. 1946. ‘A Variant of a Recursively Unsolvable Problem’. Bulletin of the American Mathematical Society , 52, 264-268.
• Pour-El, M.B., Richards, I. 1979. ‘A Computable Ordinary Differential Equation Which Possesses No Computable Solution’. Annals of Mathematical Logic , 17, 61-90.
• Pour-El, M.B., Richards, I. 1981. ‘The Wave Equation with Computable Initial Data such that its Unique Solution is not Computable’. Advances in Mathematics , 39, 215-239.
• Scarpellini, B. 1963. ‘Zwei Unentscheitbare Probleme der Analysis’, Zeitschrift fur mathematische Logik und Grundlagen der Mathematik , 9, 265-289.
• Schönfinkel, M. 1924. ‘Uber die Bausteine der mathematischen’. Mathematische Annalen , 92, 305-316.
• Searle, J. 1992. The Rediscovery of the Mind . Cambridge, Mass.: MIT Press.
• –––. 1997. The Mystery of Consciousness . New York: New York Review of Books.
• Shepherdson, J.C., Sturgis, H.E. 1963. ‘Computability of Recursive Functions’. Journal of the ACM , 10, 217-255.
• Siegelmann, H.T., Sontag, E.D. 1992. ‘On the Computational Power of Neural Nets’. Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory , 440-449.
• –––. 1994. ‘Analog Computation via Neural Networks’. Theoretical Computer Science , 131, 331-360.
• Smolensky, P. 1988. ‘On the Proper Treatment of Connectionism’. Behavioral and Brain Sciences , 11, 1-23.
• Stannett, M. 1990. ‘X-Machines and the Halting Problem: Building a Super-Turing Machine’. Formal Aspects of Computing , 2, 331-341.
• Stewart, I. 1991. ‘Deciding the Undecidable’. Nature , 352, 664-5.
• Turing, A.M. 1936. ‘On Computable Numbers, with an Application to the Entscheidungsproblem’. Proceedings of the London Mathematical Society , series 2, 42 (1936-37), 230-265.
• –––. 1946. ‘Proposal for Development in the Mathematics Division of an Automatic Computing Engine (ACE)’. In Carpenter, B.E., Doran, R.W. (eds) 1986. A.M. Turing's ACE Report of 1946 and Other Papers . Cambridge, Mass.: MIT Press.
• –––. 1947. ‘Lecture to the London Mathematical Society on 20 February 1947’. In Carpenter, B.E., Doran, R.W. (eds) 1986. A.M. Turing's ACE Report of 1946 and Other Papers . Cambridge, Mass.: MIT Press.
• –––. 1948. ‘Intelligent Machinery’. National Physical Laboratory Report. In Meltzer, B., Michie, D. (eds) 1969. Machine Intelligence 5 . Edinburgh: Edinburgh University Press. (Digital facsimile viewable athttp://www.AlanTuring.net/intelligent_machinery.)
• –––. 1950a. ‘Computing Machinery and Intelligence’. Mind, 59, 433-460.
• –––. 1950b. ‘Programmers' Handbook for Manchester Electronic Computer’. University of Manchester Computing Laboratory. (Digital facsimile viewable athttp://www.AlanTuring.net/programmers_handbook.)
• –––. 1951a. ‘Can Digital Computers Think?’. In Copeland, B.J. (ed.) 1999. ‘A Lecture and Two Radio Broadcasts on Machine Intelligence by Alan Turing’. In Furukawa, K., Michie, D., Muggleton, S. (eds) 1999. Machine Intelligence 15 . Oxford: Oxford University Press.
• –––. 1951b (circa). ‘Intelligent Machinery, A Heretical Theory’. In Copeland, B.J. (ed.) 1999. ‘A Lecture and Two Radio Broadcasts on Machine Intelligence by Alan Turing’. In Furukawa, K., Michie, D., Muggleton, S. (eds) 1999. Machine Intelligence 15 . Oxford: Oxford University Press.
• Wittgenstein, L. 1980. Remarks on the Philosophy of Psychology . Vol.1. Oxford: Blackwell.
• The Turing Archive for the History of Computing

-->Church, Alonzo --> | computing: modern history of | -->mind: philosophy of --> | Turing, Alan | Turing machines

Search anything:

Church Turing Thesis in Theory of Computation

Theory of computation.

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we have explain the meaning and importance of Church Turing Thesis in Theory of Computation along with its applications and limitations.

Table of contents:

• Introduction to Turing Church Thesis

Applications of Church Turing Thesis

Limitations of church turing thesis.

Prerequisites: Algorithms, Turing Machine

Let us get started with Church Turing Thesis in Theory of Computation.

Definition of Church Turing Thesis

Church Turing Thesis states that:

A computation process that can be represented by an algorithm can be converted to a Turing Machine.

In simple words, any thing that can be done by an Algorithm can be done by a Turing Machine as well. So, all algorithms can be implemented in a Turing Machine.

Specific Computation Models are equivalent which means any one model can be coverted to another model. These Computation Models include:

• One tape Turing Machine
• K tape Turing Machine where K >= 1
• Non Deterministic Turing Machine
• Programs in Programming Languages such as Java, C++, Lisp and others.

So, a program in C++ can be converted to a K tape Turing Machine and vice versa.

The applications of Church Turing Thesis are as follows:

• Church Turing Thesis is used to define an Algorithm (traditionally)
• Used in solving 10th Problem by Hilbert.
• Used in defining modern computing devices including Molecular and Quantum Computers.

10th Problem by Hilbert

It has been used to solve the 10th Problem by Hilbert in 8th August 1900 at the Second International Congress of Mathematicians in Paris. These problems were listed as critical problems that should be solved for progress in Mathematics.

The 10th Problem by Hilbert was:

Does there exists a process with finite number of steps that can determine if a given polynomial with integer coefficients has integral roots?

Another way to look at the problem is to find if there is an Algorithm to find if there exists an integral root for a given polynomial or not.

For example: This is a Polynomial:

35x 10 y 2 z 9 + 11x 6 z 7 + 103xyz + 17y 31 z 3 = 0.

Is there an algorithm that can find if there exist a solution in integers?

Note the solution is not needed. Only we need to find if such a solution exists or not.

In 1970, it was proved that no such algorithm exists. This was done by Matiyasevich.

Algorithm = Church Turing Thesis

To solve the 10th Hilbert Problem, one needs to understand what is meant by an algorithm. In fact, there have been different definitions and all have proved to be equivalent. Some definitions were:

• 1936: Algorithm = Turing Machine
• 1936: Algorithm = Lambda Calculus
• 1970+: Algorithm = Implementation in Programming Languages like C and Lisp
• Final: Algorithm = process converted to Turing Machine.

Finally, it was agreed that an Algorithm is based on Church Turing Thesis which said:

"Any computational process can be considered as an Algorithm if it can be converted to a Turing Machine." Note: This does not hold true as of now.

Modern Computing Devices

Traditional Computers which are in use today, are limited by Church Turing Thesis. This is because Church Turing Thesis defines an Algorithm which can be implemented in a real system.

Therefore, the Computing Device you are using is basically a Turing Machine.

The only difference is that Computing Devices are efficient while Turing Machine is inefficient. Theoretically, from a point of view of algorithms, there is no difference.

There are 3 different approaches future computers may take:

• Quantum Computer : Solve Computing Problems using atoms by quantum rules. This is an active area of research.
• Molecular Computer : Solve Computing Problems using Molecules by taking advantage of Physical laws of Moleculars. This includes replicating the idea of DNA.
• Super Recursive Algorithm : This domain has not been realized yet and exists in theory but this is the part where Church Turing Thesis fail. We have covered this in the next section on "Limitations of Church Turing Thesis".

Two different futuristic models of Computer which follows Church Turing Thesis:

• Quantum Computers can be represented as Non Deterministic Turing Machine
• Molecular Computers can be represented by Turing Machine with many tapes and heads

Therefore, Quantum and Molecular Computers are same fundamentally and they are only more efficient than Mechnical Computers.

Super Recursive Algorithms proved Church Turing Thesis wrong. The first Super Recursive algorithm was introduced in 1965 by Mark Gold and Hillary Putnam by using ideas of limit recursive and limit partial recursive functions. It was based on ideas from non standard analysis by Abraham Robinson in 1966 and Inductive Definition of sets by Spector in 1959. This resulted in Inductive Inference by Gasarch and Smith in 1997 and is used in Machine Learning.

Super Recursive Algorithms can solve problems that are unsolvable by Turing Machines. To account for this, a new idea was introduced: Inductive Turing Macine. These were not accepted as Algorithm for a long time as it was refuting Church Turing Thesis and Godel Incompleteness Theorem (as proved in 1987 by Burgin).

The idea of Inductive Turing Machine is as follows:

• Turing Machine has a property that it stops after giving a result.
• Most programs stop after giving a result and this seems to be reasonable as what a program should do once it has found the answer.
• Operating Systems are also programs but it does not give a standard output. It gives some strings to the users during its use but it cannot be considered as a output. The functionality of an Operating System is considered to be the output. It does not stop like standard program. If it stops, it cannot give any output.
• There can be programs which give a result at the moment which is good enough but
• This idea of not stopping after giving a result is the basis.

Inductive Turing Machine is more powerful than Conventional Turing Machine. Inductive Turing Machine can solve the Halting Problem which is known to be unsolvable by Conventional Turing Maching.

There are different types of Inductive Turing Machine:

• Inductive Turing Machine + Structured Memory
• Inductive Turing Machine + Structured Rules (control device)
• Inductive Turing Machine + Structured Head (Operating Device)

Today, Church Turing Thesis is not considered as an Universal Principle. Inductive Turing Machine is the most powerful super recursive algorithm.

This lead to the formulation of "Extended Church Turing Thesis".

There are three open questions:

• How to realize Super Recursive algorithms in technological devices?
• How modern computing devices are related to Super Recursive Algorithm?
• What are the new possibilities with Super Recursive Algorithm?

Think about these research open ended problems in Theory of Computation.

With this article at OpenGenus, you must have the complete idea of Church Turing Thesis in Theory of Computation.

www.springer.com The European Mathematical Society

• StatProb Collection
• Recent changes
• Current events
• Random page
• Project talk
• Request account
• What links here
• Related changes
• Special pages
• Printable version
• Permanent link
• Page information
• View source

Turing machine

2020 Mathematics Subject Classification: Primary: 68Q05 [ MSN ][ ZBL ]

The name attached to abstract computers (cf. Computer, abstract ) of a specific type. The concept of a machine of such a kind originated in the middle of the 1930's from A.M. Turing as the result of an analysis carried out by him of the actions of a human being carrying out some or other calculations in accordance with a plan worked out in advance, that is, carrying out successive transformations of complexes of symbols. This analysis, in turn, was carried out by him with the aim of solving the then urgent problem of finding a precise mathematical equivalent for the general intuitive idea of an algorithm . In the course of development of the theory of algorithms (cf. Algorithms, theory of ), there emerged a number of modifications of the original definition of Turing. The version given here goes back to E. Post [2] ; in this form the definition of a Turing machine has achieved widespread popularity (the Turing machine has been described in detail, for example, in [3] and [4] ).

• 1 Definition of a Turing Machine
• 2 Configurations
• 3 Representing Algorithms by Turing Machines
• 4.1 Operational Views
• 4.2 Multi-Tape Turing machines
• 4.3 Nondeterministic Turing machines
• 4.4 Probabilistic Turing machines
• 6 References

Definition of a Turing Machine

A Turing machine is conveniently represented as an automatically-functioning system capable of being in a finite number of internal states and endowed with an infinite external memory, called a tape. Two of the states are distinguished, the initial state and the final state. The tape is divided into cells and is unbounded to the left and to the right. Any letter of some finite alphabet $\Gamma$ can be printed on each cell of the tape (for the sake of uniformity, it is convenient to regard an empty cell as being printed with a "blank" $\sqcup\in\Gamma$ ). At each moment of discrete time the Turing machine is in one of its states, and by scanning one of the cells of its tape it perceives the symbol written there (a letter of the alphabet $\Gamma$).

If the Turing machine is in a non-final state at some moment of time, it completes a step, which is completely determined by its current state and the symbol that is perceived on the tape at this moment. A step consists of the following: 1) print a new symbol in the scanned cell, which may be the same as the old symbol or a blank; 2) go to a new state, which may be the same as the old one or the final state; and 3) move the tape to the left or to the right by one cell, or keep it in the same place. The list of all possible steps of the Turing machine in dependence on the current combination of "non-final state + symbol perceived" can be represented, for example, by a special table with two inputs, called the program, or scheme, of the given Turing machine. The codes of the corresponding steps of the machine, called its commands, are placed in the cells of this table. The program of the Turing machine is an object with a given structure, and one can stipulate that the Turing machine be identified with its program. If one wants to emphasize the connection of such a Turing machine with the alphabet $\Gamma$, then one usually says that this machine is a Turing machine in the alphabet $\Gamma$.

Following this description, a Turing machine is formally defined as 7-Tupel $(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ consisting of:

• $Q$, a finite set of states
• $\Sigma$, a finite input/output alphabet; a typical choice is $\Sigma=\{0,1\}$
• $\Gamma$, a finite tape alphabet $\Sigma\subseteq\Gamma$
• $\sqcup\in \Gamma$, a blank symbol with $\sqcup \notin \Sigma$
• $q_0 \in Q$, a start state
• $q_f \in Q$, a stop state
• $\delta: Q\setminus \{q_f\}\times\Gamma \rightarrow Q\times\Gamma\times\{L, R, N\}$, a partially defined tranistion function

If $\delta(q,a)$ is undefined, the machine will halt. The set $\{L, R, N\}$ means that in a transition the tape can be moved to the left or right one cell or can be kept at the same place.

A nontrivial example of a Turing Machine accepting primes is given in [a6] .

Configurations

The complete description of the current state of a Turing machine is given by its configuration, consisting of the following information at the given moment: 1) the actual symbols filling the cells of the tape; 2) the cell currently being scanned by the machine; and 3) the internal state of the machine. A configuration corresponding to the final state of the Turing machine is also called final. Following the convention to ignore the two empty parts of the tape to the left and to the right, the space of configurations is given as $C:=\Gamma^*\times \mathbb{Z}\times Q$. Obviously, the transition function $\delta: Q\setminus \{q_f\}\times\Gamma \rightarrow Q\times\Gamma\times \{L, R, N\}$ can be reformulated as a function $\delta\colon C \longrightarrow C$ operating on the space of configurations.

If some non-final configuration of the Turing machine is fixed as the initial configuration, then the functioning of this machine will consist of a (step by step) sequential transformation starting with the initial configuration in accordance with the machine's program until the time of attaining a final configuration. After this, the functioning of the Turing machine is considered ended and the final configuration attained is regarded as the result of the functioning of the machine. Of course, the functioning of the Turing machine does not, in general, terminate for every initial configuration.

Representing Algorithms by Turing Machines

The notion of a Turing machine can be used for making precise the general idea of an algorithm in a given alphabet, as follows. By a Turing algorithm in an alphabet $\Gamma$ is meant any algorithm $\mathcal{A}$ of the following kind. One takes a fixed Turing machine $\mathcal{M}$ in the alphabet $\Gamma$. Let $P\in (\Gamma\setminus\{\sqcup\})^\ast$ be the word taken as the initial data for the algorithm $\mathcal{A}$. The following initial configuration of the machine $\mathcal{M}$ is constructed: 1) the word $P$ is written on the tape without gaps, the remaining cells being left empty (i.e. blank); 2) the machine $\mathcal{M}$ is set up to scan the cell with the first letter of the word $P$; and 3) $\mathcal{M}$ is put into the initial state (if $P$ is empty, then the tape is chosen to be empty, and the scanned cell is any cell). Suppose that $\mathcal{M}$, starting from this initial configuration, completes its functioning. Consider the cell of the tape being scanned by $\mathcal{M}$ in the final configuration. If the symbol printed on it is blank, then $\mathcal{A}(P)$ is taken to be the empty word. Otherwise, $\mathcal{A}(P)$ is taken to be the word printed on the maximum segment of the tape including the scanned cell and not containing any blanks.

There are strong grounds for supposing that the precise description of the general idea of an algorithm in an alphabet carried out by means of the notion of a Turing machine is adequate. Namely, it is held that for every algorithm $\mathcal{A}$ in some alphabet it is possible to construct a Turing algorithm giving the same results under the same initial data as the algorithm $\mathcal{A}$. This convention is known in the theory of algorithms as the Turing thesis. The acceptance of the Turing thesis is equivalent to the acceptance of the Church thesis (for partial recursive functions) or the normalization principle (for normal algorithms, cf. Normal algorithm ). However, in contrast to the latter two, the Turing thesis is immediately highly convincing. In fact, by carrying out computations according to a selected plan, the mathematician acts in a way similar to a Turing machine: in considering some position in his writings and being in a certain "state of mind" , he makes the necessary alterations in his writing, is inspired by a new "state of mind" , and goes on to contemplate further writing. The fact that he completes more complicated steps than a Turing machine seems not principally significant.

In terms of the structure of their description and the type of functioning, Turing machines are automata of a very general kind, so that Turing's conception has to a considerable extent stimulated the origin of the abstract theory of automata and largely predetermined their particular properties (cf. Automaton ; Automata, theory of ).

The Zoo of Turing Machine Definitions

There are many modifications of Turing machines.

Operational Views

The operation of a Turing machine can be seen from several different prespectives

Multi-Tape Turing machines

The most widespread are multi-tape Turing machines, with one or several heads for each of its tapes. The motion of the heads and the printing of the letters on the tape are carried out simultaneously according to the program of the control system. Multi-tape Turing machines are conveniently used in the formalization of the notion of a relative algorithm. Thus, a function $f$ is (algorithmically) computable relative to a function $g$ if there exists a multi-tape Turing machine that computes $f$ under the condition that in any initial configuration all the values of $g$ are printed in fixed order on one of the tapes. In this form one can, in terms of relative computations, introduce the important notion of Turing reducibility in the theory of algorithms, as well as other forms of algorithmic reducibility . It is natural to formalize the concept of a probabilistic algorithm by means of multi-tape Turing machines. A common approach consists of the following: A random sequence is printed on one of the tapes of the multi-tape Turing machine; the Turing machine then deals with exactly one symbol of this sequence at each instant. In a second approach, the program of the control system of the Turing machine will allow the existence of several commands with the same left-hand sides, the choice of one or other of the commands then being carried out with prescribed probabilities.

Nondeterministic Turing machines

The notion of a nondeterministic Turing machine is based on an idea similar to multi-tape machines. Here again, the program of the control system can have several commands with the same left-hand sides. In both cases, instead of a single computation for a given input, one considers the class of all possible computations compatible with the program. For probabilistic Turing machines the probability of such computations is considered; for non-deterministic Turing machines one considers the possibility of the computation itself.

Probabilistic Turing machines

A Probabilistic Turing machine is a modification of the Turing machine allowing a randomized computation.

See also Algorithm, complexity of description of an ; Algorithm, computational complexity of an ; Complexity theory ; Computable function ; Formal languages and automata ; Machine ; Undecidability . Consult [a1] and [a2] for the importance of a Turing machine as a formalization of the intuitive notion of an algorithm and for the Church thesis, as well as for the relation of Turing machines to complexity theory in general.

• Numerical analysis and scientific computing
• Computer science
• This page was last edited on 28 December 2013, at 12:40.
• Privacy policy
• About Encyclopedia of Mathematics
• Disclaimers
• Impressum-Legal

Christian Ethics Class

Join us sundays 6pm.

Topics We Cover!

What is christian ethics, what is our source for ethical standards, is it right to tell a lie to protect human life, is it ever right to disobey the government, can a person who committed suicide be forgiven, is it right to put to death a person in great pain with no hope of recovery.

Notes from the class!

Join in the conversations.