Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I read Scott's writing a lot, and in my opinion he seems to have the right attitude about it. He's very comfortable in the definition of a computer, and is very interested in the potential for physical computers that defy the ([edit] strong) Church-Turing thesis by using crazy weirdness of physics. Quantum circuits so far only might be such a system, since we still don't know whether BPP = BQP.

So the question isn't whether soap bubbles can do certain computations, but rather whether soap bubbles can efficiently compute functions that are NP-complete in classical computing models.



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.


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)


Ugh. yes. These silly nondescript words. They should just call it the "efficient" Church-Turing thesis so I don't get confused :)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: