Hal Finney wrote:
>That would be true IF you include descriptions that are infinitely long.
>Then the set of all descriptions would be of cardinality c. If your
>definition of a description implies that each one must be finite, then the
>set of all of them would have cardinality aleph-zero.
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 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...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?
--Jesse Mazer
_________________________________________________________________
Add photos to your e-mail with MSN 8. Get 2 months FREE*.
http://join.msn.com/?page=features/featuredemail
Received on Sat Nov 30 2002 - 14:00:30 PST