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 UTM(Z,N) accepts in time T(N) if and only if N∈S. There exists a constant C such that if N∈S, then there exists a P∈JN such that maxY∈TM(N)BN(Z,Y,P)<C.
**
Proof: Let P=⌊pN⌋N. From the definition of irreducible pattern, we have that there exists c such that for all Y, |FN(Z,Y)−p|<cK(Y)√loglogQN(Z,Y)√QN(Z,Y).
Clearly,
|P−p|≤1N≤1QN(Z,Y)≤1√QN(Z,Y)≤K(Z)K(Y)√loglogQN(Z,Y)√QN(Z,Y).
Setting C=K(Z)+c, we get
|FN(Z,Y)−P|≤|FN(Z,Y)−p|+|P−p|<CK(Y)√loglogQN(Z,Y)√QN(Z,Y),
so
|FN(Z,Y)−P|√QN(Z,Y)K(Y)√loglogQN(Z,Y)<C.
Clearly, K(Z)<C, so BN(Z,Y,P)>C for all Y. Therefore, maxY∈TM(N)BN(Z,Y,P)<C.
□
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)<C, then |P−p|<ε.
Proof: Fix a C and a ε>0. It suffices to show that for all N sufficiently large, if N∈S and |P−p|≥ε, then for all X∈TM(N), we have BN(X,Z,P)≥C.
Observe that since BN(X,Z,P)≥K(X), this claim trivially holds when K(X)≥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
|FN(X,Z)−p|<cK(Z)√loglogQN(X,Z)√QN(X,Z).
We may assume that S′(X,Z) is infinite, since otherwise if we take N∈S large enough, X∉TM(N). Thus, by taking N sufficiently large, we can get QN(X,Y) sufficiently large, and in particular satisfy √QN(X,Z)K(Z)√loglogQN(X,Z)ε≥C+c.
Take N∈S large enough that this holds for each X∈TM(N) with K(X)≥C, and assume |P−p|≥ε. By the triangle inequality, we have
|FN(X,Z)−P|≥|P−p|−|FN(X,Z)−p|≥ε−cK(Z)√loglogQN(X,Z)√QN(X,Z). Therefore BN(X,Z,P)≥(ε−cK(Z)√loglogQN(X,Z)√QN(X,Z))√QN(X,Z)K(Z)√loglogQN(X,Z)=√QN(X,Z)K(Z)√loglogQN(X,Z)ε−c≥C, which proves the claim.
□
Main Theorem: Let S be an irreducible pattern with probability p. Then limN→∞N∈SBenfordLearner(N)=p.
Proof: Let Z be a Turing machine such that UTM(Z,N) accepts in time T(N) if and only if N∈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∈JN such that maxY∈TM(N)minX∈TM(N)BN(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∈JN if N∈S, and maxY∈TM(N)minX∈TM(N)BN(X,Y,P)<C, then |P−p|≤ε.
Combining these two, we get that for all ε>0, for all N sufficiently large, if N∈S and if P minimizes maxY∈TM(N)minX∈TM(N)BN(X,Y,P), then |P−p|≤ε.
Thus, by the lemma from the previous post, we get that for all ε>0, for all N sufficiently large, if N∈S, then |BenfordLearner(N)−p|≤ε, so limN→∞N∈SBLL,T(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.
**Corollary 3: Let ϕ be a sentence disprovable in ZFC, and let {sn} be defined by s0=ϕ and sn+1=¬¬sn. Then we have limn→∞BenfordLearner(sn)=0.
**
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 UTM(Z,N) accepts in time T(N) if and only if N∈S. There exists a constant C such that if N∈S, then there exists a P∈JN such that maxY∈TM(N)BN(Z,Y,P)<C. **
Proof: Let P=⌊pN⌋N. From the definition of irreducible pattern, we have that there exists c such that for all Y,
|FN(Z,Y)−p|<cK(Y)√loglogQN(Z,Y)√QN(Z,Y). Clearly, |P−p|≤1N≤1QN(Z,Y)≤1√QN(Z,Y)≤K(Z)K(Y)√loglogQN(Z,Y)√QN(Z,Y). Setting C=K(Z)+c, we get |FN(Z,Y)−P|≤|FN(Z,Y)−p|+|P−p|<CK(Y)√loglogQN(Z,Y)√QN(Z,Y), so |FN(Z,Y)−P|√QN(Z,Y)K(Y)√loglogQN(Z,Y)<C.
Clearly, K(Z)<C, so BN(Z,Y,P)>C for all Y. Therefore, maxY∈TM(N)BN(Z,Y,P)<C.
□
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)<C, then |P−p|<ε.
Proof: Fix a C and a ε>0. It suffices to show that for all N sufficiently large, if N∈S and |P−p|≥ε, then for all X∈TM(N), we have BN(X,Z,P)≥C.
Observe that since BN(X,Z,P)≥K(X), this claim trivially holds when K(X)≥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 |FN(X,Z)−p|<cK(Z)√loglogQN(X,Z)√QN(X,Z). We may assume that S′(X,Z) is infinite, since otherwise if we take N∈S large enough, X∉TM(N). Thus, by taking N sufficiently large, we can get QN(X,Y) sufficiently large, and in particular satisfy √QN(X,Z)K(Z)√loglogQN(X,Z)ε≥C+c. Take N∈S large enough that this holds for each X∈TM(N) with K(X)≥C, and assume |P−p|≥ε. By the triangle inequality, we have |FN(X,Z)−P|≥|P−p|−|FN(X,Z)−p|≥ε−cK(Z)√loglogQN(X,Z)√QN(X,Z). Therefore BN(X,Z,P)≥(ε−cK(Z)√loglogQN(X,Z)√QN(X,Z))√QN(X,Z)K(Z)√loglogQN(X,Z)=√QN(X,Z)K(Z)√loglogQN(X,Z)ε−c≥C, which proves the claim.
□
Main Theorem: Let S be an irreducible pattern with probability p. Then limN→∞N∈SBenfordLearner(N)=p.
Proof: Let Z be a Turing machine such that UTM(Z,N) accepts in time T(N) if and only if N∈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∈JN such that maxY∈TM(N)minX∈TM(N)BN(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∈JN if N∈S, and maxY∈TM(N)minX∈TM(N)BN(X,Y,P)<C, then |P−p|≤ε.
Combining these two, we get that for all ε>0, for all N sufficiently large, if N∈S and if P minimizes maxY∈TM(N)minX∈TM(N)BN(X,Y,P), then |P−p|≤ε.
Thus, by the lemma from the previous post, we get that for all ε>0, for all N sufficiently large, if N∈S, then |BenfordLearner(N)−p|≤ε, so limN→∞N∈SBLL,T(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.
**Corollary 3: Let ϕ be a sentence disprovable in ZFC, and let {sn} be defined by s0=ϕ and sn+1=¬¬sn. Then we have limn→∞BenfordLearner(sn)=0. **