3 ms·
>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
by sgt101 7y ago
>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?
- voidmain 7y agoP=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.
- sgt101 7y agoThe 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.