church turing machine 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.

• Best Twitch Extensions for 2024: Top Tools for Viewers and Streamers
• Discord Emojis List 2024: Copy and Paste
• Best Adblockers for Twitch TV: Enjoy Ad-Free Streaming in 2024
• PS4 vs. PS5: Which PlayStation Should You Buy in 2024?
• Full Stack Developer Roadmap [2024 Updated]

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:

• 1+2+3+...+10
• fewer than 4 2's with eight 4-sided dice
• mirror transformation matrix

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

A Church-Turing Thesis for Randomness?

• Conference paper
• First Online: 02 July 2021
• Cite this conference paper

• Johanna N. Y. Franklin   ORCID: orcid.org/0000-0002-7216-1562 12  

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12813))

Included in the following conference series:

• Conference on Computability in Europe

802 Accesses

We discuss the difficulties in stating an analogue of the Church-Turing thesis for algorithmic randomness. We present one possibility and argue that it cannot occupy the same position in the study of algorithmic randomness that the Church-Turing thesis does in computability theory. We begin by observing that some evidence comparable to that for the Church-Turing thesis does exist for this statement: in particular, there are other reasonable formalizations of the intuitive concept of randomness that lead to the same class of random sequences (the Martin-Löf random sequences). However, we consider three properties that we would like a random sequence to satisfy and find that the Martin-Löf random sequences do not necessarily possess these properties to a greater degree than other types of random sequences, and we further argue that there is no more appropriate version of the Church-Turing thesis for algorithmic randomness. This suggests that consensus around a version of the Church-Turing thesis in this context is unlikely.

Supported in part by Simons Foundation Collaboration Grant #420806.

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

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Computable Randomness Is About More Than Probabilities

The Mathematical Foundations of Randomness

Randomness Deficiencies

We note that there are other randomness notions that also exhibit computational weakness, e.g., weak 2-randomness. However, we discuss difference randomness here because the difference random sequences can be identified as the Martin-Löf random sequences that are computationally weak in these two standard senses.

The reader may have noted that we are working in a general computable probability space rather than the Cantor space. This is possible because any computable probability space is isomorphic to the Cantor space in every relevant way and our notions of randomness transfer naturally [ 13 ].

There is a subtlety in this result in that an incomputable function may be computable as a vector, hence the “essentially."

Bauwens, B.: Uniform van Lambalgen’s theorem fails for computable randomness. ArXiv e-prints (2015)

Google Scholar  

Bienvenu, L., Day, A., Mezhirov, I., Shen, A.: Ergodic-type characterizations of algorithmic randomness. In: Ferreira, F., Löwe, B., Mayordomo, E., Mendes Gomes, L. (eds.) CiE 2010. LNCS, vol. 6158, pp. 49–58. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13962-8_6

Chapter   Google Scholar  

Brattka, V., Miller, J.S., Nies, A.: Randomness and differentiability. Trans. Amer. Math. Soc. 368 (1), 581–605 (2016)

Chaitin, G.J.: A theory of program size formally identical to information theory. J. Assoc. Comput. Mach. 22 , 329–340 (1975)

Article   MathSciNet   Google Scholar  

Downey, R.G., Griffiths, E.J.: Schnorr randomness. J. Symbolic Logic 69 (2), 533–554 (2004)

Downey, R.G., Hirschfeldt, D.R.: Algorithmic Randomness and Complexity. Springer, New York (2010)

Book   Google Scholar  

Franklin, J.N., Greenberg, N., Miller, J.S., Ng, K.M.: Martin-Löf random points satisfy Birkhoff’s ergodic theorem for effectively closed sets. In: Proceedings of the American Mathematical Society, vol. 140, no. 10, pp. 3623–3628 (2012)

Franklin, J.N., McNicholl, T.H., Rute, J.: Algorithmic randomness and Fourier analysis. Theory Comput. Syst. 63 (3), 567–586 (2019)

Franklin, J.N., Ng, K.M.: Difference randomness. In: Proceedings of the American Mathematical Society, vol. 139, no. 1, pp. 345–360 (2011)

Franklin, J.N., Stephan, F.: Van Lambalgen’s theorem and high degrees. Notre Dame J. Formal Logic 52 (2), 173–185 (2011)

Franklin, J.N., Towsner, H.: Randomness and non-ergodic systems. Mosc. Math. J. 14 (4), 711–744 (2014)

Gács, P., Hoyrup, M., Rojas, C.: Randomness on computable probability spaces–a dynamical point of view. Theory Comput. Syst. 48 (3), 465–485 (2011). https://doi.org/10.1007/s00224-010-9263-x . http://dx.doi.org/10.1007/s00224-010-9263-x

Hoyrup, M., Rojas, C.: Computability of probability measures and Martin-Löf randomness over metric spaces. Inform. Comput. 207 (7), 830–847 (2009). https://doi.org/10.1016/j.ic.2008.12.009 . http://dx.doi.org/10.1016/j.ic.2008.12.009

Kučera, A.: Measure, \(\pi ^0_1\) , -classes and complete extensions of PA. In: Ebbinghaus, H.-D., Müller, G.H., Sacks, G.E. (eds.) Recursion Theory Week. LNM, vol. 1141, pp. 245–259. Springer, Heidelberg (1985). https://doi.org/10.1007/BFb0076224

van Lambalgen, M.: The axiomatization of randomness. J. Symbolic Logic 55 (3), 1143–1167 (1990)

Levin, L.A.: Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory. Ph.D. thesis, Moscow University (1971)

Levin, L.A.: Laws on the conservation (zero increase) of information, and questions on the foundations of probability theory. Problemy Peredači Informacii 10 (3), 30–35 (1974)

MathSciNet   Google Scholar  

Lévy, P.: Téorie de l’Addition des Variables Aléatoires. Gauthier-Villars, Paris (1937)

MATH   Google Scholar  

Martin-Löf, P.: The definition of random sequences. Inf. Control 9 , 602–619 (1966)

Miyabe, K.: Truth-table Schnorr randomness and truth-table reducible randomness. MLQ Math. Log. Q. 57 (3), 323–338 (2011). https://doi.org/10.1002/malq.200910128 . http://dx.doi.org/10.1002/malq.200910128

Miyabe, K., Rute, J.: van Lambalgen’s theorem for uniformly relative Schnorr and computable randomness. In: Downey, R., et al. (eds.) Proceedings of the Twelfth Asian Logic Conference, pp. 251–270. World Scientific (2013)

Nies, A.: Computability and Randomness. Clarendon Press, Oxford (2009)

Porter, C.P.: The equivalence of definitions of algorithmic randomness. Philosophia Mathematica To appear

Porter, C.P.: On analogues of the Church-Turing thesis in algorithmic randomness. Rev. Symb. Log. 9 (3), 456–479 (2016). https://doi.org/10.1017/S1755020316000113 . https://doi.org.ezproxy.hofstra.edu/10.1017/S1755020316000113

Rute, J.: Topics in Algorithmic Randomness and Computable Analysis. Ph.D. thesis, Carnegie Mellon University (2013)

Rute, J.: Algorithmic randomness and computable measure theory. In: Franklin, J.N., Porter, C.P. (eds.) Algorithmic Randomness: Progress and Prospects, pp. 58–114. Cambridge University Press, New York, NY (2020)

Schnorr, C.: A unified approach to the definition of random sequences. Math. Syst. Theory 5 , 246–258 (1971)

Schnorr, C.P.: Invarianzeigenschaften von Zufallsfolgen. Zufälligkeit und Wahrscheinlichkeit. LNM, vol. 218, pp. 83–88. Springer, Heidelberg (1971). https://doi.org/10.1007/BFb0112470

Stephan, F.: Martin-Löf Random and PA-complete Sets. Tech. Rep. 58, Matematisches Institut, Universität Heidelberg, Heidelberg (2002)

Turing, A.M.: Intelligent machinery. Tech. rep, National Physical Laboratory (1948)

V \(^{\prime }\) yugin, V.V.: Effective convergence in probability, and an ergodic theorem for individual random sequences. Teor. Veroyatnost. i Primenen. 42 (1), 35–50 (1997). https://doi.org/10.1137/S0040585X97975915 . http://dx.doi.org/10.1137/S0040585X97975915

Download references

Author information

Authors and affiliations.

Hofstra University, Hempstead, NY, 11590, USA

Johanna N. Y. Franklin

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Johanna N. Y. Franklin .

Editor information

Editors and affiliations.

University of Lille, Lille, France

Liesbeth De Mol

Vakgroep Wiskunde, Ghent University, Ghent, Belgium

Andreas Weiermann

University of Göttingen, Göttingen, Germany

Florin Manea

Ghent University, Ghent, Belgium

David Fernández-Duque

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Cite this paper.

Franklin, J.N.Y. (2021). A Church-Turing Thesis for Randomness?. In: De Mol, L., Weiermann, A., Manea, F., Fernández-Duque, D. (eds) Connecting with Computability. CiE 2021. Lecture Notes in Computer Science(), vol 12813. Springer, Cham. https://doi.org/10.1007/978-3-030-80049-9_20

Download citation

DOI : https://doi.org/10.1007/978-3-030-80049-9_20

Published : 02 July 2021

Publisher Name : Springer, Cham

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

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

eBook Packages : Computer Science Computer Science (R0)

Share this paper

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

A Church-Turing Thesis for Randomness?

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options, index terms.

Mathematics of computing

Probability and statistics

Probabilistic reasoning algorithms

Theory of computation

Computational complexity and cryptography

Complexity classes

Formal languages and automata theory

Models of computation

Computability

Turing machines

Recommendations

When does randomness come from randomness.

A result of Shen says that if F : 2 N ź 2 N is an almost-everywhere computable, measure-preserving transformation, and y ź 2 N is Martin-Löf random, then there is a Martin-Löf random x ź 2 N such that F ( x ) = y . Answering a question of Bienvenu and ...

Motivating the Church-Turing thesis in the twenty-first century

Theory of Computation students frequently fail to appreciate the significance of the Church---Turing Thesis for one of two reasons. First, there is a tendency, on the part of students, to regard Church---Turing as tautologous and, consequently, devoid ...

Information

Published in.

University of Lille, Lille, France

Vakgroep Wiskunde, Ghent University, Ghent, Belgium

University of Göttingen, Göttingen, Germany

Ghent University, Ghent, Belgium

Springer-Verlag

Berlin, Heidelberg

Publication History

Author tags.

• Church-Turing thesis
• Algorithmic randomness
• Computability theory

Contributors

Other metrics, bibliometrics, article metrics.

• 0 Total Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0

View options

Login options.

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.

• Organisation and Campuses
• International outreach
• Contracting and sales
• Work with us
• Quality Assurance
• Guide to choosing your programme
• First and Single Cycle Degree
• Second Cycle Degree
• Course units, transferable skills, MOOCs
• PhDs and Professional Masters programmes, Specialisations and advanced training
• Study grants and subsidies
• Enrolment, fees and other procedures
• Incoming and outgoing international mobility
• Towards the job market
• Life at university and in the city
• The latest news from Alma Mater research
• Research in numbers
• Research areas and projects
• NRRP – Opportunities, expectations and results
• Research organisation and infrastructure
• Research evaluation
• Networking for research
• Open Science
• Research at Unibo
• Research for society and businesses
• People and the community
• Business and nonprofit
• Bodies and institutions
• Development cooperation
• Continuing education
• Sustainability
• Events and news
• Prospective bachelor's students
• Enrolled students
• Organizations and companies

97263 - Mathematical Foundations of Quantum Computation

Academic year 2024/2025.

• Docente: Giacomo De Palma
• SSD: MAT/07
• Language: English
• Teaching Mode: Traditional lectures
• Campus: Bologna
• Corso: Second cycle degree programme (LM) in Mathematics (cod. 5827)

Learning outcomes

At the end of the course the student is acquainted with the basic aspects of quantum computation like those of entanglement, qubits, quantum algorithms and information. He is able to deal with the classical problems of the subject.

Course contents

Prerequisites

The basic courses of the BSc (Laurea Triennale) in Mathematics. Knowledge of linear algebra is particularly important.

Historical introduction; overview of the course

Hilbert spaces and Dirac notation; spectral theorem (no proof); positive semidefinite operators; Hilbert-Schmidt inner product

Density operators; Pauli matrices; the Bloch sphere; unitary evolution; quantum measurements; projective measurements; distinguishing quantum states; quantum observables; compatible observables; single-qubit projective measurements

Tensor product of Hilbert spaces and of linear operators; composite quantum systems; partial measurements; partial trace; reduced density operator; singular value decomposition; Schmidt decomposition

EPR paradox and CHSH inequality

Turing machines; uncomputability of the halting function; Boolean circuits; the strong Church-Turing thesis; decision problems; formal languages; the complexity classes P, BPP, NP and PSPACE; reducibility; NP-complete problems; reversible computation

Quantum circuits; duality between the operator norm and the trace norm; Helstrom bound; Solovay-Kitaev theorem (no proof); CNOT gate; universality of {H,T,CNOT} gates

The complexity class BQP; BPQ is included in PSPACE; quantum parallelism; oracles

Deutsch algorithm; Deutsch-Jozsa algorithm; Bernstein-Vazirani algorithm; Simon's algorithm

The quantum Fourier transform; quantum phase estimation

The period-finding algorithm; the order-finding algorithm; Shor's algorithm; the hidden subgroup problem

The one-time pad; public key cryptography; the RSA protocol; Grover's algorithm; quantum counting algorithm; optimality of quantum counting

Quantum operations; Kraus representation; isometric dilations; bit-flip and phase-flip channels; depolarizing channel

Quantum key distribution; the BB84 protocol

Quantum error correction; classical repetition code; bit-flip and phase-flip codes; Shor's 9-qubit code

Readings/Bibliography

The lectures will mostly follow the books

Michael A. Nielsen, Isaac L. Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2010

Wolfgang Scherer, "Mathematics of Quantum Computing", Springer, 2019

Further resources available online are

Ronald de Wolf, "Quantum Computing: Lecture Notes", arXiv:1907.09415, https://arxiv.org/abs/1907.09415

John Preskill, "Quantum Computation" (lecture notes),  http://theory.caltech.edu/~preskill/ph229/

Teaching methods

Classroom lectures

Assessment methods

The grade will be assigned upon oral examination. Each exam will include theoretical questions and the solution of a simple exercise. The student will be evaluated both on the understanding of the content of the lectures and on the ability to apply it. The students who achieve an organic vision of the topics, are able to critically apply them and master the specific language will be assessed with a grade of excellence. The students who show a mechanic or mnemonic knowledge of the topics, have limited capabilities of analysis and synthesis or a correct but not always appropriate language will be assessed with an average grade. The students who show a minimal knowledge of the topics and of the appropriate language will be assessed with the minimum passing grade. The students who show poor knowledge of the topics, inappropriate language and are not able to properly understand the material will be assessed with a non-passing grade.

Office hours

See the website of Giacomo De Palma