Re:When does a physical system compute?
by dvanduzer on Sunday May 04, 2014 @08:49PM
(#7696507)
I wouldn't quite characterize his research that way. Maybe I don't really understand what Church-Turing says, but I didn't think he was a skeptic.
[ Parent
| on HN ]
I should have said the "strong" Church-Turing thesis, which is a statement about efficiency: anything that can be computed efficiently can be computed efficiently by a Turing machine. In other words, if quantum computers can solve problems in polynomial time that classical computers cannot, then the strong Church-Turing thesis is false. The normal Church-Turing thesis, which just says that anything which can be computed can be computed by a Turing machine, is still true when you consider quantum circuits: Turing machines can simulate quantum computers just fine if you are happy to wait a long time.
That being said, there could very well be models of computing (based on weird physical phenomena) that violate one or both versions of the Church-Turing thesis. Scott has expressed a few times that the possibility intrigues him, though I don't know whether he would bet his life's fortune on one outcome or the other :)
You should actually have said the extended Church-Turing thesis (rather than strong)