define church turing thesis

• 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

• Turing machine for subtraction | Set 1
• Turing Machine for subtraction | Set 2
• Turing machine for 1's and 2’s complement
• Turing machine for multiplication
• Restricted Turing Machines
• Turing Machine in TOC
• Turing machine for copying data
• Turing Machine as Comparator
• Turing Machine for L = {a^n b^n | n>=1}
• Oracle Turing Machine
• Design a Turing Machine for equal number of a's and b's
• Turing Machine Simulator Using Python
• Design a Turing Machine to Generate 'ww' from 'w'
• Dovetailing in Turing Machines
• Turing Machine to accept maximum of two numbers
• Turing Machine Construction (Transducers Turing Machine) in Java
• Construct Turing Machine for incrementing Binary Number by 1
• Construct Turing Machine for L = {a^i b^j | i<j, i>0}
• Significance of Turing Test

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?

• 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

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons

Margin Size

• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

3.1.9: The Church-Turing Thesis

• Last updated
• Save as PDF
• Page ID 121737

• Richard Zach et al.
• Open Logic Project

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

Turing machines are supposed to be a precise replacement for the concept of an effective procedure. Turing thought that anyone who grasped both the concept of an effective procedure and the concept of a Turing machine would have the intuition that anything that could be done via an effective procedure could be done by Turing machine. This claim is given support by the fact that all the other proposed precise replacements for the concept of an effective procedure turn out to be extensionally equivalent to the concept of a Turing machine —that is, they can compute exactly the same set of functions. This claim is called the Church-Turing thesis .

Definition \(\PageIndex{1}\): Church-Turing thesis

The Church-Turing Thesis states that anything computable via an effective procedure is Turing computable.

The Church-Turing thesis is appealed to in two ways. The first kind of use of the Church-Turing thesis is an excuse for laziness. Suppose we have a description of an effective procedure to compute something, say, in “pseudo-code.” Then we can invoke the Church-Turing thesis to justify the claim that the same function is computed by some Turing machine, even if we have not in fact constructed it.

The other use of the Church-Turing thesis is more philosophically interesting. It can be shown that there are functions which cannot be computed by Turing machines. From this, using the Church-Turing thesis, one can conclude that it cannot be effectively computed, using any procedure whatsoever. For if there were such a procedure, by the Church-Turing thesis, it would follow that there would be a Turing machine. So if we can prove that there is no Turing machine that computes it, there also can’t be an effective procedure. In particular, the Church-Turing thesis is invoked to claim that the so-called halting problem not only cannot be solved by Turing machines, it cannot be effectively solved at all.

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:

• .999... = 1
• log 2 log (Khinchin's constant)

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

The Church-Turing Thesis

• First Online: 26 March 2016

Cite this chapter

• Bernhard Reus 3  

Part of the book series: Undergraduate Topics in Computer Science ((UTICS))

2735 Accesses

1 Citations

The computability results discussed so far used WHILE -programs as choice of “effective procedures”. In this chapter we show that they do not depend on this particular choice of WHILE . Various other (well known) notions of computation are formally introduced. This list includes machine languages like Turing machines, random access memory machines and counter machines, for which a program consists of a sequence of labelled instructions, and jumps are the only control flow mechanisms. We also consider a flow chart language and cellular automata. It is then argued, by means of compilation, that all these languages are equally powerful in the sense that anything that can be programmed in one can be also programmed in any other. This provides evidence for the so-called Church-Turing thesis, that all reasonable formalizations of the intuitive notion of effective computability are equivalent.

For computability considerations, does it matter which programming languages we use?

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

• Available as EPUB and PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Church acknowledges in [ 5 ] Kleene’s contributions.

Andrew Hodges (born 1949) is a British mathematician and author of the bestselling biography “Alan Turing—The Enigma” [ 14 ] the original 1983 edition of which is the loose (unauthorised) basis for the stage play “Breaking the Code” in 1986 and the movie “The Imitation Game” in 2014.

This will be discussed in Exercise 9.

The language was designed by John Kemeny and Thomas Kurtz in 1964 [ 8 ] and was one of the first intended for interactive use.

After all, we have not restricted the length of the tapes for Turing machines.

We have not restricted the size of trees that can be stored in variables of WHILE -programs either.

Born 26 December 1937, John Conway is a British mathematician working in the area of finite groups, number theory, combinatorial game theory and others. He is a Fellow of the Royal Society and professor in Applied and Computational Mathematics at Princeton University.

John von Neumann (December 28, 1903–February 8, 1957) was a Hungarian-born American scientist famous for contributions to various fields, e.g. mathematics, game theory, statistics, and of course computing that all had significant impact. The single-processor, stored-program computer architecture is, for instance, now known as von Neumann machine (or architecture).

Thus, cellular automata are often referred to as “non-standard computation”.

http://www.youtube.com/watch?v=E8kUJL04ELA .

Edward Forrest Moore (November 23, 1925–June 14, 2003) was an American professor of mathematics and computer science, who among other things defined the Moore finite state machine.

This is in analogy with unbounded size of Turing machine tapes.

So nothing can be created out of thin air, i.e. in an entirely “dead” neighbourhood.

This corresponds to the definition of the initial state for a Turing machine where only a finite part is not blank (the input word). This condition could be dropped but then we would have to consider also Turing machine computation with infinite non-empty initial tape or Turing machines with oracles which is not covered in this book.

The concept of “stabilizing computation” is also important for Chemical Reaction Networks in Sect.  22.4 .

Other patterns may need a longer interval to repeat their original state.

An excellent and efficient simulator for Life is “Golly” available for all (including mobile) platforms, see [ 11 ].

Ralph William Gosper (born 1943) is an American mathematician and programmer famous for his puzzles and among other things his discoveries of moving oscillators in Life .

Stephen Wolfram (born 29 August 1959) is a British physicist, computer scientist and entrepreneur, most famous for being the chief designer of Mathematica published by Wolfram Research whose CEO he is as well.

Issues of how long it takes are covered in the next part of the book about complexity. Other issues, for instance, how easy or convenient it is to program in those languages are not systematically studied here.

Or, seen from the other direction, that the source language can be simulated by the target language.

Without any problem one can generalise this by also encoding the data type of the source language in the data type of the target language. However, this significantly complicates the presentation, so we leave this out. More can be found in [ 15 ].

In other words, the compilation is the identity function.

OR, AND, and NOT gates.

See also: http://www.youtube.com/watch?v=My8AsV7bA94 .

Adamatzky, A. (ed.): Game of Life Cellular Automata. Springer, Berlin (2010)

Google Scholar  

Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for Your Mathematical Plays: Volume 2. Academic Press, New York (1982)

MATH   Google Scholar  

Böhm, C., Jacopini, G.: Flow diagrams, turing machines and languages with only two formation rules. Commun. ACM 9 (5), 366–371 (1966)

Article   MATH   Google Scholar  

Chapman, P.: Life universal computer. Available via DIALOG: http://www.igblan.free-online.co.uk/igblan/ca/index.html . 23 June 2015

Church, A.: An unsolvable problem of elementary number theory. Am. J. Math. 58 (2), 345–363 (1936)

Article   MathSciNet   MATH   Google Scholar  

Cook, M.: Universality in elementary cellular automata. Complex Syst. 15 , 1–40 (2004)

MathSciNet   MATH   Google Scholar  

Copeland, J.: The Church-Turing Thesis. In: References on Alan Turing. Available via DIALOG. http://www.alanturing.net/turing_archive/pages/Reference%20Articles/The%20Turing-Church%20Thesis.html . 2 June 2015 (2000)

Dartmouth College Computation Center: A manual for BASIC, the elementary algebraic language design for use with the dartmouth time sharing system. 1 Oct 1964. Available via DIALOG: http://www.mirrorservice.org/sites/www.bitsavers.org/pdf/dartmouth/BASIC_Oct64.pdf . 23 June 2015

Gardner, M.: The fantastic combinations of John Conway’s new solitaire game life. Sci. Am. 223 , 120–123 (1970)

Article   Google Scholar  

Gardner, M.: On cellular automata, self-reproduction, the garden of eden and the game of life. Sci. Am. 224 (2), 112–117 (1971)

Golly. An open-source, cross-platform application for exploring Conway’s Game of Life. Available via DIALOG. http://golly.sourceforge.net . 30 Nov 2015

Gomard, C.K., Jones, N.D.: Compiler generation by partial evaluation: a case study. In: Ritter, G. (ed.) Proceedings of the IFIP 11th World Computer Congress, pp. 1139–1144, North-Holland (1989)

Hodges, A.: Alan turing in the stanford encyclopedia of philosophy: introduction. Available via DIALOG. http://www.turing.org.uk/publications/stanford.html . 23 June 2015

Hodges, A.: Alan Turing: The Enigma, Vintage (1992)

Jones, N.D.: Computability and complexity: From a Programming Perspective (Also available online at http://www.diku.dk/neil/Comp2book.html .). MIT Press, Cambridge (1997)

Kari, J.: Cellular automata: a survey. Theor. Comput. Sci. 334 , 3–33 (2005)

Kemeny, J.G., Kurtz, ‘.T.E.: Back to BASIC: The History, Corruption and Future of the Language. Addison-Wesley Publishing, USA (1985)

Koenig, H., Goucher, A., Greene, D.: Game of Life News. Available via DIALOG: http://pentadecathlon.com/lifeNews/index.php . 19 October 2015

Kun, J.: The cellular automaton method for cave generation. Blog post. Available via DIALOG. http://jeremykun.com/tag/cellular-automata/ . 21 July 2015

Mitchell, M.: Computation in cellular automata: A selected review. In Gramss, T., Bornholdt, S., Gross, M., Mitchell, M., Pellizzari, T. (eds.) Nonstandard Computation, pp. 95–140. VCH Verlagsgesellschaft (1998)

Packard, N.H., Wolfram, S.: Two-dimensional cellular automata. J. Stat. Phys. 38 (5–6), 901–946 (1985)

Rendell, P.: A universal turing machine implemented in conway’s game of life. Available via DIALOG. http://rendell-attic.org/gol/utm/index.htm . 21 July 2015

Rendell, P.: turing universality of the game of life. In: Adamatzky, A. (ed.) Collision-Based Computing, pp. 513–539, Springer, Berlin (2002)

Shepherdson, J.C., Sturgis, H.E.: Computability of recursive functions. J. ACM 10 (2), 217–255 (1963)

Smith III, A.R.: Simple computation-universal cellular spaces. J. ACM 18 (3), 339–353 (1971)

Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. series 2 42 (Parts 3 and 4), pp. 230–265 (1936)

Von Neumann, J., Burks, A.W.: Theory of self-reproducing automata. IEEE Trans. Neural Netw. 5 (1), 3–14 (1966)

Wainwright, R.T.: Life is universal! Proceedings of the 7th conference on Winter simulation WSC’74, Vol 2, pp. 449–459, ACM (1974)

Wolfram, S.: Computation theory of cellular automata. Commun. Math. Phys. 96 (1), 15–57 (1984)

Download references

Author information

Authors and affiliations.

Department of Informatics, School of Engineering and Informatics, University of Sussex, Brighton, UK

Bernhard Reus

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Bernhard Reus .

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this chapter

Reus, B. (2016). The Church-Turing Thesis. In: Limits of Computation. Undergraduate Topics in Computer Science. Springer, Cham. https://doi.org/10.1007/978-3-319-27889-6_11

Download citation

DOI : https://doi.org/10.1007/978-3-319-27889-6_11

Published : 26 March 2016

Publisher Name : Springer, Cham

Print ISBN : 978-3-319-27887-2

Online ISBN : 978-3-319-27889-6

eBook Packages : Computer Science Computer Science (R0)

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

• Search Menu

Sign in through your institution

• Browse content in Arts and Humanities
• Browse content in Archaeology
• Anglo-Saxon and Medieval Archaeology
• Archaeological Methodology and Techniques
• Archaeology by Region
• Archaeology of Religion
• Archaeology of Trade and Exchange
• Biblical Archaeology
• Contemporary and Public Archaeology
• Environmental Archaeology
• Historical Archaeology
• History and Theory of Archaeology
• Industrial Archaeology
• Landscape Archaeology
• Mortuary Archaeology
• Prehistoric Archaeology
• Underwater Archaeology
• Zooarchaeology
• Browse content in Architecture
• Architectural Structure and Design
• History of Architecture
• Residential and Domestic Buildings
• Theory of Architecture
• Browse content in Art
• Art Subjects and Themes
• History of Art
• Industrial and Commercial Art
• Theory of Art
• Biographical Studies
• Byzantine Studies
• Browse content in Classical Studies
• Classical History
• Classical Philosophy
• Classical Mythology
• Classical Literature
• Classical Reception
• Classical Art and Architecture
• Classical Oratory and Rhetoric
• Greek and Roman Papyrology
• Greek and Roman Epigraphy
• Greek and Roman Law
• Greek and Roman Archaeology
• Late Antiquity
• Religion in the Ancient World
• Digital Humanities
• Browse content in History
• Colonialism and Imperialism
• Diplomatic History
• Environmental History
• Genealogy, Heraldry, Names, and Honours
• Genocide and Ethnic Cleansing
• Historical Geography
• History by Period
• History of Emotions
• History of Agriculture
• History of Education
• History of Gender and Sexuality
• Industrial History
• Intellectual History
• International History
• Labour History
• Legal and Constitutional History
• Local and Family History
• Maritime History
• Military History
• National Liberation and Post-Colonialism
• Oral History
• Political History
• Public History
• Regional and National History
• Revolutions and Rebellions
• Slavery and Abolition of Slavery
• Social and Cultural History
• Theory, Methods, and Historiography
• Urban History
• World History
• Browse content in Language Teaching and Learning
• Language Learning (Specific Skills)
• Language Teaching Theory and Methods
• Browse content in Linguistics
• Applied Linguistics
• Cognitive Linguistics
• Computational Linguistics
• Forensic Linguistics
• Grammar, Syntax and Morphology
• Historical and Diachronic Linguistics
• History of English
• Language Evolution
• Language Reference
• Language Acquisition
• Language Variation
• Language Families
• Lexicography
• Linguistic Anthropology
• Linguistic Theories
• Linguistic Typology
• Phonetics and Phonology
• Psycholinguistics
• Sociolinguistics
• Translation and Interpretation
• Writing Systems
• Browse content in Literature
• Bibliography
• Children's Literature Studies
• Literary Studies (Romanticism)
• Literary Studies (American)
• Literary Studies (Asian)
• Literary Studies (European)
• Literary Studies (Eco-criticism)
• Literary Studies (Modernism)
• Literary Studies - World
• Literary Studies (1500 to 1800)
• Literary Studies (19th Century)
• Literary Studies (20th Century onwards)
• Literary Studies (African American Literature)
• Literary Studies (British and Irish)
• Literary Studies (Early and Medieval)
• Literary Studies (Fiction, Novelists, and Prose Writers)
• Literary Studies (Gender Studies)
• Literary Studies (Graphic Novels)
• Literary Studies (History of the Book)
• Literary Studies (Plays and Playwrights)
• Literary Studies (Poetry and Poets)
• Literary Studies (Postcolonial Literature)
• Literary Studies (Queer Studies)
• Literary Studies (Science Fiction)
• Literary Studies (Travel Literature)
• Literary Studies (War Literature)
• Literary Studies (Women's Writing)
• Literary Theory and Cultural Studies
• Mythology and Folklore
• Shakespeare Studies and Criticism
• Browse content in Media Studies
• Browse content in Music
• Applied Music
• Dance and Music
• Ethics in Music
• Ethnomusicology
• Gender and Sexuality in Music
• Medicine and Music
• Music Cultures
• Music and Media
• Music and Religion
• Music and Culture
• Music Education and Pedagogy
• Music Theory and Analysis
• Musical Scores, Lyrics, and Libretti
• Musical Structures, Styles, and Techniques
• Musicology and Music History
• Performance Practice and Studies
• Race and Ethnicity in Music
• Sound Studies
• Browse content in Performing Arts
• Browse content in Philosophy
• Aesthetics and Philosophy of Art
• Epistemology
• Feminist Philosophy
• History of Western Philosophy
• Metaphysics
• Moral Philosophy
• Non-Western Philosophy
• Philosophy of Language
• Philosophy of Mind
• Philosophy of Perception
• Philosophy of Science
• Philosophy of Action
• Philosophy of Law
• Philosophy of Religion
• Philosophy of Mathematics and Logic
• Practical Ethics
• Social and Political Philosophy
• Browse content in Religion
• Biblical Studies
• Christianity
• East Asian Religions
• History of Religion
• Judaism and Jewish Studies
• Qumran Studies
• Religion and Education
• Religion and Health
• Religion and Politics
• Religion and Science
• Religion and Law
• Religion and Art, Literature, and Music
• Religious Studies
• Browse content in Society and Culture
• Cookery, Food, and Drink
• Cultural Studies
• Customs and Traditions
• Ethical Issues and Debates
• Hobbies, Games, Arts and Crafts
• Natural world, Country Life, and Pets
• Popular Beliefs and Controversial Knowledge
• Sports and Outdoor Recreation
• Technology and Society
• Travel and Holiday
• Visual Culture
• Browse content in Law
• Arbitration
• Browse content in Company and Commercial Law
• Commercial Law
• Company Law
• Browse content in Comparative Law
• Systems of Law
• Competition Law
• Browse content in Constitutional and Administrative Law
• Government Powers
• Judicial Review
• Local Government Law
• Military and Defence Law
• Parliamentary and Legislative Practice
• Construction Law
• Contract Law
• Browse content in Criminal Law
• Criminal Procedure
• Criminal Evidence Law
• Sentencing and Punishment
• Employment and Labour Law
• Environment and Energy Law
• Browse content in Financial Law
• Banking Law
• Insolvency Law
• History of Law
• Human Rights and Immigration
• Intellectual Property Law
• Browse content in International Law
• Private International Law and Conflict of Laws
• Public International Law
• IT and Communications Law
• Jurisprudence and Philosophy of Law
• Law and Politics
• Law and Society
• Browse content in Legal System and Practice
• Courts and Procedure
• Legal Skills and Practice
• Primary Sources of Law
• Regulation of Legal Profession
• Medical and Healthcare Law
• Browse content in Policing
• Criminal Investigation and Detection
• Police and Security Services
• Police Procedure and Law
• Police Regional Planning
• Browse content in Property Law
• Personal Property Law
• Study and Revision
• Terrorism and National Security Law
• Browse content in Trusts Law
• Wills and Probate or Succession
• Browse content in Medicine and Health
• Browse content in Allied Health Professions
• Arts Therapies
• Clinical Science
• Dietetics and Nutrition
• Occupational Therapy
• Operating Department Practice
• Physiotherapy
• Radiography
• Speech and Language Therapy
• Browse content in Anaesthetics
• General Anaesthesia
• Neuroanaesthesia
• Clinical Neuroscience
• Browse content in Clinical Medicine
• Acute Medicine
• Cardiovascular Medicine
• Clinical Genetics
• Clinical Pharmacology and Therapeutics
• Dermatology
• Endocrinology and Diabetes
• Gastroenterology
• Genito-urinary Medicine
• Geriatric Medicine
• Infectious Diseases
• Medical Toxicology
• Medical Oncology
• Pain Medicine
• Palliative Medicine
• Rehabilitation Medicine
• Respiratory Medicine and Pulmonology
• Rheumatology
• Sleep Medicine
• Sports and Exercise Medicine
• Community Medical Services
• Critical Care
• Emergency Medicine
• Forensic Medicine
• Haematology
• History of Medicine
• Browse content in Medical Skills
• Clinical Skills
• Communication Skills
• Nursing Skills
• Surgical Skills
• Browse content in Medical Dentistry
• Oral and Maxillofacial Surgery
• Paediatric Dentistry
• Restorative Dentistry and Orthodontics
• Surgical Dentistry
• Medical Ethics
• Medical Statistics and Methodology
• Browse content in Neurology
• Clinical Neurophysiology
• Neuropathology
• Nursing Studies
• Browse content in Obstetrics and Gynaecology
• Gynaecology
• Occupational Medicine
• Ophthalmology
• Otolaryngology (ENT)
• Browse content in Paediatrics
• Neonatology
• Browse content in Pathology
• Chemical Pathology
• Clinical Cytogenetics and Molecular Genetics
• Histopathology
• Medical Microbiology and Virology
• Patient Education and Information
• Browse content in Pharmacology
• Psychopharmacology
• Browse content in Popular Health
• Caring for Others
• Complementary and Alternative Medicine
• Self-help and Personal Development
• Browse content in Preclinical Medicine
• Cell Biology
• Molecular Biology and Genetics
• Reproduction, Growth and Development
• Primary Care
• Professional Development in Medicine
• Browse content in Psychiatry
• Addiction Medicine
• Child and Adolescent Psychiatry
• Forensic Psychiatry
• Learning Disabilities
• Old Age Psychiatry
• Psychotherapy
• Browse content in Public Health and Epidemiology
• Epidemiology
• Public Health
• Browse content in Radiology
• Clinical Radiology
• Interventional Radiology
• Nuclear Medicine
• Radiation Oncology
• Reproductive Medicine
• Browse content in Surgery
• Cardiothoracic Surgery
• Gastro-intestinal and Colorectal Surgery
• General Surgery
• Neurosurgery
• Paediatric Surgery
• Peri-operative Care
• Plastic and Reconstructive Surgery
• Surgical Oncology
• Transplant Surgery
• Trauma and Orthopaedic Surgery
• Vascular Surgery
• Browse content in Science and Mathematics
• Browse content in Biological Sciences
• Aquatic Biology
• Biochemistry
• Bioinformatics and Computational Biology
• Developmental Biology
• Ecology and Conservation
• Evolutionary Biology
• Genetics and Genomics
• Microbiology
• Molecular and Cell Biology
• Natural History
• Plant Sciences and Forestry
• Research Methods in Life Sciences
• Structural Biology
• Systems Biology
• Zoology and Animal Sciences
• Browse content in Chemistry
• Analytical Chemistry
• Computational Chemistry
• Crystallography
• Environmental Chemistry
• Industrial Chemistry
• Inorganic Chemistry
• Materials Chemistry
• Medicinal Chemistry
• Mineralogy and Gems
• Organic Chemistry
• Physical Chemistry
• Polymer Chemistry
• Study and Communication Skills in Chemistry
• Theoretical Chemistry
• Browse content in Computer Science
• Artificial Intelligence
• Computer Architecture and Logic Design
• Game Studies
• Human-Computer Interaction
• Mathematical Theory of Computation
• Programming Languages
• Software Engineering
• Systems Analysis and Design
• Virtual Reality
• Browse content in Computing
• Business Applications
• Computer Security
• Computer Games
• Computer Networking and Communications
• Digital Lifestyle
• Graphical and Digital Media Applications
• Operating Systems
• Browse content in Earth Sciences and Geography
• Atmospheric Sciences
• Environmental Geography
• Geology and the Lithosphere
• Maps and Map-making
• Meteorology and Climatology
• Oceanography and Hydrology
• Palaeontology
• Physical Geography and Topography
• Regional Geography
• Soil Science
• Urban Geography
• Browse content in Engineering and Technology
• Agriculture and Farming
• Biological Engineering
• Civil Engineering, Surveying, and Building
• Electronics and Communications Engineering
• Energy Technology
• Engineering (General)
• Environmental Science, Engineering, and Technology
• History of Engineering and Technology
• Mechanical Engineering and Materials
• Technology of Industrial Chemistry
• Transport Technology and Trades
• Browse content in Environmental Science
• Applied Ecology (Environmental Science)
• Conservation of the Environment (Environmental Science)
• Environmental Sustainability
• Environmentalist Thought and Ideology (Environmental Science)
• Management of Land and Natural Resources (Environmental Science)
• Natural Disasters (Environmental Science)
• Nuclear Issues (Environmental Science)
• Pollution and Threats to the Environment (Environmental Science)
• Social Impact of Environmental Issues (Environmental Science)
• History of Science and Technology
• Browse content in Materials Science
• Ceramics and Glasses
• Composite Materials
• Metals, Alloying, and Corrosion
• Nanotechnology
• Browse content in Mathematics
• Applied Mathematics
• Biomathematics and Statistics
• History of Mathematics
• Mathematical Education
• Mathematical Finance
• Mathematical Analysis
• Numerical and Computational Mathematics
• Probability and Statistics
• Pure Mathematics
• Browse content in Neuroscience
• Cognition and Behavioural Neuroscience
• Development of the Nervous System
• Disorders of the Nervous System
• History of Neuroscience
• Invertebrate Neurobiology
• Molecular and Cellular Systems
• Neuroendocrinology and Autonomic Nervous System
• Neuroscientific Techniques
• Sensory and Motor Systems
• Browse content in Physics
• Astronomy and Astrophysics
• Atomic, Molecular, and Optical Physics
• Biological and Medical Physics
• Classical Mechanics
• Computational Physics
• Condensed Matter Physics
• Electromagnetism, Optics, and Acoustics
• History of Physics
• Mathematical and Statistical Physics
• Measurement Science
• Nuclear Physics
• Particles and Fields
• Plasma Physics
• Quantum Physics
• Relativity and Gravitation
• Semiconductor and Mesoscopic Physics
• Browse content in Psychology
• Affective Sciences
• Clinical Psychology
• Cognitive Psychology
• Cognitive Neuroscience
• Criminal and Forensic Psychology
• Developmental Psychology
• Educational Psychology
• Evolutionary Psychology
• Health Psychology
• History and Systems in Psychology
• Music Psychology
• Neuropsychology
• Organizational Psychology
• Psychological Assessment and Testing
• Psychology of Human-Technology Interaction
• Psychology Professional Development and Training
• Research Methods in Psychology
• Social Psychology
• Browse content in Social Sciences
• Browse content in Anthropology
• Anthropology of Religion
• Human Evolution
• Medical Anthropology
• Physical Anthropology
• Regional Anthropology
• Social and Cultural Anthropology
• Theory and Practice of Anthropology
• Browse content in Business and Management
• Business Ethics
• Business Strategy
• Business History
• Business and Technology
• Business and Government
• Business and the Environment
• Comparative Management
• Corporate Governance
• Corporate Social Responsibility
• Entrepreneurship
• Health Management
• Human Resource Management
• Industrial and Employment Relations
• Industry Studies
• Information and Communication Technologies
• International Business
• Knowledge Management
• Management and Management Techniques
• Operations Management
• Organizational Theory and Behaviour
• Pensions and Pension Management
• Public and Nonprofit Management
• Strategic Management
• Supply Chain Management
• Browse content in Criminology and Criminal Justice
• Criminal Justice
• Criminology
• Forms of Crime
• International and Comparative Criminology
• Youth Violence and Juvenile Justice
• Development Studies
• Browse content in Economics
• Agricultural, Environmental, and Natural Resource Economics
• Asian Economics
• Behavioural Finance
• Behavioural Economics and Neuroeconomics
• Econometrics and Mathematical Economics
• Economic History
• Economic Systems
• Economic Methodology
• Economic Development and Growth
• Financial Markets
• Financial Institutions and Services
• General Economics and Teaching
• Health, Education, and Welfare
• History of Economic Thought
• International Economics
• Labour and Demographic Economics
• Law and Economics
• Macroeconomics and Monetary Economics
• Microeconomics
• Public Economics
• Urban, Rural, and Regional Economics
• Welfare Economics
• Browse content in Education
• Adult Education and Continuous Learning
• Care and Counselling of Students
• Early Childhood and Elementary Education
• Educational Equipment and Technology
• Educational Strategies and Policy
• Higher and Further Education
• Organization and Management of Education
• Philosophy and Theory of Education
• Schools Studies
• Secondary Education
• Teaching of a Specific Subject
• Teaching of Specific Groups and Special Educational Needs
• Teaching Skills and Techniques
• Browse content in Environment
• Applied Ecology (Social Science)
• Climate Change
• Conservation of the Environment (Social Science)
• Environmentalist Thought and Ideology (Social Science)
• Natural Disasters (Environment)
• Social Impact of Environmental Issues (Social Science)
• Browse content in Human Geography
• Cultural Geography
• Economic Geography
• Political Geography
• Browse content in Interdisciplinary Studies
• Communication Studies
• Museums, Libraries, and Information Sciences
• Browse content in Politics
• African Politics
• Asian Politics
• Chinese Politics
• Comparative Politics
• Conflict Politics
• Elections and Electoral Studies
• Environmental Politics
• European Union
• Foreign Policy
• Gender and Politics
• Human Rights and Politics
• Indian Politics
• International Relations
• International Organization (Politics)
• International Political Economy
• Irish Politics
• Latin American Politics
• Middle Eastern Politics
• Political Behaviour
• Political Economy
• Political Institutions
• Political Methodology
• Political Communication
• Political Philosophy
• Political Sociology
• Political Theory
• Politics and Law
• Politics of Development
• Public Policy
• Public Administration
• Quantitative Political Methodology
• Regional Political Studies
• Russian Politics
• Security Studies
• State and Local Government
• UK Politics
• US Politics
• Browse content in Regional and Area Studies
• African Studies
• Asian Studies
• East Asian Studies
• Japanese Studies
• Latin American Studies
• Middle Eastern Studies
• Native American Studies
• Scottish Studies
• Browse content in Research and Information
• Research Methods
• Browse content in Social Work
• Addictions and Substance Misuse
• Adoption and Fostering
• Care of the Elderly
• Child and Adolescent Social Work
• Couple and Family Social Work
• Direct Practice and Clinical Social Work
• Emergency Services
• Human Behaviour and the Social Environment
• International and Global Issues in Social Work
• Mental and Behavioural Health
• Social Justice and Human Rights
• Social Policy and Advocacy
• Social Work and Crime and Justice
• Social Work Macro Practice
• Social Work Practice Settings
• Social Work Research and Evidence-based Practice
• Welfare and Benefit Systems
• Browse content in Sociology
• Childhood Studies
• Community Development
• Comparative and Historical Sociology
• Economic Sociology
• Gender and Sexuality
• Gerontology and Ageing
• Health, Illness, and Medicine
• Marriage and the Family
• Migration Studies
• Occupations, Professions, and Work
• Organizations
• Population and Demography
• Race and Ethnicity
• Social Theory
• Social Movements and Social Change
• Social Research and Statistics
• Social Stratification, Inequality, and Mobility
• Sociology of Religion
• Sociology of Education
• Sport and Leisure
• Urban and Rural Studies
• Browse content in Warfare and Defence
• Defence Strategy, Planning, and Research
• Land Forces and Warfare
• Military Administration
• Military Life and Institutions
• Naval Forces and Warfare
• Other Warfare and Defence Issues
• Peace Studies and Conflict Resolution
• Weapons and Equipment

• < Previous chapter
• Next chapter >

8 The Church-Turing Thesis: Its Nature and Status

• Published: November 1996
• Cite Icon Cite
• Permissions Icon Permissions

The Church-Turing thesis (CT), as it is usually understood, asserts the identity of two classes of functions, the effectively computable functions on the one hand, and the recursive (or Turing-machine computable) functions on the other. In support of this thesis, it is customary to cite the circumstance that all serious attempts to characterize the notion of an effectively computable function in precise mathematical terms have ended up by defining the same class of functions, albeit in quite different ways. Thus CT is supported by a series of theorems to the effect that these various characterizations of effective computability (viz. Turing-machine computability, general recursiveness, A-definability, Markov algorithm computability, and the rest) are extensionally equivalent.

Signed in as

Institutional accounts.

• GoogleCrawler [DO NOT DELETE]
• Google Scholar Indexing

Personal account

• Sign in with email/username & password
• Get email alerts
• Save searches
• Purchase content
• Activate your purchase/trial code
• Add your ORCID iD

Institutional access

Sign in with a library card.

• Sign in with username/password
• Recommend to your librarian
• Institutional account management
• Get help with access

Access to content on Oxford Academic is often provided through institutional subscriptions and purchases. If you are a member of an institution with an active account, you may be able to access content in one of the following ways:

IP based access

Typically, access is provided across an institutional network to a range of IP addresses. This authentication occurs automatically, and it is not possible to sign out of an IP authenticated account.

Choose this option to get remote access when outside your institution. Shibboleth/Open Athens technology is used to provide single sign-on between your institution’s website and Oxford Academic.

• Click Sign in through your institution.
• Select your institution from the list provided, which will take you to your institution's website to sign in.
• When on the institution site, please use the credentials provided by your institution. Do not use an Oxford Academic personal account.
• Following successful sign in, you will be returned to Oxford Academic.

If your institution is not listed or you cannot sign in to your institution’s website, please contact your librarian or administrator.

Enter your library card number to sign in. If you cannot sign in, please contact your librarian.

Society Members

Society member access to a journal is achieved in one of the following ways:

Sign in through society site

Many societies offer single sign-on between the society website and Oxford Academic. If you see ‘Sign in through society site’ in the sign in pane within a journal:

• Click Sign in through society site.
• When on the society site, please use the credentials provided by that society. Do not use an Oxford Academic personal account.

If you do not have a society account or have forgotten your username or password, please contact your society.

Sign in using a personal account

Some societies use Oxford Academic personal accounts to provide access to their members. See below.

A personal account can be used to get email alerts, save searches, purchase content, and activate subscriptions.

Some societies use Oxford Academic personal accounts to provide access to their members.

Viewing your signed in accounts

Click the account icon in the top right to:

• View your signed in personal account and access account management features.
• View the institutional accounts that are providing access.

Signed in but can't access content

Oxford Academic is home to a wide variety of products. The institutional subscription may not cover the content that you are trying to access. If you believe you should have access to that content, please contact your librarian.

For librarians and administrators, your personal account also provides access to institutional account management. Here you will find options to view and activate subscriptions, manage institutional settings and access options, access usage statistics, and more.

Our books are available by subscription or purchase to libraries and institutions.

• About Oxford Academic
• Publish journals with us
• University press partners
• What we publish
• New features  
• Open access
• Rights and permissions
• Accessibility
• Advertising
• Media enquiries
• Oxford University Press
• Oxford Languages
• University of Oxford

Oxford University Press is a department of the University of Oxford. It furthers the University's objective of excellence in research, scholarship, and education by publishing worldwide

• Copyright © 2024 Oxford University Press
• Cookie settings
• Cookie policy
• Privacy policy
• Legal notice

This Feature Is Available To Subscribers Only

Sign In or Create an Account

This PDF is available to Subscribers Only

For full access to this pdf, sign in to an existing account, or purchase an annual subscription.

The Church-Turing Thesis: Logical Limit or Breachable Barrier?

• Hacker News
• Download PDF
• Join the Discussion
• View in the ACM Digital Library
• Introduction

Key Insights

History of the thesis, what is an algorithm, what justifies the church-turing thesis, is the thesis mathematically provable, complexity: the extended church-turing thesis, physical computability, ctt-p and quantum mechanics, weaker physical computability theses, physical computation thesis, relativistic computation, ctt-a and computation in the broad.

The Church-Turing thesis (CTT) underlies tantalizing open questions concerning the fundamental place of computing in the physical universe. For example, is every physical system computable? Is the universe essentially computational in nature? What are the implications for computer science of recent speculation about physical uncomputability? Does CTT place a fundamental logical limit on what can be computed, a computational “barrier” that cannot be broken, no matter how far and in what multitude of ways computers develop? Or could new types of hardware, based perhaps on quantum or relativistic phenomena, lead to radically new computing paradigms that do breach the Church-Turing barrier, in which the uncomputable becomes computable, in an upgraded sense of “computable”? Before addressing these questions, we first look back to the 1930s to consider how Alonzo Church and Alan Turing formulated, and sought to justify, their versions of CTT. With this necessary history under our belts, we then turn to today’s dramatically more powerful versions of CTT.

Back to Top

• The term “Church-Turing thesis” is used today for numerous theses that diverge significantly from the one Alonzo Church and Alan Turing conceived in 1936,
• The range of algorithmic processes studied in modern computer science far transcends the range of processes a “human cornputer” could possibly carry out.
• There are at least three forms of the “physical Church-Turing thesis”— modest, bold, and super-bold—though, at the present stage of physical inquiry, it is unknown whether any of them is true.

Turing stated what we will call “Turing’s thesis” in various places and with varying degrees of rigor. The following formulation is one of his most accessible.

Turing’s thesis. “L.C.M.s [logical computing machines, Turing’s expression for Turing machines] can do anything that could be described as … ‘purely mechanical’.” 38

Turing also formulated his thesis in terms of numbers. For example, he said, “It is my contention that these operations [the operations of an L.C.M.] include all those which are used in the computation of a number.” 36 and “[T]he ‘computable numbers’ include all numbers which would naturally be regarded as computable.” 36

Church (who, like Turing, was working on the German mathematician David Hubert’s Entscheidungsproblem ) advanced “Church’s thesis,” which he expressed in terms of definability in his lambda calculus.

Church’s thesis. “We now 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 λ-definable function of positive integers).” 5

Church chose to call this a definition. American mathematician Emil Post, on the other hand, referred to Church’s thesis as a “working hypothesis” and criticized Church for masking it in the guise of a definition. 33

Upon learning of Church’s “definition,” Turing quickly proved that λ-definability and his own concept of computability (over positive integers) are equivalent. Church’s thesis and Turing’s thesis are thus equivalent, if attention is restricted to functions of positive integers. (Turing’s thesis, more general than Church’s, also encompassed computable real numbers.) However, it is important for a computer scientist to appreciate that despite this extensional equivalence, Turing’s thesis and Church’s thesis have distinct meanings and so are different theses, since they are not intensionally equivalent. A leading difference in their meanings is that Church’s thesis contains no reference to computing machinery, whereas Turing’s thesis is expressed in terms of the “Turing machine,” as Church dubbed it in his 1937 review of Turing’s paper.

It is now widely understood that Turing introduced his machines with the intention of providing an idealized description of a certain human activity—numerical computation; in Turing’s day computation was carried out by rote workers called “computers,” or, sometimes, “computors”; see, for example, Turing. 37 The Church-Turing thesis is about computation as the term was used in 1936—human computation. Church’s term “effectively calculable function” was intended to refer to functions that are calculable by an idealized human computer; and, likewise, Turing’s phrase “numbers which would naturally be regarded as computable” was intended to refer to those numbers that could be churned out, digit by digit, by an idealized human computer working ceaselessly.

Here, then, is our formulation of the historical version of the Church-Turing thesis, as informed by Turing’s proof of the equivalence of his and Church’s theses:

CTT-Original (CTT-O). Every function that can be computed by the idealized human computer, which is to say, can be effectively computed, is Turing-computable.

Some mathematical logicians view CTT-O as subject ultimately to either mathematical proof or mathematical refutation, like open mathematical conjectures, as in the Riemann hypothesis, while others regard CTT-O as not amenable to mathematical proof but supported by philosophical arguments and an accumulation of mathematical evidence. Few logicians today follow Church in regarding CTT-O as a definition. We subscribe to Turing’s view of the status of CTT-O, as we outline later.

In computer science today, algorithms and effective procedures are, of course, associated not primarily with humans but with machines. (Note, while some expositors might distinguish between the terms “algorithm” and “effective procedure,” we use the terms interchangeably.) Many computer science textbooks formulate the Church-Turing thesis without mentioning human computers at all; examples include the well-known books by Hopcroft and Ullman 24 and Lewis and Papadimitriou. 29 This is despite the fact that the concept of human computation was at the heart of both Turing’s and Church’s analysis of computation.

We discuss several important modern forms of the Church-Turing thesis, each going far beyond CTT-O. First, we look more closely at the algorithmic form of thesis, as stated to a first approximation by Lewis and Papadimitriou 29 : “[W]e take the Turing machine to be a precise formal equivalent of the intuitive notion of ‘algorithm’.”

The range of algorithmic processes studied in modern computer science far transcends the range of processes a Turing machine is able to carry out. The Turing machine is restricted to, say, changing at most one bounded part at each sequential step of a computation. As Yuri Gurevich pointed out, the concept of an algorithm keeps evolving: “We have now parallel, interactive, distributed, real-time, analog, hybrid, quantum, etc. algorithms.” 22 There are enzymatic algorithms, bacterial foraging algorithms, slime-mold algorithms, and more. The Turing machine is incapable of performing the atomic steps of algorithms carried out by, say, an enzymatic system (such as selective enzyme binding) or a slime mold (such as pseudopod extension). The Turing machine is similarly unable to duplicate (as opposed to simulate) John Conway’s Game of Life, where—unlike a Turing machine—every cell updates simultaneously.

A thesis aiming to limit the scope of algorithmic computability to Turing computability should thus not state that every possible algorithmic process can be performed by a Turing machine. The way to express the thesis is to say the extensional input-output function ια associated with an algorithm α is always Turing-computable; ια is simply the extensional mapping of α ‘s inputs to α ‘s outputs. The algorithm the Turing machine uses to compute ια might be very different from α itself. A question then naturally arises: If an algorithmic process need not be one a Turing machine can carry out, save in the weak sense just mentioned, then where do the boundaries of this concept lie? What indeed is an algorithm?

The dominant view in computer science is that, ontologically speaking, algorithms are abstract entities; however, there is debate about what abstract entities algorithms are. Gurevich defined the concept in terms of abstract-state machines, Yiannis Moschovakis in terms of abstract recursion, and Noson Yanofsky in terms of equivalence classes of programs, while Moshe Vardi has speculated that an algorithm is both abstract-state machine and recursor. It is also debated whether an algorithm must be physically implementable. Moschovakis and Vasilis Paschalis (among others) adopt a concept of algorithm “so wide as to admit ‘non-implementable’ algorithms,” 30 while other approaches do impose a requirement of physical implementability, even if only a very mild one. David Harel, for instance, writes: [A]ny algorithmic problem for which we can find an algorithm that can be programmed in some programming language, any language, running on some computer, any computer, even one that has not been built yet but can be built … is also solvable by a Turing machine. This statement is one version of the so-called Church/Turing thesis.” 23

Steering between these debates—and following Harel’s suggestion that the algorithms of interest to computer science are always expressible in programming languages—we arrive at the following program-oriented formulation of the algorithmic thesis:

CTT-Algorithm (CTT-A). Every algorithm can be expressed by means of a program in some (not necessarily currently existing) Turing-equivalent programming language.

There is an option to narrow CTT-A by adding “physically implementable” before “program,” although in our view this would be to lump together two distinct computational issues that are better treated separately.

The evolving nature and open-endedness of the concept of an algorithm is matched by a corresponding open-endedness in the concept of a programming language. But this open-endedness notwithstanding, CTT-A requires that all algorithms be bounded by Turing computability.

Later in this article we examine complexity-theoretic and physical versions of the Church-Turing thesis but first turn to the question of the justification of the theses introduced so far. Are CTT-O and CTT-A correct?

Stephen Kleene—who coined the term “Church-Turing thesis”—catalogued four types of argument for CTT-O: First, the argument from non-refutation points out the thesis has never been refuted, despite sustained (and ongoing) attempts to find a counterexample (such as the attempts by László Kalmár and, more recently, by Doukas Kapantais). Second, the argument from confluence points to the fact that the various characterizations of computability, while differing in their approaches and formal details, turn out to encompass the very same class of computable functions. Four such characterizations were presented (independently) in 1936 and immediately proved to be extensionally equivalent: Turing computability, Church’s λ-definability, Kleene’s recursive functions, and Post’s finitary combinatory processes.

Third is an argument usually referred to nowadays as “Turing’s analysis.” Turing called it simply argument “I,” stating five very general and intuitive constraints—or axioms—the human computer may be assumed to satisfy: “The behavior of the computer at any moment is determined by the symbols which he is observing, and his ‘state of mind’ at that moment”; “[ T ] here is a bound B to the number of symbols or squares which the computer can observe at one moment”; “[E]ach of the new observed squares is within L squares of an immediately previously observed square”; “[I]n a simple operation not more than one symbol is altered”; and “[T]he number of states of mind which need be taken into account is finite.” Turing noted that reference to the computer’s states of mind can be avoided by talking instead about configurations of symbols, these being “a more definite and physical counterpart” of states of mind. 36

The second part of Turing’s argument I is a demonstration that each function computed by any human computer subject to these constraints is also computable by a Turing machine; it is not difficult to see that each of the computer’s steps can be mimicked by the Turing machine, either in a single step or by means of a series of steps. In short, Turing’s five axioms entail CTT-O. (Turing’s axiomatic approach to computability was in fact foreshadowed by Kurt Gödel in a suggestion to Church a year or so earlier. 15 Some more recent axiomatic approaches to computability proceed differently; for example, Erwin Engeler employs the Schönfinkel-Curry idea of “combinators” in order to axiomatize the concept of an algorithmic function.)

The Turing machine is restricted to, say, changing at most one bounded part at each sequential step of a computation.

Fourth in this catalog of considerations supporting CTT-O are arguments from first-order logic. They are typified by a 1936 argument of Church’s and by Turing’s argument II, from Section 9 of Turing’s 1936 paper. In 2013, Saul Kripke 28 presented a reconstruction of Turing’s argument II, which goes as follows: Computation is a special form of mathematical deduction; and every mathematical deduction—and therefore every computation—can be formalized as a valid deduction in the language of first-order predicate logic with identity (a step Kripke referred to as “Hilbert’s thesis”); following Gödel’s completeness theorem, each computation is thus formalized by a provable formula of first-order logic; and every computation can therefore be carried out by the universal Turing machine. This last step regarding the universal Turing machine is secured by a theorem proved by Turing: Every provable formula of first-order logic can be proved by the universal Turing machine.

The third and fourth of these arguments provide justification for CTT-O but not for CTT-A. As Robin Gandy 20 pointed out, the third argument—Turing’s I—contains “crucial steps … where he [Turing] appeals to the fact that the calculation is being carried out by a human being.” 20 For example, Turing assumed “a human being can only write one symbol at a time,” and Gandy noted this assumption cannot be carried over to a parallel machine that “prints an arbitrary number of symbols simultaneously.” 20 In Conway’s Game of Life, for instance, there is no upper bound on the number of cells that make up the grid, yet the symbols in all the cells are updated simultaneously. Likewise, the fourth argument (Turing’s II) involves the claim that computation is a special form of formal proof, but the notion of proof is intrinsically related to what a human mathematician—and not some oracle—can prove.

It is thus perhaps not too surprising that the third and fourth arguments in this catalog seldom if ever appear in logic and computer science textbooks. The two arguments that are always given for the Church-Turing thesis (in, for example, Lewis and Papadimitriou 29 ) are confluence and non-refutation. Yet both those arguments are merely inductive, whereas the third and fourth arguments are deductive in nature.

However, a number of attempts have sought to extend Turing’s axiomatic analysis to machine computation; for example, Gandy 20 broadened Turing’s analysis in such a way that parallel computation is included, while Dershowitz and Gurevich 16 gave a more general analysis in terms of abstract state machines. We return to the topic of extending the analysis to machine computation later in this article but first address the important question of whether CTT-O is mathematically provable.

It used to be thought by mathematical logicians and others that CTT-O is not amenable to formal proof, since it is not a mathematically precise statement. This is because it pairs an informal concept—a “vague intuitive notion,” Church called it 5 —with a precise concept. However, Elliott Mendelson gave a powerful critique of this general argument; and today the view that CTT-O is formally provable seems to be gaining acceptance; see, for example, Dershowitz and Gurevich. 16 Inspired by Gandy, 20 Wilfried Sieg 35 stated that a tightened form of Turing’s argument I proves the thesis; and Kripke 28 entertained the same claim for Turing’s argument II.

Turing’s own view was that, on the contrary, his thesis is not susceptible to mathematical proof. He thought his arguments I and II, and indeed “[a]ll arguments which can be given” for the thesis, are “fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically.” 36 Hilbert’s thesis is another example of a proposition that can be justified only by appeal to intuition, and so Kripke’s 28 tightened form of argument II, far from proving CTT-O, merely deduced it from another thesis that is also not amenable to mathematical proof.

Much the same can be said about argument I. If axioms 1–5 are formulated in precise mathematical terms, then it is certainly provable from them that computation is bounded by Turing computability; this is probably what Gandy 20 meant when he said Turing’s argument I proves a “theorem.” But the real issue is whether these axioms completely capture the concept of a computational or algorithmic process, and, so far as we see, no one has ever given a rigorous mathematical justification of that claim. The axioms may be supported by informal arguments, but the whole edifice then falls short of mathematical proof. This is most apparent when the informal arguments offered for the axioms invoke limitations in the cognitive capacities of human computers, as we point out elsewhere. 13 A justification of the second axiom may, for instance, refer to the limitations of human observation. The axioms most certainly lie beyond the scope of mathematical demonstration if their truth depends on contingent human limitations. Turing himself cheerfully appealed to cognitive limitations in the course of his analysis, saying, for example, “[j]ustification lies in the fact that the human memory is necessarily limited.” 36

Turing’s own view was that, on the contrary, his thesis is not susceptible to mathematical proof.

In summary, our answer to “Is CTT-O mathematically provable?” is: Turing thought not and we have found no reason to disagree with him. The various historical arguments seem more than sufficient to establish CTT-O, but these arguments do indeed fall short of mathematical proof.

We next address complexity theoretic forms of the Church-Turing thesis, then turn to the question of whether CTT-A is justified in the context of physically realistic computations.

It is striking that the Turing machine holds a central place not only in computability theory but also in complexity theory, where it is viewed as a universal model for complexity classes.

In complexity theory, the time complexities of any two general and reasonable models of computation are assumed to be polynomially related. But what counts as “reasonable”? Aharonov and Vazirani 1 glossover “reasonable” as “physically realizable in principle”; see also Bernstein and Vazirani. 3 If a computational problem’s time complexity is t in some (general and reasonable) model, then its time complexity is assumed to be poly( t ) in the single-tape Turing machine model; see also Goldreich. 21 This assumption has different names in the literature; Goldreich 21 called it the Cobham-Edmonds thesis, while Yao 40 introduced the term “Extended Church-Turing thesis.” The thesis is of interest only if P ≠ NP , since otherwise it is trivial.

Quantum-computation researchers also use a variant of this thesis, as expressed in terms of probabilistic Turing machines. Bernstein and Vazirani 3 said: “[C]omputational complexity theory rests upon a modern strengthening of [the Church-Turing] thesis, which asserts that any ‘reasonable’ model of computation can be efficiently simulated on a probabilistic Turing machine.” 3

Aharonov and Vazirani 1 give the following formulation of this assumption, naming it the “Extended Church-Turing thesis”—though it is not quite the same as Yao’s earlier thesis of the same name, which did not refer to probabilistic Turing machines:

CTT-Extended (CTT-E). “[A]ny reasonable computational model can be simulated efficiently by the standard model of classical computation, namely, a probabilistic Turing machine.” 1

As is well known in computer science, Peter Shor’s quantum algorithm for prime factorization is a potential counterexample to CTT-E; the algorithm runs on a quantum computer in polynomial time and is much faster than the most-efficient known “classical” algorithm for the task. But the counterexample is controversial. Some computer scientists think the quantum computer invoked is not a physically reasonable model of computation, while others think accommodating these results might require further modifications to complexity theory.

We turn now to extensions of the Church-Turing thesis into physics.

The issue of whether every aspect of the physical world is Turing-computable was broached by several authors in the 1960s and 1970s, and the topic rose to prominence in the mid-1980s.

In 1985, Stephen Wolfram formulated a thesis he described as “a physical form of the Church-Turing hypothesis,” saying, “[U]niversal computers are as powerful in their computational capacities as any physically realizable system can be, so that they can simulate any physical system.” 39 In the same year, David Deutsch, who laid the foundations of quantum computation, independently stated a similar thesis, describing it as “the physical version of the Church-Turing principle.” 17 The thesis is now known as the Church-Turing-Deutsch thesis and the Church-Turing-Deutsch-Wolfram thesis.

Church-Turing-Deutsch-Wolfram thesis (CTDW). Every finite physical system can be simulated to any specified degree of accuracy by a universal Turing machine.

Deutsch pointed out that if “simulated” is understood as “perfectly simulated,” then the thesis is falsified by continuous classical systems, since such classical systems necessarily involve uncomputable real numbers, and went on to introduce the concept of a universal quantum computer, saying such a computer is “capable of perfectly simulating every finite, realizable physical system.” Other physical formulations were advanced by Lenore Blum et al., John Earman, Itamar Pitowsky, Marian Pour-El, and Ian Richards, among others.

We next formulate a strong version of the physical Church-Turing thesis we call the “total physical computability thesis.” (We consider some weaker versions later in the article.) By “physical system” we mean any system whose behavior is in accordance with the actual laws of physics, including non-actual and idealized systems.

Total physical computability thesis (CTT-P). Every physical aspect of the behavior of any physical system can be calculated (to any specified degree of accuracy) by a universal Turing machine.

As with CTT-E, there is also a probabilistic version of CTT-P, formulated in terms of a probabilistic Turing machine.

Arguably, the phrase “physical version of the Church-Turing thesis” is an inappropriate name for this and related theses, since CTT-O concerns a form of effective or algorithmic activity and asserts the activity is always bounded by Turing computability, while CTT-P and CTDW, on the other hand, entail that the activity of every physical system is bounded by Turing computability; the system’s activity need not be algorithmic/effective at all. Nevertheless, in our “CTT-” nomenclature, we follow the Deutsch-Wolfram tradition throughout this article.

Is CTT-P true? Not if physical systems include systems capable of producing unboundedly many digits of a random binary sequence; Church showed such sequences are uncomputable, as we discussed elsewhere. 8 Moreover, speculation that there may be deterministic physical processes whose behavior cannot be calculated by the universal Turing machine stretches back over several decades; for a review, see Copeland. 9 In 1981, Pour-El and Richards 34 showed that a system evolving from computable initial conditions in accordance with the familiar three-dimensional wave equation is capable of exhibiting behavior that falsifies CTT-P; even today, however, it is an open question whether these initial conditions are physically possible. Earlier papers, from the 1960s, by Bruno Scarpellini, Arthur Komar, and Georg Kreisel, in effect questioned CTT-P, with Kreisel stating: “There is no evidence that even present-day quantum theory is a mechanistic, i.e., recursive theory in the sense that a recursively described system has recursive behavior.” 27 Other potential counterexamples to CTT-P have been described by a number of authors, including what are called “relativistic” machines. First introduced by Pitowsky, 32 they will be examined in the section called “Relativistic Computation.”

There are a number of theoretical countermodels to CTT-P arising from quantum mechanics. For example, in 1964, Komar 26 raised “the issue of the macroscopic distinguishability of quantum states,” asserting there is no effective procedure “for determining whether two arbitrarily given physical states can be superposed to show interference effects.” In 2012, Eisert et al. 19 showed “[T]he very natural physical problem of determining whether certain outcome sequences cannot occur in repeated quantum measurements is undecidable, even though the same problem for classical measurements is readily decidable.” This is an example of a problem that refers unboundedly to the future but not to any specific time. Other typical physical problems take the same form; Pitowsky gave as examples “Is the solar system stable?” and “Is the motion of a given system, in a known initial state, periodic?”

Cubitt et al. 14 described another such undecidability result in a 2015 Nature article, outlining their proof that “[T]he spectral gap problem is algorithmically undecidable: There cannot exist any algorithm that, given a description of the local interactions, determines whether the resultant model is gapped or gapless.” Cubitt et al. also said this is the “first undecidability result for a major physics problem that people would really try to solve.”

The spectral gap, an important determinant of a material’s properties, refers to the energy spectrum immediately above the ground-energy level of a quantum many-body system, assuming a well-defined least-energy level of the system exists; the system is said to be “gapless” if this spectrum is continuous and “gapped” if there is a well-defined next-least energy level. The spectral gap problem for a quantum many-body system is the problem of determining whether the system is gapped or gapless, given the finite matrices (at most three) describing the local interactions of the system.

In their proof, Cubitt et al. 14 encoded the halting problem in the spectral gap problem, showing the latter is at least as hard as the former. The proof involves an infinite family of two-dimensional lattices of atoms. But they pointed out their result also applies to finite systems whose size increases, saying, “Not only can the lattice size at which the system switches from gapless to gapped be arbitrarily large, the threshold at which this transition occurs is uncomputable.” Their proof offers an interesting countermodel to CTT-P, involving a physically relevant example of a finite system of increasing size. There exists no effective method for extrapolating the system’s future behavior from (complete descriptions of) its current and past states.

It is debatable whether any of these quantum models correspond to real-world quantum systems. Cubitt et al. 14 admitted the model invoked in their proof is highly artificial, saying, “Whether the results can be extended to more natural models is yet to be determined.” There is also the question of whether the spectral gap problem becomes computable when only local Hilbert spaces of realistically low dimensionality are considered. Nevertheless, these results are certainly suggestive: CTT-P cannot be taken for granted, even in a finite quantum universe.

Summarizing the current situation with respect to CTT-P, we can say, although theoretical countermodels in which CTT-P is false have been described, there is at present—so far as we know—not a shred of evidence that CTT-P is false in the actual universe. Yet it would seem most premature to assert that CTT-P is true.

Piccinini 31 has distinguished between two different types of physical versions of the Church-Turing thesis, both commonly found in the literature, describing them as “bold” and “modest” versions of the thesis, respectively. The bold and modest versions are weaker than our “super-bold” version just discussed (CTT-P). Bold versions of the thesis state, roughly, that “Any physical process can be simulated by some Turing machine.” 31 The Church-Turing-Deutsch-Wolfram thesis (CTDW) is an example, though Piccinini emphasized that the bold versions proposed by different researchers are often “logically independent of one another” and that, unlike the different formulations of CTT-O, which exhibit confluence, the different bold formulations in fact exhibit “lack of confluence.” 31

CTDW and other bold forms are too weak to rule out the uncomputability scenarios described by Cubitt et al. 14 and by Eisert et al. 19 This is because the physical processes involved in these scenarios may, so far as we know, be Turing-computable; it is possible that each process can be simulated by a Turing machine, to any required degree of accuracy, and yet the answers to certain physical questions about the processes are, in general, uncomputable. The situation is similar in the case of the universal Turing machine itself. The machine’s behavior (consisting of the physical actions of the read/write head) is always Turing-computable since it is produced by the Turing machine’s program, yet the answers to some questions about the behavior (such as whether or not the machine halts given certain inputs) are not computable.

Nevertheless, bold forms (such as CTDW) are interesting empirical hypotheses in their own right and the world might confute them. For instance, CTDW fails in the wave-equation countermodel due to Pour-El and Richards 34 where the mapping between the wave equation’s “inputs” and “outputs” is not a Turing-computable (real) function; although, as noted earlier, the physicality of this countermodel can readily be challenged. We discuss some other potential countermodels later in the article, but turn first to what Piccinini termed “modest” versions of the thesis.

Modest versions maintain in essence that every physical computing process is Turing-computable; for two detailed formulations, see Gandy 20 and Copeland. 8 Even if CTT-P and CTDW are in general false, the behavior of the subset of physical systems that are appropriately described as computing systems may nevertheless be bounded by Turing-computability. An illustration of the difference between modest versions on the one hand and CTT-P and CTDW on the other is given by the fact that the wave-equation example is not a counter-model to the modest thesis, assuming, as seems reasonable, that the physical dynamics described by the equation do not constitute a computing process.

Here, we formulate a modest version of the physical Church-Turing thesis we call the “Physical Computation” thesis, then turn to the question of whether it is true.

This form of the thesis maintains that physical computation is bounded by Turing-computability.

Physical computation thesis (CTT-P-C). Every function computed by any physical computing system is Turing-computable.

Is CTT-P-C true? As with the stronger physical computability theses, it seems too early to say. CTT-P-C could be false only if CTT-P and CTDW turn out to be false, since each of them entails CTT-P-C (see the figure here, which outlines the relationships among CTT-P, CTDW, and CTT-P-C). If all physical computation is effective in the 1930s sense of Turing and Church, then CTT-P-C is certainly true. If, however, the door is open to a broadened sense of computation, where physical computation is not necessarily effective in the sense of being bounded by Turing-computability, then CTT-P-C makes a substantive claim.

There is, in fact, heated debate among computer scientists and philosophers about what counts as physical computation. Moreover, a number of attempts have sought to describe a broadened sense of computation in which computation is not bounded by Turing-computability; see, for example, Copeland. 6 Computing machines that compute “beyond the Turing limit” are known collectively as “hypercomputers,” a term introduced in Copeland and Proudfoot. 11 Some of the most thought-provoking examples of notional machines that compute in the broad sense are called “supertask” machines. These “Zeno computers” squeeze infinitely many computational steps into a finite span of time. Examples include accelerating machines, 7 , 12 shrinking machines, and the intriguing relativistic computers described in the next section.

Notional machines all constitute rather theoretical countermodels to CTT-P-C, so long as it is agreed that they compute in a broadened sense, but none has been shown to be physically realistic, although, as we explain, relativistic computers come close. In short, the truth or falsity of CTT-P-C remains unsettled.

Relativistic machines operate in space-time structures with the property that the entire endless lifetime of one component of the machine is included in the finite chronological past of another component, called “the observer.” The first component could thus carry out an infinite computation (such as calculating every digit of π) in what is, from the observer’s point of view, a finite timespan of, say, one hour. (Such machines are in accord with Einstein’s general theory of relativity, hence the term “relativistic.”) Examples of relativistic computation have been detailed by Pitowsky, Mark Hogarth, and Istvan Németi.

In this section we outline a relativistic machine RM consisting of a pair of communicating Turing machines, T E and T o , in relative motion. T E is a universal machine, and T o is the observer. RM is able to compute the halting function, in a broad sense of computation. Speaking of computation here seems appropriate, since RM consists of nothing but two communicating Turing machines.

Here is how RM works. When the input ( m,n ), asking whether the m th Turing machine (in some enumeration of the Turing machines) halts or not when started on input n , enters T o , T o first prints 0 (meaning “never halts”) in its designated output cell and then transmits ( m,n ) to T E . T E simulates the computation performed by the m th Turing machine when started on input n and sends a signal back to T o if and only if the simulation terminates. If T o receives a signal from T E , T o deletes the 0 it previously wrote in its output cell and writes 1 in its place (meaning “halts”). After one hour, T o ‘s output cell shows 1 if the m th Turing machine halts on input n and shows 0 if the m th machine does not halt on n.

The most physically realistic version of this setup to date is due to Németi and his collaborators in Budapest. T E , an ordinary computer, remains on Earth, while the observer T o travels toward and enters a slowly rotating Kerr black hole. T o approaches the outer event horizon, a bubble-like hypersurface surrounding the black hole. Németi theorized that the closer T o gets to the event horizon, the faster T E ‘s clock runs relative to T o due to Einsteinian gravitational time dilation, and this speeding up continues with no upper limit. T o motion proceeds until, relative to a time t on T o clock, the entire span of T E ‘s computing is over. If any signal was emitted by T E , the signal will have been received by T o before time t. So T o will fall into the black hole with 1 in its output cell if T E halted and 0 if T E never halted. Fortunately, T o can escape annihilation if its trajectory is carefully chosen in advance, says Németi; the rotational forces of the Kerr hole counterbalance the gravitational forces that would otherwise “spaghettify” T o . T o thus emerges unscathed from the hole and goes on to use the computed value of the halting function in further computations.

Németi and colleagues emphasize their machine is physical in the sense it is “not in conflict with presently accepted scientific principles” and, in particular, “the principles of quantum mechanics are not violated.” 2 They suggest humans might “even build” a relativistic computer “sometime in the future.” 2 This is, of course, highly controversial. However, our point is that Németi’s theoretical countermodel, which counters not only CTT-P-C but also CTT-P and CTDW, helps underscore that the “physical version of the Church-Turing thesis” is quite independent of CTT-O, since the countermodel stands whether or not CTT-O is endorsed. We next reconsider CTT-A.

The continuing expansion of the concept of an algorithm is akin to the extension of the concept of number from integers to signed integers to rational, real, and complex numbers. Even the concept of human computation underwent an expansion; before 1936, computation was conceived of in terms of total functions, and it was Kleene in 1938 who explicitly extended the conception to also cover partial functions.

Gurevich argued in 2012 that formal methods cannot capture the algorithm concept in its full generality due to the concept’s open-ended nature; at best, formal methods provide treatments of “strata of algorithms” that “have matured enough to support rigorous definitions.” 22 An important question for computer science is whether CTT-A is a reasonable constraint on the growth of new strata. Perhaps not. In 1982, Jon Doyle 18 suggested equilibrating systems with discrete spectra (such as molecules and other quantum many-body systems) illustrate a concept of effectiveness that is broader than the classical concept, saying, “[E]quilibrating can be so easily, reproducibly, and mindlessly accomplished” that we may “take the operation of equilibrating as an effective one,” even if “the functions computable in principle given Turing’s operations and equilibrating include non-recursive functions.”

Over the years, there have been several departures from Turing’s 1936 analysis, as the needs of computer science led to a broadening of the algorithm concept. For example, Turing’s fourth axiom, which bounds the number of parts of a system that can be changed simultaneously, became irrelevant when the algorithm concept broadened to cover parallel computations. The future computational landscape might conceivably include more extensive revisions of the concept, if, for example, physicists were to discover that hardware effective in Doyle’s extended sense is a realistic possibility.

If such hardware were to be developed—hardware in which operations are effective in the sense of being “easily, reproducibly, and mindlessly accomplished” but not bounded by Turing computability—then would the appropriate response by computer scientists be to free the algorithm concept from CTT-A? Or should CTT-A remain as a constraint on algorithms, with instead two different species of computation being recognized, called, say, algorithmic computation and non-algorithmic computation? Not much rides on a word, but we note we prefer “effective computation” for computation that is bounded by Turing computability and “neo-effective computation” for computation that is effective in Doyle’s sense and not bounded by Turing computability, with “neo” indicating a new concept related to an older one.

The numerous examples of notional “hypercomputers” (see Copeland 9 for a review) prompt similar questions. Interestingly, a study of the expanding literature about the concept of an infinite-time Turing machine, introduced by Joel Hamkins and Andy Lewis in 2000, shows that a number of computer scientists are prepared to describe the infinite-time machine as computing the halting function. Perhaps this indicates the concept of computation is already in the process of bifurcating into “effective” and “neo-effective” computation.

In the computational literature the term “Church-Turing thesis” is applied to a variety of different propositions usually not equivalent to the original the-sis—CTT-O; some even go far beyond anything either Church or Turing wrote. Several but not all are fundamental assumptions of computer science. Others (such as the various physical computability theses we have discussed) are important in the philosophy of computing and the philosophy of physics but are highly contentious; indeed, the label “Church-Turing thesis” should not mislead computer scientists or anyone else into thinking they are established fact or even that Church or Turing endorsed them.

Submit an Article to CACM

CACM welcomes unsolicited submissions on topics of relevance and value to the computing community.

You Just Read

Copyright held by the authors. Publication rights licensed to ACM. Request permission to publish from [email protected]

The Digital Library is published by the Association for Computing Machinery. Copyright © 2019 ACM, Inc.

January 2019 Issue

Published: January 1, 2019

Vol. 62 No. 1

Pages: 66-74

Advertisement

Join the Discussion (0)

Become a member or sign in to post a comment, the latest from cacm.

How Does Life Change Post Academic Tenure?

LLM Hallucinations: A Bug or A Feature?

When Colorless Green DNNs Sleep Furiously in an Unexplainable Fantasy

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

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.

• 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

To Continue Learning Please Login