Hal Finney wrote:
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.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.
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?
Add photos to your e-mail with MSN 8. Get 2 months FREE*. http://join.msn.com/?page=features/featuredemail