How would you answer the question in the articles title? Do you think quantum computing entails a fundamentally different model of computation than the TM?

66 C O M M U N I C AT I O N S O F T H E A C M | J A N U A R Y 2 0 1 9 | V O L . 6 2 | N O . 1

contributed articles

T H E C H U R C H - T U R I N G T H E S I S (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 com- putable, in an upgraded sense of “com- putable”? Before addressing these ques- tions, we first look back to the 1930s to consider how Alonzo Church and Alan Turing formulated, and sought to jus- tify, their versions of CTT. With this nec- essary history under our belts, we then turn to today’s dramatically more pow- erful versions of CTT.

History of the Thesis Turing stated what we will call “Turing’s thesis” in various places and with vary- ing degrees of rigor. The following for- mulation is one of his most accessible.

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

Turing also formulated his thesis in terms of numbers. For example, he said, “It is my contention that these op- erations [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 work- ing on the German mathematician David Hilbert’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

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

D O I : 1 0 . 1 1 4 5 / 3 1 9 8 4 4 8

In its original form, the Church-Turing thesis concerned computation as Alan Turing and Alonzo Church used the term in 1936— human computation.

BY B. JACK COPELAND AND ORON SHAGRIR

key insights ˽ 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 computer” 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.

J A N U A R Y 2 0 1 9 | V O L . 6 2 | N O . 1 | C O M M U N I C AT I O N S O F T H E A C M 67

I M

A G

E B

Y N

A S

A ,

E S

A ,

A N

D T

H E

H U

B B

L E

H E

R I

T A

G E

T E

A M

( S

T S

C I

/A U

R A

)

function of positive integers by iden- tifying it with the notion of a recursive function of positive integers (or of a λ-definable function of positive inte- gers).”5

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

Upon learning of Church’s “defi-

nition,” Turing quickly proved that λ-definability and his own concept of computability (over positive integers) are equivalent. Church’s thesis and Tur- ing’s thesis are thus equivalent, if atten- tion is restricted to functions of positive integers. (Turing’s thesis, more gen- eral than Church’s, also encompassed computable real numbers.) However, it is important for a computer scientist to appreciate that despite this exten- sional equivalence, Turing’s thesis and

Church’s thesis have distinct meanings and so are different theses, since they are not intensionally equivalent. A lead- ing difference in their meanings is that Church’s thesis contains no reference to computing machinery, whereas Tur- ing’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

Is everything in the physical universe computable? Hubble Space Telescope view of the Pillars of Creation in the Eagle Nebula.

68 C O M M U N I C AT I O N S O F T H E A C M | J A N U A R Y 2 0 1 9 | V O L . 6 2 | N O . 1

contributed articles

each going far beyond CTT-O. First, we look more closely at the algorithmic form of thesis, as stated to a first approx- imation by Lewis and Papadimitriou29: “[W]e take the Turing machine to be a precise formal equivalent of the intuitive notion of ‘algorithm’.”

What Is an 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 con- cept of an algorithm keeps evolving: “We have now parallel, interactive, distrib- uted, real-time, analog, hybrid, quan- tum, etc. algorithms.”22 There are en- zymatic algorithms, bacterial foraging algorithms, slime-mold algorithms, and more. The Turing machine is incapable of performing the atomic steps of algo- rithms carried out by, say, an enzymatic system (such as selective enzyme bind- ing) or a slime mold (such as pseudopod extension). The Turing machine is simi- larly unable to duplicate (as opposed to simulate) John Conway’s Game of Life, where—unlike a Turing machine—ev- ery 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 al- ways Turing-computable; ια is simply the extensional mapping of α’s inputs to α’s outputs. The algorithm the Tur- ing machine uses to compute ια might be very different from α itself. A ques- tion then naturally arises: If an algo- rithmic process need not be one a Tur- ing 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 sci- ence is that, ontologically speaking, al- gorithms are abstract entities; however, there is debate about what abstract en- tities 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 class- es 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. Mos- chovakis 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 im- plementability, 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 pro- grammed in some programming lan- guage, 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 pro- gramming languages—we arrive at the following program-oriented formula- tion of the algorithmic thesis:

CTT-Algorithm (CTT-A). Every algo- rithm can be expressed by means of a program in some (not necessarily cur- rently existing) Turing-equivalent pro- gramming 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 dis- tinct computational issues that are bet- ter treated separately.

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

Later in this article we examine com- plexity-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?

What Justifies the Church-Turing Thesis? Stephen Kleene—who coined the term “Church-Turing thesis”—catalogued four types of argument for CTT-O: First,

description of a certain human activ- ity—numerical computation; in Tur- ing’s day computation was carried out by rote workers called “computers,” or, sometimes, “computors”; see, for exam- ple, 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 func- tions that are calculable by an idealized human computer; and, likewise, Tur- ing’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 work- ing 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-com- putable.

Some mathematical logicians view CTT-O as subject ultimately to either mathematical proof or mathemati- cal refutation, like open mathematical conjectures, as in the Riemann hypoth- esis, 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 defini- tion. We subscribe to Turing’s view of the status of CTT-O, as we outline later.

In computer science today, algo- rithms and effective procedures are, of course, associated not primarily with humans but with machines. (Note, while some expositors might distinguish be- tween the terms “algorithm” and “ef- fective procedure,” we use the terms in- terchangeably.) Many computer science textbooks formulate the Church-Turing thesis without mentioning human com- puters at all; examples include the well- known books by Hopcroft and Ullman24 and Lewis and Papadimitriou.29 This is despite the fact that the concept of hu- man computation was at the heart of both Turing’s and Church’s analysis of computation.

We discuss several important mod- ern forms of the Church-Turing thesis,

J A N U A R Y 2 0 1 9 | V O L . 6 2 | N O . 1 | C O M M U N I C AT I O N S O F T H E A C M 69

contributed articles

employs the Schönfinkel-Curry idea of “combinators” in order to axiomatize the concept of an algorithmic function.)

Fourth in this catalog of consider- ations 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 Kripke28 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 there- fore every computation—can be formal- ized as a valid deduction in the language of first-order predicate logic with iden- tity (a step Kripke referred to as “Hil- bert’s thesis”); following Gödel’s com- pleteness theorem, each computation is thus formalized by a provable formula of first-order logic; and every computa- tion 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 Tur- ing: Every provable formula of first-order logic can be proved by the universal Tur- ing machine.

The third and fourth of these argu- ments provide justification for CTT-O but not for CTT-A. As Robin Gandy20 pointed out, the third argument—Tur- ing’s I—contains “crucial steps … where he [Turing] appeals to the fact that the calculation is being carried out by a hu- man being.”20 For example, Turing as- sumed “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 ar- bitrary number of symbols simultane- ously.”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 ex- ample, Lewis and Papadimitriou29) are

the argument from non-refutation points out the thesis has never been refuted, despite sustained (and ongo- ing) attempts to find a counterexample (such as the attempts by László Kalmár and, more recently, by Doukas Kapan- tais). Second, the argument from con- fluence points to the fact that the vari- ous characterizations of computability, while differing in their approaches and formal details, turn out to encompass the very same class of computable func- tions. Four such characterizations were presented (independently) in 1936 and immediately proved to be extension- ally equivalent: Turing computability, Church’s λ-definability, Kleene’s recur- sive functions, and Post’s finitary com- binatory processes.

Third is an argument usually re- ferred to nowadays as “Turing’s analy- sis.” Turing called it simply argument “I,” stating five very general and intui- tive constraints—or axioms—the hu- man 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 sym- bols 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 op- eration not more than one symbol is altered”; and “[T]he number of states of mind which need be taken into ac- count is finite.” Turing noted that refer- ence to the computer’s states of mind can be avoided by talking instead about configurations of symbols, these being “a more definite and physical counter- part” of states of mind.36

The second part of Turing’s argu- ment I is a demonstration that each function computed by any human com- puter subject to these constraints is also computable by a Turing machine; it is not difficult to see that each of the com- puter’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. (Tur- ing’s axiomatic approach to comput- ability 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

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

70 C O M M U N I C AT I O N S O F T H E A C M | J A N U A R Y 2 0 1 9 | V O L . 6 2 | N O . 1

contributed articles

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 rigor- ous mathematical justification of that claim. The axioms may be supported by informal arguments, but the whole edifice then falls short of mathemati- cal proof. This is most apparent when the informal arguments offered for the axioms invoke limitations in the cogni- tive 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 ob- servation. 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

In summary, our answer to “Is CTT- O mathematically provable?” is: Turing thought not and we have found no rea- son to disagree with him. The various historical arguments seem more than sufficient to establish CTT-O, but these arguments do indeed fall short of math- ematical 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 real- istic computations.

Complexity: The Extended Church-Turing Thesis It is striking that the Turing machine holds a central place not only in com- putability theory but also in complexity theory, where it is viewed as a universal model for complexity classes.

In complexity theory, the time com- plexities of any two general and rea- sonable models of computation are as- sumed to be polynomially related. But what counts as “reasonable”? Aharonov and Vazirani1 glossover “reasonable” as “physically realizable in principle”; see also Bernstein and Vazirani.3 If a com- putational problem’s time complexity is t in some (general and reasonable) mod- el, 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; Goldreich21 called it the

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, Gandy20 broadened Turing’s analysis in such a way that parallel com- putation is included, while Dershowitz and Gurevich16 gave a more general anal- ysis 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 im- portant question of whether CTT-O is mathematically provable.

Is the Thesis 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 it5—with a precise con- cept. However, Elliott Mendelson gave a powerful critique of this general argu- ment; and today the view that CTT-O is formally provable seems to be gaining acceptance; see, for example, Dershow- itz and Gurevich.16 Inspired by Gandy,20 Wilfried Sieg35 stated that a tightened form of Turing’s argument I proves the thesis; and Kripke28 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 un- satisfactory mathematically.”36 Hilbert’s thesis is another example of a proposi- tion that can be justified only by appeal to intuition, and so Kripke’s28 tightened form of argument II, far from proving CTT-O, merely deduced it from another thesis that is also not amenable to math- ematical proof.

Much the same can be said about ar- gument I. If axioms 1–5 are formulated in precise mathematical terms, then it is certainly provable from them that com- putation is bounded by Turing comput- ability; this is probably what Gandy20 meant when he said Turing’s argument I proves a “theorem.” But the real issue

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

J A N U A R Y 2 0 1 9 | V O L . 6 2 | N O . 1 | C O M M U N I C AT I O N S O F T H E A C M 71

contributed articles

binary sequence; Church showed such sequences are uncomputable, as we discussed elsewhere.8 Moreover, specu- lation that there may be deterministic physical processes whose behavior can- not be calculated by the universal Tur- ing machine stretches back over several decades; for a review, see Copeland.9 In 1981, Pour-El and Richards34 showed that a system evolving from computable initial conditions in accordance with the familiar three-dimensional wave equation is capable of exhibiting be- havior 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 quan- tum theory is a mechanistic, i.e., recur- sive theory in the sense that a recur- sively described system has recursive behavior.”27 Other potential counterex- amples 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 “Relativ- istic Computation.”

CTT-P and Quantum Mechanics There are a number of theoretical coun- termodels to CTT-P arising from quan- tum mechanics. For example, in 1964, Komar26 raised “the issue of the macro- scopic distinguishability of quantum states,” asserting there is no effective procedure “for determining whether two arbitrarily given physical states can be superposed to show interference ef- fects.” 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 undecid- able, even though the same problem for classical measurements is readily decidable.” This is an example of a prob- lem that refers unboundedly to the fu- ture 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 mo- tion 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

Cobham-Edmonds thesis, while Yao40 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 ex- pressed in terms of probabilistic Turing machines. Bernstein and Vazirani3 said: “[C]omputational complexity theory rests upon a modern strengthening of [the Church-Turing] thesis, which as- serts that any ‘reasonable’ model of computation can be efficiently simulat- ed on a probabilistic Turing machine.”3

Aharonov and Vazirani1 give the fol- lowing 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 Tur- ing machines:

CTT-Extended (CTT-E). “[A]ny reason- able computational model can be simu- lated 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 coun- terexample 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 accom- modating these results might require further modifications to complexity theory.

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

Physical Computability 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 formu- lated a thesis he described as “a physical form of the Church-Turing hypothesis,” saying, “[U]niversal computers are as powerful in their computational capaci- ties as any physically realizable system can be, so that they can simulate any physical system.”39 In the same year, Da- vid 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 the- sis (CTDW). Every finite physical system can be simulated to any specified de- gree of accuracy by a universal Turing machine.

Deutsch pointed out that if “simu- lated” is understood as “perfectly simu- lated,” then the thesis is falsified by con- tinuous classical systems, since such classical systems necessarily involve un- computable real numbers, and went on to introduce the concept of a universal quantum computer, saying such a com- puter is “capable of perfectly simulating every finite, realizable physical system.” Other physical formulations were ad- vanced by Lenore Blum et al., John Ear- man, 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 ver- sions later in the article.) By “physical system” we mean any system whose be- havior 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 ac- curacy) by a universal Turing machine.

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

Arguably, the phrase “physical ver- sion 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 as- serts 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 algorith- mic/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

72 C O M M U N I C AT I O N S O F T H E A C M | J A N U A R Y 2 0 1 9 | V O L . 6 2 | N O . 1

contributed articles

admitted the model invoked in their proof is highly artificial, saying, “Wheth- er 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 comput- able when only local Hilbert spaces of realistically low dimensionality are con- sidered. Nevertheless, these results are certainly suggestive: CTT-P cannot be taken for granted, even in a finite quan- tum universe.

Summarizing the current situa- tion with respect to CTT-P, we can say, although theoretical countermodels in which CTT-P is false have been de- scribed, 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.

Weaker Physical Computability Theses Piccinini31 has distinguished between two different types of physical versions of the Church-Turing thesis, both com- monly found in the literature, describ- ing them as “bold” and “modest” ver- sions of the thesis, respectively. The bold and modest versions are weaker than our “super-bold” version just dis- cussed (CTT-P). Bold versions of the thesis state, roughly, that “Any physical process can be simulated by some Tur- ing machine.”31 The Church-Turing- Deutsch-Wolfram thesis (CTDW) is an example, though Piccinini emphasized that the bold versions proposed by dif- ferent 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 ex- hibit “lack of confluence.”31

CTDW and other bold forms are too

weak to rule out the uncomputabil- ity 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 Tur- ing machine, to any required degree of accuracy, and yet the answers to cer- tain physical questions about the pro- cesses 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 pro- gram, yet the answers to some questions about the behavior (such as whether or not the machine halts given certain in- puts) are not computable.

Nevertheless, bold forms (such as CTDW) are interesting empirical hy- potheses in their own right and the world might confute them. For in- stance, CTDW fails in the wave-equa- tion countermodel due to Pour-El and Richards34 where the mapping between the wave equation’s “inputs” and “out- puts” 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 Picci- nini termed “modest” versions of the thesis.

Modest versions maintain in es- sence that every physical computing process is Turing-computable; for two detailed formulations, see Gandy20 and Copeland.8 Even if CTT-P and CTDW are in general false, the behavior of the subset of physical systems that are ap- propriately described as computing sys- tems 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.

spectral gap problem is algorithmically undecidable: There cannot exist any al- gorithm that, given a description of the local interactions, determines whether the resultant model is gapped or gap- less.” Cubitt et al. also said this is the “first undecidability result for a major physics problem that people would re- ally try to solve.”

The spectral gap, an important deter- minant of a material’s properties, refers to the energy spectrum immediately above the ground-energy level of a quan- tum many-body system, assuming a well-defined least-energy level of the sys- tem exists; the system is said to be “gap- less” if this spectrum is continuous and “gapped” if there is a well-defined next- least energy level. The spectral gap prob- lem for a quantum many-body system is the problem of determining whether the system is gapped or gapless, given the fi- nite 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 arbi- trarily large, the threshold at which this transition occurs is uncomputable.” Their proof offers an interesting coun- termodel to CTT-P, involving a physical- ly relevant example of a finite system of increasing size. There exists no effective method for extrapolating the system’s future behavior from (complete descrip- tions 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

Relationships between the three physical computability theses: CTT-P, CTDW, and CTT-P-C.

Physical computability theses

super-bold

bold

modest

CTT-P

CTDW

CTTP-P-C

Total Physical Computability Thesis

Church-Turing-Deutsch-Wolfram Thesis

Physical Computation Thesis

J A N U A R Y 2 0 1 9 | V O L . 6 2 | N O . 1 | C O M M U N I C AT I O N S O F T H E A C M 73

contributed articles

nal will have been received by TO before time t. So TO will fall into the black hole with 1 in its output cell if TE halted and 0 if TE never halted. Fortunately, TO can escape annihilation if its trajectory is carefully chosen in advance, says Néme- ti; the rotational forces of the Kerr hole counterbalance the gravitational forces that would otherwise “spaghettify” TO. TO 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 ac- cepted scientific principles” and, in par- ticular, “the principles of quantum me- chanics 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 the- oretical countermodel, which counters not only CTT-P-C but also CTT-P and CTDW, helps underscore that the “phys- ical 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.

CTT-A and Computation in the Broad The continuing expansion of the con- cept of an algorithm is akin to the exten- sion of the concept of number from inte- gers to signed integers to rational, real, and complex numbers. Even the con- cept of human computation underwent an expansion; before 1936, computation was conceived of in terms of total func- tions, and it was Kleene in 1938 who ex- plicitly 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 ma- tured enough to support rigorous defi- nitions.”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 Doyle18 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

Physical Computation Thesis 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 physi- cal computing system is Turing-com- putable.

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 phi- losophers about what counts as physi- cal 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 ex- ample, Copeland.6 Computing ma- chines that compute “beyond the Tur- ing 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. Exam- ples include accelerating machines,7,12 shrinking machines, and the intrigu- ing 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, rela- tivistic computers come close. In short, the truth or falsity of CTT-P-C remains unsettled.

Relativistic Computation Relativistic machines operate in space- time structures with the property that

the entire endless lifetime of one com- ponent 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 calculat- ing every digit of π) in what is, from the observer’s point of view, a finite times- pan of, say, one hour. (Such machines are in accord with Einstein’s general the- ory of relativity, hence the term “relativ- istic.”) Examples of relativistic compu- tation 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 com- municating Turing machines, TE and TO, in relative motion. TE is a universal machine, and TO 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 in- put (m,n), asking whether the mth Tur- ing machine (in some enumeration of the Turing machines) halts or not when started on input n, enters TO, TO first prints 0 (meaning “never halts”) in its designated output cell and then transmits (m,n) to TE. TE simulates the computation performed by the mth Tur- ing machine when started on input n and sends a signal back to TO if and only if the simulation terminates. If TO receives a signal from TE, TO deletes the 0 it previously wrote in its output cell and writes 1 in its place (meaning “halts”). After one hour, TO’s output cell shows 1 if the mth Turing machine halts on input n and shows 0 if the mth 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. TE, an or- dinary computer, remains on Earth, while the observer TO travels toward and enters a slowly rotating Kerr black hole. TO approaches the outer event horizon, a bubble-like hypersurface surrounding the black hole. Németi theorized that the closer TO gets to the event horizon, the faster TE’s clock runs relative to TO due to Einsteinian gravitational time di- lation, and this speeding up continues with no upper limit. TO motion proceeds until, relative to a time t on TO clock, the entire span of TE’s computing is over. If any signal was emitted by TE, the sig-

74 C O M M U N I C AT I O N S O F T H E A C M | J A N U A R Y 2 0 1 9 | V O L . 6 2 | N O . 1

contributed articles

Conclusion In the computational literature the term “Church-Turing thesis” is applied to a variety of different propositions usu- ally 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 as- sumptions of computer science. Others (such as the various physical comput- ability theses we have discussed) are im- portant in the philosophy of computing and the philosophy of physics but are highly contentious; indeed, the label “Church-Turing thesis” should not mis- lead computer scientists or anyone else into thinking they are established fact or even that Church or Turing endorsed them.

References 1. Aharonov, D. and Vazirani, U.V. Is quantum mechanics

falsifiable? A computational perspective on the foundations of quantum mechanics. Chapter in Computability: Gödel, Turing, Church and Beyond, B.J. Copeland, C.J. Posy, and O. Shagrir, Eds. MIT Press, Cambridge, MA, 2013.

2. Andréka, H., Németi, I., and Németi, P. General relativistic hypercomputing and foundation of mathematics. Natural Computing 8, 3 (Sept. 2009), 499–516.

3. Bernstein, E. and Vazirani, U. Quantum complexity theory. SIAM Journal on Computing 26, 5 (Oct. 1997), 1411–1473.

4. Castelvecchi, D. Paradox at the heart of mathematics makes physics problem unanswerable. Nature 528 (Dec. 9, 2015), 207.

5. Church, A. An unsolvable problem of elementary number theory. American Journal of Mathematics 58, 2 (Apr. 1936), 345–363.

6. Copeland, B.J. The broad conception of computation. American Behavioral Scientist 40, 6 (May 1997), 690–716.

7. Copeland, B.J. Even Turing machines can compute uncomputable functions. Chapter in Unconventional Models of Computation, C. Calude, J. Casti, and M. Dinneen, Eds. Springer, Singapore, 1998.

8. Copeland, B.J. Narrow versus wide mechanism: Including a re-examination of Turing’s views on the mind-machine issue. The Journal of Philosophy 97, 1 (Jan. 2000), 5–32.

9. Copeland, B.J. Hypercomputation. Minds and Machines 12, 4 (Nov. 2002), 461–502.

10. Copeland, B.J. The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life, Plus the Secrets of Enigma. Oxford University Press, Oxford, U.K., 2004.

11. Copeland, B.J. and Proudfoot, D. Alan Turing’s forgotten ideas in computer science. Scientific American 280, 4 (Apr. 1999), 98–103.

12. Copeland, B.J. and Shagrir, O. Do accelerating Turing machines compute the uncomputable? Minds and Machines 21, 2 (May 2011), 221–239.

13. Copeland, B.J. and Shagrir, O. Turing versus Gödel on computability and the mind. Chapter in Computability: Gödel, Turing, Church, and Beyond, B.J. Copeland, C.J. Posy, and O. Shagrir, Eds. MIT Press, Cambridge, MA, 2013.

14. Cubitt, T.S., Perez-Garcia, D., and Wolf, M.M. Undecidability of the spectral gap. Nature 528, 7581 (Dec. 2015), 207–211.

15. Davis, M. Why Gödel didn’t have Church’s thesis. Information and Control 54, 1-2 (July 1982), 3–24.

16. Dershowitz, N. and Gurevich, Y. A natural axiomatization of computability and proof of Church’s thesis. Bulletin of Symbolic Logic 14, 3 (Sept. 2008), 299–350.

17. Deutsch, D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 400, 1818 (July 1985), 97–117.

18. Doyle, J. What is Church’s thesis? An outline. Minds and Machines 12, 4 (Nov. 2002), 519–520.

19. Eisert, J., Müller, M.P., and Gogolin, C. Quantum measurement occurrence is undecidable. Physical Review Letters 108, 26 (June 2012), 1–5.

20. Gandy, R.O. Church’s thesis and principles for mechanisms. In Proceedings of the Kleene Symposium, J. Barwise, H.J. Keisler, and K. Kunen, Eds. (Madison, WI, June 1978). North-Holland, Amsterdam, Netherlands, 1980.

21. Goldreich, O. Computational Complexity: A Conceptual Perspective. Cambridge University Press, New York, 2008.

22. Gurevich, Y. What is an algorithm? In Proceedings of the 38th Conference on Current Trends in the Theory and Practice of Computer Science (Špindleůrv Mlýn, Czech Republic, Jan. 21–27), M. Bieliková, G. Friedrich, G. Gottlob, S. Katzenbeisser, and G. Turán, Eds. Springer, Berlin, Heidelberg, Germany, 2012.

23. Harel, D. Algorithmics: The Spirit of Computing, Second Edition. Addison-Wesley, Reading, MA, 1992.

24. Hopcroft, J.E. and Ullman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 1979.

25. Kleene, S.C. Introduction to Metamathematics. Van Nostrand, New York, 1952.

26. Komar, A. Undecidability of macroscopically distinguishable states in quantum field theory. Physical Review 133, 2B (Jan. 1964), 542–544.

27. Kreisel, G. Mathematical logic: What has it done for the philosophy of mathematics? Chapter in Bertrand Russell: Philosopher of the Century, R. Schoenman, Ed. Allen and Unwin, London, U.K., 1967.

28. Kripke, S.A. Another approach: The Church-Turing ‘thesis’ as a special corollary of Gödel’s completeness theorem. Chapter in Computability: Gödel, Turing, Church, and Beyond, B.J. Copeland, C.J. Posy, and O. Shagrir, Eds. MIT Press, Cambridge, MA, 2013.

29. Lewis, H.R. and Papadimitriou, C.H. Elements of the Theory of Computation. Prentice Hall, Upper Saddle River, NJ, 1981.

30. Moschovakis, Y.N. and Paschalis, V. Elementary algorithms and their implementations. Chapter in New Computational Paradigms: Changing Conceptions of What Is Computable, S.B. Cooper, B. Lowe, and A. Sorbi, Eds. Springer, New York, 2008.

31. Piccinini, G. The physical Church-Turing thesis: Modest or bold? The British Journal for the Philosophy of Science 62, 4 (Aug. 2011), 733–769.

32. Pitowsky, I. The physical Church thesis and physical computational complexity. Iyyun 39, 1 (Jan. 1990), 81–99.

33. Post, E.L. Finite combinatory processes: Formulation I. The Journal of Symbolic Logic 1, 3 (Sept. 1936), 103–105.

34. Pour-El, M.B. and Richards, I.J. The wave equation with computable initial data such that its unique solution is not computable. Advances in Mathematics 39, 3 (Mar. 1981), 215–239.

35. Sieg, W. Mechanical procedures and mathematical experience. Chapter in Mathematics and Mind, A. George, Ed. Oxford University Press, New York, 1994.

36. Turing, A.M. On computable numbers, with an application to the Entscheidungsproblem (1936); in Copeland.10

37. Turing, A.M. Lecture on the Automatic Computing Engine (1947); in Copeland.10

38. Turing, A.M. Intelligent Machinery (1948); in Copeland.10

39. Wolfram, S. Undecidability and intractability in theoretical physics. Physical Review Letters 54, 8 (Feb. 1985), 735–738.

40. Yao, A.C.C. Classical physics and the Church-Turing thesis. Journal of the ACM 50, 1 (Jan. 2003), 100–105.

B. Jack Copeland ([email protected]) is Distinguished Professor of Philosophy at the University of Canterbury in Christchurch, New Zealand, and Director of the Turing Archive for the History of Computing, also at the University of Canterbury.

Oron Shagrir ([email protected]) is Schulman Professor of Philosophy and Cognitive Science at the Hebrew University of Jerusalem, Jerusalem, Israel.

Copyright held by the authors. Publication rights licensed to ACM. $15.00

classical concept, saying, “[E]quilibrat- ing 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 sever- al departures from Turing’s 1936 analy- sis, 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 fu- ture computational landscape might conceivably include more extensive re- visions of the concept, if, for example, physicists were to discover that hard- ware effective in Doyle’s extended sense is a realistic possibility.

If such hardware were to be devel- oped—hardware in which operations are effective in the sense of being “eas- ily, reproducibly, and mindlessly ac- complished” but not bounded by Turing computability—then would the appro- priate 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 be- ing recognized, called, say, algorithmic computation and non-algorithmic com- putation? Not much rides on a word, but we note we prefer “effective computa- tion” for computation that is bounded by Turing computability and “neo-ef- fective 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 Copeland9 for a review) prompt similar questions. In- terestingly, a study of the expanding lit- erature about the concept of an infinite- time Turing machine, introduced by Joel Hamkins and Andy Lewis in 2000, shows that a number of computer sci- entists are prepared to describe the in- finite-time machine as computing the halting function. Perhaps this indicates the concept of computation is already in the process of bifurcating into “effec- tive” and “neo-effective” computation.