FOM: Canonical non-computable number?

[JoeShipman@aol.com]

The best examples of canonical non-computable numbers (or canonical sets of 
natural numbers) I can think of would use the two most natural "unsolvable 
problems" --  the word problem for groups and Hilbert's 10th problem.  The 
number of arbitrary choices involved is much smaller, but you still need to 
code presentations of groups or Diophantine equations as natural numbers.  
The Diophantine problem is probably more natural, so here's an attempt:

Use Godel's trick of representing the sequence of non-negative integers 
(c1,c2,...,c_n,0,0,0,...) by the positive integer 
(2^(c1))*(3^(c2))*...*(p_n^(c_n)), where p_n is the nth prime number.  (This 
is as "canonical" a coding as you will find; we assume here that all 
sequences are infinite with only finitely many non-zero elements, and 
identify finite sequences with the infinite sequences obtained by adding 
infinitely many zeroes to them.  The sequence with all zeroes corresponds to 
the number 1.)  This gives a canonical enumeration of sequences of 
non-negative integers [ignoring trailing zeroes]:

1=(),
2=(1),
3=(0,1),
4=(2),
5=(0,0,1),
6=(1,1),
7=(0,0,0,1),
8=(3),
9=(0,2),
10=(1,0,1),
11=(0,0,0,0,1),
12=(2,1), 
etc.

Every Diophantine equation with nonnegative integer coefficients is naturally 
represented as a sequence of coefficients of monomials

The problem is now reduced to canonically enumerating the monomials, but 
since each monomial can be represented as the sequence of non-negative  
integer exponents of the denumerable set of variables {x1,x2, x3,...} we just 
use the same trick as before.  Thus, we enumerate the monomials

M1=()=1 (constant term),
M2=(1)=x1,
M3=(0,1)=x2,
M4=(2)=x1^2,
M5=(0,0,1)=x3,
M6=(1,1)=x1*x2,
M7=(0,0,0,1)=x4,
M8=(3)=x1^3,
M9=(0,2)=x2^2,
M10=(1,0,1)=x1*x3,
M11=(0,0,0,0,1)=x5,
M12=(2,1)=x1^2*x2, 
etc.

Interpret a positive integer as a Diophantine equation by regarding it as a 
sequence of non-negative integer coefficients of monomials.

Thus, the Diophantine equation 2(x1^2*x2) + (x1*x3) + 4(x1^2)+2 = 0

can be rewritten replacing monomials by their "names":
2*M12 + M10 + 4*M4 +2*M1 = 0

which is the sequence (2,0,0,4,0,0,0,0,0,1,0,2,0,0,0,0,0,0,0,....)

which has the Godel number 2^2 * 7^4 * 29 * 37^2

= 381,288,404.

The corresponding canonical non-computable set of positive integers is the 
set of positive integers corresponding to Diophantine equations with no 
solution.  (Notice the careful distinction here -- the Godel numbering 
matches positive integers with sequences of nonnegative integers, but the 
"variables" x1,x2,... are allowed to take on values in the entire set of 
integers.)

The corresponding canonical non-computable number is the one whose fractional 
base-two expansion has ones in the set of places corresponding to unsolvable 
Diophantine equations.  

I haven't seen this anywhere, but it's canonical enough that I'd feel a 
little embarrassed claiming it as my own discovery....

-- Joe Shipman