is the Strong Church-Turing Thesis really falsifiable?

[gusl]

While arguing that CS is more fundamental than Physics, Daniel Lemire gives it the status of a "natural science", since it supposedly makes fundamental predictions about the universe. He claims that both (a) Digital Physics / Strong Church-Turing Thesis (SCTT) and (b) the possibility of AI are falsifiable predictions ("Yet, these predictions remain unfalsified to this day.")

I made a skeptical argument for each of the above. Below I'm quoting my objection to (a).

In our usage here, "Strong Church-Turing Thesis" refers to the idea that the computation that can occur in our universe is asymptotically equivalent to Turing Machine computation, as far as space- and time-complexity is concerned.

from the comments to Computer Science is the most fundamental natural science. [edited]

@Daniel
I was just thinking: is the Strong Church-Turing Thesis (SCTT) really falsifiable?
Any such falsification must involve a proof that nature solves a certain problem (i.e. via a "physical algorithm") asymptotically faster^* than a Turing Machine. To my knowledge, there is no accepted way to prove complexity results empirically: remember you're trying to draw conclusions about what happens to the computation time (and/or space) as n goes to infinity! To extrapolate to infinity, you need a theory (a.k.a. computational model) to tell you how your algorithm scales (in this case, this will be a physical theory). With a computational model in hand, you are back in CS Theory land, and can compare things asymptotically, but it's hard to see how you could validate a physical model in the first place.

OTOH, it seems like we've accepted that the asymptotic behavior of PCs is modeled by Turing Machines... although we've seen in practice that this is an idealization, and PC performance is in fact slightly worse than what would be predicted by Random-Access Machines, as we scale up.

---

^{* - or the opposite: nature cannot compute as fast as some algorithm in a Turing Machine!}

If one can prove that quantum computing can scale and that QP!=P, that would falsify SCTT (at least the classical SCTT), so it seems falsifiable afterall... to the extent that such a thing can be proven.

Comments

[simrob.livejournal.com]

You made what seems to be an important error here - SCTT has nothing to do with speed at all, it has to do with computability. A physical process that produced a halting oracle (whatever that means) would violate SCTT. You can only make arguments about speed or asymptotic - maybe - when dealing with a question of "relatively quickly" versus "more time than the lifespan of the universe Big Bang to Heat Death."

But I'm speaking very off the cuff, tell me if I'm wrong.

[gustavolacerda.livejournal.com]

The speed issue is what distinguishes SCTT from CTT, as Daniel himself suggested. Sorry that wasn't clear.

[simrob.livejournal.com]

Aah, I speed-read and misunderstood

[gustavolacerda.livejournal.com]

I've added a little paragraph to clarify this.

[gustavolacerda.livejournal.com]

one of the reasons I'm not a speed-reader is that the real world is confusing enough as it is. :-)

[gustavolacerda.livejournal.com]

I am, however, a speed-writer much of the time.

[rdore.livejournal.com]

You probably mean QBP (error rate that's exponentially small, but not zero). As far as I know there's no superpolynomial quantum speedups that work with probability 1.

[gustavolacerda.livejournal.com]

I guess I mean QBP != BP.

What's the B for?

[rdore.livejournal.com]

The BP stands for bounded probability. It should probably be QBPP (like BPP which is used). Maybe QBPP was just too long.