3
$\begingroup$

Turing introduced the fact that the limit of a computable sequence is not necessarily computable, and the Specker sequence is a specific example of such a number (with supremum not computable).

My question is what is known about the Specker sequence in particular and limits of computable reals in general in terms of the type of number it is. The next largest structure being the Arithmetic Hierarchy: are such limits Arithmetic reals?

Furthermore do the Arithmetic reals decompose via the Arithmetic Hierarchy? In other words are there levels: with presumably the Computable reals at level one; level two Arithmetic reals (presumably encoding the Halting function); level three etc, for Arithmetic reals?

If there are such levels do the limits of computable sequence all belong to level 2?

1 Answers 1

3

A direct computation shows that a real is the limit of a uniform sequence of computable reals (like the reals obtained from Specker sequences) if and only it is at level $\Delta^0_2$ of the arithmetical hierarchy. The limit lemma shows that these are exactly the reals that are computable from $\emptyset'$, that is, computable from an oracle for the halting problem.

More generally, Post's theorem shows that a real is $\Delta^0_{n+1}$ if and only if it is computable from $\emptyset^{(n)}$, the $n$th iterated Turing jump of the empty set. These do indeed form a hierarchy, because $\emptyset^{(n+1)}$ is never computable from $\emptyset^{(n)}$, by direct relativization of the usual proof of the uncomputability of the Halting problem.

  • 0
    Yes, thanks: computability in the limit is an interesting concept.2012-09-15