# Asymptotic Logical Uncertainty: The Benford Test

This is the sec­ond post in a se­ries on Asymp­totic Log­i­cal Uncer­tainty.

All Tur­ing Machines we dis­cuss will have no in­put, and will out­put an in­finite (or finite) se­quence of bits. We let de­note the th bit out­put by the Tur­ing ma­chine .

Let be the th Ack­er­mann num­ber as defined in Con­way and Guy’s “The Book of Num­bers.” Let be a sim­ple enu­mer­a­tion of sen­tences in first or­der logic over ZFC. Let be a de­ter­minis­tic Tur­ing ma­chine such that if and only if is prov­able with proof length at most . We will be dis­cussing Tur­ing ma­chines which are de­signed to try to guess the out­put of in a very limited time. It will be clear later why we need to be com­putable, and there­fore must define us­ing bounded proofs.

Given a prob­a­bil­is­tic Tur­ing ma­chine , and a Time com­plex­ity func­tion , we define an in­finite col­lec­tion of de­pen­dent ran­dom vari­ables for . is defined to be if out­puts the first bits in time at most . If does not out­put bits in time , then is ei­ther 0 or 1 uniformly at ran­dom. Th­ese ran­dom vari­ables are de­pen­dent, be­cause we only run once to de­ter­mine for all .

Let be a prob­a­bil­is­tic Tur­ing ma­chine de­signed to try to guess the out­put of in time at most . Let be the sub­set of nat­u­ral num­bers defin­ing the sen­tences “The first digit of in base 10 is 1.” Let be defined to be 1 if is a power of 10, and oth­er­wise. We say that satis­fies the Ben­ford test if

The Ben­ford test is a de­sired prop­erty, be­cause we be­lieve that is always true when is a power of 10, and oth­er­wise is pseu­do­ran­domly true with prob­a­bil­ity . For­mally, we are mak­ing the as­sump­tion that for any prob­a­bil­is­tic Tur­ing ma­chine , the prob­a­bil­ity that for all is in .

The num­ber comes from Ben­ford’s Law. In­tu­itively, we ex­pect that when is not a power of 10, is true of the time, and is too large for there to be any pro­ce­dure which pre­dicts bet­ter than ran­domly.

The Ben­ford test is ex­tremely easy to pass if you are al­lowed to hard code into your al­gorithm. What is more difficult is find­ing an al­gorithm which passes the test in a nat­u­ral way.

The weak Ben­ford test will re­fer to the ver­sion of the test where the al­gorithm is al­lowed to know that it will only be judged on its an­swers to . This means that in­stead of try­ing to pre­dict , the al­gorithm tries to pre­dict the out­put of , which is defined to agree with on the th bit when and out­put a 0 for all other bits. The dis­tinc­tion be­tween the Ben­ford test and the weak Ben­ford test is in­for­mal. The only differ­ence is chang­ing the bit string that the al­gorithm is “try­ing to pre­dict.”

Next, we will pre­sent an al­gorithm which uses a strat­egy similar to Solomonoff in­duc­tion to satisfy the weak Ben­ford test.

• Char­lie, note that I am talk­ing about the first digit of A(n), not the last digit. The par­ity of A(n) does not mat­ter much. The rea­son pow­ers of 10 are spe­cial is that the A(n) is a power of 10, and must start with a 1.

I per­son­ally be­lieve the as­sump­tion I am mak­ing about S, but if you do not, you can re­place it with some other se­quence that you be­lieve is pseu­do­ran­dom.

• This af­terthought con­fused me. I spent fif­teen min­utes try­ing to figure out why you claim that Ack­er­mann num­bers are all pow­ers of 10 and start with 1. I guess you wanted to write some­thing like: »The rea­son […] is that if n is a power of 10, A(n) must be a power of 10, and start with a 1« Right?

• Oh, whoops! Man­aged to con­fuse my­self. I’m not to­tally sure about Ben­ford’s law, but am happy to as­sume for the sake of ar­gu­ment now that I’m not ac­tu­ally de­luded.

Dou­ble Edit: Hm, the con­verse of the equidis­tri­bu­tion the­o­rem doesn’t hold even close to as strictly as I thought it did. Nev­er­mind me.

• (ed­ited) I dunno that I buy that the Ben­ford test is a desider­a­tum at all lev­els of com­pu­ta­tional re­sources (if n is even, A(n) is even), but I’m still pretty hyped that you’re post­ing about log­i­cal un­cer­tainty.

Ac­tu­ally, now I’m cu­ri­ous about the mod­ulo ar­ith­metic prop­er­ties of Ack­er­mann’s func­tion.