Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Questions concerning the Church-Turing thesis

  1. Apr 18, 2013 #1
    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?

  2. jcsd
  3. Apr 18, 2013 #2

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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
  4. Apr 19, 2013 #3
    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.
    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.
    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.
  5. Apr 19, 2013 #4

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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 :)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Questions concerning the Church-Turing thesis
  1. Church'e thesis (Replies: 1)