Diagonally non-computable functions

($\Rightarrow$) Let $g \leq_T X$ be DNC. By the parameter form of SMN (Parameter form), there is a total computable function $q$ such that $\Phi_{q(n, v)}$ is the function defined only at the input $n$, with value $v$. Let $f(n) = q(n, g(n))$; it is $X$-computable. If $\Phi_{f(n)} = \Phi_n$ for some $n$, then $\Phi_n(n)\converge = \Phi_{f(n)}(n) = g(n)$, contradicting the fact that $g$ is DNC. So $f$ is fixed-point free.

($\Leftarrow$) Let $f \leq_T X$ be fixed-point free. By SMN, there is a total computable function $d$ such that the program $d(n)$, on input $m$, computes $\Phi_n(n)$ and, if this converges with value $v$, runs $\Phi_v(m)$. So $\Phi_{d(n)} = \Phi_{\Phi_n(n)}$ when $\Phi_n(n)\converge$. Let $g(n) = f(d(n))$; it is $X$-computable and total, since it does not run the computation $\Phi_n(n)$. If $g(n) = \Phi_n(n)$ for some $n$ with $\Phi_n(n)\converge$, then $\Phi_{f(d(n))} = \Phi_{\Phi_n(n)} = \Phi_{d(n)}$, contradicting the fact that $f$ is fixed-point free. So $g$ is DNC.

Let $\langle k_0, \dots, k_{n-1} \rangle$ denote a computable bijection between $\nat^n$ and $\nat$, uniform in $n \geq 1$.

(1 ⇒ 2) Let $f \leq_T X$ be DNC. By SMN, there is a total computable function $u$ such that the program $u(e, n, i)$, for $i < n$, on any input, waits for the $i$-th element $k$ enumerated into $W_e$ (counting from $0$), and if it appears, outputs the $i$-th component $k_i$ of the tuple $k = \langle k_0, \dots, k_{n-1} \rangle$; otherwise it diverges. For $n \geq 1$, let

and $h(e, 0) = 0$. It is $X$-computable. Suppose that $|W_e| \leq n$ and $h(e, n) \in W_e$. Then $n \geq 1$, and $h(e, n)$ is the $i$-th element enumerated into $W_e$ for some $i < n$. So the program $u(e, n, i)$, on input $u(e, n, i)$, outputs the $i$-th component of $h(e, n)$, which is $f(u(e, n, i))$. This contradicts the fact that $f$ is DNC.

(2 ⇒ 3) Let $h \leq_T X$ be as in (2). Let $\gamma$ be the partial computable function such that $\gamma(e)$ is the canonical index of the set of the first $e + 1$ elements enumerated into $W_e$, defined if and only if $|W_e| \geq e + 1$. We build an $X$-computable strictly increasing sequence $x_0 < x_1 < \cdots$ such that, for every $s$,

Suppose that $x_0, \dots, x_{s-1}$ are defined, for some $s \geq 0$. By SMN, uniformly in $s$ and in the finite sequence $x_0, \dots, x_{s-1}$, one computes an index $v$ with

where the first part is empty for $s = 0$. This set has at most $n_s = (x_{s-1} + 1) + \sum_{e \leq s} (e + 1)$ elements, a number computable from $s$ and $x_{s-1}$. Let $x_s = h(v, n_s)$; then $x_s \notin W_v$. So $x_s > x_{s-1}$, and $x_s \notin D_{\gamma(e)}$ for every $e \leq s$ with $\gamma(e)\converge$.

We check $(\star_s)$. Let $e \leq s$ with $\gamma(e)\converge$. If $e < s$, by $(\star_{s-1})$ some element of $D_{\gamma(e)}$ is not among $x_0, \dots, x_{s-1}$, and it is not $x_s$ either, since $x_s \notin D_{\gamma(e)}$. If $e = s$, the set $D_{\gamma(s)}$ has $s + 1$ elements and does not contain $x_s$; it cannot be contained in the $s$-element set $\{ x_0, \dots, x_{s-1} \}$.

Let $H = \{ x_s : s \in \nat \}$; it is infinite and $X$-computable, since the sequence is increasing. If $W_e \subseteq H$ and $|W_e| \geq e + 1$, then $\gamma(e)\converge$ and $D_{\gamma(e)} \subseteq H$ is finite, so $D_{\gamma(e)} \subseteq \{ x_0, \dots, x_s \}$ for some $s \geq e$, contradicting $(\star_s)$. So $|W_e| \leq e$ whenever $W_e \subseteq H$: $H$ is effectively immune, with $q(e) = e$.

(3 ⇒ 1) Let $H \leq_T X$ be effectively immune, with bound $q$. By SMN, there is a total computable $k$ with $W_{k(n)} = D_n$. Let $f(e) = k(c(e))$, where $c(e)$ is the canonical index of the set of the first $q(e) + 1$ elements of $H$; $f$ is $X$-computable. If $W_{f(e)} = W_e$, then $W_e$ is a subset of $H$ with $q(e) + 1$ elements, contradicting the choice of $q$. So $W_{f(e)} \neq W_e$, hence $\Phi_{f(e)} \neq \Phi_e$ for every $e$: $f$ is fixed-point free, and $X$ computes a DNC function by Theorem 3.2.

If $A \equiv_T \emptyset'$, it computes a DNC function. Conversely, let $A$ be c.e., with a c.e. approximation $(A_s)$, and suppose that $A$ computes a DNC function. By Theorem 3.2, there is a functional $\Phi_i$ such that $f = \Phi^A_i$ is total and fixed-point free. Let $f_s(x) = \Phi^{A_s}_i(x)[s]$ if this computation converges, and $f_s(x) = 0$ otherwise; the function $(s, x) \mapsto f_s(x)$ is computable. Let $\emptyset'_t$ be the set of $n \leq t$ with $\Phi_n(n)[t]\converge$.

By SMN, there is a total computable function $r$ such that the program $r(n, x)$, on input $m$, searches for the least $t$ with $n \in \emptyset'_t$ and, if it finds one, runs $\Phi_{f_t(x)}(m)$. By the fixed point theorem with parameters (Fixed point theorem with parameters), there is a total computable function $p$ with $\Phi_{p(n)} = \Phi_{r(n, p(n))}$ for every $n$.

With oracle $A$, compute for each $n$ the least stage $s(n)$ such that $\Phi^{A_s}_i(p(n))[s]$ converges, with use $u$, and $A_s \uh u = A \uh u$, for $s = s(n)$. Such a stage exists, since $f(p(n))$ is defined and $A_s \uh u$ eventually equals $A \uh u$; and the condition is decided by $A$. Since $A$ is c.e., $A_t \uh u = A \uh u$ for every $t \geq s(n)$, so the same computation gives $f_t(p(n)) = f(p(n))$ for every $t \geq s(n)$.

We claim that $n \in \emptyset'$ if and only if $n \in \emptyset'_{s(n)}$, which shows $\emptyset' \leq_T A$. Suppose that $n \in \emptyset'$, and let $t$ be the least stage with $n \in \emptyset'_t$. If $t > s(n)$, then the program $r(n, p(n))$ runs $\Phi_{f_t(p(n))} = \Phi_{f(p(n))}$, so $\Phi_{p(n)} = \Phi_{r(n, p(n))} = \Phi_{f(p(n))}$, contradicting the fact that $f$ is fixed-point free. So $t \leq s(n)$, and $n \in \emptyset'_{s(n)}$, since $\emptyset'_t \subseteq \emptyset'_{s(n)}$. Conversely, $\emptyset'_{s(n)} \subseteq \emptyset'$.

1. A PA set computes a DNC function.
2. If $A$ is effectively simple, then $A$ computes its complement, which is effectively immune; by Theorem 3.4, $A$ computes a DNC function, and Theorem 3.5 applies.
3. A low simple set exists (Theorem 3.1 of “A low simple set”). Its complement is immune; if it were effectively immune, the set would be complete by 2, hence not low.