Crossposted from the AI Alignment Forum. May contain more technical jargon than usual.
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. **