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.