Asymptotic Logical Uncertainty: Passing the Benford Test

This post is part of the Asymptotic Logical Uncertainty series. Here, we give the proof that BenfordLearner passes the Benford test.

We start with 2 Lemmas.

**Lemma 1: Let $S$ be an irreducible pattern with probability $p$ , and let $Z$ be a Turing machine such that $U T M (Z, N)$ accepts in time $T (N)$ if and only if $N \in S$ . There exists a constant $C$ such that if $N \in S$ , then there exists a $P \in J_{N}$ such that $max Y \in T M (N) B_{N} (Z, Y, P) < C .$ **

Proof: Let $P = \frac{⌊ p N ⌋}{N}$ . From the definition of irreducible pattern, we have that there exists $c$ such that for all $Y$ ,
$| F_{N} (Z, Y) - p | < \frac{c K (Y) \sqrt{log log Q_{N} (Z, Y)}}{\sqrt{Q_{N} (Z, Y)}} .$ Clearly, $| P - p | \leq \frac{1}{N} \leq \frac{1}{Q_{N} (Z, Y)} \leq \frac{1}{\sqrt{Q_{N} (Z, Y)}} \leq \frac{K (Z) K (Y) \sqrt{log log Q_{N} (Z, Y)}}{\sqrt{Q_{N} (Z, Y)}} .$ Setting $C = K (Z) + c$ , we get $| F_{N} (Z, Y) - P | \leq | F_{N} (Z, Y) - p | + | P - p | < \frac{C K (Y) \sqrt{log log Q_{N} (Z, Y)}}{\sqrt{Q_{N} (Z, Y)}},$ so $\frac{| F_{N} (Z, Y) - P | \sqrt{Q_{N} (Z, Y)}}{K (Y) \sqrt{log log Q_{N} (Z, Y)}} < C .$

Clearly, $K (Z) < C$ , so $B_{N} (Z, Y, P) > C$ for all $Y$ . Therefore, $max Y \in T M (N) B_{N} (Z, Y, P) < C .$

$□$

Lemma 2: Let $S$ be an irreducible pattern with probability $p$ , and let $Z$ be a Turing machine such that $U T M (Z, N)$ accepts in time $T (N)$ if and only if $N \in S$ . For all $C$ , for all $ε > 0$ , for all $N$ sufficiently large, for all $P \in J_{N}$ , if $N \in S$ , and $min X \in T M (N) B_{N} (X, Z, P) < C,$ then $| P - p | < ε$ .

Proof: Fix a $C$ and a $ε > 0$ . It suffices to show that for all $N$ sufficiently large, if $N \in S$ and $| P - p | \geq ε$ , then for all $X \in T M (N)$ , we have $B_{N} (X, Z, P) \geq C .$

Observe that since $B_{N} (X, Z, P) \geq K (X)$ , this claim trivially holds when $K (X) \geq C$ . Therefore we only have to check the claim for the finitely many Turing machines expressible in fewer than $C$ bits.

Fix an arbitrary $X$ . Since $S$ is an irreducible pattern, there exists a $c$ such that $| F_{N} (X, Z) - p | < \frac{c K (Z) \sqrt{log log Q_{N} (X, Z)}}{\sqrt{Q_{N} (X, Z)}} .$ We may assume that $S^{'} (X, Z)$ is infinite, since otherwise if we take $N \in S$ large enough, $X \notin T M (N)$ . Thus, by taking $N$ sufficiently large, we can get $Q_{N} (X, Y)$ sufficiently large, and in particular satisfy $\frac{\sqrt{Q_{N} (X, Z)}}{K (Z) \sqrt{log log Q_{N} (X, Z)}} ε \geq C + c .$ Take $N \in S$ large enough that this holds for each $X \in T M (N)$ with $K (X) \geq C$ , and assume $| P - p | \geq ε$ . By the triangle inequality, we have $| F_{N} (X, Z) - P | \geq | P - p | - | F_{N} (X, Z) - p | \geq ε - \frac{c K (Z) \sqrt{log log Q_{N} (X, Z)}}{\sqrt{Q_{N} (X, Z)}} .$ Therefore $B_{N} (X, Z, P) \geq \frac{(ε - \frac{c K (Z) \sqrt{log log Q_{N} (X, Z)}}{\sqrt{Q_{N} (X, Z)}}) \sqrt{Q_{N} (X, Z)}}{K (Z) \sqrt{log log Q_{N} (X, Z)}} = \frac{\sqrt{Q_{N} (X, Z)}}{K (Z) \sqrt{log log Q_{N} (X, Z)}} ε - c \geq C,$ which proves the claim.

$□$

Main Theorem: Let $S$ be an irreducible pattern with probability $p$ . Then $lim \begin{matrix} N \to \infty N \in S \end{matrix} B e n f o r d L e a r n e r (N) = p .$

Proof: Let $Z$ be a Turing machine such that $U T M (Z, N)$ accepts in time $T (N)$ if and only if $N \in S$ .

By considering the case when $X = Z,$ Lemma 1 implies that there exists a constant $C$ such that for all $N$ sufficiently large, there exists a $P \in J_{N}$ such that $max Y \in T M (N) min X \in T M (N) B_{N} (X, Y, P) < C .$

Similarly, using this value of $C$ , and considering the case where $Y = Z$ , Lemma 2 implies that for all $ε > 0$ , for all $N$ sufficiently large, for all $P \in J_{N}$ if $N \in S$ , and $max Y \in T M (N) min X \in T M (N) B_{N} (X, Y, P) < C,$ then $| P - p | \leq ε$ .

Combining these two, we get that for all $ε > 0$ , for all $N$ sufficiently large, if $N \in S$ and if $P$ minimizes $max Y \in T M (N) min X \in T M (N) B_{N} (X, Y, P),$ then $| P - p | \leq ε$ .

Thus, by the lemma from the previous post, we get that for all $ε > 0$ , for all $N$ sufficiently large, if $N \in S$ , then $| B e n f o r d L e a r n e r (N) - p | \leq ε,$ so $lim \begin{matrix} N \to \infty N \in S \end{matrix} B L_{L, T} (N) = p .$

$□$

Corollary 1: Let $S$ be the set of all the Benford test sentences. If $S$ is an irreducible pattern with probability ${log}_{10} (2)$ , then $B e n f o r d L e a r n e r$ passes the Benford Test.

Corollary 2: Let $ϕ$ be a sentence provable in $Z F C$ , and let ${s_{n}}$ be defined by $s_{0} = ϕ$ and $s_{n + 1} = \neg \neg s_{n}$ . Then we have ${lim}_{n \to \infty} B e n f o r d L e a r n e r (s_{n}) = 1.$

**Corollary 3: Let $ϕ$ be a sentence disprovable in $Z F C$ , and let ${s_{n}}$ be defined by $s_{0} = ϕ$ and $s_{n + 1} = \neg \neg s_{n}$ . Then we have ${lim}_{n \to \infty} B e n f o r d L e a r n e r (s_{n}) = 0.$ **

LESSWRONG
LW

LESSWRONG
LW

3

Asymptotic Logical Uncertainty: Passing the Benford Test

3

Ω 2

3

Ω 2