Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Yes, thanks: computability in the limit is an interesting concept. –  Roy Simpson Sep 15 '12 at 8:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.