Classifying a set in the arithmetical hierarchy

227 Views Asked by At

It is easy to see that not every recursive partial function has a recursive total extension: consider a function which returns how long it takes $W_e$ to halt on input $e$. If this function had a recursive total extension, we could use it to solve the halting problem.

What is the location of the set of all numbers $e$ such that $\phi_e$ has a primitive recursive extension (where $\phi_e$ is the $e$th partial recursive function) in the arithmetical hierarchy?

1

There are 1 best solutions below

1
On BEST ANSWER

We can get an upper bound by just writing the sentence out, with quantifiers displayed clearly (and generally this upper bound is in fact exact, although that takes additional proof):

$\varphi_e$ has a primitive recursive extension iff there is some $n$ such that

$$\mbox{For each $k$ and $s$, if $\varphi_e(k)[s]$ halts, then it equals $p_n$}$$ where $p_n$ denotes the $n$th primitive recursive function in some standard enumeration, and $\varphi_e(k)[s]$ represents the $e$th partial computable function run on input $k$ for $s$-many stages.

Now every primitive recursive function is total, so "it equals $p_n$" doesn't add any quantifier complexity (we can just wait to see the function halt); and "$\varphi_e(k)[s]$ halts", unlike "$\varphi_e(k)$ halts," is also $\Delta_1^0$ because of the time bound $s$. So the only quantifiers which apply here are the "$\exists n$" and the "$\forall k, s$" at the beginning; so this is at worst $\Sigma^0_2$.

And it's easy to show that in fact this index set is $\Sigma^0_2$-complete: given a $\Sigma^0_2$ sentence $\psi=\exists x\forall y\theta(x, y)$, we build a computable partial function $g=\varphi_{f(\psi)}$ which "gradually diagonalizes" against the primitive recursive functions, as follows:

  • At the beginning of each stage, we'll have a current guess at a witness for $\psi$ being true. We begin with $m_0=0$.

  • At stage $n$, we'll define $g(n)$.

  • Specifically, at stage $n$, look for a counterexample $y\le n$ to "$\forall y\theta(m_n, y)$. If you find one, let $g(n)>p_i(n)$ for each $i\le n$ (where $p_i$ is the $i$th primitive recursive function in some fixed enumeration); otherwise, let $g(n)=p_{m_n}(n)$. If you find a counterexample, set $m_{n+1}=m_n+1$; otherwise, set $m_{n+1}=m_n$.

If $\psi$ holds, we eventually settle on the right witness $m$; at which point $g=p_m$ from then on. Since $g$ differs from a primitive recursive function at only finitely many points, $g$ is itself primitive recursive. Meanwhile, if $\psi$ fails, then for each $i$ there is some $n$ such that $g(n)>p_i(n)$ (just look for a "finds-a-counterexample" step after stage $i$); so $g$ differs from every primitive recursive function.

So $\psi$ holds iff $g=\varphi_{f(\psi)}$ can be extended to a primitive recursive function (in fact, is primitive recursive).


Now, you also ask about extendability to a total recursive function. This is different, since total recursive functions properly include primitive recursive functions; in particular, there is no effective enumeration of the total recursive functions (if there were we could diagonalize against it).

So let's look at the new extendability property: $\varphi_e$ has a total recursive extension iff there is some $c$ such that $$\mbox{For all $k$ and $s$, there is some $t$ such that $\varphi_c(k)[t]$ halts and if $\varphi_e(k)[s]$ halts, it equals $\varphi_c(k)[t]$}.$$ We've gained a quantifier - specifically, the clause "there is some $t$ such that $\varphi_c(k)[t]$ halts". Now our upper bound is $\Sigma^0_3$. And, in fact, this is sharp - but that argument is a bit tedious so I'll leave it out.