A limit-computable, self-reflective distribution

[TsviBT]

We present a ${\Delta }_2$-definable probability distribution $\Psi$ that satisfies Christiano’s reflection schema for its own defining formula. The strategy is analogous to the chicken step employed by modal decision theory to obfuscate itself from the eyes of $PA$; we will prevent the base theory $T$ from knowing much about $\Psi$, so that $\Psi$ can be coherent over $T$ and also consistently believe in reflection statements. So, the method used here is technical and not fundamental, but it does at least show that limit-computable and reflective distributions exist. These results are due to Sam Eisenstat and me, and this post benefited greatly from extensive notes from Sam; any remaining errors are probably mine.

Prerequisites: we assume familiarity with Christiano’s original result and the methods used there. In particular, we will freely use Kakutani’s fixed point theorem. See Christiano et al.’s paper.

---

Outline

• Section 1. Introduction and problem statement

• Section 2. A definable, self-reflective distribution $\Psi$

• Section 3. A ${\Delta }_2$-definable, self-reflective distribution $\Lambda$

• Section 4. Discussion and open problems

Section 1. Problem statement

Probabilistic reflection

We have some base theory $T$ in a language $L$, where $T$ is able to talk about arithmetic (e.g.$PA$ or $ZFC$). We wish to find probability distributions over completions of $T$, or equivalently functions $P:L\to [0,1]$ satisfying $\varphi \in T$ implies $P\left(\varphi \right)=1$ and probabilistic coherence conditions like $P\left(\neg \varphi \right)=1-P\left(\varphi \right)$. In particular, we want $P$ to have accurate beliefs about itself:

$$\forall \varphi \in L:\forall a,b\in Q:P\left(\varphi \right)\in (a,b)\Rightarrow P\left(P\right(┌\varphi ┐)\in (a,b\left)\right)=1,$$

where $P$ is a symbol in $L$. Christiano showed that there exists such a distribution $P$. In other words, taking an additional symbol $P$ in the metalanguage, writing ${\text{Coh}}_T\left(P\right)$ for the statement that $P$ is a coherent distribution over $T$, and for the statement that $P$ is reflective, we have that the theory

$$ZFC+{\text{Coh}}_T\left(P\right)+\text{Refl}\left(P\right)$$

is consistent. That consistency of this theory is equivalent to the existence of a reflective $P$ requires an argument due to Fallenstein, wherein we take the standard part of $P$ according to some completion of this theory. We will use this idea in Section 3 and explain it there.

Definable reflection

Christiano asked: Can we find a distribution that is definable, and furthermore reflective about its own defining formula?
This is different from the original reflective $P$ because we had a symbol $P$ in the language, and $P$ reflected itself in that symbol; in that case, speaking imprecisely, $P$ knew that $P$ assigned the same probabilities that $P$ assigned. Now we want a formula $\Psi$ that defines a distribution, and that distribution assigns probability 1 to certain true statements about what probabilities $\Psi$ assigns. ($\Psi$ stands for $P$-Self-reflective.)

Formally, can we have a coherent distribution on $T$ defined by some formula $\Psi$ in the language $L$, where $L$ now does not contain a distinguished symbol $P$, satisfying:

$$\forall \varphi \in L:\forall a,b\in Q:\text{if}\Psi (┌\varphi ┐)\in (a,b)\text{, then}\Psi (┌\Psi (┌\varphi ┐)\in (a,b)┐)=1?$$

Our strategy is to apply Kakutani’s fixed point theorem to the following reflection correspondence ${⊲}_{\Psi }$ on the set $\Delta \left(T\right)\subset [0,1{]}^L$ of coherent distributions over $T$. For any $P,Q\in \Delta \left(T\right)$, we write $P{⊲}_{\Psi }Q$ and say that $Q$ reflects $P$ in $\Psi$ if and only if, whenever $P\left(\varphi \right)$ is in some interval, $Q$ believes that $\Psi$ assigns to $\varphi$ a value in that interval. Formally, for all $P,Q\in \Delta \left(T\right)$, we have $P{⊲}_{\Psi }Q$ if and only if:

$$\forall \varphi \in L:\forall a,b\in Q:\text{if}P\left(\varphi \right)\in (a,b)\text{, then}Q\left(\Psi \right(┌\varphi ┐)\in (a,b\left)\right)=1.$$

If we can obtain a fixed point of this correspondence ${⊲}_{\Psi }$, and have $\Psi$ define this same distribution, then we will have a definable self-reflective distribution.

(The notation ${⊲}_{\Psi }$ does not denote an ordering, and is meant to suggest a single point on the left with a larger corresponding set on the right; better recommendations are welcome. Also, in the following section, $P$ and $Q$ are actual distributions, not symbols in a language; this is distinguished by their arguments having the type of formulas rather than Gödel numbers of formulas.)

Most of the conditions for Kakutani’s theorem are satisfied by ${⊲}_{\varphi }$ for any formula $\varphi$ just as in Christiano’s proof, so we won’t verify them in detail. For example, the set of distributions reflect $Q$ in $\varphi$ is still convex, because interpolation preserves coherence and reflection. (I can make an auxiliary post if people would like to see the details.) However, we need ${⊲}_{\Psi }$ to satisfy the crucial non-emptiness condition:

$$\forall P\in \Delta \left(T\right):\exists Q\in \Delta \left(T\right):P{⊲}_{\Psi }Q.$$

In the next section, we give a definition $\Psi$ that meets this criterion, assuming a strong background theory such as $ZFC$. This will illustrate the diagonalization method we will apply. Section 3 gives a $\Lambda$ that uses the same strategy as $\Psi$, but is ${\Delta }_2$-definable in arithmetic, i.e. computable relative to a halting oracle. Section 4 discusses the meta-theoretic assumptions used, optimality of our results, and open questions.

Section 2. A definable, self-reflective distribution $\Psi$

Consider the theory $T_{\Psi =P}:=T\cup \left\{\Psi \right(┌\varphi ┐)\in (a,b)|\varphi \in L,a,b\in Q,P(\varphi )\in (a,b\left)\right\}$ stating that $\Psi$ behaves according to $P$. If $T_{\Psi =P}$ is a consistent theory, then we can take a completion $T^{\prime }$ of $T_{\Psi =P}$, and then take the 0-1-valued distribution $Q\left(\varphi \right):=I\{\varphi \in T^{\prime }\}$, i.e. the indicator function for membership in the complete theory $T^{\prime }$. This $Q$ is coherent over $T$, and furthermore by fiat $Q$ assigns probability 1 to each reflection statement for $P$ by $\Psi$.

In the original existence proof of a reflective $P$, the analogous reflection theory $T_{p=P}$ for a symbol $p$ is consistent: the distribution $P$ itself provides a model for $T_{p=P}$. However, in the present case, we have to be more careful. Perhaps $T$ proves some non-trivial facts about the behavior of the function $\Psi$ we are defining. Then $T_{\Psi =P}$ may be inconsistent, if $T$ proves that $\Psi$ cannot behave according to $P$, e.g. if $P\left(\varphi \right)\in (a,b)$ but $T⊢\Psi (┌\varphi ┐)\notin (a,b)$.

To overcome this, we will obfuscate the behavior of $\Psi$ from the prying proofs of $T$, to such an extreme extent that $T$ cannot rule out any finite set of behaviors of $\Psi$; then $T_{\Psi =P}$ will be consistent. (Unfortunately, this weakens the main potential use in reflective agents of having a definable self-reflective distribution, namely, that the theory can reason concretely about the distribution, other than what can be said about generic coherent distributions. It may be possible to have the base theory prove more about the distribution by not diagonalizing against certain behaviors, and working around that in the application of Kakutani’s theorem.)

Definition of $\Psi$

Take the set $B_{\Psi }:=\left\{{\bigwedge }_{i\in \left[n\right]}\right(\Psi (┌{\varphi }_i┐)\in (a_i,b_i))|n\in N;a_j,b_j\in Q\cap [0,1];\forall k\in [n]:a_k<b_k\}$ of possible finite specifications of behaviors for $\Psi$. Here ${\varphi }_i$ is some enumeration of all sentences in $L$. Note that $B_{\Psi }$ is countable, and each sentence in $B_{\Psi }$ is consistent with $\Psi$ being a function, though not necessarily a coherent distribution. Now we can define $\Psi$ by the following informally stated construction, which can be translated into a formula $\Psi (n,r)$ defining the graph of a function from sentences to real numbers:

Step 1. Search for a proof in $T$ of the negation of some statement in $B_{\Psi }$. If such a statement ${\bigwedge }_{i\in \left[n\right]}\left(\Psi \right(┌{\varphi }_i┐)\in (a_i,b_i\left)\right)$ is found, then output some value in $(a_i,b_i)$ on input ${\varphi }_i$, and otherwise output 0.

Step 2. Otherwise, output values according to the least fixed point of the reflection correspondence ${⊲}_{\Psi }$.

By the least fixed point, we mean the fixed point with minimal first coordinate; minimal second coordinate out of those with minimal first coordinate; minimal third coordinate . . . etc. This exists because the set of fixed points is closed, and therefore also compact. Note that we require $L$ and $T$ to be expressive enough to define fixed points of ${⊲}_{\Psi }$ and the ordering just described. Taking $T=ZFC$ suffices. This is not a crucial point, as we will later show that a much weaker theory suffices.

Theorem 1.

If $T$ is a sound theory, then $\Psi$ defines a function on $L$ that assigns probability 1 to each sentence in $T$, is coherent, and is reflective.

Proof.

Suppose we have $T⊢\neg \xi$ for some $\xi \in B_{\Psi }$, where $\xi ={\bigwedge }_{i\in \left[n\right]}\left(\Psi \right(┌{\varphi }_i┐)\in (a_i,b_i\left)\right)$. Then by step 1 of $\Psi$, we have that $\Psi \left(\varphi \right)\in (a_i,b_i)$ for all $i\in \left[n\right]$. This contradicts soundness of $T$.

Thus, by compactness, we have that for all $P\in \Delta \left(T\right)$, the theory $T_{\Psi =P}$ is consistent. Then by the argument above, the correspondence ${⊲}_{\Psi }$ gives a non-empty image for each point in $\Delta \left(T\right)$. By Kakutani’s theorem, there is a fixed point of this correspondence.

Step 2 then outputs probabilities according to some such fixed point $P$. That is, $\forall \varphi :\Psi \left(\varphi \right)=P\left(\varphi \right)$. Furthermore, $P{⊲}_{\Psi }P$, i.e.$\Psi$ is reflective. $\square$

In fact, we do not need to assume soundness of $T$ in Theorem 1; we only need to assume that $T$ is consistent. Proof: suppose that $T⊢\neg \xi$ for some $\xi \in B_{\Psi }$. Then there is a least such $\xi$. But then $T$ can prove that $\xi$ is the first sentence in $B_{\Psi }$ that $T$ refutes, so $T$ can prove that $\Psi$ finds this proof and outputs according to $\xi$. Then we have that $T$ both proves and refutes that $\Psi$ behaves according to $\xi$, contradicting the consistency of $T$.

Section 3. A ${\Delta }_2$-definable, self-reflective distribution $\Lambda$

Step 1 in $\Psi$ as defined above is ${\Delta }_2$-definable, i.e. computable with a halting oracle: we just need to check the halting of the machine that searches for refutations by $T$ of the (computably recognizable) sentences in $B_{\Psi }$. If the machine halts, find the proof computably, and output rational numbers given by the refuted behavior.

Step 2, however, uses set-theoretic notions; namely, it quantifies over the large and complicated set of fixed points of ${⊲}_{\Psi }$. In this section we replace Step 2 with a ${\Delta }_2$ computation, thereby defining a ${\Delta }_2$ formula $\Lambda$ that is self-reflective. ($\Lambda$ stands for Limit-computable.)

Definition of $\Lambda$

By the arguments for Theorem 1, regardless of what $\Lambda$ does in Step 2, there will be some $P\in \Delta \left(T\right)$ such that $P{⊲}_{\Lambda }P$. Thus, for Step 2, it suffices to run a ${\Delta }_2$ computation that outputs a fixed point as long as one exists. We now define $\Lambda$ by the following construction, which can be viewed as an algorithm executed by a machine with a halting oracle:

Step 1. Search for a proof in $T$ of the negation of some statement in $B_{\Lambda }$. If such a statement ${\bigwedge }_{i\in \left[n\right]}\left(\Lambda \right(┌{\varphi }_i┐)\in (a_i,b_i\left)\right)$ is found, then output some value in $(a_i,b_i)$ on input ${\varphi }_i$, and otherwise output 0.

Step 2. Otherwise, enumerate a completion $\overline{Z}$ of the theory $Z:=ZFC+{\text{Coh}}_T\left(P\right)+P{⊲}_{\Lambda }P$ in the language of set theory plus a constant symbol $P$. That is, list all sentences $\sigma$, and print out each $\sigma$ that is consistent with $Z$ and the finitely many sentences that have already been printed. Given a sentence $\varphi$ and a precision $0<\epsilon \in Q$, search $\overline{Z}$ for the first quadruple of rational numbers $a<a^{\prime }<b^{\prime }<b$ such that $\overline{Z}⊢P(┌\varphi ┐)\in (a^{\prime },b^{\prime })$, and such that $b-a<\epsilon$. Output $(a,b)$.

(Note: This is the technique alluded to earlier of taking the standard part of a distribution. If we just output $(a,b)$ with $\left(P\right(┌\varphi ┐)\in (a,b\left)\right)\in \overline{Z}$, then we might output e.g.$(0,1/n)$ for all $n\in N$, which has empty intersection. Also note that we could take a much more basic theory than $Z$; we could have a base theory that says all true atomic statements about $Q$, and take ${\text{Coh}}_T\left(P\right)$ and $P{⊲}_{\Lambda }P$ to be schema of quantifier-free formulas.)

Observation: $\Lambda$ is ${\Delta }_2$.

Proof: Step 1 is ${\Delta }_2$ by the argument given at the beginning of this section. Step 2 is computable, except that we need to check whether each new sentence $\sigma$ is consistent with $Z$ and the previously printed sentences. To check the consistency of a computably enumerable theory $S$, we ask our halting oracle whether not $M$ halts, where $M$ is a machine that enumerates all the theorems of $S$, and halts iff it prints $\perp$.

Theorem 2.

$\Lambda$ defines a coherent, self-reflective distribution.

Proof.

By the argument for $\Psi$, if $T$ is consistent, it does not refute any behavior of $\Lambda$. So there is some fixed point $P{⊲}_{\Lambda }P$, and also $\Lambda$ behaves according to Step 2.

The distribution $P$ provides an interpretation for the symbol $P$ satisfying coherence over $T$ and self-reflection in $\Lambda$. Hence the theory $Z$ is consistent, and so $\overline{Z}$ is non-trivial. By construction, for each $\varphi$ there is a unique (standard) real $P_{\overline{Z}}\left(\varphi \right)$ that, for all $\epsilon >0$, lies in the interval output by $\Lambda$ on $\varphi$ and $\epsilon$.

Now we argue that $P_{\overline{Z}}$ is coherent over $T$ and reflects itself in $\Lambda$. For any $\varphi \in T$, since $\overline{Z}⊢{\text{Coh}}_T\left(P\right)$, we also have $\overline{Z}⊢P(┌\varphi ┐)=1$. Thus, for all $\epsilon >0$ we have that $\overline{Z}⊢P(┌\varphi ┐)\in (1-\epsilon ,1+\epsilon )$, and therefore $P_{\overline{Z}}\left(\varphi \right)=1$. A very similar argument works to show the other coherence conditions and reflection. For example, if $P_{\overline{Z}}\left(\varphi \right)\in (a,b)$, then we have $\overline{Z}⊢P(┌\varphi ┐)\in (a,b)$. By an instance of $P{⊲}_{\Lambda }P$, also $\overline{Z}⊢P(┌\Lambda (┌\varphi ┐)\in (a,b)┐)=1$, and hence $P_{\overline{Z}}\left(\Lambda \right(┌\varphi ┐)\in (a,b\left)\right)=1$.

Thus $\Lambda$ computes a coherent distribution over $T$ which assigns probability 1 to each reflection statement for $\Lambda$. $\square$

Section 4. Discussion

${\Delta }_2$ is roughly optimal for the properties of $\Lambda$; computable distributions can’t even be coherent over essentially undecidable theories. (If we could compute a coherent distribution over $T$, then for each $\varphi$ we could wait for 1 or 0 to be excluded from the intervals we output for $\varphi$, and thereby computably separate the provable and refutable sentences, which is impossible.) A slightly stronger statement is that for any definable completion $\overline{PA}$ of $PA$, there is a distribution $P$ over completions of $T$ that is computable from $\overline{PA}$, which is reflective for the definition of $P$ that uses $\overline{PA}$ in Step 2 to complete $Z$.

As mentioned earlier, $\Lambda$ is very obfuscated from $T$. In fact, if $T$ is strong enough, then $\Lambda \left(\text{Con}\right(T\left)\right)=0$. Otherwise, since $\Lambda$ believes each sentence of $T$, by coherence and , we would have that . But this is not possible for a reflective, coherent distribution.

If our metatheory $K$ is strong enough to prove some facts like Kakutani’s theorem, then $K+\text{Con}\left(T\right)$ proves ${\text{Coh}}_T\left(\Lambda \right)$ and $\text{Refl}\left(\Lambda \right)$. This likely roughly optimal: if the meta-theory even proves ${\text{Coh}}_T\left(\Lambda \right)$, then it also proves $\text{Con}\left(T\right)$. Probably $PA$ is sufficient to prove the necessary first-order statements, since the second-order theory ${\text{ACA}}_0$ is probably strong enough to prove a literal statement of Kakutani’s theorem, and $PA$ is the first-order part of ${\text{ACA}}_0$. See for example Fixed point theory in weak second-order arithmetic, by Naoki Shioji and Kazuyuki Tanaka , though that paper only proves Kakutani in finite dimensions and the Tychonoff-Schauder theorem (in the weaker system ${\text{WKL}}_0$).

Questions

• We conjecture that a modification of $\Lambda$ might give a distribution ${\rm Y}$ that satisfies the same properties, and also assigns probability 1 to the statement ${\text{Coh}}_T\left({\rm Y}\right)$.

• We also conjecture that Fallenstein’s reflection principle for expectations can be similarly defined.

• Can there be a distribution that is reflective and computably approximable (from below)? (This may be easy to refute.)

• Can a definable reflective distribution be coherent over a theory that proves some useful facts about the distribution?

• What are some weaker notions of reflection that can be computable or computably approximable (from below)?

• What reflective properties of beliefs are needed for self-verification in the context of general decision-making?

Open questions (Christiano):

• What sorts of bad beliefs can be avoided given coherence and reflection?

• What are some weaker notions of reflection such that probability distributions can be coherent, reflective, and also assign high probability to their own reflectivity?