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.

  • 3
    $\begingroup$ Every real is the limit of a sequence of rationals (which are C-computable for any nontrivial C). Perhaps you mean that the sequence itself is also computable, but then it should be specified what exactly this means and how you want C to figure in the statement. $\endgroup$ – Emil Jeřábek May 14 '16 at 9:30
  • 3
    $\begingroup$ Oh, and don't simultaneously cross-post to more than one SE site, as you did here: cstheory.stackexchange.com/questions/34756 . It leads to duplication of effort, wasting time of the people you ask for help. $\endgroup$ – Emil Jeřábek May 14 '16 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.