FOM: Canonical non-computable number?

Robert Swartz rs at interaccess.com
Tue Sep 4 10:44:25 EDT 2001


A simple canonical non-computable number can be constructed as follows.

First take the usual definition of the the Busy Beaver Problem. BB(n) is
defined as the the number of ones a turing machine of n states can write
and still halt. One can construct a non-computable number in the
following manner,  the first set of digits of the number is BB(1)
followed by a space,  the second set of digits is BB(2) followed by a
space and so on.  This number is canonical, and is only dependent on the
alphabet chosen.  This approach can readily extended to the the variants
of Busy Beaver, such as run time, amount of tape consumed, the number of
state transitions and so on.

Bob Swartz






More information about the FOM mailing list