Effectively, there is either some natural number n such that physics allows for n levels of physically-implementable Turing oracles, or the number is omega. Mostly, we think the number should either be zero or omega, because once you have a first-level Turing Oracle, you construct the next level just by phrasing the Halting Problem for Turing Machines with One Oracle, and then positing an oracle for that, and so on.
Likewise, having omega (cardinality of the natural numbers) bits of algorithmic information is equivalent to having a first-level Turing Oracle (knowing the value of Chaitin’s Omega completely). From there, you start needing larger and larger infinities of bits to handle higher levels of the Turing hierarchy.
So the question is: how large a set of bits can physics allow us to compute with? Possible answers are:
Finite only. This is what we currently believe.
Countably infinite (Alef zero) or Continuum infinite (Alef one). Playing time-dilation games with General Relativity might, in certain funky situations I don’t quite understand but which form the basis of some science fiction, almost allow you to get up to here. But it would require negative energy or infinite mass or things of that nature.
Arbitrarily large infinities. Almost definitely not.
Omega: if we’re completely wrong about the relationship between computation and physics as we know it, possible.
Effectively, there is either some natural number
nsuch that physics allows fornlevels of physically-implementable Turing oracles, or the number is omega. Mostly, we think the number should either be zero or omega, because once you have a first-level Turing Oracle, you construct the next level just by phrasing the Halting Problem for Turing Machines with One Oracle, and then positing an oracle for that, and so on.Likewise, having omega (cardinality of the natural numbers) bits of algorithmic information is equivalent to having a first-level Turing Oracle (knowing the value of Chaitin’s Omega completely). From there, you start needing larger and larger infinities of bits to handle higher levels of the Turing hierarchy.
So the question is: how large a set of bits can physics allow us to compute with? Possible answers are:
Finite only. This is what we currently believe.
Countably infinite (Alef zero) or Continuum infinite (Alef one). Playing time-dilation games with General Relativity might, in certain funky situations I don’t quite understand but which form the basis of some science fiction, almost allow you to get up to here. But it would require negative energy or infinite mass or things of that nature.
Arbitrarily large infinities. Almost definitely not.
Omega: if we’re completely wrong about the relationship between computation and physics as we know it, possible.