turing computability thesis

Collectibles

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

by history tools
March 28, 2024

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

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

Origins of Computability Theory in the 1930s

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

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

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

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

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

Computable and Uncomputable Functions

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

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

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

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

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

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

Variations and Extensions to the Church-Turing Thesis

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

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

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

The Computational Lens on Mind and Universe

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

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

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

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

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

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

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

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

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

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

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

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

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

Key Insights

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

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

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

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

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

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

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

Church’s thesis. “We now define the notion … of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers (or of a λ-definable function of positive integers).” 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Submit an Article to CACM

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

You Just Read

January 2019 Issue

Published: January 1, 2019

Vol. 62 No. 1

Pages: 66-74

Join the Discussion (0)

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

Dark Patterned Voices Manipulate Users

laptop computer with megaphone, illustration

Nobel Prizes and AI: The Promise, the Peril, and the Path Forward

entrance to the Nobel Prize Museum, Stockholm

The Software Sins of Bloat and Debt

complex flowchart on a scale with OMG! on the display, illustration

Shape the Future of Computing

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

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

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

Search Menu

Sign in through your institution

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

Machines and Thought: The Legacy of Alan Turing Volume 1

< Previous chapter
Next chapter >

8 The Church-Turing Thesis: Its Nature and Status

Published: November 1996
Cite Icon Cite
Permissions Icon Permissions

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

Personal account

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

Institutional access

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

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

IP based access

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

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

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

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

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

Society Members

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

Sign in through society site

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

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

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

Sign in using a personal account

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

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

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

Viewing your signed in accounts

Click the account icon in the top right to:

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

Signed in but can't access content

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

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

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

Month:	Total Views:
September 2024	2

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

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

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

This Feature Is Available To Subscribers Only

This PDF is available to Subscribers Only

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

The Church-Turing Thesis

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

Our systems are now restored following recent technical disruption, and we’re working hard to catch up on publishing. We apologise for the inconvenience caused. Find out more: https://www.cambridge.org/universitypress/about-us/news-and-blogs/cambridge-university-press-publishing-update-following-technical-disruption

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings .

Login Alert

> Turing's Legacy
> Turing and the discovery of computability

Book contents

Frontmatter
Turing's legacy: developments from Turing's ideas in logic
Computability and analysis: the legacy of Alan Turing
Alan Turing and the other theory of computation (expanded)
Turing in Quantumland
Computability theory, algorithmic randomness and Turing's anticipation
Computable model theory
Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
Mathematics in the age of the Turing machine
Turing and the development of computational complexity
Turing machines to word problems
Musings on Turing's Thesis
Higher generalizations of the Turing Model
Step by recursive step: Church's analysis of effective calculability
Turing and the discovery of computability
Transfinite machine models

Published online by Cambridge University Press: 05 June 2014

Abstract . In §1 we give a short overview for a general audience of Godel, Church, Turing, and the discovery of computability in the 1930s. In the later sections we mention a series of our previous papers where a more detailed analysis of computability, Turing's work, and extensive lists of references can be found. The sections from §2—§9 challenge the conventional wisdom and traditional ideas found in many books and papers on computability theory. They are based on a half century of my study of the subject beginning with Church at Princeton in the 1960s, and on a careful rethinking of these traditional ideas.

The references in all my papers and books are given in the format, author [year], as in Turing [1936], in order that the references are easily identified without consulting the bibliography and are uniform over all papers. A complete bibliography of historical articles from all my books and papers on computabilityis given on the page as explained in §10.

§1. A very brief overview of computability .

1.1. Hilbert's programs . Around 1880 Georg Cantor, a German mathematician, invented naive set theory. A small fraction of this is sometimes taught to elementary school children. It was soon discovered that this naive set theory was inconsistent because it allowed unbounded set formation, such as the set of all sets. David Hilbert, the world's foremost mathematician from 1900 to 1930, defended Cantor's set theory but suggested a formal axiomatic approach to eliminate the inconsistencies. He proposed two programs.

Access options

Save book to kindle.

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle .

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service .

By Robert Irving Soare , The University of Chicago
Edited by Rod Downey , Victoria University of Wellington
Book: Turing's Legacy
Online publication: 05 June 2014
Chapter DOI: https://doi.org/10.1017/CBO9781107338579.014

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox .

Save book to Google Drive

Turing Computability

Theory and Applications

© 2016
Robert I. Soare 0

Department of Mathematics, The University of Chicago, Chicago, USA

You can also search for this author in PubMed Google Scholar

Author is among the world's leading authorities on the topic of computability
Content has been thoroughly class-tested for many years by hundreds of lecturers and teachers in this field
Emphasizes the art of computability, that is, a skill to be practiced but also important an esthetic sense of beauty and taste in mathematics

Part of the book series: Theory and Applications of Computability (THEOAPPLCOM)

74k Accesses

63 Citations

21 Altmetric

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

Access this book

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
Compact, lightweight edition
Dispatched in 3 to 5 business days
Free shipping worldwide - see info
Durable hardcover edition

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

About this book

Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine. This model led to both the development of actual computers and to computability theory, the study of what machines can and cannot compute. This book presents classical computability theory from Turing and Post to current results and methods, and their use in studying the information content of algebraic structures, models, and their relation to Peano arithmetic. The author presents the subject as an art to be practiced, and an art in the aesthetic sense of inherent beauty which all mathematicians recognize in their subject.

Part I gives a thorough development of the foundations of computability, from the definition of Turing machines up to finite injury priority arguments. Key topics include relative computability, and computably enumerable sets, those which can be effectively listed but not necessarily effectively decided, such as the theorems of Peano arithmetic. Part IIincludes the study of computably open and closed sets of reals and basis and nonbasis theorems for effectively closed sets. Part III covers minimal Turing degrees. Part IV is an introduction to games and their use in proving theorems. Finally, Part V offers a short history of computability theory.

The author has honed the content over decades according to feedback from students, lecturers, and researchers around the world. Most chapters include exercises, and the material is carefully structured according to importance and difficulty. The book is suitable for advanced undergraduate and graduate students in computer science and mathematics and researchers engaged with computability and mathematical logic.

Computability and Analysis, a Historical Approach

Alan Turing
Computability theory
Computably enumerable (C.E.) sets
Turing reducibility
Finite injury method
Oracle constructions
Tree method
Minimal degrees
Games in computability theory
Relative computability
Peano arithmetic

Table of contents (17 chapters)

Front matter, foundations of computability, defining computability.

Robert I. Soare

Computably Enumerable Sets

Turing reducibility, the arithmetical hierarchy, classifying c.e. sets, oracle constructions and forcing, the finite injury method, trees and $$\pi_1^0$$ classes, open and closed classes, basis theorems, peano arithmetic and $\pi_1^0$ -classes, randomness and $\pi_1^0$ -classes, minimal degrees, minimal degrees below $\emptyset^{\prime\prime}$, minimal degrees below $\emptyset^{\prime}$, games in computability theory, banach-mazur games, gale-stewart games, authors and affiliations, about the author.

Robert Soare is the Paul Snowden Russell Distinguished Service Professor Emeritus of Mathematics and Computer Science at the University of Chicago. He was the founding chairman of the Department of Computer Science in 1983. He has supervised the dissertations of nineteen Ph.D. students using the content of this book. He wrote the primary reference on computability theory for students and researchers: Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets (Springer, 1987). He is the author of numerous papers on computability theory and mathematical logic. His 1974 Annals of Mathematics paper on automorphisms of computably enumerable sets was selected in the 2003 book by Gerald Sacks as one of the most important in mathematical logic in the twentieth century. He has been an invited speaker at the International Congress of Mathematicians, and a plenary speaker at the International Congress of Logic, Methodology, and Philosophy of Science, the Association of Symbolic Logic Centennial in 2000, the British Mathematical Colloquium in 2012, the Royal Society Meeting on the Incomputable in 2012, and Computability in Europe (CiE) in 2007 and 2012. He was the winner of the 2011 University of Chicago Award for Excellence in Graduate Teaching and is a Fellow of the American Mathematical Society.

Bibliographic Information

Book Title : Turing Computability

Book Subtitle : Theory and Applications

Authors : Robert I. Soare

Series Title : Theory and Applications of Computability

DOI : https://doi.org/10.1007/978-3-642-31933-4

Publisher : Springer Berlin, Heidelberg

eBook Packages : Computer Science , Computer Science (R0)

Hardcover ISBN : 978-3-642-31932-7 Published: 28 June 2016

Softcover ISBN : 978-3-662-56858-3 Published: 07 June 2018

eBook ISBN : 978-3-642-31933-4 Published: 20 June 2016

Series ISSN : 2190-619X

Series E-ISSN : 2190-6203

Edition Number : 1

Number of Pages : XXXVI, 263

Number of Illustrations : 4 b/w illustrations

Topics : Theory of Computation , Mathematics of Computing , Mathematical Logic and Foundations

Publish with us

Policies and ethics

Find a journal
Track your research

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:

5, 14, 23, 32, 41, ...
continued fraction sqrt(2)
inv {{10, -9, -12}, {7, -12, 11}, {-10, 10, 3}}

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

IMAGES

(PDF) Turing computability of (non-)linear optimization
Turing Computability: Structural Theory
The Present Theory of Turing Machine Computability
PPT
Computability and Complexity Church-Turing Thesis
PPT

VIDEO

Learning About Computability With Turing (Part 1 Chapter 1)
Theory of Computation
6c Turing Machine and Computability Theory 2022
Computability and Complexity
Theory of Computation
Computability Freaks Episode 1: "Turing Machines"

COMMENTS

Church-Turing thesis
In computability theory, the Church-Turing thesis (also known as computability thesis, [ 1 ] the Turing-Church thesis, [ 2 ] 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 ...
The Church-Turing Thesis
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.
The Church-Turing Thesis Explained: A Deep Dive into the Foundations of
Origins of Computability Theory in the 1930s. The Church-Turing thesis emerged in a period of remarkable ferment in the fields of mathematics and logic. In 1931, Kurt Gödel had just published his famous incompleteness theorems, which shattered the formalist program of reducing all of mathematics to axiomatic systems.
The Church-Turing Thesis > The Rise and Fall of the
Turing gave two formulations of what he called "the Hilbert Entscheidungsproblem" (1936 [2004: 84, 87]): ... Given Turing's thesis, the two formulations are equivalent. ... who worked closely with Church and played a leading part in the development of computability theory in the 1930s. Kleene noted that
The Church-Turing Thesis
A thesis aiming to limit the scope of algorithmic computability to Turing computability should thus not state that every possible algorithmic process can be performed by a Turing machine. The way to express the thesis is to say the extensional input-output function ια associated with an algorithm α is always Turing-computable; ια is simply ...
PDF "The Church-Turing "Thesis" as a Special Corollary of Gödel's
The Church-Turing "Thesis" as a Special Corollary 79 a person who computes, 11, 12 not the later idea of a computing machine, nevertheless the influence of the " Turing machine" (and perhaps the subtle influence of his later philosophical paper Turing 1950 ) has led in many writings to a computer-science orientation to the problem.
PDF Turing's Thesis
notions: computability by a Turing machine, general recursiveness in the sense of Herbrand-Gödel-Kleene, and λ-definability in the sense of Kleene and the present ... Thus was born what is now called the Church-Turing Thesis, according to which the effectively computable functions are exactly those computable by a Turing machine.5 The (Church ...
Alan Turing
Very rapidly it was shown that the mathematical scope of Turing computability coincided with Church's definition (and also with the scope of the general recursive functions defined by Gödel). Turing wrote his own statement (Turing 1939, p. 166) of the conclusions that had been reached in 1938; it is in the Ph.D. thesis that he wrote under ...
What is the Church-Turing Thesis?
The notions of algorithm and computability as formal subjects of mathematical reasoning gained prominence in the twentieth century with the advent of symbolic logic and the discovery of inherent limitations to formal deductive reasoning. The most popular formal model of computation is due to Alan Turing. The claim that computation paradigms such as Turing's capture the intuitive notion of ...
Computability : Turing, Gödel, Church, and Beyond
Publication date: 2013. Computer scientists, mathematicians, and philosophers discuss the conceptual foundations of the notion of computability as well as recent theoretical developments. In the 1930s a series of seminal works published by Alan Turing, Kurt Gödel, Alonzo Church, and others established the theoretical basis for computability.
Computability (Church-Turing) Thesis Revisited
The Computability (Church-Turing) Thesis formalized the informal notions of computation and enabled their mathematical treatment. The thesis is by many viewed as an unproved or even unprovable proposition, although it has been subjected to continuous examination. Nevertheless, the consequences of this breakthrough are immense.
The Church-Turing Thesis: Its Nature and Status
Abstract. The Church-Turing thesis (CT), as it is usually understood, asserts the identity of two classes of functions, the effectively computable functions on the one hand, and the recursive (or Turing-machine computable) functions on the other. In support of this thesis, it is customary to cite the circumstance that all serious attempts to characterize the notion of an effectively computable ...
Computability theory
Computability theory originated in the 1930s, with the work of Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene, and Emil Post. [3] [b]The fundamental results the researchers obtained established Turing computability as the correct formalization of the informal idea of effective calculation. In 1952, these results led Kleene to coin the two names "Church's thesis" [4 ...
PDF Computability and Complexity The Church-Turing Thesis
the Church-Turing Thesis: "a problem can be solved by an algorithm iff it can be solved by a Turing Machine". Turing Machines implement. algorithms. all algorithmically solvable problems can be solved by a Turing Machine. "a function is computable iff it can be solved by a Turing Machine". at a Turing Machine implements.
The Church-Turing Thesis
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 ...
Turing Thesis
The Church- Turing thesis states that a function on the positive integers is effectively calculable if and only if it is computable. An informal accumulation of the tradition in S. C. Kleene (1952) has transformed it to the Computability thesis: there is an objective notion of effective computability independent of a particular formalisation ...
Turing and the discovery of computability
In §1 we give a short overview for a general audience of Godel, Church, Turing, and the discovery of computability in the 1930s. In the later sections we mention a series of our previous papers where a more detailed analysis of computability, Turing's work, and extensive lists of references can be found. The sections from §2—§9 challenge ...
Turing Computability: Theory and Applications
Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine. This model led to both the development of actual computers and to computability theory, the study of what machines can and cannot compute. This book presents classical computability theory from Turing and Post to current results and methods, and ...
PDF The History and Concept of Computability
or e ectively calculable under Church's Thesis or Turing's Thesis. The subject of computability theory was accidentally named \recursive function theory" or simply \recursion theory" in the 1930's but has recently acquired the more descriptive of \Computability Theory," which is also historically accurate
Church-Turing Thesis -- from Wolfram MathWorld
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. ... "The Structure of Computability in Analysis and Physical Theory: An Extension of Church's Thesis." Ch. 13 in Handbook of Computability Theory (Ed. E. R ...
Computable function
Computability of a function is an informal notion. ... The Church-Turing thesis states that any function computable from a procedure possessing the three properties listed above is a computable function. Because these three properties are not formally stated, the Church-Turing thesis cannot be proved. ...