- #1
nomadreid
Gold Member
- 1,674
- 209
The differences in the following versions of the Church-Turing thesis
1) any algorithmic process can be simulated on a Turing machine
2) any algorithmic process can be simulated efficiently on a Turing machine
3) any algorithmic process can be simulated efficiently on a probabilistic Turing Machine
evoke the questions:
a) Does version 3 refer to definitive results, or just results with a high probability of being correct?
b) If definitive, then has there yet been found an algorithm which would be able to be simulated on a probabilistic (e.g., quantum) computer that would not be able to be simulated at all (hence referring to version 1, not version 2) on a Turing machine?
c) Finally, are there algorithms which can handle higher-order logics (not just those parts of these logics which are reducible to first-order logic)? If so, does the thesis also refer to them?
Thanks.
1) any algorithmic process can be simulated on a Turing machine
2) any algorithmic process can be simulated efficiently on a Turing machine
3) any algorithmic process can be simulated efficiently on a probabilistic Turing Machine
evoke the questions:
a) Does version 3 refer to definitive results, or just results with a high probability of being correct?
b) If definitive, then has there yet been found an algorithm which would be able to be simulated on a probabilistic (e.g., quantum) computer that would not be able to be simulated at all (hence referring to version 1, not version 2) on a Turing machine?
c) Finally, are there algorithms which can handle higher-order logics (not just those parts of these logics which are reducible to first-order logic)? If so, does the thesis also refer to them?
Thanks.