FOM: Unsolvable problems and coding
JoeShipman@aol.com
JoeShipman at aol.com
Thu Sep 6 01:47:15 EDT 2001
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
More information about the FOM
mailing list