17
$\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.

$\endgroup$
  • $\begingroup$ I believe this answer I wrote three years ago answers your question: math.stackexchange.com/a/1267124/161559 $\endgroup$ – kasperd Apr 2 '18 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 Apr 3 '18 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 Apr 3 '18 at 17:06
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$.

$\endgroup$
  • $\begingroup$ The $\epsilon$ you mentioned is any real number or is it a computable real number? (Does it make a difference?) $\endgroup$ – Pedro A Apr 3 '18 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 Apr 3 '18 at 20:57

Your Answer

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

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