## The Church-Turing Thesis

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

## The Thesis and its History

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

All computable functions are computable by Turing machine.

Corollaries such as the following are sometimes offered:

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

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

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

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

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

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

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

So too Johnson-Laird, and the Churchlands:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

## Margin Size

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

selected template will load here

This action is not available.

## 3.1.9: The Church-Turing Thesis

- Last updated
- Save as PDF
- Page ID 121737

- Richard Zach et al.
- Open Logic Project

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

## Church-Turing Thesis

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

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

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

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

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

This entry contributed by Todd Rowland

## Explore with Wolfram|Alpha

More things to try:

- .1234 with the last 2 digits repeating
- CNF (P && ~Q) || (R && S) || (Q && R && ~S)
- Is {{3,-3},{-3,5}} positive definite?

## 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

## IMAGES

## VIDEO

## COMMENTS

The Church-Turing Thesis. First published Wed Jan 8, 1997; substantive revision Mon Dec 18, 2023. The Church-Turing thesis (or Turing-Church thesis) is a fundamental claim in the theory of computability. It was advanced independently by Church and Turing in the mid 1930s. There are various equivalent formulations of the thesis.

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 computability theory, the Church-Turing thesis (also known as computability thesis, the Turing-Church thesis, the Church-Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of computable functions.It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing ...

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.

The Church-Turing Thesis has two parts: Turing's Thesis: The Turing Machine is equivalent in power to the Human Mind Church's Thesis: Any serious formalization of computation is equivalent to the Turing machine Together, these imply that a Turing Machine, although incredibly simple, is an excellent choice for us to reason about computation.

What is the Church-Turing Thesis? "Algorithm" is an informal, intuitive notion of a process. A set of instructions to complete some task. A Turing Machine is a formal definition of a model of computation The Church-Turing Thesis asserts that the Turing machine captures the intuitive definition. That everything computable in the intuitive sense is computable by a

The Extended Church-Turing Thesis , otherwise known as the Invariance Thesis , is more presumptuous. It asserts, not only that there is a Turing machine corresponding to each effective algorithm, but that there is one that is no more than polynomially slower (counting atomic actions) than any other effective means of performing that computation.

In particular, the Church-Turing thesis is invoked to claim that the so-called halting problem not only cannot be solved by Turing machines, it cannot be effectively solved at all. This page titled 3.1.9: The Church-Turing Thesis is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. ( Open Logic ...

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.

Let me describe some of these methods that arrive at the identification of the effectively enumerable sets with the E sets. The proofs that these methods all yield the same result is labor intensive and not a little tedious, so I won't attempt it here. Turing machines. Alan Turing, in his senior undergraduate thesis at Cambridge, attempted to

Church-Turing Thesis: The partial functions over the natural numbers that can be effectively computed are exactly the functions that can be computed by Turing machines. 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].

Church's Thesis (Church-Turing Thesis) All formalisms powerful enough to describe everything we think of as a computational algorithm are equivalent. Implication: we should not expect to find some other reasonable computational model that is more powerful • that can solve problems not solvable by Turing machines

Examples of Turing Machines 30 •example: describe a Turing machine M 1 that describes B = {w#w | w ∈ {0,1}*}, cont. •state diagram explanation •label 0,1 → R on arc from q 3 to itself •stay in q 3 and move to right when reading a 0 or 1 in state q 3 •do not change symbol on tape •stage 1 implemented by q 1 through q 7

Perhaps a modern programming language, such as Java, can describe processes which cannot be carried out by a Turing machine. Alan Turing argued that his model was a correct formulation of effective computability. He defended the following proposition, which has come to be called the Church-Turing thesis in acknowledgment of the

history of the subject, and going to lead to our discussion of what's called the Church Turing thesis. So we will get to that in due course. And we'll also talk about some notation for notations for Turing machines and for encoding objects to feed into Turing machines as input, but we'll get to that shortly as well. So let's move on, then.

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 ...

Church-Turing Thesis ~1936 Alan Turing 1912-1954 Alonzo Church 1903-1995 Algorithm = Turing machine Intuitive Formal Instead of Turing machines, ... We will use high-level English descriptions of algorithms when we describe TMs, knowing that we could (in principle) convert those descriptions into states,

The history of the Church-Turing thesis ("thesis") involves the history of the development of the study of the nature of functions whose values are effectively calculable; or, in more modern terms, functions whose values are algorithmically computable. It is an important topic in modern mathematical theory and computer science, particularly associated with the work of Alonzo Church and Alan ...

The Church-Turing Thesis states that any problem that can be solved via some step-by-step algorithm can be solved by a Turing machine. Because of the Church-Turing thesis, we may use other algorithmic means besides the Turing machine to describe an algorithm. With that said, there are occasions when we will need to work with Turing

Church-Turing Thesis; Persistent Turing Machines; Sequential Interaction Thesis; computation expressiveness; paradigm shift 1. Introduction Computer science, like other disciplines, aims to describe its nature by fundamental principles that distinguish its goals and methods from those of related disciplines. Physics relied for centuries on ...