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 be an irreducible pattern with probability , and let be a Turing machine such that accepts in time if and only if . There exists a constant such that if , then there exists a such that **

Proof: Let . From the definition of irreducible pattern, we have that there exists such that for all ,
Clearly, Setting , we get so

Clearly, , so for all . Therefore,

Lemma 2: Let be an irreducible pattern with probability , and let be a Turing machine such that accepts in time if and only if . For all , for all , for all sufficiently large, for all , if , and then .

Proof: Fix a and a . It suffices to show that for all sufficiently large, if and , then for all , we have

Observe that since , this claim trivially holds when . Therefore we only have to check the claim for the finitely many Turing machines expressible in fewer than bits.

Fix an arbitrary . Since is an irreducible pattern, there exists a such that We may assume that is infinite, since otherwise if we take large enough, . Thus, by taking sufficiently large, we can get sufficiently large, and in particular satisfy Take large enough that this holds for each with , and assume . By the triangle inequality, we have Therefore which proves the claim.

Main Theorem: Let be an irreducible pattern with probability . Then

Proof: Let be a Turing machine such that accepts in time if and only if .

By considering the case when Lemma 1 implies that there exists a constant such that for all sufficiently large, there exists a such that

Similarly, using this value of , and considering the case where , Lemma 2 implies that for all , for all sufficiently large, for all if , and then .

Combining these two, we get that for all , for all sufficiently large, if and if minimizes then .

Thus, by the lemma from the previous post, we get that for all , for all sufficiently large, if , then so

Corollary 1: Let be the set of all the Benford test sentences. If is an irreducible pattern with probability , then passes the Benford Test.

Corollary 2: Let be a sentence provable in , and let be defined by and . Then we have

**Corollary 3: Let be a sentence disprovable in , and let be defined by and . Then we have **

New Comment