Multibit reflective oracles

[Benya_Fallenstein]

This post describes a new version of the reflective oracles I described in a previous forum post. This work extends probabilistic Turing machines with an oracle that answers certain kinds of queries about other probabilistic Turing machines with the same kind of oracle; straight-forward ways of doing this would lead to diagonalization problems, which this kind of oracle avoids by answering certain queries probabilistically. Applications include a variant of AIXI that is able to reason about universes containing other instances of the same variant of AIXI; I expect we’ll have forum posts about this in the coming weeks.

The new version, which is based on this comment thread with Paul, is significantly simpler to use than the previous version: The previous version only gave useful answers about machines that halt with probability one, no matter how the oracle behaves. The new version basically just doesn’t have an analogous requirement. In addition, the new version allows for queries about machines that output more than a single bit; it turns out that this makes it much simpler to define simplicity priors of the kind used in AIXI, doing away with most of the complexity I described in “Simplicity priors with reflective oracles”.

This is still a fairly technical post, whose purpose is to help with figuring out the details of a nice version reflective oracles and of their applications. At some point in the future when all of this has stabilized more, I expect to write a more introductory post on these topics.

ETA: Thanks to Matt Elder, who helped me think through the details of this system! I wrote the original post pretty quickly and forgot to acknowledge this, mea culpa.

---

Let’s write $B:=\{0,1\}$ for the set of bits, $B^{<\omega }$ for the set of finite bitstrings, and $B^{\omega }$ for the set of infinite streams of bits; further, let’s write $\epsilon$ for the empty bitstring. Then $\Delta \left(B\right)$ is the set of probability distributions over single bits, which we can represent by a single number in $[0,1]$, specifying the probability that the bit is $1$; that is, we can think of $\Delta \left(B\right)$ as the set $[0,1]$. Moreover, $\Delta \left(B^{\omega }\right)$ is the set of probability distributions over infinite bitstreams, which we can represent by functions $P:B^{<\omega }\to [0,1]$, where $P\left(\overline{x}\right)$ represents the probability that the infinite bitstream starts with the finite bitstring $\overline{x}$, such that $P\left(\epsilon \right)=1$ (every bitstream starts with the empty bitstring), and $P\left(\overline{x}\right)=P\left(\overline{x}0\right)+P\left(\overline{x}1\right)$, $\forall \overline{x}\in B^{<\omega }$. In other words, we can think of $\Delta \left(B^{\omega }\right)$ as the set of all functions $P:B^{<\omega }\to [0,1]$ which satisfy these two conditions.

Let’s also write $P:=Q\cap [0,1]$ for the set of probabilities that are rational numbers, and $M\subseteq N$ for the set of all Gödel numbers of probabilistic Turing machines that can make calls to a probabilistic oracle (i.e., to an oracle that may answer some queries probabilistically). We will consider machines with advance-only binary output tapes—that is, the machine has instructions to write a $0$ or a $1$ on its output tape, and no way of going back and deleting something it has written; thus, a machine’s output is either an element of $B^{<\omega }$ (if the machine halts at some point, or runs forever but stops producing output after a finite amount of time), or an element of $B^{\omega }$ (if the machine keeps producing output).

---

A query to the oracle is a triple $(┌M┐,\overline{x},q)\in (M\times B^{<\omega }\times P)$, roughly interpreted as asking whether the probability that the output of the oracle machine $M$ starts with $\overline{x}$ is greater than $q$. The output of the oracle is a single bit, which, on some queries, may be chosen randomly: If $M$ definitely produces at least $len\left(\overline{x}\right)$ bits of output, and $q$ is greater than the probability that the output starts with $\overline{x}$, the oracle definitely outputs $1$; if $q$ is smaller, it definitely outputs $0$; if it is equal, the oracle’s output may be random, with the probability of outputting $1$ anywhere in $[0,1]$. (This is crucial for getting around diagonalization.) If $M$ isn’t guaranteed to produce at least $len\left(\overline{x}\right)$ bits of output, then see below.

In the new formulation, an oracle $O$ is a pair of functions, $O=(O_{query},O_{eval})$. The first of these, $O_{query}:M\times B^{<\omega }\times P\to \Delta \left(B\right)$, specifies the behavior of the oracle: $O_{query}(┌M┐,\overline{x},q)$ is the probability that the oracle outputs $1$ when called on the query $(┌M┐,\overline{x},q)$.

The second function has to do with what happens when we query the oracle about machines which aren’t guaranteed to produce $len\left(\overline{x}\right)$ bits. In an intuitive sense, the idea is that we pretend that every machine always produces an infinite bitstream, even if in reality, the machine goes into an infinite loop after producing only a finite output; in this case, we choose some arbitrary probability distribution over the “output” we pretend the machine produces after this point. The function $O_{eval}:M\to \Delta \left(B^{\omega }\right)$ specifies the resulting probability distribution over infinite bitstreams; that is, $O_{eval}(┌M┐)$ is the distribution that the oracle pretends the machine $M$ produces. Since we represent elements of $\Delta \left(B^{\omega }\right)$ as functions from $B^{<\omega }$ to $[0,1]$, this means that $O_{eval}(┌M┐)\left(\overline{x}\right)$ is what our oracle pretends is the probability that $M$’s output starts with $\overline{x}$. In particular, if $q>O_{eval}(┌M┐)\left(\overline{x}\right)$, then invoking the oracle on $(┌M┐,\overline{x},q)$ will definitely output $1$, i.e., then $O_{query}(┌M┐,\overline{x},q)=1$; and if $q<O_{eval}(┌M┐)\left(\overline{x}\right)$, then $O_{query}(┌M┐,\overline{x},q)=0$.

The intuition for $O_{eval}(┌M┐)$ is that it should only “fill in” probabilities when actually running $M$ stops generating any output; as long as $M$ keeps generating output, the distribution $O_{eval}(┌M┐)$ should reflect this. We can formalize this by the condition that for any bitstring $\overline{x}\in B^{<\omega }$, the probability $O_{eval}(┌M┐)\left(\overline{x}\right)$ should be greater or equal to the probability that $M$ outputs $\overline{x}$ given that calls to the oracle behave according to $O_{query}$.

At the end of this post, I’ll show that a pair $O=(O_{query},O_{eval})$ satisfying these conditions does in fact exist.

---

First, though, let me give you an indication about why it seems useful to move from single-bit to multi-bit oracles. I should say, first of all, that they aren’t actually more powerful than single-bit oracles—Marcello has shown that you can construct a multi-bit oracle given an oracle that works as described above, but allows only for single-bit queries—but it’s not as easy as you might think; Marcello’s construction uses three different tricks which you’d need to wrap your head around first. It seems easier to define the multi-bit oracle directly.

The place where multi-bit oracles are useful is when you want to define a simplicity prior, as in Solomonoff induction. In the reflective oracle setting, the natural way of doing so is to define a universal prior over bitstrings as an oracle machine that samples the Gödel number of another machine $M^{\prime }$ with probability proportional to $2^{-\text{source code length}}$, and then just runs $M^{\prime }$. We’d then like to use our oracle to answer queries about the resulting distribution over bitstrings. However, like in the case of Solomonoff induction, we will need to deal with the fact that not all machines $M^{\prime }$ produce an infinite amount of output. It would be nice if we could just check whether a given $M^{\prime }$ eventually loops, and don’t run it if it does, but we won’t be able to define an oracle that lets us do so (for machines with access to the same oracle), because of the halting problem: otherwise, we could write an $M^{\prime }$ that asks the oracle whether it goes into an infinite loop, and does so iff the oracle says it doesn’t.

I’ve previously described a bag of tricks for solving this problem in the context of my original definition of reflective oracles, but with the definition given above, the problem becomes trivial: We just define our simplicity prior as a machine $M$ that samples an arbitrary $M^{\prime }$ and runs it, and then use our oracle on $M$ to give us a corresponding distribution over infinite bitstreams. If the $M^{\prime }$ we sample fails to output an infinite stream of bits, our oracle will fill in the probabilities arbitrarily, so we get a consistent distribution over infinite bitstreams. And we still have the essential property we expect of a simplicity prior: For any machine $M^{\prime }$, there is a constant $C>0$ such that $O_{eval}(┌M┐)\left(\overline{x}\right)$ is lower-bounded by $C$ times the probability that $M^{\prime }$ outputs $\overline{x}$.

---

Before giving the existence proof, I’ll give a more formal definition of the conditions we place on $O_{query}$ and $O_{eval}$.

In order to state these conditions, it will be helpful to assume that machines $┌M┐\in M$ are specified in a way which includes the current state of their working tapes: Thus, we can run a machine $M$ for a single step and describe its next state as a new machine $M^{\prime }$. (In other words, elements of $M$ are really machine states.) Then, we can describe every machine by its behavior when running it for a single timestep: Either it executes a single deterministic computation, leading a new machine state $N$, which we write as $step(┌N┐)$; or it outputs a single bit $x\in B$ and transitions to state $N$, which we write as $output(x,┌N┐)$; or it queries the oracle on some triple $(┌M┐,\overline{x},q)$, and transitions into state $N$ or $N^{\prime }$ depending on the answer, which we write as $query(┌M┐,\overline{x},q,┌N┐,┌N^{\prime }┐)$; or it flips a fair coin and transitions to $N$ or $N^{\prime }$ depending on the result, which we write as $flip(┌N┐,┌N^{\prime }┐)$. In a slight abuse of notation, we’ll write things like $O_{eval}\left(step\right(┌N┐\left)\right)$, which is really supposed to mean ”$O_{eval}(┌M┐)$ for any state $M$ in the set described by $step(┌N┐)$”.

An oracle is a pair $O=(O_{query},O_{eval})$, where $O_{query}:M\times B^{<\omega }\times P\to \Delta \left(B\right)$ and $O_{eval}:M\to \Delta \left(B^{\omega }\right)$. We now define a notion of an oracle $O^{\prime }$ “reflecting” another oracle $O$; an oracle is reflective if it reflects itself. An oracle $O^{\prime }=(O_{query}^{\prime },O_{eval}^{\prime })$ reflects an oracle $O$ if the following conditions are satisfied:

• If $q>O_{eval}(┌M┐)\left(\overline{x}\right)$, then $O_{query}^{\prime }(┌M┐,\overline{x},q)=1$.

• If $q<O_{eval}(┌M┐)\left(\overline{x}\right)$, then $O_{query}^{\prime }(┌M┐,\overline{x},q)=0$.

• $O_{eval}^{\prime }\left(step\right(┌N┐\left)\right)=O_{eval}(┌N┐)$.

• $O_{eval}^{\prime }\left(output\right(x,┌N┐\left)\right)\left(x\overline{y}\right)=O_{eval}(┌N┐)\left(\overline{y}\right)$.

• $O_{eval}^{\prime }\left(output\right(x,┌N┐\left)\right)\left(\right(1-x\left)\overline{y}\right)=0$.

• $O_{eval}^{\prime }\left(flip\right(┌N┐,┌N^{\prime }┐\left)\right)=\frac{1}{2}{O}_{eval}(┌N┐)+\frac{1}{2}{O}_{eval}(┌N^{\prime }┐)$ .

• $O_{eval}^{\prime }\left(query\right(┌M┐,\overline{x},q,┌N┐,┌N^{\prime }┐\left)\right)$ $=$ $(1-O_{query}(┌M┐,\overline{x},q\left)\right)\cdot O_{eval}(┌N┐)$ $+$ $O_{query}(┌M┐,\overline{x},q)\cdot O_{eval}(┌N^{\prime }┐)$.

The first two of these conditions just write out in symbols what I earlier said in words. The latter five conditions imply the demand that $O_{eval}(┌M┐)\left(\overline{x}\right)$ must be lower-bounded by the probability that $M$ returns $\overline{x}$ if oracle calls behave according to $O_{query}$, but this isn’t quite as obvious. The proof is to show by induction on $T\in N$ that for all $M$ and $\overline{x}$, $O_{eval}(┌M┐,\overline{x})$ is $\ge$ the probability that $M$ outputs $\overline{x}$ within the next $T$ timesteps. I’ll omit the details here.

---

As in my previous posts about versions of this system, I’ll actually prove a slightly stronger result, which I expect will be helpful in showing a relation between reflective oracles and Nash equilibria. This makes use of the notion of a partial oracle, which is a pair of partial functions $\pi =({\pi }_{query},{\pi }_{eval})$, ${\pi }_{query}:M\times B^{<\omega }\times P\nrightarrow \Delta \left(B\right)$ and ${\pi }_{eval}:M\times B^{<\omega }\nrightarrow [0,1]$, which specify the values that $O_{query}$ and $O_{eval}$ should take on certain inputs. An oracle extends a partial oracle if $O_{query}(┌M┐,\overline{x},q)={\pi }_{query}(┌M┐,\overline{x},q)$ and $O_{eval}(┌M┐)\left(\overline{x}\right)={\pi }_{eval}(┌M┐,\overline{x})$ whenever the right-hand side of these equations is defined. We call a partial oracle $\pi$ reflective if for every $O$ extending $\pi$, there is an $O^{\prime }$, also extending $\pi$, which reflects $O$.

Theorem.

i. There is a reflective oracle $O$. ii. For every reflective partial oracle $\pi$, there is a reflective oracle $O$ extending $\pi$.

Proof. We begin by showing that the empty partial oracle ${\pi }^{\varnothing }$ (i.e., the partial oracle satisfying $dom\left({\pi }_{query}^{\varnothing }\right)=\varnothing$ and $dom\left({\pi }_{eval}^{\varnothing }\right)=\varnothing$) is reflective, since (i) then follows from (ii). Thus, let $O$ be any oracle (since every oracle extends ${\pi }_{\varnothing }$), and define $O^{\prime }$ as follows: If $q>O_{eval}(┌M┐)\left(\overline{x}\right)$, let $O_{query}^{\prime }(┌M┐,\overline{x},q)=1$; else, let $O_{query}^{\prime }(┌M┐,\overline{x},q)=0$. Define $O_{eval}^{\prime }$ by the equations in the definition of ”$O^{\prime }$ reflects $O$”. Then, $O^{\prime }$ clearly both reflects $O$ and (trivially) extends ${\pi }^{\varnothing }$. This finishes the proof that ${\pi }^{\varnothing }$ is a reflective partial oracle.

It remains to show (ii). For this, we use the infinite-dimensional generalization of Kakutani’s fixed point theorem:

Suppose that $A$ is a non-empty, convex and compact subset of a locally convex topological vector space. Suppose further that $f:A\to Pow\left(A\right)$ is a set-valued function such that $f\left(x\right)$ is non-empty, convex and compact for all $x\in A$, and such that the graph of $f$, $$\left\{\right(x,y):x\in A,y\in f(x\left)\right\},$$ is a closed set. Then $f$ has a fixed point; that is, there is an $x\in A$ such that $x\in f\left(x\right)$.

Let $A$ be the set of all oracles. We can see this as a subset of $[0,1{]}^{M\times B^{<\omega }\times P}\times [0,1{]}^{M\times B^{<\omega }}$, which in turn is a subset of $R^{M\times B^{<\omega }\times P}\times R^{M\times B^{<\omega }}$, which is a locally convex topological vector space when endowed with the product topology (since this is true of any power of $R$). $A$ consists of all elements $(O_{query},O_{eval})$ of $[0,1{]}^{M\times B^{<\omega }\times P}\times [0,1{]}^{M\times B^{<\omega }}$ such that $g$ satisfies the additivity properties we demand of elements of $\Delta \left(B^{<\omega }\right)$, namely $O_{eval}(┌M┐)\left(ϵ\right)=1$ and $O_{eval}(┌M┐)\left(\overline{x}0\right)+O_{eval}(┌M┐)\left(\overline{x}1\right)=O_{eval}(┌M┐)\left(\overline{x}\right)$. Clearly, $A$ is nonempty, convex, and closed, and it is a subset of a product of $[0,1]$, which, by Tychonoff’s theorem, is compact. Moreover, both $M\times B^{<\omega }\times P$ and $M\times B^{<\omega }$ are countable, so it’s sufficient to consider convergence of sequences in $A$.

We choose $f\left(O\right)$ to consist of all oracles $O^{\prime }$ that reflect $O$ and extend $\pi$. By the assumption that $\pi$ is reflective, $f\left(O\right)$ is non-empty for every $O\in A$. Moreover, it is easy to see that $f\left(O\right)$ is both closed and convex; hence, if we can also show that $f$ has closed graph, then by the fixed point theorem, there is a $O\in A$ such that $O\in f\left(O\right)$, which is exactly what we want to show.

Thus, assume that we have sequences $O_n=(O_{n,query},O_{n,eval})$ and $O_n^{\prime }=(O_{n,query}^{\prime },O_{n,eval}^{\prime })$ of oracles extending $\pi$ such that $O_n^{\prime }\in f\left(O_n\right)$ for every $n\in N$, and suppose that these sequences converge to limits $O,O^{\prime }\in A$; then we need to show that $O^{\prime }\in f\left(O\right)$, i.e., that $O^{\prime }$ reflects $O$. For the five equalities about $O_{eval}^{\prime }$ in the definition of ”$O^{\prime }$ reflects $O$”, we simply take the limit $n\to \infty$ of both sides of the equation, using the fact that convergence in the product topology is pointwise.

This leaves the two conditions about $O_{query}^{\prime }$. Since the proof of the second condition is exactly symmetrical, consider without loss of generality the first of these conditions, i.e., “If $q>O_{eval}(┌M┐)\left(\overline{x}\right)$, then $O_{query}^{\prime }(┌M┐,\overline{x},q)=1$”.

Thus, suppose that indeed $q>O_{eval}(┌M┐)\left(\overline{x}\right)$. Since $O_n\to O$ and convergence is pointwise, there must be an $n_0$ such that $q>O_{n,eval}\left(\overline{x}\right)$ for all $n\ge n_0$. Since $O_n^{\prime }$ reflects $O_n$ for all $n$, it follows that $O_{n,query}^{\prime }(┌M┐,\overline{x},q)=1$ for all $n\ge n_0$, whence by pointwise convergence $O_{query}^{\prime }(┌M┐,\overline{x},q)=1$, concluding the proof. □