96
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Check the appendix in this great (but hard to read) paper by L. Levin arxiv.org/PS_cache/cs/pdf/0203/0203029v16.pdf $\endgroup$
    – user2471
    Feb 9, 2011 at 4:06
  • $\begingroup$ see also applicability of Church-Turing thesis to interactive models of computation $\endgroup$
    – vzn
    Mar 8, 2013 at 19:50
  • $\begingroup$ How can it be true? A classical computer cannot efficiently simulate a quantum computer. There exists quantum algorithms which provide exponential speed up over classical computers running classical algorithms: Shor's algorithm being one. $\endgroup$
    – Robert McGwier
    Oct 30, 2018 at 18:39
  • $\begingroup$ 1) There may be a classical polytime factoring algorithm. We don't know one, but its existence is entirely consistent with the state of complexity theory. 2) The original Church-Turing thesis is about computability, not about efficient computability. $\endgroup$
    – Sasho Nikolov
    Oct 30, 2018 at 21:03
  • $\begingroup$ Why is a function that takes non-numerical objects as its arguments not a counterexample of Turing Thesis? An example would be Godel numbering function, which takes syntactical entities as its domain. $\endgroup$
    – Abraham Lim Ken Zhi
    Jul 10, 2020 at 23:58

9 Answers 9

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
17
  • 29
    $\begingroup$ 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). $\endgroup$
    – Emil
    Sep 1, 2010 at 13:56
  • 11
    $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Sep 2, 2010 at 14:26
  • 61
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Sep 2, 2010 at 16:21
  • 57
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Nov 22, 2010 at 12:36
  • 9
    $\begingroup$ @Peter Shor (and others): Given the amount of embarrassing attention my answer has received, I considered deleting it. I have decided to let it stand, though, since the comments are so good. Hopefully someone will learn something from them -- or at least be entertained! $\endgroup$
    – Aaron Sterling
    Nov 23, 2010 at 19:04
75
$\begingroup$

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.

Improve this answer
$\endgroup$
30
  • 2
    $\begingroup$ 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.) $\endgroup$
    – orcmid
    Feb 9, 2011 at 20:06
  • 3
    $\begingroup$ @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. $\endgroup$
    – Timothy Chow
    Feb 9, 2011 at 21:18
  • 10
    $\begingroup$ @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. $\endgroup$
    – Timothy Chow
    Feb 10, 2011 at 16:32
  • 9
    $\begingroup$ @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"? $\endgroup$
    – Timothy Chow
    Feb 13, 2011 at 2:23
  • 2
    $\begingroup$ This is interesting, maybe we can't really know that the machine is computing f, because we are just Turing complete. Maybe it'd take a hypercomputating observer to check that a hypercomputing object is indeed hypercomputing o.O $\endgroup$
    – guillefix
    May 4, 2016 at 1:38
61
$\begingroup$

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.

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ 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? $\endgroup$
    – Vag
    May 26, 2011 at 14:08
  • 2
    $\begingroup$ 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). $\endgroup$
    – Vag
    May 26, 2011 at 16:54
  • 3
    $\begingroup$ 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. $\endgroup$
    – Carl Mummert
    Mar 14, 2012 at 20:50
  • 3
    $\begingroup$ @CarlMummert: Turing's original statement of the Church-Turing thesis: We shall use the expression "computable function" to mean a function calculable by a machine, and let "effectively calculable" refer to the intuitive idea without particular identification with any one of these definitions. Nowhere does it mention "human calculability". $\endgroup$
    – Peter Shor
    Jul 16, 2020 at 18:43
  • 1
    $\begingroup$ @CarlMummert: I don't believe your relativity example works. According to general relativity, to get the most computation out of the computer it must follow a geodesic, so in its own reference frame, it stands still. You might claim that by falling into a black hole, and thus effectively surviving the end of the universe, you can watch a computer do an infinite amount of computation, but that doesn't work either because the computer needs an infinite amount of energy to get the answer to you. As far as I know, nobody has shown how physics can falsify the Church-Turing thesis. $\endgroup$
    – Peter Shor
    Jul 17, 2020 at 0:46
37
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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?) $\endgroup$
    – Emil
    Sep 2, 2010 at 22:51
  • 7
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Sep 2, 2010 at 22:55
  • 2
    $\begingroup$ I added a sentence to clarify it. $\endgroup$
    – Gil Kalai
    Sep 3, 2010 at 5:46
  • $\begingroup$ 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. $\endgroup$
    – John Sidles
    Jun 1, 2011 at 13:25
  • $\begingroup$ 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. $\endgroup$
    – John Sidles
    Jun 1, 2011 at 16:00
26
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – user200
    Aug 17, 2010 at 3:12
  • 1
    $\begingroup$ Dershowitz and Gurevich 2008 axiomatize "effectively calculable" by using abstract state machines. $\endgroup$
    – Aaron Sterling
    Aug 17, 2010 at 5:00
  • 5
    $\begingroup$ 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? $\endgroup$
    – Blaisorblade
    Sep 9, 2010 at 3:14
  • $\begingroup$ We could use human power as such an oracle, devising a formal proof for (non)termination. Bad runtime, though... $\endgroup$
    – Raphael
    Nov 22, 2010 at 13:05
10
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Bekenstein's bound may hold yet hypercomputation could still be possible. $\endgroup$
    – András Salamon
    Sep 3, 2010 at 8:13
  • $\begingroup$ @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. $\endgroup$
    – Charles Stewart
    Sep 3, 2010 at 12:40
  • $\begingroup$ Do the ones involving closed loops close to black holes violate the bound? $\endgroup$
    – András Salamon
    Sep 3, 2010 at 13:01
  • $\begingroup$ @András: I don't know which ones you mean. String theory is generally compatible with Bekenstein's bound. $\endgroup$
    – Charles Stewart
    Sep 3, 2010 at 16:46
  • $\begingroup$ 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. $\endgroup$
    – András Salamon
    Sep 7, 2010 at 17:23
9
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ian
    Aug 17, 2010 at 4:22
  • $\begingroup$ Yes, thank you for this -- I have corrected my sloppy use of the two terms. $\endgroup$
    – Daniel Apon
    Aug 17, 2010 at 4:28
  • $\begingroup$ 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? $\endgroup$
    – John Sidles
    Jun 1, 2011 at 14:33
5
$\begingroup$

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

Improve this answer
$\endgroup$
0
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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... $\endgroup$
    – Christopher Monsanto
    May 6, 2011 at 3:33
  • $\begingroup$ I have just sent you the paper by email. $\endgroup$
    – Massimo Cafaro
    May 29, 2011 at 10:40
  • $\begingroup$ Here is one of these papers: research.cs.queensu.ca/home/akl/techreports/even.pdf. More here: research.cs.queensu.ca/Parallel/projects.html. There is no actual definition of a "computer" in the paper, just a hand-wavy description. Presumably that hand-wavy description can be formalized with a bit of work, using the Turing machine model or something similar as the basis. $\endgroup$
    – Sasho Nikolov
    Oct 30, 2018 at 21:30
  • 1
    $\begingroup$ Mathematically, the main theorem is a triviality: you define the computational task to require that $W(t)$ operations be performed by time $t$. Then, because the number of operations performed by the computer per time step is defined to be at most some constant $c$, define $W(t) > ct$. So the slight of hand is to define an unusual "problem". Then there is a ton of philosophizing why that's supposedly interesting. I think it's not. But people are free to waste their lives however they want. I just hope this person is not supervising students to work on this. $\endgroup$
    – Sasho Nikolov
    Oct 30, 2018 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.