FOM: Canonical codings: reply to critics

[JoeShipman@aol.com]

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