FOM: Canonical non-computable number?
G Barmpalias
georgeb at amsta.leeds.ac.uk
Mon Sep 3 13:23:27 EDT 2001
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
More information about the FOM
mailing list