# Stabilization of lower approximation

Let $f:\mathbb{N} \to \mathbb{R}$ be a lower semicomputable function, i.e. there exists a recursive function $g:\mathbb{N}\times \mathbb{N} \to \mathbb{Q}$ s.t.

$$\forall x \in \mathbb{N} \quad \lim_{k \to \infty} g(k,x) = f(x) \qquad\qquad (1)$$ $$\forall x \in \mathbb{N} \quad g(k,x) \le g(k+1,x)\qquad\qquad (2)$$

Question: can we assume that if $f(x)$ is rational then eventually $g(k,x)$ stabilizes on the true value? Formally, can we prove that there exists a recursive function $g':\mathbb{N}\times\mathbb{N}\to\mathbb{Q}$, possibly different from $g$, s.t. $(1)$ and $(2)$ holds for $g'$ and additionally

$$\forall x \in \mathbb{N} \quad \left( f(x) \in \mathbb{Q} \Rightarrow \exists k_0 \in \mathbb{N}\, \forall k>k_0 ~~g'(k,x) = f(x) \right)$$

I tried many different strategies but they all seem to a dead end.

Notice that $g'$ need not to be build from $g$ (there may be no relations among the two) and we need not to be able to know when $g'$ stabilizes. Think for example to the function $f$ that prints 1 if the $n$-th TM halts otherwise 0 (i.e. the characteristic function of the halting set). If you pick $g'$ as $g'(k,n)=$"$1$ if the TM $n$ halts in $k$ steps and $0$ otherwise" you clearly get that $g'$ eventually stabilizes on all $n \in \mathbb{N}$ even though we will never be able to say when.

Currently I don't even know whether this should be true or false. Maybe I'd bet on true, but it's just a feeling and that can be totally wrong of course.

• Two questions: First, I assume you want $g'$ to be (in contrast to $f$) computable, otherwise setting $g(k,x) = f(x)$ is a trivial, yet not very useful, solution. Second: I don't see how $g'$ makes any statement about $g$, if $g$ and $g'$ are not related? Assume that such a $g'$ exists, and set $g(k,x) = g'(k,x) - 1/k$. Now certainly $g$ does not "stabilize on the true value" although a $g'$ exists as required? – Lukas Barth Aug 11 '16 at 9:46
• Why doesn't the trick you used to debunk Yuval's answer always work? – Raphael Aug 11 '16 at 9:50
• @LukasBarth 1) I actually want $g'$ to be recursive, i.e. there exists a TM that halts iff $g'$ is defined and, when executed with an input which is the coding of $k$ and $x$ halts with a coding of $g'(k,x)$. Of course this cannot hold if $f(x)$ is irrational. 2) Sure, I don't really care about $g$, that was only to point out the definition I'm using of lower semicomputable. The question is whether $g'$ exists (if it does then we can always assume $g=g'$). – Manlio Aug 11 '16 at 10:14
• @Raphael Because that trick cannot be extended to the case when there is an infinity of points in which $f$ is rational. And of course, the fact that it cannot be extended does't mean that there aren't smarter tricks that can be applied. Btw, maybe it's me but I deem TM are related to the question (as $g$ and $g'$ need to be recursive, otherwise the question is trivial as in Lukas comment). I'll keep things as they are anyway :) – Manlio Aug 11 '16 at 10:16
• @Saphrosit Ad tagging: computability covers that; turing-machines should (imho) only be used if the question is about Turing machines themselves -- which this is not. – Raphael Aug 11 '16 at 11:03

Define $h(k,x)$ as the maximal $\ell \leq k$ such that program $x$ halts on inputs $1,\ldots,\ell$ after at most $k$ steps. Clearly $h(k,x)$ is computable. Define $g(k,x) = -1/h(k,x)$. Clearly $g(k,x)$ is computable and monotone.
If $x$ computes a total function then $\lim_{k\to\infty} g(k,x) = 0$. Otherwise, if $s$ is the first input on which $x$ doesn't halt then $\lim_{k\to\infty} g(x,k) = -1/(s-1) < 0$.
Suppose now that some computable function $g'(k,x)$ satisfies $\lim_{k\to\infty} g(k,x) = \lim_{k\to\infty} g'(k,x)$ for all $x$, and $g'(k,x)$ eventually stabilizes for all $x$. Thus $x$ is total iff $\exists k.g'(k,x) = 0$, putting TOT in $\Sigma_1$. However, TOT is known to be $\Pi_2$-complete, and in particular doesn't belong to $\Sigma_1$.