Minimum of a tail of computable function

Question

Let $G$ be a unary recursive (total computable, on natural numbers) function. Define $F$ by a formula $F(x):=\min_{y\ge x}G(y)$. Does $F$ have to be recursive?

I've solved a few hundred of tasks like this one, and usually I almost always see either an algorithm (or a nonconstructive existence of an algorithm), or a reduction from the Halting problem. But this one eludes me for almost a month already.

Of course, my hunch is that $F$ doesn't have to be recursive. But every counterexample I try to find actually has a computable $F$. Do you have any idea?

Answer 1

Your hunch is right: $F$ does not have to be recursive.

For simplicity, I'll think of $F$ and $G$ as infinite sequences of natural numbers. Here's the idea: consider the sequence $G$ whose $n$th term is $2$ if $\varphi_0(0)[n]\uparrow$ and $1$ otherwise. So e.g. if $\varphi_0(0)$ halts at stage $3$, then $G$ looks like $$2,2,2,1,1,1,1,1,...$$ The point is that we now have $F(0)=2$ iff $\varphi_0(0)\uparrow$, so we've encoded a bit of the halting problem into $F$.

Of course, coding one bit isn't enough - we need to do better. So what we'll do is start with a "default" sequence $G_*$ (I'd call it "$G_0$" but that would be way too confusing) and fold in a lot of "drops" which code halting facts. To accommodate dropping, $G_*$ needs to grow without bound, so let's take it to be the identity function $0,1,2,3,...$

I'll also adopt the convention that $(i)$ for each $s$ there is at most one $e$ such that $\varphi_e(e)$ halts in exactly $s$ stages and $(ii)$ we never have $\varphi_e(e)$ halt in $\le e$ stages. (I believe in Soare's book this is called the "hat trick," but I don't have my copy on hand. It's a good exercise to show that this isn't bogus, either by modifying the construction below to work without it or - much more flexibly - passing from the usual universal Turing machine to one with the property above.)

Now my sequence $G$ is simple: the $s$th term of $G$ is the unique $e$ such that $\varphi_e(e)$ halts in exactly $s$ stages, if such an $e$ exists, and is $s$ itself otherwise.

• Note that by the convention above, there are only finitely many possible candidates for this $e$ (namely, if $G(s)=e$ then $e\le s$ since no program with index at least $s$ halts in $s$ steps), so $G$ is in fact computable.

For example, if $\varphi_1(1)$ halts at stage $2$, $\varphi_0(0)$ halts at stage $4$, and no programs halt at stages $0, 1$, or $3$, the sequence $G$ will begin $$0, 1, \color{red}{1}, 3, \color{red}{0}, ...$$

It's a good exercise to show that from the corresponding $F$ we can compute the halting problem.

• HINT: note that $F(e+1)\le e$ iff some $\varphi_e(e)$ halts at some stage $>e$. So to tell if $\varphi_e(e)$ halts, compute $F(e+1)$; if $F(e+1)=e$ it does and if $F(e+1)>e$ it doesn't. What if $F(e+1)<e$? Then we search for some $s\ge e+1$ such that $G(s)=F(e+1)$. Run $\varphi_e(e)$ for $s$ steps; if it halts in that time then it halts, and if it doesn't go ahead and compute $F(s)$. If $F(s)=e$ then ...