FOM: Canonical non-computable number?
JoeShipman@aol.com
JoeShipman at aol.com
Sun Sep 2 19:10:46 EDT 2001
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
More information about the FOM
mailing list