Hacker News Reader

>There are no formal arguments against Church–Turing thesis.

do you mean "all computation that can be done, can be done using a Turing machine"? Or do you mean "no one has proven Church Turing wrong?"

If it's the second - yes, that's so. But so what?

If it's the first then many people in Quantum Computing community will be quite upset, P=BQP? You have proof?

View on HN

P=BPP would contradict the extended Church-Turing thesis. Quantum computers can definitely be simulated by classical ones (with an exponential slowdown) so the CTT, which says nothing about performance, is not threatened by them.

The life time of the universe and the physical extent of possible classical computers limits "all the computing that can be done" quite strongly. Especially with regard to intelligence - where the physical and temporal extent of brains are clear.

Reply on news.ycombinator.com