FOM: Canonical codings: reply to critics
JoeShipman@aol.com
JoeShipman at aol.com
Tue Sep 4 13:21:04 EDT 2001
Baumpalis seems to miss Boldt's orginal point. What we are looking for is a
SPECIFIC set of integers which is both noncomputable and defined using so few
arbitrary choices that a hypothetical extraterrestrial mathematician is
likely to define the exact same set of integers, not just a simply equivalent
but different set of integers. Since we get noncomputable sets of integers
from unsolvable problems, this requires finding ways of coding instances of
problems into integers using no or very few arbitrary choices. This is why I
defined a toolkit of codings of varying degrees of canonicalness used them to
come up with two candidates for canonical noncomputable sets.
Bauer mistakenly supposes Boldt is looking for a canonical Omega-like real
(that is, one which codes the halting problem compactly) when he is merely
looking for a canonical noncomputable real (or set of positive integers,
since the mapping from sets of integers to reals given by {x1,x2,...}-->
((2^-x1)+(2^-x2)+...) is so canonical that everyone here seems to accept it
without comment). The difference is that, speaking loosely, the first n
bits of Omega contain the information for the halting of the first 2^n Turing
machines. Ordinarily, noncomputable sets are defined in such a way that the
membership of a particular integer in the set codes for the halting of at
most ONE Turing machine. Thus, the "canonical noncomputable sets" I defined
are very non-random and very far from Omega-like. (Of course, the coding of
halting information in Omega-like reals, while maximally efficient in terms
of space, is maximally inefficient in terms of time, since extracting the
halting information from Omega requires running time that grows as the Busy
Beaver function!)
For a canonical Omega-like set of integers, we need a canonical universal
computer that is equivalent to a Universal Turing Machine by an efficient
coding. It is probably possible to do this with group presentations though
not Diophantine equations. However, the particular canonical coding I
defined to enumerate group presentations is not appropriate for this, because
the presentations which correspond to computations are way too sparse.
Swartz's "canonical non-computable number" is not very canonical because
there are so many different ways to define "Turing machine of n states" (not
to mention that Turing machines, as mathematical objects, are not as
"canonical" as Diophantine equations or finitely presented groups).
Kanovei's enumeration of dyadic rationals is closely related to the
enumeration I gave of all rationals using Farey fractions. There is a
natural (and continuous) 1-1 correspondence between dyadic rationals and
rationals, involving Farey fractions, which is treated in detail on page
82-86 of Conway's "On Numbers and Games", where the "Farey average" (a/b,
c/d)-->((a+c)/(b+d)) of two rationals corresponds to the ordinary average of
two dyadic rationals. (The extension of this correspondence to the entire
set of real numbers is called "Minkowski's question-mark function".)
-- Joe Shipman
More information about the FOM
mailing list