Asymptotic Logical Uncertainty: Uniform Coherence

[Scott Garrabrant]

EDIT: This post is out of date, the new, better definition is here.

This post is part of the Asymptotic Logical Uncertainty series. Here, I give a concrete proposal for a definition of Uniform Coherence, as mentioned here.

This is only a proposal for a definition. It may be that this definition is bad, and we would rather replace it with something else

Let $M$ be a Turing machine which on input $N$ runs for some amount of time $R\left(N\right)$ then outputs a probability, representing the probability assigned to ${\varphi }_N$.

In the following definition, we fix a function $T\left(N\right)$ (e.g. $2^N$). We say that a sequence $\left\{s_n\right\}$ is quickly computable if it is an increasing sequence and there exists a Turing machine which determines whether or not an input $N$ is of the form $s_n$ in time $T\left(N\right)$.

We say that $M$ is Uniformly Coherent if

1. ${lim}_{n\to \infty }M(┌(\neg \neg {)}^n\perp ┐)=0$

2. If $\left\{s_n\right\}$ is quickly computable and $PA⊢{\varphi }_{s_n}\to {\varphi }_{s_{n+1}}$ for all $n$, then ${lim}_{n\to \infty }M\left(s_n\right)$ exists.

3. If $\left\{q_n\right\}$, $\left\{r_n\right\}$, and $\left\{s_n\right\}$ are quickly computable and $PA⊢({\varphi }_{q_i}\vee {\varphi }_{r_n}\vee {\varphi }_{r_n})\wedge \neg ({\varphi }_{q_n}\wedge {\varphi }_{r_n})\wedge \neg ({\varphi }_{q_n}\wedge {\varphi }_{s_n})\wedge \neg ({\varphi }_{r_n}\wedge {\varphi }_{s_n})$ for all $n$, then ${lim}_{n\to \infty }M\left(q_n\right)+M\left(r_n\right)+M\left(s_n\right)=1$

Open Question 1: Does there exist a uniformly coherent logical predictor $M$?

Open Question 2: Does there exist a uniformly coherent logical predictor $M$ which also passes the Generalized Benford Test? (Here, we mean the generalization of the Benford Test to all irreducible patterns)

Theroem: If $M$ is uniformly coherent, then if we define $P\left(\varphi \right)={lim}_{n\to \infty }M(┌(\neg \neg {)}^n\varphi ┐)$, then $P\left(\varphi \right)$ is defined for all $\varphi$ and is a computably approximable coherent probability assignment. (see here for definitions.)

Proof: Computable approximability is clear. For coherence, it suffices to show that $P\left(\varphi \right)$ is well defined, $P\left(\varphi \right)=1$ for provable $\varphi$, $P\left(\varphi \right)=0$ for disprovable $\varphi$, and $P(\varphi \wedge \psi )+P(\varphi \wedge \neg \psi )=P\left(\varphi \right)$.

The fact that $P\left(\varphi \right)$ is well defined comes from applying 2 to the sequence $s_n=┌(\neg \neg {)}^n\varphi ┐$.

The fact that $P\left(\varphi \right)=1$ for provable $\varphi$, comes from applying 3 to $q_n=┌(\neg \neg {)}^n\perp ┐$, $r_n=┌(\neg \neg {)}^n\perp ┐$, and $s_n=┌(\neg \neg {)}^n\varphi ┐$. The fact that $P\left(\varphi \right)=0$ for disprovable $\varphi$, comes from applying 3 to $q_n=┌(\neg \neg {)}^n\perp ┐$, $r_n=┌(\neg \neg {)}^n\top ┐$, and $s_n=┌(\neg \neg {)}^n\varphi ┐$, since we already know that $P\left(\top \right)=1$.

The fact that $P(\varphi \wedge \psi )+P(\varphi \wedge \neg \psi )=P\left(\varphi \right)$ comes from applying 3 to $q_n=┌(\neg \neg {)}^n\varphi \wedge \psi ┐$, $r_n=┌(\neg \neg {)}^n\varphi \wedge \neg \psi ┐$, and $s_n=┌(\neg \neg {)}^n\neg \varphi ┐,$ then applying 3 again to $q_n=┌(\neg \neg {)}^n\perp ┐$, $r_n=┌(\neg \neg {)}^n\varphi ┐$, and $s_n=┌(\neg \neg {)}^n\neg \varphi ┐,$ to get that $P(\varphi \wedge \psi )+P(\varphi \wedge \neg \psi )+P\left(\varphi \right)=1=P\left(\varphi \right)+P\left(\varphi \right)$. $\square$

Uniform Coherence is however much stronger than coherence. To see an example, consider an infinite sequence of sentences ${\varphi }_{s_n}=$“PA is consistent on proofs of length up to $n$.” Uniform coherence can be shown to imply that ${lim}_{n\to \infty }M\left(s_n\right)=1$. (Each of the sentences is provable, so you can apply 3 to this sequence and a pair of $┌(\neg \neg {)}^n\perp ┐$ sequences.)

Theorem: If we take a quickly computable sequence of mutually exclusive sentences, $\left\{{\varphi }_{s_n}\right\}$, then if $M$ is uniformly coherent, we have ${lim}_{n\to \infty }M\left(s_n\right)=0$.

Proof: Let ${\varphi }_{r_n}$ be the disjunction of all the ${\varphi }_{s_i}$ for $i<n$. Let ${\varphi }_{q_n}=\neg {\varphi }_{r_{n+1}}$. By 2, ${lim}_{n\to \infty }M\left(q_n\right)$ converges to some $p$. Applying 3 to $\left\{q_n\right\}$, $\left\{r_{n+1}\right\}$ and $\{┌(\neg \neg {)}^n\perp ┐\}$ shows that ${lim}_{n\to \infty }M\left(r_n\right)$ converges to $1-p$. Therefore, applying 3 to $\left\{q_n\right\}$, $\left\{r_n\right\}$, and $\left\{s_n\right\}$ shows that ${lim}_{n\to \infty }M\left(s_n\right)$ converges to 0.(Note that I assumed here that $T$ was reasonable enough that $q_n$ and $r_n$ ane also quickly computable)$\square$

[abramdemski]

This notion, by the argument you give before the final theorem, implies belief (with probability 1) in all true ${\Pi }_1$ sentences—therefore it must disbelieve true ${\Pi }_2$ sentences. This is quite intriguing, but likely means it’s not quite what we want.

If uniformly coherent predictors exist, their self-referential knowledge would obey Paul Christiano’s reflection principle (which follows directly from believing true ${\Pi }_1$ sentences).

[Scott Garrabrant]

It does not imply belief in all true ${\Pi }_1$ sentences. If $f\left(x\right)$ is true for all $x$, the probability of $f\left(x\right)$ will go to 1 as $x$ goes to infinity, but the probability of $\left(\neg \neg {)}^n\forall xf\right(x)$ may stay bounded away from 1.

[abramdemski]

Ahh, right. Silly mistake.

So the difference in this example is that a coherent prior with approximation $P_t\left(n\right)$ can have $li{m}_t{P}_t\left({\varphi }_{s_n}\right)\to 1$ for all $n$, but not have $li{m}_t{P}_t\left({\varphi }_{s_t}\right)\to 1$; uniformly coherent must have this. To be precise, if we set $P_t\left(\varphi \right):=M(┌(\neg \neg {)}^t\varphi ┐)$ with $M$ uniformly coherent, we must have this.

[Scott Garrabrant]

Correct.