# What would it mean to disprove Church-Turing thesis?

Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why?

Turing, Rosser etc used different terms to differentiate between: "what can be computed" and "what can be computed by a Turing machine".

Turing's 1939 definition regarding this is: "We shall use the expression "computable function" to mean a function calculable by a machine, and we let "effectively calculable" refer to the intuitive idea without particular identification with any one of these definitions".

So, the Church-Turing thesis can be stated as follows: Every effectively calculable function is a computable function.

So again, how will the proof look like if one disproves this conjecture?

-
Check the appendix in this great (but hard to read) paper by L. Levin arxiv.org/PS_cache/cs/pdf/0203/0203029v16.pdf –  user2471 Feb 9 '11 at 4:06
–  vzn Mar 8 '13 at 19:50

The Church-Turing thesis has been proved for all practical purposes.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402

Dershowitz and Gurevich, Bulletin of Symbolic Logic, 2008.

(This reference discusses the history of Church's and Turing's work, and argues for a separation between "Church's Thesis" and "Turing's Thesis" as distinct logical claims, then proves them both, within an intuitive axiomatization of computability.)

-
I'm a bit concerned about this answer. It may give the wrong impression to people that the Church-Turing thesis has been proved, when in fact it has not (and I would imagine most people think it can't be proved). –  Emil Sep 1 '10 at 13:56
Hi Emil, could you explain the flaw in the paper I cited? Either mathematical or philosophical flaws are ok, of course. It doesn't really matter what "most people think"; it matters whether the Dershowitz-Gurevich paper is a correct proof. I think the main obstacle is that complexity and computability theorists are not used to abstract state machines, so it's hard to read by people who tend to use the term "Church-Turing thesis." –  Aaron Sterling Sep 1 '10 at 14:49
If Dershowitz and Gurevich proved Church's and Turing's theses, then they also proved that in the future we will not be able to build a computer which performs infinitely many computational steps in finite time, see for example arxiv.org/abs/gr-qc/0104023 which discusses such possibilities. –  Andrej Bauer Sep 2 '10 at 14:26
As normally understood, the Church-Turing thesis is not a formal proposition that can be proved. It is a scientific hypothesis, so it can be "disproved" in the sense that it is falsifiable. Any "proof" must provide a definition of computability with it, and the proof is only as good as that definition. I'm sure Dershowitz-Gurevich have a fine proof, but the real issue is whether the definition really covers everything computable. Answering "can it be disproved?" by saying "it's been proved" is misleading. It has been proved under a reasonable (falsifiable!) definition of computability. –  Ryan Williams Sep 2 '10 at 16:21
The Dershowitz-Gurevich paper says nothing about probabilistic or quantum computation. It does write down a set of axioms about computation, and prove the Church-Turing thesis assuming those axioms. However, we're left with justifying these axioms. Neither probabilistic nor quantum computation is covered by these axioms (they admit this for probabilistic computation, and do not mention quantum computation at all), so it's quite clear to me these axioms are actually false in the real world, even though the Church-Turing thesis is probably true. –  Peter Shor Nov 22 '10 at 12:36

While it seems quite hard to prove the Church-Turing thesis because of the informal nature of "effectively calculable function", we can imagine what it would mean to disprove it. Namely, if someone built a device which (reliably) computed a function that cannot be computed by any Turing machine, that would disprove the Church-Turing thesis because it would establish existence of an effectively calculable function that is not computable by a Turing machine.

-
In what sense someone must "to build" the machine? We live in finite world which only may contain computers that are strictly weaker than Turing machines. Perhaps he must invent instead some new intuitively appealing logical characterization? What it may be like? –  Vag May 26 '11 at 14:08
And our universe ever more restricted than theoretical Finite State Mashines due to boundedness of mass/energy by concrete constant and Bremmermann Limit pespmc1.vub.ac.be/ASC/Bremer_limit.html so there exists computations that bigger imaginary FSMs can do but physical computers can't (transcomputational problems). –  Vag May 26 '11 at 16:54
It would be necessary, of course, for a human being to be able to simulate the machine, in order to disprove the original thesis of Turing that identifies effective calculability with human calculability. –  Carl Mummert Mar 14 '12 at 20:50

There's a subtle point that I rarely see mentioned in these kinds of discussions and that I think deserves more attention.

Suppose, as Andrej suggests, someone builds a device which reliably computes a function $f$ that cannot be computed by any Turing machine. How would we know that the machine is in fact computing $f$?

Obviously, no finite number of input/output values would suffice to demonstrate that the machine is computing $f$ as opposed to some other Turing-computable function that agrees with $f$ on that finite set. Therefore, our belief that the machine is computing $f$ would have to be based on our physical theories of how the machine is operating. If you look at some of the concrete proposals for hypercomputers, you will find that, sure enough, what they do is to take some fancy cutting-edge physical theory and extrapolate that theory to infinity. O.K., fine, but now suppose we build the hypercomputer and ask it whether a Turing machine that searches for a contradiction in ZFC will ever halt. Suppose further that the hypercomputer replies, "No." What do we conclude? Do we conclude that the hypercomputer has "computed" the consistency of ZFC? How can we rule out the possibility that ZFC is actually inconsistent and we have just performed an experiment that has falsified our physical theory?

A crucial feature of Turing's definition is that its philosophical assumptions are very weak. It assumes, as of course it must, certain simple features of our everyday experience, such as the basic stability of the physical world, and the ability to perform finite operations in a reliable, repeatable, and verifiable manner. These things everyone accepts (outside of a philosophy classroom, that is!). Acceptance of a hypercomputer, however, seems to require us to accept an infinite extrapolation of a physical theory, and all our experience with physics has taught us not to be dogmatic about the validity of a theory in a regime that is far beyond what we can experimentally verify. For this reason, it seems highly unlikely to me that any kind of overwhelming consensus will ever develop that any specific hypercomputer is simply computing as opposed to hypercomputing, i.e., doing something that can be called "computing" only if you accept some controversial philosophical or physical assumptions about infinite extrapolations.

Another way to put it is that disproving the Church-Turing thesis would require not only building the device that Andrej describes, but also proving to everybody's satisfaction that the device is performing as advertised. While not inconceivable, this is a tall order. For today's computers, the finitary nature of computation means that if I don't believe the result of a particular computer's "computation," I can in principle carry out a finite sequence of steps in some totally different manner to check the result. This kind of "fallback" to common sense and finite verification is not available if we have doubts about a hypercomputer.

-
Tim, clearly, the Church-Turing thesis can be refuted by the successful demonstration of a model of effective computation that transcends the common scope of the equivalent models Church and Turing identified. One can argue how inconceivable that might be, but I believe that is still what it would take. (Notice that I avoid "prove" and "disprove" in this context.) –  orcmid Feb 9 '11 at 20:06
I'm not arguing that we have seen a viable candidate for a refutation of the thesis, but what it would take: a counter-example. It might have to be a well-argued thought experiment (probably the wrong term) that is comparable to the demonstration that there are UTMs (not to be confused with the creation of practical digital computers that we accept as equivalent to within time and space and dependability limitations). –  orcmid Feb 9 '11 at 20:13
@Neel: You're misunderstanding my point. I'm saying that if Physical Computer X performs a computation involving n steps, then in principle I can verify the computation by performing n steps in some manner that doesn't rely on fancy physical theories. True, I can't perform $2^{2^{2^{50}}}$ steps, but neither can Physical Computer X, so that's irrelevant to my point. –  Timothy Chow Feb 9 '11 at 21:18
@Neel: On the contrary, my point is precisely that it is perfectly reasonable to doubt the fancy physics underlying a computer, either one that exists today or a hypercomputer of the future. A major reason that we tolerate today's computers is that they are tasked with finite calculations that we can in principle mimic without fancy physics. But build a hypercomputer whose correctness inherently relies on extrapolating physical theories infinitely beyond experimentally accessible regimes, and we have no way to tell whether the computation is correct or whether our theories have gone awry. –  Timothy Chow Feb 10 '11 at 16:32
@orcmid: Physics must enter the picture somewhere; otherwise what is to stop us from declaring that all functions are computable? To deserve the name, a "computation" must be something that we can envisage actually carrying out. That's why proposals for hypercomputers take pains to explain how they could be physically constructed. My point is that we should take the thought experiment a step further: Faced with an alleged hypercomputer, how would we know that it really works as advertised? If we couldn't know, then would it really be legitimate to refer to its results as "computations"? –  Timothy Chow Feb 13 '11 at 2:23

Disproving the Church-Turing thesis seems indeed extremely unlikely and conceptually very hard to imagine. There are various "hypothetical physical worlds" which are in some tension with the Church-Turing thesis (but whether they contradict it is by itself an interesting philosophical question). A paper by Pitowsky "The Physical Church’s Thesis and Physical Computational Complexity", Iyun 39, 81-99 (1990) deals with such hypothetical physical worlds. See also the paper by Itamar Pitowsky and Oron Shagrir: "The Church-Turing Thesis and Hyper Computation", Minds and Machines 13, 87-101 (2003). Oron Shagrir have written several philosophical papers about the Church-Turing thesis see his webpage. (See also this blog post.)

The effective or efficient Church-Turing thesis is an infinitely stronger assertion than the original Church-Turing assertion which asserts that every possible computation can be simulated effciently by a Turing machine. Quantum computers will indeed show that The efficient Church-Turing thesis is invalid (modulo some computational complexity mathematical conjectures, and modulo the "asymptotic interpretation"). I think the efficient Church-Turing conjecture was first formulated in 1985 by Wolfram, the paper is cited in Pitowsky's paper linked above. In fact, you do not even need universal quantum computers to refute the efficient C-T thesis, and it is interesting line of research (that Aaronson among others studies) to propose as simple as possible demonstration of the computational superiority of quantum systems.

It is also an interesting problem if there are simpler ways to demonstrate the computational superiority of quantum computers in the presence of noise, rather than to have full-fledge quantum fault-tolerance (that allows universal quantum computation). (Scott A. is indeed interested also in this problem.)

-
I thought Turing machines could simulate quantum computers? (At great loss of efficiency of course.) (Edit: ah, I notice you said the "Effective C-T thesis" - is this the thesis that TMs can simulate any computation device efficiently?) –  Emil Sep 2 '10 at 22:51
I think Gil is talking about the "extended" Church-Turing thesis (which he calls the "effective" Church-Turing thesis) that everything efficiently computable in nature is also computable on a polytime Turing machine. –  Ryan Williams Sep 2 '10 at 22:55
I added a sentence to clarify it. –  Gil Kalai Sep 3 '10 at 5:46
Gil, thank you for this fine post! To express a quantum systems engineering point-of-view, we humans exist in a noisy universe in which (absent error correction) the E-C-T is empirically true---in that quantum dynamical processes can be efficiently simulated---via formalisms in which (effectively) quantum superposition is a local approximation, in much the same sense that Euclidean geometry is a local approximation to Riemannian geometry. Does Nature embrace similar quantum flows, so as to compute herself efficiently? That is an open question ... and a very interesting one IMHO. –  John Sidles Jun 1 '11 at 13:25
Inspired by Gil's post and by Timothy Chow's post (below), I have promoted the above comment to a formal TCS question: "What is the proper role of validation in quantum sampling, simulation, and extended-Church-Turing (E-C-T) testing?" Thank you Gil and Timothy. –  John Sidles Jun 1 '11 at 16:00

As far as I understand, the "impossibility" of proving or disproving the thesis is that there is no formal definition of "effectively calculable". Today, we take it to be precisely "computable by a Turing machine", but that rather begs the question.

Models of computation that are strictly more powerful than a Turing machine have been studied, take a look at http://en.wikipedia.org/wiki/Hypercomputation for some examples. Or just take a Turing machine with an oracle for the Halting Problem for Turing Machines. Such a machine will have its own Halting Problem, but it can solve the original Halting Problem just fine. Of course, we have no such oracle, but there's nothing mathematically impossible about the idea.

-
Thanks for the answer. So, coming up with a function that is mathematically realizable (but not physically) by some model but not by a Turing machine does not disprove the thesis? –  user200 Aug 17 '10 at 3:12
Dershowitz and Gurevich 2008 axiomatize "effectively calculable" by using abstract state machines. –  Aaron Sterling Aug 17 '10 at 5:00
So, they are defining another computation model, and proving it equivalent to the existing ones, isn't it? Why is that computational model more trustworthy than the existing ones? –  Blaisorblade Sep 9 '10 at 3:14
We could use human power as such an oracle, devising a formal proof for (non)termination. Bad runtime, though... –  Raphael Nov 22 '10 at 13:05

Regarding the Extended Church-Turing Thesis (meant as "A probabilistic Turing machine can efficiently simulate any physically computable function."):

One possibility is the difference between classical and quantum computers. Specifically the question, "Is there a task that quantum computers can perform that classical computers cannot?" A recent ECCC report by Scott Aaronson (see Conjecture 9 on page 5) highlights a conjecture that, if proven, would provide strong evidence against the Extended Church-Turing Thesis.

If one were to disprove the Extended Church-Turing Thesis, it could look like that -- specifically, by demonstrating an efficiently computable task that a (classical) Turing machine cannot efficiently compute.

-
To clarify, quantum computation only call into question the Efficient/Extended/Strong Church-Turing Thesis which states that all realizable models of computation can be simulated on a Turing machine in polynomial time. The normal Church-Turing thesis places no restrictions on efficiency. Quantum computers have no hope of toppling this version because a Turing machine can simply simulate all of the exponentially-many branches of a quantum computation in finite time. –  Ian Aug 17 '10 at 4:22
Yes, thank you for this -- I have corrected my sloppy use of the two terms. –  Daniel Apon Aug 17 '10 at 4:28
Hmmm ... but according to standard definitions, hasn't the E-C-T already been conclusively disproved? Alice: "Here's a sample of truly random binary digits computed by my (one-mode) quantum optical network". Bob: "Here's a sample of pseudo-random digits computed by a classical Turing machine." Alice: "Sorry Bob ... your sample is algorithmically compressible, and mine isn't. Therefore my data demonstrate that the E-C-T is false!" Formally speaking, Alice's reasoning is impeccable. Yet absent validation testing of Alice's claims, should we be satisfied? –  John Sidles Jun 1 '11 at 14:33

Disproofs of hypercomputation generally assume the validity of Bekenstein's bound, which asserts a particular limit on the amount of information that a finite amount of space can contain. There is controversy over this bound, but I think most physicists accept it.

If Bekenstein's bound is badly violated, and there is no bound on the amount of information contained in a particular region (say, a black hole, or an infinitely fine and robust engraving), and there are arbitrarily refinable mechanisms to examine the contents of that region (say, by carefully examining the radiation emitted as a carefully constructed object falls into the black hole, or by running a stylus over the grooves of the engraving), one can suppose that an artefact just happens to already exist that codes a halting oracle.

All very unlikely, but it does show that the claim that hypercomputation is impossible is not a mathematical truth, but based in physics. Which is to say that Andrej is right when he says we can imagine what it would mean to disprove [the Church-Turing thesis]. Namely, if someone built a device which (reliably) computed a function that cannot be computed by any Turing machine.

-
Bekenstein's bound may hold yet hypercomputation could still be possible. –  András Salamon Sep 3 '10 at 8:13
@András: In principle yes: we need much more physical theory to get a negative argument to work. But the attempts to "describe" hypercomputing machinery that I've seen all violate it. –  Charles Stewart Sep 3 '10 at 12:40
Do the ones involving closed loops close to black holes violate the bound? –  András Salamon Sep 3 '10 at 13:01
@András: I don't know which ones you mean. String theory is generally compatible with Bekenstein's bound. –  Charles Stewart Sep 3 '10 at 16:46
I mean things like arxiv.org/abs/gr-qc/0209061 which instead of relying on string theory, "just" assumes one can send calculations into the past. –  András Salamon Sep 7 '10 at 17:23

The following papers from Selim Akl may be of interest and relevant to the discussion:

Akl, S.G., "Three counterexamples to dispel the myth of the universal computer", Parallel Processing Letters, Vol. 16, No. 3, September 2006, pp. 381 - 403.

Akl, S.G., "Even accelerating machines are not universal", International Journal of Unconventional Computing, Vol. 3, No. 2, 2007, pp. 105 - 121.

Nagy, M. and Akl, S.G., "Parallelism in quantum information processing defeats the Universal Computer", Parallel Processing Letters, Special Issue on Unconventional Computational Problems, Vol. 17, No. 3, September 2007, pp. 233 - 262.

Here is the abstract of the first one:

It is shown that the concept of a Universal Computer cannot be realized. Specifically, instances of a computable function F are exhibited that cannot be computed on any machine U that is capable of only a finite and fixed number of operations per step. This remains true even if the machine U is endowed with an infinite memory and the ability to communicate with the outside world while it is attempting to compute F. It also remains true if, in addition, U is given an indefinite amount of time to compute F. This result applies not only to idealized models of computation, such as the Turing Machine and the like, but also to all known general-purpose computers, including existing conventional computers (both sequential and parallel), as well as contemplated unconventional ones such as biological and quantum computers. Even accelerating machines (that is, machines that increase their speed at every step) cannot be universal.

-
Can you provide a link to the first paper that isn't behind a paywall? What is their definition of "computable function?" Under the standard definition (there is a Turing machine that computes the function) their claim is by definition false... –  Christopher Monsanto May 6 '11 at 3:33
I have just sent you the paper by email. –  Massimo Cafaro May 29 '11 at 10:40

A new paper presented at DCM2011: A Formalization and Proof of the Extended Church-Turing Thesis (Nachum Dershowitz and Evgenia Falkovich)

-
Thanks very much for posting this. –  Aaron Sterling Jul 14 '11 at 16:30