Some Adventures in Computability

A partial function $f\colon\mathbb N^2\rightarrow \mathbb N$ is code invariant if $$\forall n\in\mathbb N\forall \text{Turing machines }T_0, T_1 (\varphi_{T_0}=\varphi_{T_1}\rightarrow f(n, \ulcorner T_0\urcorner)=f(n, \ulcorner T_1\urcorner)).$$ We denote the set of (partial) recursive code invariant functions by $\mathcal I$.

The $*$-recursive functions are the smallest family $\mathcal F$ of partial functions $f\colon \mathbb N^k\times\mathcal P\rightarrow \mathbb N$ so that

$(1)$ $g(\vec x, \varphi)=h(\vec x)$ is in $\mathcal F$ for any recursive $h$,

$(2)$ the application function $a(n, \varphi)=\varphi(n)$ is in $\mathcal F$,

$(3)$ $\mathcal F$ is closed under the usual recursive operations in which the last argument is simply passed through. For example, if $h_0,\dots, h_n\colon\mathbb N^k\times\mathcal R\rightarrow\mathbb N$ and $g\colon\mathbb N^{n+1}\times\mathcal R\rightarrow\mathbb N$ are in $\mathcal F$ then the composition $$(\vec x, \varphi)\mapsto g(h_0(\vec x, \varphi),\dots, h_n(\vec x, \varphi),\varphi)$$ (defined whenever possible) is in $\mathcal F$.

Suppose $\mathcal F$ is a set of partial functions of type $\mathbb N^2\rightarrow \mathbb N$ and $\mathcal G$ is a set of functions of type $\mathbb N\times\mathcal P\rightarrow\mathbb N$.

$(1)$ $\mathcal F$ is reducible to $\mathcal G$ (resp. $\mathcal G$ is reducible to $\mathcal F$) if there is a function $F\colon\mathcal F\rightarrow \mathcal G$ (resp. $G\colon\mathcal G\rightarrow\mathcal F$) so that whenever $F(f)=g$ (resp. $G(g)=f$) then $$\forall n\in\mathbb N\forall \text{ Turing machines }T\ f(n, \ulcorner T\urcorner) = g(n, \varphi_T).$$ This is supposed to be interpreted in the strong sense that also $f(n,\ulcorner T\urcorner)$ is defined iff $g(n, \varphi_T)$ is defined.

$(2)$ $\mathcal F$ and $\mathcal G$ are equivalent if each of them is reducible to the other.

Is $\mathcal I$ equivalent to $\mathcal R_\ast$?

$\mathcal R_\ast$ is reducible to $\mathcal I$, but $\mathcal I$ is not reducible to $\mathcal G$.

A $\ast$-recursive $g$ is essentially a program which has access to an additional private function $\mathrm{apply}(k)$ which returns $f(k)$, where $f$ is the second argument of $g$. However, invoking $\mathrm{apply}$ is dangerous since if $f$ is not defined on the input we are passing to $\mathrm{apply}$, we immediately get stuck in an infinite loop. We can produce a program which on input $n, \ulcorner T\urcorner$ simulates $g(n, \varphi_T)$: we simply follow the program which induces $g$ and whenever $\mathrm{apply}$ is invoked with input $k$, we simulate $T$ with input $k$. This program holds iff $g(n, \varphi_T)$ is defined and in case it is defined outputs $g(n, \varphi_T)$.

To see that $\mathcal I$ is not reducible to $\mathcal G$, note that there is a recursive function $d\colon\mathbb N\rightarrow \{0\}$ which semi-decides whether a Turing machine $T$ halts on some input. That is $d(\ulcorner T\urcorner)$ is defined iff $\mathrm{dom}(\varphi_T)\neq\emptyset$. This function is not induced by any $*$-recursive function: If $g\colon\mathcal P\rightarrow\mathbb N$ is in $\mathcal R_\ast$ and non-trivial then there will be a first instance where $g$ invokes $\mathrm{apply}$ with input $k$ (no matter the input of $g$!). Let $\varphi$ be any finite function which is defined on $k+1$, but not on $k$. Then $g(\varphi)$ is not defined.

Suppose $g\colon \mathbb N^{k+1}\times\mathcal P\rightarrow \mathbb N$ is a partial function. Then $\eta(g)\colon\mathbb N^k\times\mathcal P$ is the partial function which is defined on $x_1,\dots, x_k,f$ iff $\exists x_0\ (x_0,\dots, x_k, \varphi)\in\mathrm{dom}(g)$ in which case $\eta(x_1,\dots, x_k, \varphi)=0$.

The $\eta$-recursive functions are the smallest collection $\mathcal F$ of partial functions of type $\mathbb N^k\times\mathcal P\rightarrow\mathbb N$ which satisfies $(1)-(3)$ from the definition of $*$-recursive functions and is closed under the $\eta$-operation. That is, whenever $g\in\mathcal F$ is of type $\mathbb N^{k+1}\times\mathcal P\rightarrow\mathbb N$ then $\eta(g)\in\mathcal F$.

$\mathcal R_{\eta}$ denotes the collection of $\eta$-recursive functions.

Is $\mathcal I$ equivalent to $\mathcal R_\eta$?

For any $f\in\mathcal R_\eta$ there is $g\in\mathcal R_\ast$ with $f\subseteq g$.

Any $f\in\mathcal R_\eta$ is induced by a program $T$ which has access to $\mathrm{apply}$ and another private function $\mathrm{halts\_on\_some\_input}(n, \vec x)$, which when passed the source code of another $\mathcal R_\eta$-program returns $0$ iff it halts on some input with further arguments $\vec x$ (and loops infintely otherwise).

Let $T_\ast$ be the computation in which calls to $\mathrm{halts\_on\_some\_input}()$ are replaced with calls to $\mathrm{returns\_zero}()$ which always returns $0$. If $T$ halts on input $\vec x, \varphi$ then $T_\ast$ halts on input $\vec x,\varphi$ and returns the same value.

$\mathcal R_\eta$ is reducible to $\mathcal I$, but $\mathcal I$ is not reducible to $\mathcal R_\eta$.

We leave prove something stronger than the first part later and instead focus on the second part.

Let $\mathbb P$ be the partial order of finite partial functions $p\colon\mathbb N\rightarrow\mathbb N$ ordered by inclusion and let $$A=\{a_k\mid k\leq n\}$$ be any finite antichain in $\mathbb P$ with $\bigcap_{k\leq n} \mathrm{dom}(a_k)=\emptyset$ and $n>1$. That $A$ is an antichain means that for $i\neq j$ there is some $n\in\mathrm{dom}(a_i)\cap\mathrm{dom}(a_j)$ with $a_i(n)\neq a_j(n)$.

Let $f\colon\mathbb N\rightarrow\mathbb N$ be defined by $f(\ulcorner T\urcorner)=k$ where $k$ is unique such that $a_k\subseteq \varphi_T$ (if there is such a $k$, otherwise $f$ is undefined on that input). Note that $f$ is indeed recursive and trivially code invariant.

We will argue that there is no $g\in\mathcal R_\eta$ so that $f(\ulcorner T\urcorner)=g(\varphi_T)$ for all Turing machines $T$. By the previous proposition, it suffices to show that there is no $h\in\mathcal R_\ast$ with $f(\ulcorner T\urcorner)=h(\varphi_T)$ whenever $\ulcorner T\urcorner\in\mathrm{dom}(f)$. Suppose such an $h$ exists and let's run a $*$-recursive program which induces such an $h$. As $n>1$, whis program must call $\mathrm{apply}()$ at some point, say the first instance does so with input $m$. Note that $m$ does not depend on the input function. As $\bigcap_{k\leq n} \mathrm{dom}(a_k)=\emptyset$, there is some $k\leq n$ with $m\notin \mathrm{dom}(a_k)$. But then $h$ is not defined on $a_k$, yet $f(\ulcorner T\urcorner)$ is defined for any $T$ with $\varphi_T=a_k$, contradiction!

The $\tilde{\eta}$-recursive functions are the smallest family $\mathcal F$ of (total) functions of type $\mathbb N^k\times\mathcal P\rightarrow\mathcal P(\mathbb N)$ satisfying the following conditions.

$(1)$ for any recursive $g$, $f\in\mathcal F$ where $f(\vec x, \varphi)=\{g(\vec x)\}$.

$(2)$ $a\in\mathcal F$ where $a(n,\varphi)=\{\varphi(n)\}$.

$(3)$ $\mathcal F$ is closed under the usual recursive operations in the approriate sense, e.g. whenever $g_0,\dots, g_k, h\in\mathcal F$ then $$(\vec x_0,\dots, \vec x_k, \varphi)\mapsto\bigcup_{n_0,\dots, n_k\in\mathbb N}\{h(n_0,\dots, n_k,\varphi)\mid\forall i\leq k\ n_i\in g_i(\vec x_i,\varphi)\}$$ is in $\mathcal F$.

$(4)$ whenever $f\in\mathcal F$ is of type $\mathbb N^{k+1}\times\mathcal P\rightarrow\mathcal P(\mathbb N)$ then $\tilde{\eta}(f)\in\mathcal F$ where $$\tilde{\eta}(f)(x_1,\dots, x_k,\varphi)=\{n\in\mathbb N\mid f(n,x_1,\dots, x_k,\varphi)\neq\emptyset\}.$$

A (partial) function $g\colon\mathbb N^k\times\mathcal P\rightarrow \mathbb N$ is deterministic $\tilde{\eta}$-recursive iff $$h(\vec x, \varphi)=\{g(\vec x,\varphi)\}$$ is $\tilde{\eta}$-recursive.

The collecion of all deterministic $\tilde{\eta}$-recursive functions is $\mathcal R_{\tilde{\eta}}^{\mathrm{det}}$.

$\mathcal I$ is equivalent to $\mathcal R_{\tilde{\eta}}^{\mathrm{det}}$.

(Rice-Shapiro) Suppose $g\in \mathcal I$ and $g(n,\ulcorner T\urcorner)=m$.

$(1)$ If $T'$ is any Turing machine with $\varphi_T\subseteq\varphi_{T'}$ then $g(n, \ulcorner T'\urcorner)=m$.

$(2)$ There is some $T'$ so that $\varphi_{T'}$ is finite, $\varphi_{T'}\subseteq\varphi_T$ and $g(n, \ulcorner T'\urcorner)=m$.

We first prove $(1)$, so assume $\varphi_T\subseteq\varphi_{T'}$. By the recursion theorem, there is a Turing machine $S$ so that given input $k$,

• $S$ starts by simultaneously computing $g(n, \ulcorner S\urcorner)$ and $\varphi_T(k)$.

• If the computation of $\varphi_T(k)$ halts first, return $\varphi_T(k)$.

• Otherwise if $g(n, \ulcorner S\urcorner)$ halts with output $l$ then return $\varphi_T(k)$ if $l\neq m$ and return $\varphi_{T'}(k)$ if $l=m$.

For $(2)$, let $S$ be the Turing machine which on input $k$ first simulates the first $k$ steps of the computation of $g(n, \ulcorner S\urcorner)$. If this halted with output $m$ then loop indefinitely. Otherwise, return $\varphi_T(k)$. Once again, such a $S$ exists by the recursion theorem.

If $g(n, \ulcorner S\urcorner)$ is not defined or $\neq m$ then $\varphi_S=\varphi_T$, contradiction. So $g(n, \ulcorner S\urcorner)=m$ and $\varphi_S$ is a finite subfunction of $\varphi_T$.

(Rice-Shapiro for $\mathcal R_{\tilde{\eta}}$) Suppose $g\in \mathcal R_{\tilde{\eta}}$ and $m\in g(\vec x, \varphi)$.

$(1)$ If $\varphi\subseteq\psi$ then $m\in g(\vec x,\psi)$.

$(2)$ There is some finite $\varphi'\subseteq\varphi$ with $m\in g(\vec x, \varphi')$.

We prove this by induction on the complexity of $g$. This is easy for $g$ as in $(1)$ or $(2)$ in the definition of $\mathcal R_{\tilde{\eta}}$.

Suppose $(1)+(2)$ hold for $g$. We show that it holds for $\tilde{\eta}(g)$. Say, $$m\in \tilde{\eta}(g)(\vec x, \varphi).$$ Note that this implies $g(m,\vec x,\varphi)\neq\emptyset$.

To see that $(1)$ holds, by induction, $g(m,\vec x,\psi)\neq \emptyset$ and hence by definition of $\tilde{\eta}$, $$m\in \tilde{\eta}(g)(\vec x,\varphi).$$

Let's prove $(2)$. By induction, there is some finite $\varphi'\subseteq\varphi$ so that $g(m,\vec x,\varphi')\neq\emptyset$. But then once again $m\in\tilde{\eta}(g)(\vec x,\varphi)$.

We leave the remaining cases to the reader.

(Rice-Shapiro for $\mathcal R_{\tilde{\eta}}^{\mathrm{det}}$) Suppose $g\in \mathcal R_{\tilde{\eta}}^{\mathrm{det}}$ and $g(n,\varphi)=m$.

$(1)$ If $\varphi\subseteq\psi$ then $g(n, \psi)=m$.

$(2)$ There is some finite $\varphi'\subseteq\varphi$ with $g(n,\varphi')=m$.

Let's start with the easier direction, namely that $\mathcal R_{\tilde{\eta}}^{\mathrm{det}}$ is reducible to $\mathcal I$. Let $g\in \mathcal R_{\tilde{\eta}}^{\mathrm{det}}$ and let $h\in\mathcal R_{\tilde{\eta}}$ induce $g$. As before we will simulate a computation of $h$ and we will do an exhaustive search for a legal behaviour of that program which terminates. We only explain how to simulate the $\mathrm{random\_halting\_point}()$-function calls. Whenever $h$ performs such a call with input the code for some $z\in\mathcal R_{\tilde{\eta}}$ and $\vec x\in\mathbb N^k$, we start searching for some $y_0$ so that $z(y,\vec x, \varphi_T)\neq\emptyset$ (by induction on $h$, we already know how to do that). But crucially, we don't stop once we find such $y_0$. Instead, we pass on $y_0$ to the further simulation and simultaneously search for a further $y_1$. If we find $y_1$ we pass this on further and so on.

If this program halts on input $n, \ulcorner T\urcorner$ with output $m$ then there is some possible behaviour of $\mathrm{random\_halting\_point}()$ which results in $T$ halting with output $m$. Equivalently, $m\in h(n,\varphi)$. But then $g(n,\varphi_T)=m$. Also, this program halts iff $h(n,\varphi_T)\neq\emptyset$, or equivalently, $(n,\varphi_T)\in\mathrm{dom}(g)$. So we successfully simulate $g$ in this way.

Now for the more interesting direction. Let $f$ be code invariant, we will find some $g\in\mathcal R_{\tilde{\eta}}^{\mathrm{det}}$ so that $f(n, \ulcorner T\urcorner)=g(n, \varphi_T)$ for all $n, T$.

Consider the following function $h\colon\mathbb N^2\times\mathcal P\rightarrow\mathbb N$. On input $k, n, \varphi$, the computation proceeds as follows.

• First compute the $k$-th finite subset $s_k\subseteq\mathbb N$ (by some fixed recursion).

• Then try to figure out $\varphi(l)$ for all $l\in s_k$.

• If this succeeds, we know $\varphi\upharpoonright s_k$. Then construct a Turing machine $S$ with $\varphi_{S}=\varphi\upharpoonright s_k$.

• Finally, compute $f(n, \ulcorner S\urcorner)$ and return the output.

We then let $$\tilde{g}(n, \varphi)=\{h(k, n, \varphi)\mid k\in \tilde{\eta}(\tilde h)(k,n,\varphi)\}$$ and note that $\tilde g$ is $\tilde{\eta}$-recursive.

We will see that $\tilde{\eta}$ induces some $g\in\mathcal R_{\tilde{\eta}}^{\mathrm{det}}$, i.e. $\tilde{g}(n,\varphi)=\{g(n,\varphi)\}$.

Suppose $f(n,\ulcorner T\urcorner)=m$. Then by $(1)$ of Rice-Shapiro, if $h(k, n, \varphi_T)$ is defined with output $m$ then $f(n, \ulcorner T\urcorner)=m$ and, by $(2)$ of Rice-Shapiro, there is some $k$ so that $h(k, n,\varphi_T)$ is defined. It follows that $$m\in \tilde{g}(n, \varphi_T).$$ Similarly, if $m\in \tilde{g}(n, \varphi_T)$ then $f(n,\ulcorner T\urcorner)=m$.

This shows that $\tilde{g}(n,\varphi)$ has size at most $1$ for any recursive $\varphi$, in particular any finite $\varphi$. By Rice-Shapiro for $\mathcal R_{\tilde{\eta}}$, this is true for any $\varphi\in\mathcal P$. Hence $\tilde{g}$ indeed induces a deterministic $g$.

Suppose $f\colon\mathbb N^2\rightarrow\mathbb N$ is recursive and code invariant for total functions. Then there is some $g\in\mathbb R_\ast$ so that $$f(n,\ulcorner T\urcorner)=g(n,\varphi_T)$$ for all $n$ and Turing machines $T$ so that $\varphi_T$ is total.

Suppose $f\colon \mathbb N^2\rightarrow N$ is recursive and code invariant for total functions. Then there is a fully code invariant recursive $g\colon\mathbb N^2\rightarrow\mathbb N$ so that $$f(n,\ulcorner T\urcorner)=g(n,\ulcorner T\urcorner)$$ for all $n$ and Turing machines $T$ so that $\varphi_T$ is total.

We may assume that $f$ is fully code invariant. We can now argue as in the proof of equivalence of $\mathcal I$ and $\mathrm{R}_{\tilde{\eta}}^{\mathrm{det}}$ and, borrowing some notation from that proof, replace the use of the $\tilde{\eta}$-operation with a standard $\mu$-recursion and simply search for some $k$ so that $h(k, n,\varphi)$ halts. Given the promise that $\varphi$ is total, this works as intended: the only reason $h(k, n, \varphi)$ may not halt is that $f(n, \ulcorner S\urcorner)$ is not defined (where $S$ is the Turing machine constructed from $k$ and $\varphi$). But we can simulate that computation step-by-step.

Let $\mathcal F_0$ be the collection of partial recursive $f\colon\mathbb N\rightarrow\mathbb N$ with $0\in\mathrm{dom}(f)$. There is a recursive universal function for $\mathcal F_0$.

Given $n$, split $n$ reasonably into $k, l\in\mathbb N$. Then define $U_n(0)=k$ and $U_n(m+1)=\varphi_l(m)$ where $\varphi_l$ is the $l$-th recursive function.

$\mathcal R_M$ is the smallest family $\mathcal F$ satisfying $(1)+(3)$ from the definition of $\mathcal R_\ast$ with $M\in\mathcal F$.

$\mathcal I$ is equivalent to $\mathcal R_M$.

We will only argue that $\mathcal I$ is reducible to $\mathcal R_M$. So let $f\in\mathcal I$. Fix a recursive map $k\mapsto T_k$ so that $\varphi_{T_k}=s_k$. Run a program which on input $n$, computes $f(n, \ulcorner T_m\urcorner)$ for all $m$ simultaneously. Let $g(n, m)$ be the first $k$ which is found so that $f(n, \ulcorner T_k\urcorner)$ is defined and $\{s_{g(n, 0)},\dots, s_{g(n, m-1)}, s_k\}$ is an antichain. So $\lambda m. g(n, m)$ enumerates some antichain $\vec a^{h(n)}$. If done carefully, we can assume that $h$ is recursive.

We will now define a computation $F$ within $\mathcal R_M$. To figure out $F(n, \varphi)$, first compute $k=M(h(n), \varphi)$. Then return $f(n, T_{\vec a^{h(n)}_k})$. Similarly as before, we see that $$f(n, \ulcorner T\urcorner)=F(n, \varphi_T)$$ for all $n$ and Turing machines $T$ using the Rice-Shapiro theorem.

There is a recursive universal function for $\mathcal I$.

Construct a Turing machine which on input $k, n, \ulcorner T\urcorner$ simulates the $k$-th computation in $\mathcal R_M$ with input $n, \varphi_T$.

(The halting problem for $\mathcal R_{\tilde{\eta}}^{\mathrm{det}}$) There is no total $g\in\mathcal R_{\tilde{\eta}}^{\mathrm{det}}$, $g\colon\mathcal P\rightarrow\mathbb N$ so that $g(\varphi)=0$ iff $0\in\mathrm{dom}(\varphi)$.

By $(1)$ of Rice-Shapiro for $\mathcal R_{\tilde{\eta}}^{\mathrm{det}}$, $g(\emptyset)=g(\varphi)$ for all $\varphi\in\mathcal P$.