News for hackers. Stuff that matters.
Re:When does a physical system compute? by j2kun on Sunday May 04, 2014 @09:15PM (#7696559)
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 :)

Re:When does a physical system compute? by doetoe on Monday May 05, 2014 @10:30AM (#7698742)
You should actually have said the extended Church-Turing thesis (rather than strong)
Re:When does a physical system compute? by j2kun on Monday May 05, 2014 @10:53AM (#7698862)
Ugh. yes. These silly nondescript words. They should just call it the "efficient" Church-Turing thesis so I don't get confused :)