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.

  • 1
    $\begingroup$ 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? $\endgroup$ – Lukas Barth Aug 11 '16 at 9:46
  • $\begingroup$ Why doesn't the trick you used to debunk Yuval's answer always work? $\endgroup$ – Raphael Aug 11 '16 at 9:50
  • $\begingroup$ @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'$). $\endgroup$ – Manlio Aug 11 '16 at 10:14
  • 2
    $\begingroup$ @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 :) $\endgroup$ – Manlio Aug 11 '16 at 10:16
  • $\begingroup$ @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. $\endgroup$ – 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$.

  • $\begingroup$ Can't find any error on the reasoning, so it's probably the counterexample I was looking for! Thank you very much! $\endgroup$ – Manlio Aug 13 '16 at 12:19

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.