FOM: Canonical non-computable number?

[Andrej Bauer]

At the recent "Mathematical Foundations of Computer Science"
conference in the Czech republic, Denis R. Hirschfeldt from University
of Chicago (witch coauthors R.G. Downey, and G. LaForte) gave a very
nice talk titled "Randomness and Reducibility". In it he mentioned
R. Slaman's result which says that


             x is a random real <===> x is an Omega-like real


Speaking imprecisely, a random real is one that does _not_ have an
efficient description, whereas an Omega-like real is one that is as
hard to compute as any other c.e. real.

You can find the relevant definitions in the conference proceedings
of MFCS 2001 (LNCS 2136), or in a related paper "Randomness,
Computability and Density" by Hirschfeldt and Downey, available at
http://www.math.uchicago.edu/~drh/randomness.html 

Chaitin's Omega is just one example of an Omega-real. It inspired
Solovay's definition of Omega-like reals.

Alex Boldt is interested in a canonical Omega-like real. By the above
this is like asking for a canonical random real. I would be quite
surprised if among all the random reals we could somehow pick a
"canonical one"--for how could _the_ canonical random real be random?
Perhaps some experts are lurking in this forum that could tell us
whether all random reals look the same (up to certain logical
complexity?).

I would say that the canonical concept here is not this or that
_particular_ Omega-like real, but rather the _set_ of all Omega-like
reals.

The aliens will not broadcast Chaitin's Omega into outer space. For
starters, they won't be able to compute its digits, and even if they
had the ability to broadcast it, we would have no way of knowing that
the real they are broadcasting is special in any way. The aliens will
broadcast a _definition_ of Omega-like real instead. Even more likely,
they will send us the alien equivalent of a Jerry Springer show--like
the Jerry Springer show dubbed in Czech that they broadcast in my
hotel at the conference. It was very close to a genuine alien show.


Andrej Bauer
Institute of Mathematics, Physics, and Mechanics
University of Ljubljana
Slovenia
http://andrej.com