Oracle machines instead of topological truth predicates

In a comment on my post on topological truth predicates, Paul suggests an approach that uses probabilistic oracle machines instead, in order to make this work more comprehensible to computer scientists. I like this idea!

Paul sketches a framework developed by him and Jessica Taylor, based on a conversation with Scott Aaronson; in this post, I propose a slight simplification of their framework. My version has an oracle $O (┌ M ┐, p)$ , which takes the source code of a probabilistic oracle machine $M$ and a $p \in Q \cap [0, 1]$ . If for every possible oracle $O^{'}$ , $M [O^{'}]$ halts with probability one and outputs either $0$ or $1$ , then $O (┌ M ┐, p)$ : (i) returns “true” if the probability that $M [O]$ returns $1$ is $> p$ ; (ii) returns “false” if it is $< p$ ; (iii) randomly returns “true” or “false” if it is exactly $p$ . If $M$ is not of this form, the oracle always returns “false”. I think this is sufficient for all the applications I have in mind—in particular, for defining a variant of AIXI that is able to reason about worlds containing other, equally powerful variant AIXIs (but many details remain to be checked).

To be clear, by “probabilistic oracle machine” I mean a probabilistic Turing machine with access to our oracle, which itself behaves probabilisticly. Let’s write $P := Q \cap [0, 1]$ for the set of all rational probabilities, and let’s consider an oracle to be a function $O : N \times P \to [0, 1]$ , such that $O (┌ M ┐, p)$ specifies the probability that the oracle will return “true” when invoked on the pair $(┌ M ┐, p)$ . (If the oracle is invoked multiple times on the same arguments, each of these is an independent random event.) The function $O (┌ M ┐, p)$ plays a similar role in this framework to the function $θ (┌ φ ┐, ┌ ψ ┐)$ from the topological truth predicates post. Feedback on notation and terminology is encouraged—my exposure to theoretical CS is limited.

Let’s define a query to be a probabilistic oracle machine $M$ such that for every oracle $O$ , $M [O]$ halts with probability one and outputs either $0$ or $1$ . If $M$ is a query, let $P (M, O)$ be the probability that $M [O]$ outputs $1$ . Then our condition above can be re-stated as follows:

(i) If $P (M, O) > p$ , then $O (┌ M ┐, p) = 1$ . (ii) If $P (M, O) < p$ , then $O (┌ M ┐, p) = 0$ . (iii) If $P (M, O) = p$ , then $O (┌ M ┐, p) \in [0, 1]$ is arbitrary. (iv) For any $n$ which is not the Gödel number of a query, $O (n, p) = 0$ .

The last of these conditions is a bit of a devious trick; it gives the machine access to a fairly powerful halting oracle, which can e.g. check whether a probabilistic Turing machine halts with probability one. (Given such a machine $T$ , construct the machine $T^{'}$ which runs $T$ and outputs $1$ if $T$ halts; then if $T$ halts with probability $1$ , $T^{'}$ is a query and $O (┌ T^{'} ┐, 0) = 1$ , but if $T$ halts with probability $< 1$ , $T^{'}$ is not a query and $O (┌ T^{'} ┐, 0) = 0$ .) I think that I need this in my variant of AIXI in order to filter out “world models” which don’t necessarily halt, and I think this will be enough to do so, but I’ll leave working out the details to a later post.

At the end of this post, I’ll prove that a $O$ with these properties exists. But first, let me sketch how it can be used.

Suppose that we have an agent which is trying to choose between two actions, $A$ and $A^{'}$ , and suppose that the agent has two probabilistic oracle machines, $M$ and $M^{'}$ , which represents the agent’s model of what will happen in the world if it chooses action $A$ or action $A^{'}$ , respectively. (This doesn’t mean that the agent has to have perfect knowledge about how the world works—since these are probabilistic machines, they can represent probability distributions over the laws of physics.) We could think of $M$ and $M^{'}$ as outputting information about things that happen in the world, which we can then plug into a computable utility function, but it will be easier to think of them as directly returning a utility.

Our goal, then, is for our agent to choose $A$ if the expectation of the utility returned by $M$ is greater than the expectation of the utility returned by $M^{'}$ .

Utilities are real numbers (and if we consider infinite-horizon problems with temporal discounting, rational utilities won’t suffice), so we need a way for probabilistic machines in our framework to represent probability distributions over reals. Let’s say that an machine “outputs the real number $r \in [0, 1]$ ” if it outputs a sequence of nested closed intervals with endpoints in $P = Q \cap [0, 1]$ , converging to the single point $r$ . We’ll assume that $M [O^{'}]$ and $M^{'} [O^{'}]$ output real numbers in $[0, 1]$ with probability one, for every oracle $O^{'} : N \times P \to [0, 1]$ . I’ll write $E [N]$ for the expected value of the number returned by $N [O]$ , if $N$ is such an oracle machine (leaving the oracle $O$ implicit in the notation).

We want to find an oracle machine that will output $A$ if $E [M] > E [M^{'}]$ , output $A^{'}$ if $E [M] < E [M^{'}]$ , and output either $A$ or $A^{'}$ if the expectations are equal. Note that in our representation, we can write machines that compute e.g. the sum or difference of the numbers computed by two other machines; and note that $E [M] > E [M^{'}]$ is equivalent to $E [(1 + M - M^{'}) / 2] > 0.5$ . We have $E [(1 + M - M^{'}) / 2] \in [0, 1]$ ; thus, if we could find a query $N$ such that $N [O]$ returns $1$ with probability $E [(1 + M - M^{'}) / 2]$ , we could simply call our oracle on $O (┌ N ┐, 0.5)$ , and take action $A$ if the oracle returns “true”, action $A^{'}$ otherwise.

We can implement $N$ as follows. Set $x_{0} := 0$ and $y_{0} := 1$ , and initialize a run of $(1 + M - M^{'}) / 2$ . Then, for every $n \in N_{\geq 1}$ : run $(1 + M - M^{'}) / 2$ until it returns its next ( $n$ ’th) interval, with lower bound $x_{n}$ and upper bound $y_{n}$ . Then, with probability $(x_{n} - x_{n - 1}) / (y_{n - 1} - x_{n - 1})$ , halt and output $1$ ; with probability $(y_{n - 1} - y_{n}) / (y_{n - 1} - x_{n - 1})$ , halt and output $0$ ; otherwise, continue looping.

Since with probability one, $(1 + M - M^{'}) / 2$ outputs a sequence of intervals that converge to a single point, $N$ halts with probability one and outputs either $0$ or $1$ , whatever oracle we run it on; i.e., it is a query. We can describe its behavior as sampling a random number $r \in [0, 1]$ from the distribution $(1 + M - M^{'}) / 2$ , and then outputting $1$ with probability $r$ and $0$ with probability $(1 - r)$ . When looked at it this way, it’s clear that when run on $O$ , this machine will output $1$ with probability $E [(1 + M - M^{'}) / 2]$ , as desired.

Let’s now proceed to the proof that an appropriate $O$ exists. This is analogous to the proof in the topological truth predicates post. (However, while we’ll still need to use the product topology and the infinite-dimensional generalization of Kakutani’s fixed point theorem, this proof won’t require knowledge of Grothendieck universes, set theory, or formal logic.)

Recall that an oracle is an arbitrary function $O : N \times P \to [0, 1]$ . We say that an oracle $O^{'}$ reflects another oracle $O$ if for every $p \in P$ and every query $M$ , we have $O^{'} (┌ M ┐, p) = 1$ if $P (M, O) > p$ and $O^{'} (┌ M ┐, p) = 0$ if $P (M, O) < p$ , and for any $n$ that is not the Gödel number of a query, we have $O (n, p) = 0$ . In interpretation, $O^{'}$ reflects $O$ if it gives correct information about the probability that a query returns $1$ when it’s executed with oracle $O$ .

An oracle is called reflective if it reflects itself; reflective oracles give answers which are true about the oracle itself.

Our main goal in this post is just to show that reflective oracles exist. However, later I’ll want to show that for every Nash equilibrium of a finite game, there is a reflective oracle which makes the players of that finite game play that Nash equilibrium, and in order to do so, it will be helpful to have a slightly stronger statement, which shows that there are reflective oracles satisfying certain constraints.

These constraints will take the form of a partial function $π : N \times P ↛ [0, 1]$ , which specifies the values $O$ should take on a certain set $d o m (π) \subseteq N \times P$ . We call a function of this type a partial oracle, and say that $O$ extends $π$ if $O (n, p) = π (n, p)$ for all $(n, p) \in d o m (π)$ . We call a partial oracle $π$ reflective if for every oracle $O$ extending $π$ , there is an oracle $O^{'}$ which reflects $O$ and which also extends $π$ .

With these preliminaries, we can state our existence result for reflective oracles:

Theorem.

(i) There is a reflective oracle $O : N \times P \to [0, 1]$ . (ii) For every reflective partial oracle $π : N \times P ↛ [0, 1]$ , there is a reflective oracle $O$ which extends $π$ .

Proof. We begin by showing that the empty partial oracle $π_{\emptyset}$ (i.e., the partial oracle satisfying $d o m (π_{\emptyset}) = \emptyset$ ) is reflective, since (i) then follows from (ii). Thus, let $O$ be any oracle (since every oracle extends $π_{\emptyset}$ ), and define $O^{'} : N \times P \to [0, 1]$ as follows: For any $M$ and $p$ such $M$ is a query and $P (M, O) > p$ , set $O^{'} (┌ M ┐, p) = 1$ ; for all other pairs $(n, p)$ , set $O (n, p) = 0$ . Then, $O^{'}$ clearly both reflects $O$ and (trivially) extends $π_{\emptyset}$ . This finishes the proof that $π_{\emptyset}$ 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 P o w (A)$ is a set-valued function such that $f (x)$ is non-empty, convex and compact for all $x \in A$ , and such that the graph of $f$ , ${(x, y) : x \in A, y \in f (x)},$ is a closed set. Then $f$ has a fixed point; that is, there is an $x \in A$ such that $x \in f (x)$ .

We let $A$ be the set of all oracles extending $π$ ; then $A \subset R^{N \times P}$ , which is a locally convex topological vector space when endowed with the product topology (since this is true of any power of $R$ ). $A$ is clearly non-empty, convex, and closed, and it is a subset of $[0, 1]^{N \times P}$ which, by Tychonoff’s theorem, is compact. Moreover, $N \times P$ is countable, so it’s sufficient to consider convergence of sequences in $R^{N \times P}$ .

We choose $f (O)$ to consist of all oracles $O^{'}$ that reflect $O$ and extend $π$ . By the assumption that $π$ is reflective, $f (O)$ is non-empty for every $O \in A$ . Moreover, it is easy to see that $f (O)$ 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 (O)$ , which is exactly what we want to show.

Thus, assume that we have sequences $O_{n}$ and $O_{n}^{'}$ of oracles extending $π$ such that $O_{n}^{'} \in f (O_{n})$ for every $n \in N$ , and suppose that these sequences converge to limits $O, O^{'} \in A$ ; then we need to show that $O^{'} \in f (O)$ , i.e., that $O^{'}$ reflects $O$ . To see this, we must show that for every query $M$ and any $p \in P$ , $P (M, O) > p$ implies $O^{'} (┌ M ┐, p) = 1$ , and $P (M, O) < p$ implies $O^{'} (┌ M ┐, p) = 0$ . (The condition that $O^{'} (n, p) = 0$ for any $n$ that is not the Gödel number of a query follows directly from the fact that this is true about all $O_{n}^{'}$ .)

Without loss of generality, assume that $P (M, O) < p$ . Let $ε := (p - P (M, O)) / 2$ . Since $M$ is a query, $M [O]$ halts with probability one (and returns either 0 or 1); hence, there is some $T \in N$ such that with probability $> 1 - ε$ , $M [O]$ halts in at most $T$ steps. Despite the fact that $M$ is probabilistic and can make calls to an oracle, there are only finitely many possible execution traces of $M$ during the first $T$ timesteps, and thus only finitely many pairs $(┌ M^{'} ┐, p^{'})$ on which $M$ might invoke its oracle during these timesteps.

Since $O_{n}$ converges to $O$ , there is an $n_{0}$ such that for all $n \geq n_{0}$ , $| O_{n} (┌ M^{'} ┐, p^{'}) - O (┌ M^{'} ┐, p^{'}) | < ε / T$ for each of these finitely many pairs $(┌ M^{'} ┐, p^{'})$ . Suppose that we model each call to the oracle as sampling a random number from a uniform $[0, 1]$ distribution, and returning “true” if this number is greater than $O (┌ M^{'} ┐, p^{'})$ ; then the above result implies that with probability $> 1 - ε$ , $M [O_{n}]$ and $M [O]$ behave the same way during the first $T$ timesteps. Hence, with probability $> 1 - 2 ε$ , $M [O_{n}]$ and $M [O]$ both halt during the first $T$ steps and return the same result. But this implies that $P (M, O_{n}) < P (M, O) + 2 ε = p$ , for all $n \geq n_{0}$ .

Since $O_{n}^{'}$ reflects $O_{n}$ , this implies $O_{n}^{'} (┌ M ┐, p) = 0$ , and since this holds for all $n \geq n_{0}$ and $O_{n}^{'}$ converges to $O^{'}$ , it follows that $O^{'} (┌ M ┐, p) = 0$ , as desired. □