What would it mean to disprove Church-Turing thesis?

Question

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?

see also applicability of Church-Turing thesis to interactive models of computation — vzn, Mar 08 '13 at 19:50
Check the appendix in this great (but hard to read) paper by L. Levin http://arxiv.org/PS_cache/cs/pdf/0203/0203029v16.pdf — user2471, Feb 09 '11 at 04:06
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. — Abraham Lim Ken Zhi, Jul 10 '20 at 23:58
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. — Robert McGwier, Oct 30 '18 at 18:39

Timothy Chow · Answer 1 · 2011-02-09T19:55:10.707

75

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.

edited Feb 09 '11 at 19:55

answered Feb 09 '11 at 19:45

Timothy Chow

7,550
35
43

2

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 09 '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 09 '11 at 20:13
"...I can in principle carry out a finite sequence of steps in some totally different manner to check the result." The principle of induction easily justifies the totality of triply-exponential functions. Is it really possible in principle to verify that $2^{2^{2^{50}}}$ terminates for Peano representations? This sequence of marks could hardly fit in the universe! "$\forall n \in \mathbb{N} \ldots$" already contains an enormous extrapolation beyond our experience; I don't see "$\forall x \in \mathbb{R}\ldots$" as that much worse, philosophically speaking -- in for a penny, in for a pound! – Neel Krishnaswami Feb 09 '11 at 21:03
@orcmid: Rephrased in your language, I'm saying that to "demonstrate a model of effective computation" requires demonstrating that it is possible to know that a putative physical instantiation of a model is an fact a physical instantiation of the model. – Timothy Chow Feb 09 '11 at 21:14
3

@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 09 '11 at 21:18
1

@Timothy: I did misunderstand. Still, I think you may be underestimating the theoretical fanciness underpinning computers. Even basic ideas like using redundancy to reduce failure probabilities requires strong physical assumptions about isolation and locality of subsystems to justify the probabilistic independence assumptions. – Neel Krishnaswami Feb 10 '11 at 13:27
10

@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
@Timothy I don't understand your rephrasing. I'm not sure that physical instantiation is required. Do you apply that position to the Turing models of computation (TM and UTM cases)? – orcmid Feb 12 '11 at 20:07
@Timothy I do like the challenge you pose for any system of computation that realizes some functions, $F$, that are not in the effectively calculable set of those equivalent models that the Church-Turing thesis posits to be comprehensive. Clearly, such a function cannot be characterized in any of those models, which means it is not identifiable by existing means based on one or the other of the recognized-as-equivalent models. But then, you can't use the inability to do so in existing schemes as confirmation of C-T. Interesting. – orcmid Feb 12 '11 at 20:19
9

@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 02:23
I think the demonstration that not all functions are computable is demonstratable either way. It does hinge on the descriptions of the computations being finitely-expressed and not so much on the actual model of computation.
I concur that one has to be cautious about demonstrating a computational model that realizes functions not attainable in the currently-accepted models, since it must be inexpressable in those.
– orcmid Feb 17 '11 at 00:09
This same verification problem appears in sampling contexts, where it is even more interesting (and difficult). E.g., suppose someone builds an Aaronson/Arkhipov device that produces photon data claimed to be sampled from an infeasible-to-simulate distribution. The question of whether there does or does not exist PTIME (or even EXPTIME) verification procedures for this claim then becomes very important ... and (AFAICT) not much is known about the answer. – John Sidles Jun 01 '11 at 13:32
Inspired by Timothy's post and by Gil Kalai's post (above), 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 01 '11 at 16:01
2

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 – guillefix May 04 '16 at 01:38
1

The answer to the above question "How do we know that the machine is computing function f?" is that we are able to calculate the function f ourselves. This calculational procedure would use perhaps new mathematical procedures, which are confirmed as extending $\it {our}$ abilities using only recursive functions. An analogy comes from an alternative history in which Finite State Automata are discovered first and considered to be the basis of an "FSM C-T Thesis". This later gets disproved by the discovery of the TM model and partial recursion. What is physically possible is a different matter. – Roy Simpson Oct 15 '19 at 18:08
2

@RoySimpson : I think you're still dodging the main question. Let's say someone proposes "new mathematical procedures" for calculating things. How would we go about "confirming" that these new mathematical procedures are correct? If we try to spell this out in full detail, rather than just waving our hands and assuming that it can be done somehow, we'll run into the same difficulty. – Timothy Chow Oct 15 '19 at 18:15
2

(continued) For example, someone proposes a "new mathematical procedure" for "calculating" whether a given Turing machine halts. How do we "confirm" the correctness of this procedure, whatever it is, in such a way that when we apply this "new mathematical procedure" to a Turing machine that searches for a contradiction in ZFC, we can "confirm" that it's giving the right answer? – Timothy Chow Oct 15 '19 at 18:16
1

Any new-computational procedure powerful enough to be claiming to provide a proof of the consistency of ZFC will need to embody the (currently unknown) proof ordinal for ZFC. Likewise any new-computational procedure powerful enough to be claiming that it shows the consistency of Peano Arithmetic will need to embody $\epsilon_{0}$. Mathematicians would have to convince themselves that the new-computational procedures actually do this. If either of these things happened then a new-C-T H would be formulated. (cont) – Roy Simpson Oct 16 '19 at 18:03
1

(cont). Perhaps more likely than all this would be that a proof of inconsistency of ZFC is found, and a corollary is that C-T is false. I am not convinced, though, that the invalidity of C-T automatically requires that new halting theorems can now be proven, especially not new claims about ZFC or PA consistency. I agree though that the current hypercomputation community seem to talk in these terms. – Roy Simpson Oct 16 '19 at 18:07
2

@RoySimpson : You're still not addressing the point that even if mathematicians agree on some abstract notion of "computation," you haven't said how one would go about "confirming" that any particular implementation actually computes the function that it is allegedly computing. – Timothy Chow Oct 16 '19 at 20:18
1

Agreed. Your answer is concerned with the "Infinite Processes" (IP) - and especially the "infinite Completed Processes" (IPC) that come along with most/all hypercomputation models. Mathematicians need not be convinced that a given IPC is really valid, and would probably need an axiom to be convinced, generating the question "why should we believe that axiom?". I (and we) do not have a candidate for replacing the C-T hypothesis, but it is probably the case that any such candidate not come with such an IPC axiom. A mild example of a possibility is limit-computation. Here an IP is involved (cont) – Roy Simpson Oct 17 '19 at 09:23
1

(cont) but the IP (if convergent) will converge in finite number of steps. The catch, preventing it from being a real counter-example to C-T, is that such convergence is undecidable (rather than being infinite though). Still some hypercomputationalists might view this as a FAPP extension of the C-T H because convergence is finite. You are seemingly arguing that no "axiom-free" or "physics-free" new extended C-T is possible (thus superseding and invalidating the current one). Of course that might be correct. – Roy Simpson Oct 17 '19 at 09:38
1

@RoySimpson : Yes, I am in effect arguing that no "axiom-free" or "physics-free" new extended C-T hypothesis is possible. Your suggestion of an undecidable but finite convergence is easy to imagine: We encounter a gnome who quickly tells us whether any giving Turing machine halts. Whenever we can independently confirm the gnome's answer, the gnome is correct. I don't know what FAPP stands for, but I certainly cannot see how anyone can plausibly claim that we can totally trust the gnome without introducing any new axiom or physical principle. – Timothy Chow Oct 17 '19 at 15:50
1

OK. FAPP is short for "For All Practical Purposes" and is used in philosophical-technical discussions around Bell's Theorem in the Foundation of Quantum Mechanics (my other subject). A certain view is not formally deducible (arguably therefore not formally "correct"), but is believed a correct description of physical practice (by those who use the term). The associated Quantum Gnome is statistically highly correct FAPP. – Roy Simpson Oct 18 '19 at 15:36
If a hyper-computer could not only decide if a program halts or not, but also output some sort of proof that it does or does not, then it would be more reputable assuming we could check the proof in a reasonable amount of time, but those proofs could probably be arbitrarily long even if oracle computation could make them shorter/speed them up – Colonizor48 Sep 22 '23 at 19:19
@Colonizor48 Goedel's theorems already tell us that there cannot always exist a proof, even if we allow arbitrarily long proofs. Take any formal system X whose theorems you trust. The hypercomputer will assure us that the Turing machine whose job it is to find a contradiction in X will never halt. But Goedel's 2nd theorem tells us that there does not exist an X-based proof that the Turing machine halts. – Timothy Chow Sep 22 '23 at 21:25
@Timothy Chow, if we do assume the computer can solve the halting problem though as an axiom, our space of possible proofs grows immensely, though that kind of defeats the purpose of the question. But if you write a normal program to compute some totally normal even polynomial time computable function. How do you know any given program is computing this function? – Colonizor48 Sep 22 '23 at 22:33
@Colonizor48 I addressed this point already. Some degree of extrapolation is indeed necessary, as is the case with any physical theory. The point is that hypercomputing requires a type of extrapolation to infinity which is never used in physics or engineering, and which experience tells us is a rather foolhardy move. – Timothy Chow Sep 22 '23 at 23:17
@Timothy Chow, that could be a possible idea, but there are likely others. For example, there could be an undiscovered subatomic particle or system who's state evolves according to some uncomputable function, in such a way that is useful for computation. But that seems unlikely – Colonizor48 Sep 23 '23 at 00:16
@Colonizor48 That could very well be. But my point is, even if such a particle existed and we detected it, how would we know that it evolves according to some uncomputable function? We would have to extrapolate to infinity what we learned about the particle from our finite observations of it. – Timothy Chow Sep 23 '23 at 01:12

score 61 · Answer 2 · answered Sep 02 '10 at 14:40

61

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.

answered Sep 02 '10 at 14:40

Andrej Bauer

28,823
1
80
133

1

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
2

And our universe ever more restricted than theoretical Finite State Mashines due to boundedness of mass/energy by concrete constant and Bremmermann Limit http://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
3

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
3

@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". – Peter Shor Jul 16 '20 at 18:43
@PeterShor: this is well discussed in the Stanford Encyclopedia entry at https://plato.stanford.edu/entries/church-turing/ (esp. sec 2.1). When Turing refers to the notion of "effectively calculable" he is referring to calculability by a human being via an algorithm. If we drop the 'human' requirement, the thesis is easily shown to be false, for example by using relativity to allow a computer an infinite amount of time in its own reference frame to perform an unbounded search, which finishes in a finite amount of time in our reference frame, allowing us to compute the halting problem. – Carl Mummert Jul 17 '20 at 00:22
1

@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. – Peter Shor Jul 17 '20 at 00:46
And while the operation Turing machines were definitely inspired by humans working with pen and paper, it's not clear to mean that this is what Turing meant by "effectively calculable." – Peter Shor Jul 17 '20 at 01:00
The key point, of course, is the human aspect of Turing's notion of effective calculability. I find the relativistic accelerated Turing machine model a compelling example if this requirement is dropped - I think this example was originally due to Pitowsy. In any event, the SEP article by Copeland discusses why it is important to distinguish the Turing thesis from the "Physical Turing Thesis" which does not include the aspect of human computability. As soon as we drop the "human" requirement, we have to start adding other restrictions (e.g. the "infinite amount of energy" mentioned above) – Carl Mummert Jul 17 '20 at 01:11
@CarlMummert : As I said in my previous comment, your "relativistic accelerated Turing machine" is incorrect physics. You can delay computation by accelerating computers, but you can't speed it up. – Peter Shor Aug 03 '20 at 20:05
That question - can an infinite time for some computer be visible in a finite time to an observer - is the subject of Hogarth, M.L. (1992), ‘Does General Relativity Allow an Observer to View an Eternity in a Finite Time?’, Foundations of Physics Letters 5, pp. 173–181. – Carl Mummert Aug 04 '20 at 01:17
1

@CarlMummert: And the abstract says "A theorem shows that most standard spacetimes cannot accommodate this scenario." So maybe in some alternate universe, it could happen, but not in this one. – Peter Shor Aug 06 '20 at 19:48

Gil Kalai · Answer 3 · 2011-02-08T23:12:48.990

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 02 '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 02 '10 at 22:55
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 01 '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 01 '11 at 16:00

score 26 · Answer 4 · answered Aug 17 '10 at 03:01

26

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.

answered Aug 17 '10 at 03:01

Evgenij Thorstensen

1,089
10
17

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? – Aug 17 '10 at 03:12
1

Dershowitz and Gurevich 2008 axiomatize "effectively calculable" by using abstract state machines. – Aaron Sterling Aug 17 '10 at 05:00
5

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 09 '10 at 03: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

score 10 · Answer 5 · answered Sep 03 '10 at 07:23

10

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.

answered Sep 03 '10 at 07:23

Charles Stewart

4,316
28
45

Bekenstein's bound may hold yet hypercomputation could still be possible. – András Salamon Sep 03 '10 at 08: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 03 '10 at 12:40
Do the ones involving closed loops close to black holes violate the bound? – András Salamon Sep 03 '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 03 '10 at 16:46
I mean things like http://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 07 '10 at 17:23
@András: That paper doesn't claim to give a model of hypercomputation, it only claims that such a machine has better than classical complexity performance. – Charles Stewart Sep 08 '10 at 07:39

Daniel Apon · Answer 6 · 2010-08-17T04:25:40.313

9

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.

edited Aug 17 '10 at 04:25

answered Aug 17 '10 at 03:06

Daniel Apon

6,001
1
37
53

2

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 04:22
Yes, thank you for this -- I have corrected my sloppy use of the two terms. – Daniel Apon Aug 17 '10 at 04: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 01 '11 at 14:33

score 5 · Answer 7 · answered Jul 14 '11 at 12:23

5

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

answered Jul 14 '11 at 12:23

Giorgio Marinelli

51
1
3

score 4 · Answer 8 · answered Apr 08 '11 at 18:37

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 06 '11 at 03:33
Here is one of these papers: http://research.cs.queensu.ca/home/akl/techreports/even.pdf. More here: http://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. — Sasho Nikolov, Oct 30 '18 at 21:30
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. — Sasho Nikolov, Oct 30 '18 at 21:34

score 2 · Accepted Answer · answered Aug 17 '10 at 03:50

2

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

answered Aug 17 '10 at 03:50

Aaron Sterling

6,994
6
42
74

29

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 01 '10 at 13:56
3

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 01 '10 at 14:49
@Aaron, well I am not going to read their paper. I'm pretty sure that they do not prove the CT thesis, or it would be big news! Arora and Barak say in their well-known book, recently published: "The CT thesis is not a theorem, merely a belief about the nature of the world as we currently understand it." (Pick up any CS Theory book and you'll find something similar.) – Emil Sep 02 '10 at 10:14
5

This will be my last comment here, but I think you might want to ask why a site like this is necessary if all we need to do is to look at textbooks. Arora and Barak are great researchers, but they aren't logicians, or complexity theory researchers (they wrote a complexity book anyway, even though this was not their main research area), or experts in programming language semantics (which was the original motivation for abstract state machines). Conventional wisdom isn't necessarily true, and, at the end of the day, we have to think for ourselves. – Aaron Sterling Sep 02 '10 at 12:54
11

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 http://arxiv.org/abs/gr-qc/0104023 which discusses such possibilities. – Andrej Bauer Sep 02 '10 at 14:26
61

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 02 '10 at 16:21
1

It has been proved under a reasonable (falsifiable!) definition of computability. <-- I'd certainly agree with this. I think to make their metaclaim stronger, it would be useful to extend their framework to other notions of computation. I've thought some about "quantumizing" their construction, to formalize Scott Aaronson's remark that quantum computing is physically inevitable (just allow amplitudes instead of probabilities and voila). I haven't gotten anywhere yet, though. – Aaron Sterling Sep 02 '10 at 17:38
2

@Aaron: there is this video on youtube (http://www.youtube.com/watch?v=7XfA5EhH7Bc) given by Gurevich himself. It's about the paper you mention. Haven't read the paper but the video is great. Everybody agrees that "it has been proved under a reasonable (falsifiable!) definition of computability". If you manage to do some progress on the quantization of Gurevich's result that would be spectacular. – Marcos Villagra Sep 03 '10 at 00:07
1

Thanks for the pointer, Marcos. I didn't know about it, and I'll watch it for sure. I feel I should say the following, since avinash accepted my answer: in case you don't know, avinash, Ryan Williams and Gil Kalai have much more in the way of research credentials than I do. I'm confident/foolish enough to still think I'm right, despite their disagreements, but you should be aware I'm very much in the minority position at this point. – Aaron Sterling Sep 03 '10 at 00:39
2

@Aaron: Thanks. I tried reading Dershowitz's paper, but it's beyond my reach at this moment. One of the reasons I accepted your answer was to get attention of more people on this paper for their valuable comments (which happened!). I think Ryan's "it has been proved under a reasonable (falsifiable!) definition of computability" would be a good substitute "for all practical purposes" in your answer. Also, I understand Ryan Williams and Gil Kalai are great theorist, but I read everyone's comments with same seriousness (though Gil's answer/link is very enlightening). – Sep 03 '10 at 02:34
57

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
9

@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! – Aaron Sterling Nov 23 '10 at 19:04
4

I think you should let it stand. It's not entirely clear what Church and Turing meant with the Church-Turing thesis (although I'm quite sure they didn't believe that their two statements of the thesis were actually different, as Dershowitz and Gurevich claim), so it's possible that they'd believe this was a proof. And if somebody ever asks a question about this paper (is this really a proof of the Church-Turing thesis?), we have this discussion to point them to. – Peter Shor Nov 24 '10 at 01:46
Just to make discussion more complete: "EVEN ACCELERATING MACHINES ARE NOT UNIVERSAL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.6941&rep=rep1&type=pdf (Abstract: We draw an analogy between Godel's Incompleteness Theorem in mathematics, and the impossibility of achieving a Universal Computer in computer science. We show that there does not exist a general-purpose computer that is universal in the sense of being able to simulate any computation executable on another computer." – Vag May 27 '11 at 06:43
4

I've summarized some of the discussion in this blog entry. – Aaron Sterling Jul 05 '11 at 14:39
2

Just wanted to thank you for leaving this answer here, I can assure you at least someone has learned a lot from it. – MaiaVictor Sep 27 '18 at 15:30
@Vag They claim to disprove the Church-Turing-Thesis by using a 'computation model' that would fail computation when not performing a certain number of operations per time unit (see 'proof' of Theorem U). That's not a computation model, that's magic. I call bs. – xamid Nov 20 '23 at 05:29

What would it mean to disprove Church-Turing thesis?

9 Answers9

Linked

Related