Asymptotic Logical Uncertainty: Uniform Coherence — AI Alignment Forum

Asymptotic Logical Uncertainty: Uniform Coherence — AI Alignment Forum

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 (N)$ then outputs a probability, representing the probability assigned to $ϕ_{N}$ .

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

We say that $s_{n}$ is Uniformly Coherent if

$T (N)$
If ${s_{n}}$ is quickly computable and $P A ⊢ ϕ_{s_{n}} \to ϕ_{s_{n + 1}}$ for all $n$ , then ${lim}_{n \to \infty} M (s_{n})$ exists.
If ${q_{n}}$ , ${r_{n}}$ , and ${s_{n}}$ are quickly computable and $P A ⊢ (ϕ_{q_{i}} \lor ϕ_{r_{n}} \lor ϕ_{r_{n}}) \land \neg (ϕ_{q_{n}} \land ϕ_{r_{n}}) \land \neg (ϕ_{q_{n}} \land ϕ_{s_{n}}) \land \neg (ϕ_{r_{n}} \land ϕ_{s_{n}})$ for all $n$ , then ${lim}_{n \to \infty} M (q_{n}) + M (r_{n}) + M (s_{n}) = 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 (ϕ) = {lim}_{n \to \infty} M (┌ (\neg \neg)^{n} ϕ ┐)$ , then $P (ϕ)$ is defined for all $ϕ$ 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 (ϕ)$ is well defined, $P (ϕ) = 1$ for provable $ϕ$ , $P (ϕ) = 0$ for disprovable $ϕ$ , and $P (ϕ \land ψ) + P (ϕ \land \neg ψ) = P (ϕ)$ .

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

The fact that $P (ϕ) = 1$ for provable $ϕ$ , comes from applying 3 to $q_{n} = ┌ (\neg \neg)^{n} ⊥ ┐$ , $r_{n} = ┌ (\neg \neg)^{n} ⊥ ┐$ , and $s_{n} = ┌ (\neg \neg)^{n} ϕ ┐$ . The fact that $P (ϕ) = 0$ for disprovable $ϕ$ , comes from applying 3 to $q_{n} = ┌ (\neg \neg)^{n} ⊥ ┐$ , $r_{n} = ┌ (\neg \neg)^{n} ⊤ ┐$ , and $s_{n} = ┌ (\neg \neg)^{n} ϕ ┐$ , since we already know that $P (⊤) = 1$ .

The fact that $P (ϕ \land ψ) + P (ϕ \land \neg ψ) = P (ϕ)$ comes from applying 3 to $q_{n} = ┌ (\neg \neg)^{n} ϕ \land ψ ┐$ , $r_{n} = ┌ (\neg \neg)^{n} ϕ \land \neg ψ ┐$ , and $s_{n} = ┌ (\neg \neg)^{n} \neg ϕ ┐,$ then applying 3 again to $q_{n} = ┌ (\neg \neg)^{n} ⊥ ┐$ , $r_{n} = ┌ (\neg \neg)^{n} ϕ ┐$ , and $s_{n} = ┌ (\neg \neg)^{n} \neg ϕ ┐,$ to get that $P (ϕ \land ψ) + P (ϕ \land \neg ψ) + P (ϕ) = 1 = P (ϕ) + P (ϕ)$ . $□$

Uniform Coherence is however much stronger than coherence. To see an example, consider an infinite sequence of sentences $ϕ_{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 (s_{n}) = 1$ . (Each of the sentences is provable, so you can apply 3 to this sequence and a pair of $┌ (\neg \neg)^{n} ⊥ ┐$ sequences.)

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

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