[FOM] computable numbers, independent freindly logic

[G Barmpalias]

On Sat, 27 Dec 2003, [iso-8859-7] George Kapoulas wrote:

> The concept of a computable real number is well
> known, namely we use indices of total functions to code
> sequences of rational numbers and the convergence
> rate.
> The question is if we know the complexity of the set
> of indices that represent the natural, integer and
> rational numbers in this context and if yes the relevant
> references.

I haven't got any references but it is not difficult to see that for
natural and integer the problem is $\Pi_1$-complete and for rational it is
$\Sigma_2$-complete (so the first one is of Turing degree 0' and the
second one of Turing degree 0'').

To prove it, consider the definition of computable reals in terms of
computable sequences of nested intervals with rational endpoints.
This doesn't make a difference as the two definitions are effectively
equivalent.

Now for the first problem you can effectively find an interval of the
given sequence which contains at most one integer (or natural). If it
doesn't contain any, then you can say that it doesn't converge to an
integer. Otherwise ask the $\Pi_1$ question whether that particular
natural number belongs to all intervals of the given sequence.

To show that it is $\Pi_1$-complete it is easy to translate any $\Pi_1$
problem into such an approximation problem.

For the second problem you just ask the $\Sigma_2$ question whether there
exists a rational which belongs to all intervals of the given sequence.
And again it is easy to do the translation of any $\Sigma_2$ problem into
an approximation problem of this kind.

Best wishes,

George Barmpalias

School of Mathematics
University of Leeds, UK
URL: http://www.maths.leeds.ac.uk/~georgeb/