Questions concerning the Church-Turing thesis

[nomadreid]

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.

 

[Simon Bridge]

The last two are just being specific. Best not to read too much into the specific wording.
eg. A probabilistic Turing machine is a subset of a Turing machine. Some simulations are more efficient than others. (Shouldn't that be "effective" though?)

Unless I have misunderstood...
(a) "any algorithmic process" means: if it can be written down as a series of steps, then it counts.
(b) no. #1 always holds. If it is simulated by a PTM, then any TM can simulate it - the program will be different.
(c) No doubt there are, and the thesis refers to any algorithmic process.
... all subject to restrictions in the same thesis of course.

I have fluffed a bit. See also:
http://www.alanturing.net/turing_archive/pages/reference articles/The Turing-Church Thesis.html

 

[nomadreid]

Simon Bridge, thank you for your reply. The reference you gave includes some extremely interesting articles in its bibliography. (Pedantic side note: the bibliography cites some preprints which themselves start off by forbidding anyone from citing the preprint due to its differences to the final published version...and the text cites a reference -- Hogarth -- which does not exist in its bibliography. But, as the famous last line in "Some Like It Hot": "Well, nobody's perfect."). Copeland, especially, makes some interesting distinctions.

A probabilistic Turing machine is a subset of a Turing machine.

By "Turing machine" I meant (mea culpa for not writing it explicitly) "deterministic Turing machine". In that case, a deterministic Turing machine is a subset of probabilistic Turing machines. So, the question becomes
***Can a probabilistic Turing machine do something which a deterministic Turing machine cannot do?
The inspiration for thinking that it might comes from the irreducibility of quantum mechanics to classical physics, that is, killing classical determinism, so I get a gut feeling that a quantum computer (a probabilistic Turing machine) might not be reducible to a classical one, i.e., a deterministic Turing machine. Put another way, perhaps Turing's oracles might come from the real world and hence not reducible to a deterministic TM. But that is only a gut feeling that I am not sure can be justified. Hence my question.

Some simulations are more efficient than others. (Shouldn't that be "effective" though?)

No, "effectively computable" just means algorithmic, so that would have been redundant. Rather, a strong version of the Church-Turing Thesis is using the very strong (and dubious) assumption that any problem solvable on a deterministic TM that requires, say, exponential time on the deterministic TM can be reduced to a problem that requires only polynomial time ("efficient") on a deterministic TM. This is in contrast to version #3, which makes a similar claim but takes away the restriction to deterministic TM's, and which therefore has perhaps a bit more appeal.

 

[Simon Bridge]

In that case, a deterministic Turing machine is a subset of probabilistic Turing machines. So, the question becomes ***Can a probabilistic Turing machine do something which a deterministic Turing machine cannot do?

Oh OK - I'd say "yes" to that - but, like you, do not have an example handy.
Lets see if I can attract someone better versed than me :)