the physical Church-Turing thesis

[gusl]

Today, Cris Moore gave an excellent lecture about computational complexity. I managed to record some bits. He had a Scott Aaronson quote

Computers play the same role in complexity that clocks, trains, and elevators play in relativity.

which sounds a lot like this Dijkstra one:

Computer science is no more about computers than astronomy is about telescopes.

In an offline conversation afterwards, the topic of alternative computers (e.g. DNA computers, brains, etc) came up.

As we know, in terms of computability, the CT thesis says that all realizable computations can be simulated by a Turing Machine. Pretty much everybody believes this. But it says nothing about complexity (whether time or space). Occasionally people claim that alternative computers (such as the above) are more powerful than classical computers. This annoys me.

I told him I had a thesis that no physical system (except possibly for quantum computers) is more powerful than a Turing Machine, in terms of complexity.

Then he stated some version of the "Strong Physical Church-Turing Thesis":

all computations done using a polynomial amount of matter and a polynomial amount of time can also be done with a Turing Machine with a polynomial-sized tape in polynomial time. (paraphrased)

I strongly believe that this holds for systems that don't use quantum entanglement (chemical computers, brains, etc don't).

UPDATE: I forgot to say: apparently, primality testing is in P!

Comments

[rdore.livejournal.com]

An alternate term I've heard suggested before is computing science.

[gustavolacerda.livejournal.com]

that's common Canadian usage: that's what SFU and UAlberta call their CS departments.

[easwaran.livejournal.com]

That is of course Scott Aaronson's major thesis, from what I've read by him. Well, actually, not quite. I think his thesis is that no physical computer can solve NP-complete problems in polynomial time. He believes that factoring is non-polynomial, but that quantum computers are physically possible and that they can factor in polynomial time.