Turing degrees of lim infs of computable functions

Question

The limit lemma gives a natural characterisation of functions $f : \mathbb{N} \to 2$ with Turing degree below $0'$: they are precisely those that can be written as $f(n) = \lim_k f_k(n)$ where $f_k : \mathbb{N} \to 2$ are uniformly computable. This question is about what happens when we replace $\lim$ with limit infimum $\lim \inf$, i.e. consider those $f$ that can be written as $f(n) = \lim \inf_k f_k(n)$ where $f_k : \mathbb{N} \to 2$ are uniformly computable.

Note that $0''$ is of this form. To give a direct proof, we can define $f_k(n)$ as follows. We keep track of a variable $m$, initialised to $m := 0$. As $k$ increases, we wait for the $n$th Turing machine to halt on input $m$. While waiting, we set $f_k(n)$ to be $1$. If the Turing machine halts in $k$ steps, then we set $f_k(n)$ to be $0$, increment $m$, and then do the same thing again. The limit infimum of $f_k(n)$ is 0 iff $\varphi_n$ is total, and one of the standard characterisations of $0''$ is the subset of partial computable functions that are total.

I expect (but haven't checked in detail) that you get exactly the Turing degrees below $0''$ this way.

Since this seems a fairly natural notion, I think of this question as a reference request, so ideally I would like to know if there is somewhere in the literature where the limit inferior has been studied in this way, or somewhere the above observation is made, maybe as a remark or exercise?

Answer 1

You need a uniformity requirement in your limit characterization of $0'$, that is, the functions $f_k(n)$ need to be uniformly computable, in that there is a single computable function $f(k,n)$, such that $f(n)=\lim_{k\to\infty}f(k,n)$. In effect, $f_k(n)=f(k,n)$.

Theorem. The functions $f:\newcommand\N{\mathbb{N}}\N\to 2$ that are computable from $0'$ are exactly the total functions that are the limit of a uniformly computable sequence $f(n)=\lim_k f(k,n)$.

Proof. If $f(n)=\lim_k f(k,n)$, then with $0'$ as an oracle, we can tell if $f_k(n)$ has stabilized yet, and so we can know whether we have achieved the limit value. So we can compute $f$ from $0'$.

Conversely, if $f$ is computable from $0'$, then we can start computing approximations to $0'$---at stage $k$ let the approximation be all the programs that have halted in $k$ steps. Let $f(k,n)$ try to compute $f$ using that approximation as an oracle, trying for $k$ steps. Eventually, for large enough $k$, the approximation will be accurate enough to support a halting computation with the true oracle, and so $f(k,n)$ will converge to $f(n)$. $\Box$

Consider now the case of $\liminf$ with $0''$.

First, we can see that $\liminf_k f(k,n)=0$ if and only if there are infinitely many $k$ for which $f(k,n)=0$, that is, $\forall m\exists k>m\ f(k,n)=0$, and otherwise it is $1$. Thus, the zero set of any such function is $\Pi^0_2$, which is therefore computable from $0''$.

But not every function computable from $0''$ will arise as such a liminf function, for the simple reason that in computability from $0''$, we can computably take the complement. That is, let $f:\N\to 2$ be a function whose $0$ set is complete $\Sigma^0_2$. This is computable from $0''$, but since the zero set is not $\Pi^0_2$, it cannot arise as the $\liminf$ of a uniformly computable system of functions.

Meanwhile, we get a positive characterization as follows.

Theorem. The functions $f:\N\to 2$ that are realized as $\liminf_k f_k$ of a uniformly computable system are exactly the characteristic functions of a $\Sigma^0_2$ set.

Proof. We've proved above that the zero set of such a $\liminf$ function is $\Pi^0_2$, so it is the characteristic function of the complement set, where the value is $1$, which is $\Sigma^0_2$.

Conversely, suppose $A\subseteq\N$ is a $\Sigma^0_2$ set $A$. The characteristic function $f_A$ is realized, I claim, as the $\liminf_k f_k$ of a uniformly computable system of functions. To see this, assume $n\in A\iff \exists r\forall s\ \varphi(r,s,n)$, where $\varphi$ has only bounded quantifiers. Let $f(k,n)$ undertake the following process. We try out $r=0$, $r=1$ and so forth in turn. For each candidate $r$, we check $s=0$, $s=1$, $s=2$, and see whether $\varphi(r,s,n)$. We do this all for $k$ steps. And the point is that every time we find a bad $r$, one for which some $s$ fails, then we define $f(k,n)=0$ at that moment, and otherwise keep $f(k,n)=1$. This will ensure $\liminf_k f(k,n)=1$ just in case there is a good $r$. And this is the same as $n\in A$. So we realized $f_A$ as a $\liminf$ of a computable system. $\Box$