18
$\begingroup$

Does there exist a computable function $f:\mathbb{N}\rightarrow \mathbb{Q}$ such that:

  • For all $t\in\mathbb{N}: 0\le f(t) < X$
  • $\lim\limits_{t\rightarrow\infty} f(t) = X$

Where $X$ is an uncomputable real number.

The only reference to this question I have found was the answer to this question: https://math.stackexchange.com/a/1052579/168764, where the function seems that it would hold, but I have no idea how to prove that the limit of this function is an uncomputable real number.

Improve this question
$\endgroup$
3
  • $\begingroup$ I believe this answer I wrote three years ago answers your question: math.stackexchange.com/a/1267124/161559 $\endgroup$
    – kasperd
    Commented Apr 2, 2018 at 23:34
  • 2
    $\begingroup$ The numbers obtainable as such as limit $X$ are called left-c.e. reals, in case you want to search for more about their properties. $\endgroup$
    – Arno
    Commented Apr 3, 2018 at 9:11
  • $\begingroup$ maybe also math.stackexchange.com/a/462835/128985 which gives such a function I think (unless I have the logic the wrong way around) $\endgroup$
    – Philip Oakley
    Commented Apr 3, 2018 at 17:06

1 Answer 1

Reset to default
31
$\begingroup$

Consider the real number encoding of the (almost) halting problem, i.e. $0.r_1r_2...$ where $r_i=1$ if the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r_i=0$ otherwise. Let us denote this number by $R$.

Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $< n$ on the empty input for $n$ steps, and returns $0.\hat{r_1}...\hat{r_{2^n-1}}$ where $\hat{r_i}=1$ if the $i$'th Turing machine halts on the empty input in less than $n$ steps, and $\hat{r_i}=0$ otherwise. Clearly for all $n$ it holds that $M(n)< R$, and it is not too hard to show that $\{M(n)\}_{n\in\mathbb{N}}$ converges to $R$. The key point is that rate of convergence is not computable, meaning that given $\epsilon$, you cannot compute the index such that beyond it the series is $\epsilon$-close to $R$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The $\epsilon$ you mentioned is any real number or is it a computable real number? (Does it make a difference?) $\endgroup$
    – Pedro A
    Commented Apr 3, 2018 at 20:25
  • 1
    $\begingroup$ There isn't any computability issue here, but since we're talking about an input to a Turing machine, it has to have some finite representation, so we can think of $\epsilon$ as a small rational number. $\endgroup$
    – Ariel
    Commented Apr 3, 2018 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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