the physical Church-Turing thesis
Jun. 22nd, 2009 08:54 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
guslToday, Cris Moore gave an excellent lecture about computational complexity. I managed to record some bits. He had a Scott Aaronson quote
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":
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!
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!