FOM: Canonical non-computable number?

Stephen Fenner fenner at cse.sc.edu
Tue Sep 4 13:29:11 EDT 2001


On Tue, 4 Sep 2001, Robert Swartz wrote:

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

Wouldn't it also depend on the definition of Turing machine used?
(one-way infinite single tape, two-way infinite single tape, k-tape, what
tape movements are allowed, etc.)  To me, the definition of Turing machine
is complicated enough that it is unlikely that an alien race would happen
upon the same definition, thus producing the same Busy Beaver function as
ours.  Only an opinion, though.

Steve





More information about the FOM mailing list