Asymptotic Logical Uncertainty: Passing the Benford Test
post by Scott Garrabrant · 2015-07-06T03:34:36.000Z · LW · GW · 0 commentsContents
Lemma 2: Let S be an irreducible pattern with probability p, and let Z be a Turing machine such that UTM(Z,N) accepts in time T(N) if and only if N∈S. For all C, for all ε>0, for all N sufficiently large, for all P∈JN, if N∈S, and minX∈TM(N)BN(X,Z,P)Main Theorem: Let S be an irreducible pattern with probability p. Then limN→∞N∈SBenfordLearner(N)=p. Corollary 1: Let S be the set of all the Benford test sentences. If S is an irreducible pattern with probability log10(2), then BenfordLearner passes the Benford Test. Corollary 2: Let ϕ be a sentence provable in ZFC, and let {sn} be defined by s0=ϕ and sn+1=¬¬sn. Then we have limn→∞BenfordLearner(sn)=1. None No comments
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 **
0 comments
Comments sorted by top scores.