According to wikipedia, turing machines can be equipped with oracles that solve the halting problem; but then a new halting problem arises - whether machines equivalent to themselves ie with the oracle will halt. This gives rise to a hierarchy of turing machines with increasingly difficult halting problems. (This hierarchy can be continued into the transinfinite (ordinal) realm by using ordinal arithmetic, which shows that there are profoundly Oracular oracles or equivalently profoundly difficult halting problems).

Supposing, as some posit, that the universe is a Turing machine, and given that there is a well-defined theoretical hierarchy of Turing machines of differing strength what evidence do we have that the universe must be the simplest one, that is the first in this term? Other than using Occams Razor and simply taking the choice of the simplest? Could in fact it be equipped with an Oracle of some kind?

Note: Oracles as an idea was posited by Turing as a choice machine but not pursued or elaborated by him.


The universe is not a Turing machine. It's not an infinite tape upon which some head skitters around according to local rules. If it is being simulated upon a Turing machine,we're in the simulation, whether or not it's going to halt. So, sure, it could have any kind of oracle or none, and that might be useful to the entities (if any) running the universe-program, but to us, in a universe that could be simulated by a standard (oracle-free) Turing machine to arbitrary accuracy, it's irrelevant. (An effectively finite universe, which ours appears to be, is strictly weaker than an infinite Turing machine anyway.)

  • How is the universe effectively finite when if you take virtual particles into account there are an infinite number of particles in the smallest fragment of space? Jul 13 '13 at 21:59
  • @MoziburUllah - Planck length, Planck time. There's no evidence you need to keep track of the states of an infinity of infinitely short-lived virtual particles.
    – Rex Kerr
    Jul 13 '13 at 22:27
  • @Kerr: Is that provable? A strip of paper 1 cm in width and 10 cm long can be divided into an infinity of infinitely thin strips; if I don't keep track of all those strips I won't have my original strip. One could say my orginal strip is just an elegant way of keeping track of all that infinity of infinitely thin strips. Jul 13 '13 at 22:39
  • @MoziburUllah - You cannot actually physically do that, so it's irrelevant.
    – Rex Kerr
    Jul 14 '13 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.