FOM: Canonical non-computable number?
wcalhoun at planetx.bloomu.edu
Fri Sep 7 17:31:24 EDT 2001
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
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
More information about the FOM