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 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?

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?

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

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 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?