short note on 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

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?

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

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:

• -0.283882181415
• homotopy 3-sphere

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

What is the Church-Turing Thesis?

• First Online: 18 September 2022

Cite this chapter

• Udi Boker 4 &
• Nachum Dershowitz 5  

680 Accesses

2 Citations

1 Altmetric

We aim to put some order to the multiple interpretations of the Church-Turing Thesis and to the different approaches taken to prove or disprove it.

[Answer:] Rosser and its inventor proved that its beta-reduction satisfies the diamond property, and Kleene (pron. clean-ee) proved that it was equivalent to his partial recursive functions. The previous result combined with a similar one with the Turing Machine, led to the Church-Turing thesis. [Question: “What is ...?”] —Quizbowl Tournament (2004)

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

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Luther, Martin

Between Gospel and Church: Resisting the Canonization of Rosa Luxemburg

Franck, Sebastian

Peter Wegner and Dina Goldin asserted that the Church-Turing Thesis should be interpreted with respect to functions over natural numbers [ 17 ]. Yet, if one considers it in the more general form, they claim that he/she must admit it wrong due to the actuality of interactive computations. All this means is that the original thesis needs to be adapted to refer to the nature of non-function-computing uses of computation. See, for example, [ 19 ].

There are numerous other names for the various versions of the thesis in the literature. Even the terms “mathematical” and “physical” have different connotations for different authors.

In [ 13 , 33 ] it is shown that while strict containment of function sets is in general not enough to infer the presence of extra computational power, general recursion is indeed more powerful than primitive recursion, even under rigorous definitions of power comparison.

Sieg [ 49 ] in explaining Church [ 4 ]: “Calculability is explicated by that of derivability in a logic.”

Gandy’s idea of basing a formalization of computability on hereditarily finite sets, which are precisely the finite objects of set theory, was presaged by Moto-o Takahashi [ 53 ].

Another argument of Bringsjord, explicitly touted as “a case against Church’s thesis”, takes its cue from the perceived ability of humans to judge the literary quality of writings that they cannot for the life of them produce themselves [ 101 ].

Herbert Robbins, the statistician: “Nobody is going to run 100-meters in five seconds, no matter how much is invested in training and machines. The same can be said about using the brain. The human mind is no different now from what it was five thousand years ago. And when it comes to mathematics, you must realize that this is the human mind at an extreme limit of its capacity” [ 105 ].

Emil L. Post. Finite combinatory processes—formulation 1. Journal of Symbolic Logic , 1 (3): 103–105, September 1936.

Google Scholar  

Yiannis N. Moschovakis. What is an algorithm? In Björn Engquist and Wilfried Schmid, editors, Mathematics Unlimited — 2001 and Beyond , pages 919–936. Springer, Berlin, 2001.

Erwin Engeler. The Combinatory Programme . Progress in Theoretical Computer Science. Birkhäuser, Boston, 1995.

Alonzo Church. An unsolvable problem of elementary number theory. American Journal of Mathematics , 58: 345–363, 1936.

Article   MathSciNet   MATH   Google Scholar  

Alan. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society , 42: 230–265, 1936–37. URL http://www.abelard.org/turpap2/tp2-ie.asp . Corrections in vol. 43 (1937), pp. 544–546. Reprinted in M. Davis (ed.), The Undecidable , Raven Press, Hewlett, NY, 1965.

Stephen C. Kleene. Lambda-definability and recursiveness. Duke Mathematical Journal , 2: 340–353, 1936.

Martin Davis. The Church-Turing thesis: Consensus and opposition. In Logical Approaches to Computational Barriers , pages 125–132, Berlin, 2006. Springer.

Chapter   Google Scholar  

Andrew Hodges. Did Church and Turing have a thesis about machines? In Adam Olszewski, Jan Wolenski, and Robert Janusz, editors, Church’s Thesis After 70 Years , pages 214–224. Ontos Verlag, 2006.

Robert I. Soare. The history and concept of computability. In Handbook of Computability Theory , pages 3–36. Elsevier, 1999.

Ian Parberry. Parallel speedup of sequential machines: A defense of parallel computation thesis. SIGACT News , 18 (1): 54–67, March 1986.

Article   MATH   Google Scholar  

Peter van Emde Boas. Machine models and simulations. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science , volume A: Algorithms and Complexity, pages 1–66. North-Holland, Amsterdam, 1990. URL http://www.illc.uva.nl/Research/Reports/CT-1988-05.text.pdf .

MATH   Google Scholar  

Scott Aaronson. The toaster-enhanced Turing machine, 2012. URL https://www.scottaaronson.com/blog/?p=1121 . The Blog of Scott Aaronson.

Udi Boker and Nachum Dershowitz. Comparing computational power. Logic Journal of the IGPL , 14 (5): 633–648, 2006. URL http://nachum.org/papers/ComparingComputationalPower.pdf .

Udi Boker and Nachum Dershowitz. The Church-Turing thesis over arbitrary domains. In Arnon Avron, Nachum Dershowitz, and Alexander Rabinovich, editors, Pillars of Computer Science, Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday , volume 4800 of Lecture Notes in Computer Science , pages 199–229. Springer, 2008. URL http://nachum.org/papers/ArbitraryDomains.pdf .

Martin Davis. The myth of hypercomputation. In Christof Teuscher, editor, Alan Turing: Life and Legacy of a Great Thinker , pages 195–212. Springer, 2003.

Gualtiero Piccinini. The physical Church-Turing thesis: Modest or bold? The British Journal for the Philosophy of Science , 62: 733–769, 2011.

Dina Goldin and Peter Wegner. The Church-Turing Thesis: Breaking the myth. In S. Barry Cooper, Benedikt Löwe, and Leen Torenvliet, editors, New Computational Paradigms: First Conference on Computability in Europe (CiE 2005, Amsterdam) , volume 3526 of Lecture Notes in Computer Science , pages 152–168, Berlin, June 2005.

Dina Goldin and Peter Wegner. The interactive nature of computing: Refuting the strong church-turing thesis. Minds and Machines , 18: 17–38, March 2008.

Article   Google Scholar  

Manfred Broy. Computability and realizability for interactive computations. Information and Computation , 241: 277–301, 2015.

Dina Q. Goldin, Scott A. Smolka, and Peter Wegner, editors. Interactive Computation: The New Paradigm . Springer, Berlin, 2006.

Stephen C. Kleene. Turing’s analysis of computability, and major applications of it. In A Half-century Survey on The Universal Turing Machine , pages 17–54. Oxford University Press, Inc., 1988.

Janet Folina. Church’s thesis: Prelude to a proof. Philosophia Mathematica , 6 (3): 302–323, 1998.

Stewart Shapiro. Understanding Church’s thesis, again. Acta Analytica , 11: 59–77, 1993.

Stephen C. Kleene. Introduction to Metamathematics . North Holland, 1952.

László Kalmár. An argument against the plausibility of Church’s thesis. In A. Heyting, editor, Constructivity in Mathematics, Proceedings of the Colloquium Held at Amsterdam, 1957 , pages 72–80, Amsterdam, 1959. North-Holland.

Martin Davis. Why Gödel didn’t have Church’s Thesis. Information and Control , 54 (1/2): 3–24, 1982.

Joseph R. Shoenfield. Recursion Theory , volume 1 of Lecture Notes In Logic . Springer-Verlag, Heidelberg, New York, 1991.

Elliott Mendelson. Second thoughts about Church’s thesis and mathematical proofs. Journal of Philosophy , 87 (5): 225–233, 1990.

Robin Gandy. The confluence of ideas in 1936. In A Half-Century Survey on the Universal Turing Machine , pages 55–111, New York, NY, 1988. Oxford University Press, Inc. URL http://dl.acm.org/citation.cfm?id=57249.57252 .

Stewart Shapiro. Proving things about the informal. In G. Sommaruga and T. Strahm, editors, Turing’s Revolution: The Impact of his Ideas About Computability , pages 283–296. Springer, Cham, January 2015.

Harvey M. Friedman. Mathematical logic in the 20th and 21st centuries, 2000. URL http://cs.nyu.edu/pipermail/fom/2000-April/003913.html . FOM mailing list. April 27, 2000.

Saul A. Kripke. The Church-Turing “thesis” as a special corollary of Gödel’s completeness theorem. In J. Copeland, C. Posy, and O. Shagrir, editors, Computability: Turing, Gödel, Church, and Beyond , pages 77–104. MIT Press, 2013.

Udi Boker and Nachum Dershowitz. The influence of domain interpretations on computational models. Journal of Applied Mathematics and Computation , 215 (4): 1323–1339, 2009.

Henk Barendregt. The impact of the lambda calculus in logic and computer science. Bulletin of Symbolic Logic , 3 (2): 181–215, 1997. URL http://www.math.ucla.edu/~asl/bsl/0302/0302-003.ps .

Solomon Feferman. Theses for computation and recursion on concrete and abstract structures. In Turing’s Revolution: The Impact of His Ideas about Computability , pages 105–126. Springer International Publishing, 2015.

David Chalmers. A computational foundation for the study of cognition. Journal of Cognitive Science , 12 (4): 325–359, 2011. Written in 1993.

Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability . McGraw-Hill, New York, 1966.

Stephen C. Kleene. Origins of recursive function theory. Annals of the History of Computing , 3 (1): 52–67, 1981.

Wilfried Sieg. Step by recursive step: Church’s analysis of effective calculability. Bulletin of Symbolic Logic , 3: 154–180, June 1997.

Alonzo Church. Review of “On computable numbers, with an application to the Entscheidungsproblem”. The Journal of Symbolic Logic , 2 (1): 42–43, 1937.

Hao Wang. A Logical Journey. From Gödel to Philosophy . MIT Press, 1996.

Kurt Gödel. Some remarks on the undecidability results. In Solomon Feferman, John Dawson, and Stephen Kleene, editors, Kurt Gödel: Collected Works, Vol. II , pages 305–306. Oxford University Press, 1972.

Hao Wang. Reflections on Kurt Gödel . Bradford Books. MIT Press, 1990.

Hao Wang. From Mathematics to Philosophy . Kegan Paul, London,UK, 1974.

Oron Shagrir. Gödel on Turing on computability. In Adam Olszewski, Jan Wolenski, and Robert Janusz, editors, Church’s Thesis after 70 Years , pages 393–419. Ontos-Verlag, 2006.

Arnon Avron. The problematic nature of Gödel’s disjunctions and Lucas-Penrose’s theses. Semiotic Studies , 34(1): 83–108, 2020.

Jon Barwise. An introduction to first-order logic. In Jon Barwise, editor, Handbook of Mathematical Logic , chapter A.1, pages 5–46. North-Holland, 1977.

Reinhard Kahle. Is there a “Hilbert Thesis?” Studia Logica , 107: 145–165, 2019.

Wilfried Sieg. Mechanical procedures and mathematical experience. In Alexander George, editor, Mathematics and Mind , pages 71–117. Oxford University Press, 1994.

Saul A. Kripke. The origins and nature of computation, 2006. URL https://www.youtube.com/watch?v=D9SP5wj882w . Presented at the 21st International Workshop on the History and Philosophy of Science. Jerusalem, Israel.

Robin Gandy. Church’s thesis and principles for mechanisms. In J. Barwise, D. Kaplan, H. J. Keisler, P. Suppes, and A. S. Troelstra, editors, The Kleene Symposium , volume 101 of Studies in Logic and The Foundations of Mathematics , pages 123–148. North-Holland, 1980.

Wilfried Sieg. Church without dogma: Axioms for computability. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable , pages 139–152, New York, 2007. Springer.

Moto-o Takahashi. A foundation of finite mathematics. Publications of the Research Institute for Mathematical Sciences , 12: 577–708, 1977.

Yuri Gurevich. What is an algorithm? In SOFSEM 2012: Theory and Practice of Computer Science , pages 31–42, 2012.

Yuri Gurevich. Sequential abstract state machines capture sequential algorithms. ACM Transactions on Computational Logic , 1: 77–111, 2000.

Donald E. Knuth. Algorithm and program; information and data. Communications of the ACM , 9: 654, 1968.

Emil L. Post. Absolutely unsolvable problems and relatively undecidable propositions: Account of an anticipation. In M. Davis, editor, Solvability, Provability, Definability: The Collected Works of Emil L. Post , pages 375–441. Birkhaüser, Boston, MA, 1994. Unpublished notes, 1941.

Andreĭ N. Kolmogorov. O ponyatii algoritma [On the concept of algorithm] (in Russian). Uspekhi Matematicheskikh Nauk [Russian Mathematical Surveys] , 8 (4): 1175–1176, 1953. English version in: Vladimir A. Uspensky and Alexei L. Semenov, Algorithms: Main Ideas and Applications , Kluwer, Norwell, MA, 1993, pp. 18–19.

Udi Boker and Nachum Dershowitz. Abstract effective models. In M. Fernández and I. Mackie, editors, New Developments in Computational Models: Proceedings of the First International Workshop on Developments in Computational Models (DCM 2005), Lisbon, Portugal (July 2005) , volume 135 of Electronic Notes in Theoretical Computer Science , pages 15–23, 2006.

Nachum Dershowitz and Yuri Gurevich. A natural axiomatization of computability and proof of Church’s Thesis. Bulletin of Symbolic Logic , 14 (3): 299–350, 2008. https://doi.org/10.2178/bsl/1231081370 .

Wolfgang Reisig. The computable kernel of Abstract State Machines. Theoretical Computer Science , 409: 126–136, 2008.

Udi Boker and Nachum Dershowitz. Three paths to effectiveness. In Andreas Blass, Nachum Dershowitz, and Wolfgang Reisig, editors, Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday , volume 6300 of Lecture Notes in Computer Science , pages 36–47, Berlin, 2010. Springer. URL http://nachum.org/papers/ThreePathsToEffectiveness.pdf .

Wilfried Sieg. Axioms for computability: Do they allow a proof of Church’s thesis? In Hector Zenil, editor, A Computable Universe. Understanding and Exploring Nature as Computation , pages 99–123. World Scientific/Imperial College Press, Singapore, 2013.

Elliott Mendelson. Introduction to Mathematical Logic . Discrete Mathematics and Its Applications. CRC Press, 5th edition, 2009.

William J. Rapaport. Philosophy of Computer Science . Online draft, 2020. URL https://cse.buffalo.edu/~rapaport/Papers/phics.pdf .

John E. Hopcroft and Jeffrey D. Ullman. Formal Languages and Their Relation to Automata . Addison-Wesley, Reading, MA, 1968.

Harry R. Lewis and Cristos H. Papadimitriou. Elements of the Theory of Computation . Prentice-Hall, Englewood Cliffs, NJ, 1981.

Máté Szabó. Kalmár’s argument against the plausibility of Church’s thesis. History and Philosophy of Logic , 39 (2): 140–157, 2018.

Benjamin Wells. Is there a nonrecursive decidable equational theory? Minds and Machines , 12 (2): 301–324, 2002.

Rózsa Péter. Rekursivität und konstruktivität. In A. Heyting, editor, Constructivity in Mathematics, Proceedings of the Colloquium Held at Amsterdam, 1957 , pages 226–233, Amsterdam, 1959. North-Holland.

Jean Porte. Quelques pseudo-paradoxes de la ‘calculabilite effective’. In Actes du 2me Congrès International de Cybernétique , pages 332–334, Namur, Belgium, 1960.

Elliott Mendelson. On some recent criticism of Church’s thesis. Notre Dame Journal of Formal Logic , IV (3): 201–205, July 1963.

MathSciNet   MATH   Google Scholar  

Yiannis N. Moschovakis. Review of four recent papers on Church’s thesis. Journal of Symbolic Logic , 33 (3): 471–472, 1968.

Stewart Shapiro. Acceptable notation. Notre Dame Journal of Formal Logic , 23 (1): 14–20, 1982.

Michael Rescorla. Copeland and Proudfoot on computability. Studies in History and Philosophy of Science Part A , 43 (1): 199–202, 2012. Reconsidering the Dynamics of Reason: A Symposium in Honour of Michael Friedman.

B. Jack Copeland and Diane Proudfoot. Deviant encodings and Turing’s analysis of computability. Studies in History and Philosophy of Science , 41: 247–252, September 2010.

Michael Rescorla. Church’s thesis and the conceptual analysis of computability. Notre Dame Journal of Formal Logic , 48 (2): 253–280, 2007.

Michał Wroclawski. Representations of natural numbers and computability of various functions. In Florin Manea, Barnaby Martin, Daniël Paulusma, and Giuseppe Primiero, editors, Proceedings of the 15th Conference on Computability in Europe - Computing with Foresight and Industry (CiE 2019, Durham, UK) , volume 11558 of Lecture Notes in Computer Science , pages 298–309. Springer, July 2019.

Udi Boker and Nachum Dershowitz. A hypercomputational alien. Applied Mathematics and Computation , 178 (1): 44–57, 2006.

Roger Penrose. The Emperor’s New Mind: Concerning Computers, Minds, and The Laws of Physics . Oxford University Press, New York, 1989.

Roger Penrose. Shadows of the Mind: A Search for the Missing Science of Consciousness . Oxford University Press, Oxford, 1994.

Christopher Strachey. An impossible program. Computer Journal , 7 (4): 313, 1965.

John R. Lucas. Minds, machines and Gödel. Philosophy , XXXVI: 112–127, 1961. Reprinted in The Modeling of Mind , K. M. Sayre and F. J. Crosson, eds., Notre Dame Press, 1963, pp. 269–270. https://doi.org/10.1017/S0031819100057983

Arnon Avron. Mishpete Gedel u-ve‘ayat ha-yesodot shel ha-matematikah (= Gödel’s Theorems and the Problem of the Foundations of Mathematics) . Broadcast University, Ministry of Defence, Jerusalem, Israel, 1998. In Hebrew.

David Chalmers, editor. Symposium on Roger Penrose’s Shadows of the Mind , volume 2, 1995. Association for the Scientific Study of Consciousness. URL http://journalpsyche.org/files/0xaa25.pdf .

Geoffrey LaForte, Patrick J. Hayes, and Kenneth M. Ford. Why Gödel’s theorem cannot refute computationalism. Artificial Intelligence , 104 (1–2): 265–286, 1998.

Nachum Dershowitz. The four sons of Penrose. In Proceedings 12th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR) (Montego Bay, Jamaica) , volume 3835 of Lecture Notes in Computer Science , pages 125–138. Springer, December 2005.

Martin Davis. The Universal Computer: The Road from Leibniz to Turing . CRC Press, 3rd edition, 2018.

Hilary Putnam. Book review: Shadows of the Mind by Roger Penrose. Bulletin of the American Mathematical Society , 32 (3): 370–373, July 1995.

John. C. Shepherdson. On the definition of computable function of a real variable. Zeitschrift für mathematische Logik und Grundlagen der Mathematik (Mathematical Logic Quarterly) , 22 (1): 391–402, 1976.

Oron Shagrir. Effective computation by humans and machines. Minds and Machines , 12: 221–240, 2002.

Wilfried Sieg and John Byrnes. An abstract model for parallel computations: Gandy’s thesis. The Monist , 82 (1): 150–164, 1999.

Olivier Bournez, Nachum Dershowitz, and Pierre Néron. An axiomatization of analog algorithms. In Computability in Europe 2016: Pursuit of the Universal (CiE, Paris, France) , volume 9709 of Lecture Notes in Computer Science , pages 215–224, Switzerland, June 2016. Springer. URL http://nachum.org/papers/AxiomatizationAnalog.pdf . Full version at https://arxiv.org/pdf/1604.04295v2.pdf .

Jack B. Copeland and Oron Shagrir. Physical computation: How general are Gandy’s principles for mechanisms? Minds and Machines , 17 (2): 217–231, 2007.

Pablo Arrighi and Gilles Dowek. The physical Church-Turing thesis and the principles of quantum theory. International Journal of Foundations of Computer Science , 23 (5): 1131–1145, 2012.

Tien D. Kieu. Quantum algorithm for Hilbert’s Tenth Problem. International Journal of Theoretical Physics , 42: 1461–1478, 2003.

Pablo Arrighi and Gilles Dowek. The principle of a finite density of information. In H. Zenil, editor, Irreducibility and Computational Equivalence , volume 2 of Emergence, Complexity and Computation , pages 127–134. Springer, Berlin, 2013.

David Beckman, Daniel Gottesman, Michael A. Nielsen, and John Preskill. Causal and localizable quantum operations. Phys. Rev. A , 64, 2001.

Benjamin Schumacher and Michael D. Westmoreland. Locality and information transfer in quantum operations. Quantum Information Processing , 4 (1): 13–34, 2005.

Apostolos Syropoulos. Hypercomputation: Computing Beyond the Church-Turing Barrier . Springer Science & Business Media, 2008.

Selmer Bringsjord and David A. Ferrucci. The narrative-based refutation of Church’s thesis. In Artificial Intelligence and Literary Creativity: Inside the Mind of BRUTUS, a Storytelling Machine , chapter 5, pages 105–148. Lawrence Erlbaum, Mahwah, NJ, 2000.

Selmer Bringsjord, Owen Kellett, Andrew Shilliday, Joshua Taylor, Bram van Heuveln, Yingrui Yang, Jeffrey Baumes, and Kyle Ross. A new Gödelian argument for hypercomputing minds based on the Busy Beaver problem. Applied Mathematics and Computation , 176 (2): 516–530, 2006.

Owen Kellett. A multi-faceted attack on the Busy Beaver problem. Master’s thesis, Rensselaer Polytechnic Institute, Troy, New York, July 2005.

Selmer Bringsjord and Michale Zenzen. Superminds: People Harness Hypercomputation, and More , volume 29 of Studies in Cognitive Systems . Kluwer Academic, Dordrecht, The Netherlands, 2003.

Warren Page. An interview with Herbert Robbins. The Two-Year College Mathematics Journal , 15 (1): 2–24, 1984.

Mario Stipčević and Çetin Kaya Koç. True random number generators. In Çetin Kaya Koç, editor, Open Problems in Mathematics and Computational Science , pages 275–315. Springer International Publishing, 2014.

G. Lee Bowie. An argument against Church’s thesis. The Journal of Philosophy , 70 (3): 66–76, 1973.

Cristian S. Calude. Algorithmic randomness, quantum physics, and incompleteness. In Proceedings of the Conference on Machines, Computations and Universality (MCU 2004) , volume 3354, pages 1–17, september 2004.

David Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 400: 97–117, 1985.

John Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing , 6 (4): 675–695, 1977.

Karl de Leeuw, Edward F. Moore, Claude E. Shannon, and Norman Shapiro. Computability by probabilistic machines. In Claude E. Shannon and John McCarthy, editors, Automata Studies , volume 34 of Annals of Mathematics Studies , pages 183–212. Princeton University Press, 1956.

Yuri Gurevich. Unconstrained Church-Turing thesis cannot possibly be true. Bull. EATCS , 127, 2019. URL http://bulletin.eatcs.org/index.php/beatcs/article/view/566/565 .

B. Jack Copeland. Accelerating Turing machines. Minds and Machines , 12 (2): 281–300, 2002.

E. Mark Gold. Limiting recursion. J. Symbolic Logic , 30 (1): 28–48, 1965.

Hilary Putnam. Trial and error predicates and the solution to a problem of Mostowski. J. Symbolic Logic , 30 (1): 49–57, 1965.

Hermann Weyl. Philosophy of Mathematics and Natural Science . Princeton University Press, 1949.

Adolf Grünbaum. Messrs. Black and Taylor on temporal paradoxes. Analysis , 12 (6): 144–148, 1952. URL http://www.jstor.org/stable/3326977 .

Gábor Etesi and István Németi. Non-Turing computations via Malament-Hogarth space-times. International Journal of Theoretical Physics , 41 (2): 341–370, 2002.

Mark L. Hogarth. Non-Turing computers and non-Turing computability. In Proceedings of the Philosophy of Science Association , volume 1994, pages 126–138, 1994.

Mark L. Hogarth. Does general relativity allow an observer to view an eternity in a finite time? Foundations of Physics Letters , 5 (2): 173–181, 1992.

Article   MathSciNet   Google Scholar  

Itamar Pitowsky. The physical Church thesis and physical computational complexity. Iyyun: The Jerusalem Philosophical Quarterly , 39: 81–99, 1990.

Oron Shagrir and Itamar Pitowsky. Physical hypercomputation and the Church-Turing thesis. Minds and Machines , 13 (1): 87–101, 2003.

John Earman and John D. Norton. Forever is a day: Supertasks in Pitowsky and Malament-Hogarth spacetimes. Philosophy of Science , 60 (1): 22–42, 1993.

Antony Galton. The Church-Turing thesis: Still valid after all these years? Applied Mathematics and Computation , 178: 93–102, 2006.

Paolo Cotogno. Hypercomputation and the physical Church-Turing thesis. The British Journal for the Philosophy of Science , 54 (2): 181–223, 2003.

Fred G. Abramson. Effective computation over the real numbers. In 12th Annual Symposium on Switching and Automata Theory (SWAT 1971) , pages 33–37, 1971.

Jean-Claude. Carréga. Théorie des corps - La règle et le compas . Hermann, Paris, 1981.

Pascal Schreck. On the mechanization of straightedge and compass constructions. Journal of Systems Science and Complexity , 32: 124–149, February 2019.

Jesper Lützen. Why was Wantzel overlooked for a century? The changing importance of an impossibility result. Historia Mathematica , 36 (4): 374–394, 2009.

Arnon Avron. Personal communication, 2020.

Hava T. Siegelmann. Neural Networks and Analog Computation: Beyond the Turing Limit . Birkhäuser, Boston, 1998.

Paul Cockshotta, Lewis Mackenzie, and Greg Michaelson. Physical constraints on hypercomputation. Theoretical Computer Science , 394: 159–174, 2008.

Cristian S. Calude and Boris Pavlov. Coins, quantum measurements, and Turing’s barrier. Quantum Information Processing , 1 (1): 107–127, 2002.

Michael A. Nielsen. Computable functions, quantum measurements, and quantum dynamics. Physical Review Letters , 79 (15): 2915–2918, 1997.

Andrew Hodges. Can quantum computing solve classically unsolvable problems? arXiv, 2005. URL http://arXiv.org/abs/quant-ph/0512248 .

Warren D. Smith. Three counterexamples refuting Kieu’s plan for “quantum adiabatic hypercomputation”; and some uncomputable quantum mechanical tasks. Applied Mathematics and Computation , 178 (1): 184–193, 2006. Special Issue on Hypercomputation.

Boris Tsirelson. The quantum algorithm of Kieu does not solve the Hilbert’s tenth problem. arXiv, November 2001. URL http://arXiv.org/abs/quant-ph/0111009.

John W. Carroll. Laws of nature. In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy . Metaphysics Research Lab, Stanford University, fall 2016 edition, 2016. URL https://plato.stanford.edu/archives/fall2016/entries/laws-of-nature .

George Kreisel. Mathematical logic: What has it done for the philosophy of mathematics? In Ralph Schoenman, editor, Bertrand Russell: Philosopher of the Century . George Allen and Unwin, London, 1967.

Robert Black. Proving Church’s Thesis. Philosophia Mathematica , 8 (3): 244–258, October 2000.

Download references

Acknowledgements

We are enormously grateful for comments and suggestions from Arnon Avron, Erwin Engeler, Oron Shagrir, Wilfried Sieg, and an anonymous reader.

Author information

Authors and affiliations.

School of Computer Science, Reichman University, Herzliya, Israel

School of Computer Science, Tel Aviv University, Ramat Aviv, Israel

Nachum Dershowitz

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Udi Boker .

Editor information

Editors and affiliations.

Departamento de Matemática, Faculdade de Ciências, Universidade de Lisboa, Lisboa, Portugal

Fernando Ferreira

Carl Friedrich von Weizsäcker-Zentrum, Universität Tübingen, Tübingen, Germany

Reinhard Kahle

Department of Mathematics, ETH Zurich, Zurich, Switzerland

Giovanni Sommaruga

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this chapter

Boker, U., Dershowitz, N. (2022). What is the Church-Turing Thesis?. In: Ferreira, F., Kahle, R., Sommaruga, G. (eds) Axiomatic Thinking II. Springer, Cham. https://doi.org/10.1007/978-3-030-77799-9_9

Download citation

DOI : https://doi.org/10.1007/978-3-030-77799-9_9

Published : 18 September 2022

Publisher Name : Springer, Cham

Print ISBN : 978-3-030-77798-2

Online ISBN : 978-3-030-77799-9

eBook Packages : Mathematics and Statistics Mathematics and Statistics (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 Numismatics
• Classical Literature
• Classical Reception
• Classical History
• Classical Philosophy
• Classical Mythology
• Classical Art and Architecture
• Classical Oratory and Rhetoric
• Greek and Roman Archaeology
• Greek and Roman Epigraphy
• Greek and Roman Law
• Greek and Roman Papyrology
• Late Antiquity
• Religion in the Ancient World
• Social History
• 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 Agriculture
• History of Education
• History of Emotions
• 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 Variation
• Language Families
• Language Acquisition
• Language Evolution
• Language Reference
• Lexicography
• Linguistic Theories
• Linguistic Typology
• Linguistic Anthropology
• Phonetics and Phonology
• Psycholinguistics
• Sociolinguistics
• Translation and Interpretation
• Writing Systems
• Browse content in Literature
• Bibliography
• Children's Literature Studies
• Literary Studies (Modernism)
• Literary Studies (Asian)
• Literary Studies (European)
• Literary Studies (Eco-criticism)
• Literary Studies (Romanticism)
• Literary Studies (American)
• 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 Culture
• Music and Religion
• Music and Media
• 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 Action
• Philosophy of Law
• Philosophy of Religion
• Philosophy of Science
• Philosophy of Language
• Philosophy of Mind
• Philosophy of Perception
• 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 Society
• Law and Politics
• Browse content in Legal System and Practice
• Courts and Procedure
• Legal Skills and Practice
• Legal System - Costs and Funding
• 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
• Restitution
• 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
• 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 Oncology
• Medical Toxicology
• Pain Medicine
• Palliative Medicine
• Rehabilitation Medicine
• Respiratory Medicine and Pulmonology
• Rheumatology
• Sleep Medicine
• Sports and Exercise Medicine
• Clinical Neuroscience
• Community Medical Services
• Critical Care
• Emergency Medicine
• Forensic Medicine
• Haematology
• History of Medicine
• Medical Ethics
• Browse content in Medical Dentistry
• Oral and Maxillofacial Surgery
• Paediatric Dentistry
• Restorative Dentistry and Orthodontics
• Surgical Dentistry
• Browse content in Medical Skills
• Clinical Skills
• Communication Skills
• Nursing Skills
• Surgical Skills
• 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 Games
• Computer Security
• 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 Neuroscience
• Cognitive Psychology
• 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 History
• Business Strategy
• Business Ethics
• Business and Government
• Business and Technology
• 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
• Social Issues in Business and 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 Methodology
• Economic Systems
• Economic History
• 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)
• Management of Land and Natural Resources (Social Science)
• Natural Disasters (Environment)
• Pollution and Threats to the Environment (Social Science)
• Social Impact of Environmental Issues (Social Science)
• Sustainability
• 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
• Ethnic Politics
• European Union
• Foreign Policy
• Gender and Politics
• Human Rights and Politics
• Indian Politics
• International Relations
• International Organization (Politics)
• Irish Politics
• Latin American Politics
• Middle Eastern Politics
• Political Theory
• Political Methodology
• Political Communication
• Political Philosophy
• Political Sociology
• Political Behaviour
• Political Economy
• Political Institutions
• Politics and Law
• Politics of Development
• Public Administration
• Public Policy
• Qualitative Political Methodology
• 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
• Disability Studies
• 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.

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.

• Trending Categories

• 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

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.

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

What's the significance of the Church-Turing Thesis?

My understanding is that the thesis is essentially a definition of the term "computable" to mean something that is computable on a Turing Machine.

Is this really all there is to it? If so, what makes this definition so important? What makes this definition so significant as to warrant having it's own name?

In most other branches of mathematics, a definition is an important part of the scaffolding, but not a result onto itself. In the case of the Church Turing Thesis, it seems like there must be more, but all I can see is the definition.

So, what is the significance of the Church-Turing Thesis?

• soft-question
• computability
• turing-machines

• $\begingroup$ Not exactly ... The rigorous definition of Turing machine gives as the precise mathematical concept of "Turing computable". The same for the many other equivalent definitions : recursive function, etc. It is quite obvious that any Turing computable fucntion or relation is intuitively effectively (i.e.mechanically) computableThe Church-Turing thesis is the "unprovable" assertion that all functions intuitively computable are Turing computable, i.e. that the mathematically rigorous def of Tuting computability (and its equivalents) exhasut the intuitive content of "mechanically" computable. $\endgroup$ –  Mauro ALLEGRANZA Commented Apr 28, 2015 at 11:53
• $\begingroup$ As far as I can see, the thesis is not importand because of its definition, but because it provides a bridge between the real world, where functions are effectively computable or not, and the theoretical world of mathematics, in which we have a strict definition of what "computable" means. $\endgroup$ –  5xum Commented Apr 28, 2015 at 11:55

2 Answers 2

The answer from user73985 explains the content of the Church-Turing thesis, but I'd like to add a few words about its value; why do we want it.

The first benefit that we get from this thesis is that it lets us connect formal mathematical theorems to real-world issues of computability. For example, the theorem that the word problem for groups is Turing-undecidable has the real-world interpretation that no algorithm can solve all instance of the word problem.

The second benefit is in mathematics itself, specifically in computability theory. Published proofs that something is Turing-computable almost never proceed by exhibiting a Turing-machine program, or indeed a program in any actual computing language. Sometimes, if the matter is simple enough, they provide some sort of pseudo-code. Most often, though, they merely give an informal description of an algorithm. It is left to the reader to see that this actually does give an algorithm (in the intuitive sense) and therefore, by the Church-Turing thesis, could be simulated by a Turing machine. The usual situation is that, although experts in Turing-machine programming would (if they existed) be able to routinely convert the intuitive algorithm into a Turing machine program, the program would be too large and complicated to be worth writing down.

• $\begingroup$ Isn't this a bit of a tautology? you can't prove the thesis, since the informal notion of computability isn't well defined without the thesis. Then, you use the thesis to "bridge" between the formal and the informal, even though you don't actually know the bridge exists! $\endgroup$ –  Nathaniel Bubis Commented Apr 28, 2015 at 12:44
• $\begingroup$ @nbubis I"ll go out on a limb and say that I do know the bridge exists, i.e., I do know that the Church-Turing thesis is true. Of course, as you said, I can't prove that mathematically, since it involves the non-mathematical notion of intuitive computability. But I know lots of things that I can't prove mathematically, for example, the fact that I'm typing this comment. There is, of course, an issue about the use of such non-mathematical knowledge in a mathematical proof; hence the last sentence in my answer: You could give a mathematical proof instead, but it would be messy. $\endgroup$ –  Andreas Blass Commented Apr 28, 2015 at 12:49

The idea is that we have an informal notion of "computable" - that is, "something that can be computed". (This is explicitly not a precise definition). We also have a formal definition of "computable", that is, "computable by a Turing machine". The Church-Turing thesis is that these two notions coincide, that is, anything that "should" be computable is in fact computable by a Turing machine. (It's pretty clear that anything that is computable by a Turing machine is computable in the more informal sense).

Put another way, the Church-Turing thesis says that "computable by a Turing machine" is a correct definition of "computable".

• $\begingroup$ One might add that another reason why we can believe that "computable by a Turing machine" is the correct definition of "computable", because "GOTO" and "WHILE" computabilities are equivalent to Turing-computability. So three different approaches lead to the same kind of computability, which is why we can believe that they describe the "correct" definition of computability. $\endgroup$ –  TheWaveLad Commented Apr 28, 2015 at 12:01

You must log in to answer this question.

Not the answer you're looking for browse other questions tagged soft-question computability turing-machines ..

• Featured on Meta
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Bringing clarity to status tag usage on meta sites
• 2024 Community Moderator Election
• 2024 Election Results: Congratulations to our new moderator!

Hot Network Questions

• Calling get_GeodesicArea from ogr2ogr
• The McDonald's Option
• bash script quoting frustration
• Would weightlessness (i.e. in thrill rides, planes, skydiving, etc.) be different on a Flat Earth?
• Did anyone ever ask Neil Armstrong whether he said "for man" or "for a man?"
• block-structure matrix
• Fitting 10 pieces of pizza in a box
• How does a closed-cycle rocket engine keep the chamber pressure from stalling the pump turbine?
• Can objective morality be derived as a corollary from the assumption of God's existence?
• How do we know for sure that the dedekind axiom is logically independent of the other axioms?
• Why do combinatorists care about Kazhdan–Lusztig polynomials?
• \includegraphics not reading \newcommand
• Ethics application: secondary analysis of anonymous data without "future use" consent
• I can't select a certain record with like %value%
• Is it OK to use the same field in the database to store both a percentage rate and a fixed money fee?
• Travel to UK with temporary passport as EU citizen
• Kids' educational VHS series about a man who's friends with a parrot and a chimpanzee
• How would Earth's plants change in this speculated Earth-like planet?
• Why is global state hard to test? Doesn't setting the global state at the beginning of each test solve the problem?
• How to raise a vector to powers contained in a vector, change the list into a product, and do this for all the lines of a matrix, efficiently?
• Should I be worried about this giant crack?
• Why did Worf respond when Picard ordered the Enterprise out of the asteroid in TNG: The Pegasus?
• How to add a segment to an Excel radar plot
• Explaining Arithmetic Progression