Cheap and Secure Web Hosting Provider : See Now

[Answers] Stabilization of lower approximation

, , No Comments
Problem Detail: 

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.

Asked By : Saphrosit

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/62487

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback