3 ms·
Hacker News doesn't attract a ton of theoretical computer scientists, but have you read Scott Aaronson's paper on the subject? http://www.scottaaronson.com/blog
by dvanduzer 12y ago
Hacker News doesn't attract a ton of theoretical computer scientists, but have you read Scott Aaronson's paper on the subject? http://www.scottaaronson.com/blog/?p=1438 http://www.scottaaronson.com/blog/?p=1438
- j2kun 12y agoI 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.
- dvanduzer 12y agoI 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.
- j2kun 12y agoI 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 :)