FOM: Unsolvable problems and coding

[JoeShipman@aol.com]

All the enumerable nonrecursive sets usually defined are finite objects with 
some structure (solvable diophantine equations, trivial finitely presented 
groups, halting Turing machines, simply connected simplicial 4-manifolds), so 
that obtaining a nonrecursive set of integers from them requires some coding. 
 Although (as I pointed out in an earlier posting) the codings can be very 
canonical, this still does not give a completely satisfactory answer to 
Boldt's request for a "canonical noncomputable real number" (where we DO 
regard the mapping from sets of integers to real numbers given by binary 
expansion as perfectly canonical so that this is equivalent to asking for a 
canonical noncomputable set of integers).

Can we derive a noncomputable set of integers from the above nonrecursive 
sets without using any coding?

One way is to have the set of integers describe the nonrecursive set in some 
other way than a 1-1 correspondence.  For example, define f(n) to be the 
number of solvable Diophantine equations in which the absolute value of the 
coefficients and the total degree of monomials and the number of variables 
are all bounded by n.  It is clear that f is nonrecursive, because with an 
oracle for f we could tell whether an arbitrary Diophantine equation D had a 
solution by enumerating all possible solutions to all Diophantine equations 
whose corresponding bounds are no greater than the bound for D until we have 
all of them -- we will know we are done because f tells us how many we have 
to wait for.  (Of course this has a busy beaverish running time, but who's 
counting?)

f is obviously a "canonical" nonrecursive function because no coding is 
involved -- the effect of the counting is to sum over and thereby render 
irrelevant whatever coding is used.  But this is not quite a canonical 
nonrecursive SET of integers.  We could use the graph of f to get a set of 
pairs of integers and then code that by a single application of a pairing 
function; but it is not so easy to find a canonical pairing function and this 
is still coding.

A better candidate is simply the set {m | there exists n such that f(n)=m}, 
the range of f.  Since f is obviously a strictly increasing function, because 
increasing the bound from n to n+1 introduces the new solvable Diophantine 
equation (n+1)x=0, f can be recovered from an oracle for its range set.

The only arbitrariness here lies in the choice of which aspects of the 
Diophantine equations to bound simultaneously -- for example, instead of 
maximum total degree of monomials I could have used maximum exponent of any 
variable in a monomial.

Does anyone have any alternative suggestions?

-- Joe Shipman