Revising the Church-Turing thesis
[extended-church-turing]
Revising the Church-Turing thesis [extended-church-turing]
The extended Church-Turing thesis is the belief that Turing machines capture our intuitive notion of what is efficiently computable. It postulates that everything we can compute in time on any physical computer can be computed on a Turing machine in time , for some constant .
Is this true, does it hold? Maybe not, with newer forms of computation like quantum computers.