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 :)

 

[blue_raver22]

I would like to provide a response to these questions concerning the Church-Turing thesis. The Church-Turing thesis is a fundamental concept in computer science and mathematics, and it states that any algorithmic process can be computed by a Turing machine. This thesis has been the subject of much discussion and debate, and the different versions of the thesis that have been proposed have raised important questions about the limits of computation.

The first version of the Church-Turing thesis states that any algorithmic process can be simulated on a Turing machine. This version does not specify anything about the efficiency of the simulation. It simply implies that a Turing machine is capable of carrying out any computation that can be described by an algorithm.

The second version of the thesis adds the word "efficiently" and states that any algorithmic process can be simulated efficiently on a Turing machine. This version raises the question of what is considered efficient and whether there are algorithms that cannot be efficiently simulated on a Turing machine.

The third version of the Church-Turing thesis states that any algorithmic process can be simulated efficiently on a probabilistic Turing machine. This version introduces the concept of probability and raises the question of whether this version refers to definitive results or just results that have a high probability of being correct.

In response to question a), it is important to note that the word "efficiently" in this version implies a high probability of being correct, but not a definitive result. This means that the simulation on a probabilistic Turing machine may not always be correct, but it has a high chance of being correct.

In response to question b), it is possible that there are algorithms that can be efficiently simulated on a probabilistic Turing machine, but not on a regular Turing machine. However, it is not yet known if such algorithms exist. The search for such algorithms is an active area of research in computer science.

In response to question c), the Church-Turing thesis does not explicitly refer to higher-order logics. However, the thesis does imply that any algorithmic process, regardless of its complexity or logical structure, can be computed by a Turing machine. This means that the thesis does apply to algorithms that can handle higher-order logics, as long as they can be described by an algorithmic process.

In conclusion, the different versions of the Church-Turing thesis raise important questions about the limits of computation and the capabilities of Turing machines. While the thesis may not provide definitive answers, it serves as a guiding principle in the