Jesse Mazer writes:
> What about descriptions that are finite but would require an oracle machine
> to actually "compute"? We can define Omega, whose digits can be known only
> if you know whether each and every turing machine halts or not, in a finite
> number of words, but it can't be computed by any turing machine. If I'm
> remembering correctly there are also 2nd-order oracle machines that
> "compute" things 1st-order oracle machines cannot, and 3rd-order oracle
> machines, and so on, with a new level of oracle for each new ordinal
> (although I'm not sure if it makes sense to talk about aleph-one-order
> oracles or if it's just for the countable ordinals). This would suggest that
> no countable list of "finite descriptions" which includes descriptions for
> arbitrary oracle machines could ever be complete--as long as you have some
> finite rule for generating the list, you can use diagonalization to come up
> with a new number which has a finite description for some oracle machine.
I don't think this is true. Diagonalization inherently produces an
infinite-length string. You then have to assume that this string will
automatically have a finite description by using a higher-level oracle.
But I don't think the oracles work like this. There is an oracle for
Omega, but it doesn't follow that there is an oracle for every possible
infinite-length calculation (or at least that each such oracle would
have a finite description).
In other words, there are c infinite-length descriptions, and if there
is an oracle for each one, then there are c oracles, and describing a
typical one will itself require an infinite length string. Hence you
won't be able to turn an arbitrary infinite-length description into
"a new number which has a finite description for some oracle machine",
at least not if you also have to describe the oracle.
> I think that numbers like Omega really "exist" in the same sense as pi (in
> Platonia, if you will). I am not so sure about "random reals" which have no
> finite description of any kind. I don't know what implications this
> philosophy would have for a TOE...
I'm not sure it has any practical implications; my intuition is that the
measure of such objects, if they exist, would be insignificant compared
to the measure of finite strings. Hence even if universes exist based
on random reals, we are essentially certain not to live in one.
> even a number like Omega can in some sense
> be computed "in the limit" by a turing machine (by initially assuming each
> turing machine fails to halt, then simulating each one and revising the
> number each time a particular machine is found to halt), even if the value
> of a particular digit cannot be decided in a finite time as with pi or other
> computable numbers. I assume this would probably be true for any number with
> a finite description. Doesn't the UDA argument in some sense depend on the
> idea of computing "in the limit" too?
Juergen Schmidhuber explores some of the implications of extending the
class of machines, including ones that can compute Omega, at
http://www.idsia.ch/~juergen/toesv2/.
Hal Finney
Received on Sat Nov 30 2002 - 14:12:55 PST