What is the power of the “anti-halting” oracle?

Question

Let me first ask the question, and then, as it may seem a bit cryptic, explain how it comes up (and whence the “anti-halting oracle” in the title):

Notations: we write $\langle m,n\rangle$ for a standard (p.r.) coding of pairs of natural numbers by natural numbers; we also write $\varphi_e(n)$ for the value (possibly undefined) of the $e$-th partial computable function with the argument $n$, and more generally $\varphi_e^{\mathscr{A}}(n)$ for the value of the $e$-th partial computable functional in a function $\mathscr{A}\colon \mathbb{N}\to\mathbb{N}$ used as a (Turing) oracle; also, let $u$ be the code for some universal oracle Turing machine, that is, $\varphi_u^{\mathscr{A}}(\langle e,n\rangle) \simeq \varphi_e^{\mathscr{A}}(n)$ (for any $\mathscr{A}$).

For $A, B$ two subsets of $\mathbb{N}$, define: $$ (A \sqcup B) := \lbrace\langle 0,m\rangle : m\in A\rbrace \cup \lbrace\langle 1,n\rangle : n\in B\rbrace $$ and $$ (A \Rrightarrow B) := \lbrace p\in \mathbb{N} : \forall m\in A.(\varphi_p(m){\downarrow} \in B)\rbrace $$ (where “$\varphi_p(m){\downarrow} \in B$” means, of course, that $\varphi_p(m)$ is defined and belongs to $B$).

Also define, for $A \subseteq \mathbb{N}$: $$ H_0(A) := \lbrace m\in \mathbb{N} : \varphi_u^{\mathscr{H}}(m){\downarrow} \in A \rbrace $$ where $\mathscr{H}$ is the halting problem, i.e., $\mathscr{H}(\langle e,n\rangle) = 1$ if $\varphi_e(n){\downarrow}$, and $0$ otherwise.

Finally, we define two more functions $H_1,H_2$ from $\mathscr{P}(\mathbb{N})$ to $\mathscr{P}(\mathbb{N})$ as follows: $$ H_1(B) := \bigcap_{A \subseteq \mathbb{N}} (H_0(A) \Rrightarrow (A \sqcup B)) $$ $$ H_2(C) := \bigcap_{B \subseteq \mathbb{N}} (H_1(B) \Rrightarrow (B \sqcup C)) $$

THE QUESTION: is one of the following two sets of natural numbers inhabited? (Note: I'm just using “inhabited” to mean “nonempty” here: the question is asked in classical logic.) $$ K_1 := H_2(\varnothing) = \bigcap_{B\subseteq \mathbb{N}} (H_1(B) \Rrightarrow B) $$ $$ K_2 := \bigcap_{C\subseteq \mathbb{N}} (H_2(C) \Rrightarrow H_0(C)) $$

Remarks: as a sanity check, note that the sets $\bigcap_{B\subseteq \mathbb{N}} (B \Rrightarrow H_1(B))$ and $\bigcap_{C\subseteq \mathbb{N}} (H_0(C) \Rrightarrow H_2(C))$ (arrow reversed) are indeed inhabited. Also note that since $K_1 = H_2(\varnothing)$, if $K_2$ is inhabited, then $(H_2(\varnothing) \Rrightarrow H_0(\varnothing)) = (K_1 \Rrightarrow \varnothing)$ is, so $K_1$ is empty: in other words, at most one of $K_1$ and $K_2$ can be inhabited. As another sanity check, note that $H_1(\varnothing) = \varnothing$ (which is one possible way to witness the fact that the halting problem is not computable).

(It would not at all surprise me if the question had a totally obvious answer, which I missed, and that I've been misled and confused by how I came up with the question in not seeing this obvious answer. So maybe it's best to not read the following motivation?)

---

Possible intuition: given a “problem” $P\subseteq\mathbb{N}$ (that is, the problem consists of finding an element of $P$), the set $H_0(P)$ is the set of “solutions with the help of the halting problem oracle”, while the set $H_1(P)$ consists of some sort of “witnesses of the uselessness of having access to the halting problem oracle in trying to find a solution to $P$”, which describes a kind of “anti-halting” oracle (see below for the generalized notion of “oracle”), and $H_2(P)$ describes a kind of anti-anti-halting oracle.

Motivation for asking this question: I am trying to wrap my mind around the ideas in two papers by Takayuki Kihara, “Lawvere-Tierney topologies for computability theorists” and “Rethinking the notion of oracle”, which provides a link between a generalized notion of oracle (an extended Turing-Weihrauch reducibility, of sorts) and Lawvere-Tierney topologies on the effective topos.

Specifically, the map $H_0\colon \mathscr{P}(\mathbb{N}) \to \mathscr{P}(\mathbb{N})$ defined above from the halting problem can be seen as a Lawvere-Tierney topology $h_0 \colon \Omega\to\Omega$ in the effective topos (where $\Omega$ is its object of truth values), or, if we want, a (globally defined) element of the frame $N(\Omega)$ which is the dissolution of $\Omega$. The maps $H_1$ and $H_2$ correspondingly define Lawvere-Tierney topologies $h_1,h_2$ which are respectively $\neg h_0$ and $\neg\neg h_0$ in the frame $N(\Omega)$ (see here for the computation of the Heyting operation, and in particular the pseudocomplement $\neg j$, in $N(\Omega)$). So my question is whether $\neg h_0 = \bot$, on the one hand (this is saying that $K_1$ is inhabited), and whether $\neg\neg h_0 = h_0$ on the other (this is saying that $K_2$ is inhabited; clearly both cannot hold); or, to state it differently, whether $h_0$ is either dense or regular in the frame $N(\Omega)$ of Lawvere-Tierney topologies on the effective topos.

The “anti-halting oracle” itself is (a “bilayer function” in the terminology used by the first aforequoted paper of Kihara, an “extended Weihrauch predicate” in the terminology of the second) the partial multivalued function $H_1^{\leftarrow}$ on $\mathbb{N} \times \mathscr{P}(\mathbb{N})$ with values in $\mathbb{N}$ which is defined on $(n,B)$ when $n \in H_1(B)$, and whose values there are precisely the elements of $B$. (In more intuitive terms, to query the “anti-halting oracle”, you (“Arthur” in Kihara's terminology) provide an element $n \in H_1(B)$ for some $B$, the oracle (“Nimuë”) guesses which $B$ you want to ask about, and (“Merlin”) returns some element of it. In even more intuitive terms, the “anti-halting” oracle is willing to answer any question whatsoever ($B$) provided you provide it with a witness $n \in H_1(B)$ that the halting oracle is of no use to you.)

Saying that $K_1$ is inhabited means that the “anti-halting oracle” is worthless. Saying that $K_2$ is inhabited means it is maximally useful (and the “anti-anti-halting oracle” $H_2^{\leftarrow}$ has no more power than the halting oracle).

---

Final remark: I used the halting problem $\mathscr{H}$ in the above question, not because I am specifically interested in it but because it seems like the simplest nontrivial one we can ask about (of course if we replace $\mathscr{H}$ by a computable function, then $H_1(\varnothing)$ is inhabited, and so is $K_2$, for trivial reasons). If, however, an answer can be easily given with some other well-defined noncomputable function instead of $\mathscr{H}$, then I will be happy with it.

Answer 1

The set $K_1 := \bigcap_{B\subseteq\mathbb{N}} (H_1(B) \Rrightarrow B)$ is inhabited, that is, the “anti-halting oracle” is trivial, i.e., can be simulated with a Turing machine (consequently, as explained in the question, $K_2 = \varnothing$). Here is a discussion trying to make the question a bit more palatable, and then a proof.

Discussion: An element $H_0(A)$ is an $\langle e,n\rangle$ such that $\varphi_e^{\mathscr{H}}(n){\downarrow} \in A$, i.e., a code for a Turing machine $e$ with access to the halting oracle $\mathscr{H}$ and an input $n$ to that machine, such that $e$ halts on $n$ with a return value $k := \varphi_e^{\mathscr{H}}(n){\downarrow}$ in $A$. Now $H_1(B) := \bigcap_{A\subseteq\mathbb{N}} (H_0(A) \Rrightarrow (A\sqcup B))$ in fact equals $\bigcap_{k\in\mathbb{N}} (H_0(\lbrace k\rbrace) \Rrightarrow (\lbrace k\rbrace\sqcup B))$ as is easy to see (one inclusion is trivial, and the other follows from the fact that $H_0(A) = \bigcup_{k\in A} H_0(\lbrace k\rbrace)$). In other words, an element $f$ of $H_1(B)$ is a program that takes as input an $\langle e,n\rangle$ such that $\varphi_e^{\mathscr{H}}(n){\downarrow}$ and must return either (“success”) the pair $\langle 0,k\rangle$ with $k := \varphi_e^{\mathscr{H}}(n)$ or (“failure”) a pair $\langle 1,\ell\rangle$ with $\ell\in B$. Our goal (in algorithmically implementing the “anti-halting oracle”) is to produce an element $g$ of $\bigcap_{B\subseteq\mathbb{N}} (H_1(B) \Rrightarrow B)$, in other words this $g$ takes as input such an $f$ and must exhibit one of its failures. The proof is a fairly straightforward variation on the standard argument showing that the halting problem is not computable and that we can actually generate failure of a candidate for solving it.

Proof of the fact that $\bigcap_{B\subseteq\mathbb{N}} (H_1(B) \Rrightarrow B)$ is inhabited:

We construct a program $g$ as follows. It takes $f$ as input (which is supposed to be in $H_1(B)$, for some $B$, and we are supposed to return an element of $B$).

Using $f$, we construct $\langle e,n\rangle$ as follows. Thanks to a standard argument using Kleene's (“amazing”) second recursion theorem, we can assume $\langle e,n\rangle$ has access to $\langle e,n\rangle$ in its own code.

The program $e$ proceeds as follows. First, it asks its oracle (which is intended to be $\mathscr{H}$) whether $f$ terminates on input $\langle e,n\rangle$ (i.e., whether $\varphi_f(\langle e,n\rangle){\downarrow}$). If so, it simulates the execution of $f$ on $\langle e,n\rangle$. If the result $\varphi_f(\langle e,n\rangle)$ is $\langle 0,k_0\rangle$, it returns $k_0+1$. In all other cases (including when the oracle replied that $f$ does not terminate on $\langle e,n\rangle$), it returns $0$.

This construction ensures that $\varphi_e^{\mathscr{H}}(n){\downarrow}$, and that if we let $k := \varphi_e^{\mathscr{H}}(n)$ we cannot have $\varphi_f(\langle e,n\rangle){\downarrow} = \langle 0,k\rangle$. But since $f \in \bigcap_{k\in\mathbb{N}} (H_0(\lbrace k\rbrace) \Rrightarrow (\lbrace k\rbrace\sqcup B))$, we must have $\varphi_f(\langle e,n\rangle){\downarrow}$ and by what has just been said, its value is necessarily of the form $\langle 1,\ell\rangle$ with $\ell \in B$.

Now the program $g$ proceeds as follows (having constructed $\langle e,n\rangle$ as described above). It simulates the execution of $f$ on $\langle e,n\rangle$: by what has just been said, the execution terminates and the result is necessarily of the form $\langle 1,\ell\rangle$ with $\ell \in B$, and we return the value $\ell$. Thus we have $g \in (H_1(B) \Rrightarrow B)$ for whatever $B$ was (which was not used in the construction, so $g$ is in $K_1$). ∎