Return to Answer

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

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$

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

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

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

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 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. Eventually, 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 prove 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$

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