FOM: Canonical non-computable number?

[G Barmpalias]

Axel Boldt wrote:


>Are there any canonical
>non-computable numbers known or is there a quick argument that none can
>exist? 
 
 Would you call a real with non-computable binary expansion (given by a known 
non-computable function) canonical? If not, then  this question reminds me a 
previous FOM discussion about Naturalness of non-recursive sets (I think that 
naturalness was discussed in a more general framework).

Isn't that what we mean by 'canonical'?

Axel Boldt says:

>I would call a number canonical if I can be sure that any sufficiently
>advanced civilization will have a name for the number or for a variant of
>it.

(well we have a name for Chaitin's omega number although Axel Boldt does not 
accept it as 'canonical'. I suppose that he meant to have a name independently 
of the fact that it is non-computable).

 and from that I understand that a number is canonical if it can be defined in 
some 'natural' way or, more precicely, it appears in some 'natural' context.
 
 The problem is how to interprete 'natural'. 
  
 
 We could look at classical mathematics for such natural contexts, and so in 
computable mathematics for a non-computable example. And since we are talking 
about real numbers, computable analysis may be appropriate. But many examples of 
non-effectivity in this area are based on the use of non-recursive sets. So, the
 question then is raised about the 'naturalness' of these sets.
 
( If we are looking for a non-trivial answer, we should rule out the 
non-recursive sets conctructed in computability theory (via diagonalization)
 with the excuse that they are somewhat artificial (they were specially 
constructed with this purpoce: to differ from all the computable ones). )
 
 Moreover since every  real number is associated with a 0-1 sequence of natural 
numbers (e.g. via its binary expansion) and vice-versa, in a 
computability-preserving way, the question is really about sets or even 
functions (we can associate a real number to any sequence of naturals in a 
complutability-preserving way).
 
 If we are to look for non-recursive sets again in mathematical practice, we 
should look at unsolvable problems. But still, these require some coding. Thus
 we may have a finitely presented group with unsolvable word problem, but to 
obtain the non-computable function we use coding, a teqnique which has been 
specially developed for diagonalizing and not encountered in mathematical 
practice, apart from logic.  
 
 Another (perhaps better) example is Julia Robinson's [JSL Vol.32 Number 3, 
Sept. 1967] system of functional equations (resonably simple and with the 
auxiliary functions elementary and very common in mathematical practice) which 
has a unique non-computable (in fact, non-arithmetical!) solution. But again, 
that system was especially constructed so that its solution gives an answer for 
the validity of any arithmetical formula.
 
 But is it impossible that seemingly (by its simplicity) innocent system of 
functional equations (or another similar) to have special importance (say, 
already known in the past) in some branch of mathematics, not having to do with 
effectivity? In that case, the system would be known as e.g. 'the system $A$'. 
And then someone (either by accident or by trying to construct a system of 
equations with non-computable solution) could observe that 'the system $A$' 
actually contains so much information (e.g. related to the validity of 
arithmetical formulae) that its solution must be non-computable. Then, we would 
say that THE SOLUTION TO THE SYSTEM $A$ (it has already a NAME) is 
non-computable. 
 
 So, the same (non-computable) mathematical object could be accepted as 
'canonical' (or 'natural'), although in the actual context of its original 
discovery (by J. Robinson) it may be criticised (for the reasons mentioned) as 
artificial.
 
 But is (or must be) the notion of 'naturalness' of an object so sensitive to 
(dependent on) the context in which that very object appears (is discovered)? 
 
 Personally, I don't think so. This search for a natural non-computable say, 
number, by rejecting the known non-computable numbers as artificial, seems 
vague. For, even if we eventually found such a 'natural' number (known 
previously in a branch of mathematics) one may not know it. So it is possible 
that he discovers it as an 'artificial' example of a non-computable number (by 
constructing it as a number which codes too much information contained in a 
known unsolvable problem). In that case the notion of naturalness would be 
totally surjective, which does not seem plausible.
 
 
 George
 Leeds University
 UK