FOM: Canonical non-computable number?

[William Calhoun]

I think the definition of "canonical" needs to be considered.  To think
this through, I'm going to consider an analogous question:  What is a
canonical irrational number? I think of PI, but is it reasonable to
suppose our hypothetical alien would?  I believe PI is too natural to be
completely avoided, but our alien friend might well think of PI/2 or 2PI
or some other rational multiple of PI.  So these should all be considered
equivalent for our purposes.

In the context of non-computable numbers, numbers that are Turing-
equivalent should be considered equivalent.  So I would propose the set 0'
(the set of reals that are Turing equivalent to the Halting Problem) as a
a canonical set of noncomputable numbers.  This is analogous to saying any
set of cardinality 2^omega is a canonical example of an uncountable set. 
(You might want to say specifically the set of real numbers, but do you
really want to pin down a single defintion of the real numbers and require
that the alien uses your definition?)

I understand that "canonizing" a SET of numbers won't satisfy the desire
to single out a particular number, but I mostly agree with Bauer: 

 >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. 

except that I think 0' is a simpler choice for the canonical set. 

Finally, why is pi a canonical irrational?  It is canonical in the sense
that it is a constant that naturally appears everywhere and it happens to
be irrational.  But sqrt(2) is probably a better canonical IRRATIONAL,
because there is a short proof that it is irrational.  I think 0' is the
best choice for a canonical non-computable Turing Degree, because a simple
diagonalization shows it is non-computable. 

-Bill Calhoun  (Research interest: Computability)
-Math, CS, and Stats 		wcalhoun at planetx.bloomu.edu	
-Bloomsburg University		Telephone: 570-389-4507  
-Bloomsburg, PA 17815		FAX: 570-389-3599