Skip to main content
MathOverflow

Return to Question

prevent \downarrow from being musformatted as a binary relation symbol
Source Link
Emil Jeřábek
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

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 $$$$ (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$$\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 $$$$ 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$$\varphi_e(n){\downarrow}$, and $0$ otherwise.

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.

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.

fix typo + give an even more intuitive version of what the anti-halting oracle does
Source Link
Gro-Tsen
Gro-Tsen
  • 32.4k
  • 5
  • 86
  • 372

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 = \top$$\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.)

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 = \top$, 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.)

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

Source Link
Gro-Tsen
Gro-Tsen
  • 32.4k
  • 5
  • 86
  • 372

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

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 = \top$, 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.)

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.