The differences in the following versions of the Church-Turing thesis(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Questions concerning the Church-Turing thesis

**Physics Forums | Science Articles, Homework Help, Discussion**