<p>Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a_i)_{i \in \mathbb{N}}$ such that (1) the function $i \mapsto a_i$ is recursive and (2) there exists a recursive function $\xi$ such that, for all $j,k,n \in \mathbb{N}$, if $j,k&lt;\xi(n)$, then $\vert a_j - a_k \vert &lt; n^{-1}$. </p>

<p>Specker (1949) showed that there exist sequences of recursive reals that converge to a nonrecursive real.</p>

<p>Given any complexity class $\mathsf{C}$, however, we can define a notion of $\mathsf{C}$-computable real number by uniformly replacing 'recursive function' in the definition above with 'function in $\mathsf{C}$'. </p>

<p>Do analogues of Specker's result hold for the most obvious such notions? I.e., do there exist sequences of $\mathsf{C}$-computable reals that converge to non-$\mathsf{C}$-computable limits when $\mathsf{C} = \mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXP}$, etc.? </p>

<p>I have not been able to find any discussions of this question in the literature; if some exist, I'd be very grateful for any pointers. I don't think there's any trivial way to generalize Specker's proof since it relies on the existence of a recursive enumeration of a nonrecursive set.  </p>

CC BY-SA 3.0
2016-05-14T01:39:08.550Z
Yes, see Ker-I Ko's book "[Complexity Theory of Real Functions](https://books.google.ca/books?id=QJnVBwAAQBAJ)" or chapter 6 of Klaus Weihrauch's book "[Computable Analysis](https://books.google.ca/books?id=Ir6qCAAAQBAJ)"
Kaveh
CC BY-SA 3.0
2016-05-14T09:34:11.620Z
Simultaneously cross-posted to http://mathoverflow.net/questions/238803 .
Emil Jeřábek
CC BY-SA 3.0
2016-05-14T09:46:03.233Z
Your defintion of computable real has a mistake, it should say $j, k > \xi(n)$, not $<$. And Specker proved more than what you claim: the recursive sequence is a strictly increasing rational sequence, contained in $[0,1]$ and computably away from every computable real.
Andrej Bauer
CC BY-SA 3.0
2016-05-14T09:47:13.457Z
And it should say that $a_i$ are ratonals, presumably.
Andrej Bauer
CC BY-SA 4.0
2019-06-20T03:38:15.813Z
It's also vital that the sequence *itself* be computable.  In fact, that's the key point; the individual reals in the sequence may (without loss of generality) be taken to simply be rational numbers.  After all, *every* real number is the limit of a sequence of rational numbers, just not the limit of a *computable* sequence; and the surprising thing is that there are computable sequences with *non*-computable limits.
Toby Bartels
<complexity-classes><computability><computing-over-reals>
Are there analogues of Specker sequences for other complexity classes?
Beau Madison Mount
# Are there analogues of Specker sequences for other complexity classes?

(Asked by: username_0 on 2016-05-14)

Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a\_i)\_{i \in \mathbb{N}}$ such that (1) the function $i \mapsto a\_i$ is recursive and (2) there exists a recursive function $\xi$ such that, for all $j,k,n \in \mathbb{N}$, if $j,k<\xi(n)$, then $\vert a\_j - a\_k \vert < n^{-1}$.

Specker (1949) showed that there exist sequences of recursive reals that converge to a nonrecursive real.

Given any complexity class $\mathsf{C}$, however, we can define a notion of $\mathsf{C}$-computable real number by uniformly replacing 'recursive function' in the definition above with 'function in $\mathsf{C}$'.

Do analogues of Specker's result hold for the most obvious such notions? I.e., do there exist sequences of $\mathsf{C}$-computable reals that converge to non-$\mathsf{C}$-computable limits when $\mathsf{C} = \mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXP}$, etc.?

I have not been able to find any discussions of this question in the literature; if some exist, I'd be very grateful for any pointers. I don't think there's any trivial way to generalize Specker's proof since it relies on the existence of a recursive enumeration of a nonrecursive set.

**Tags:** complexity-classes, computability, computing-over-reals
> **Comments:**
> **username_1**: Yes, see Ker-I Ko's book "[Complexity Theory of Real Functions](https://books.google.ca/books?id=QJnVBwAAQBAJ)" or chapter 6 of Klaus Weihrauch's book "[Computable Analysis](https://books.google.ca/books?id=Ir6qCAAAQBAJ)"  
> **username_2**: Simultaneously cross-posted to http://mathoverflow.net/questions/238803 .  
> **username_3**: Your defintion of computable real has a mistake, it should say $j, k > \xi(n)$, not $<$. And Specker proved more than what you claim: the recursive sequence is a strictly increasing rational sequence, contained in $[0,1]$ and computably away from every computable real.  
> **username_3**: And it should say that $a_i$ are ratonals, presumably.  
> **username_4**: It's also vital that the sequence *itself* be computable.  In fact, that's the key point; the individual reals in the sequence may (without loss of generality) be taken to simply be rational numbers.  After all, *every* real number is the limit of a sequence of rational numbers, just not the limit of a *computable* sequence; and the surprising thing is that there are computable sequences with *non*-computable limits.  

---

## 0 answers

