Asymptotic Logical Uncertainty: The Benford Test
This is the second post in a series on Asymptotic Logical Uncertainty.
All Turing Machines we discuss will have no input, and will output an infinite (or finite) sequence of bits. We let denote the th bit output by the Turing machine .
Let be the th Ackermann number as defined in Conway and Guy’s “The Book of Numbers.” Let be a simple enumeration of sentences in first order logic over ZFC. Let be a deterministic Turing machine such that if and only if is provable with proof length at most . We will be discussing Turing machines which are designed to try to guess the output of in a very limited time. It will be clear later why we need to be computable, and therefore must define using bounded proofs.
Given a probabilistic Turing machine , and a Time complexity function , we define an infinite collection of dependent random variables for . is defined to be if outputs the first bits in time at most . If does not output bits in time , then is either 0 or 1 uniformly at random. These random variables are dependent, because we only run once to determine for all .
Let be a probabilistic Turing machine designed to try to guess the output of in time at most . Let be the subset of natural numbers defining the sentences “The first digit of in base 10 is 1.” Let be defined to be 1 if is a power of 10, and otherwise. We say that satisfies the Benford test if
The Benford test is a desired property, because we believe that is always true when is a power of 10, and otherwise is pseudorandomly true with probability . Formally, we are making the assumption that for any probabilistic Turing machine , the probability that for all is in .
The number comes from Benford’s Law. Intuitively, we expect that when is not a power of 10, is true of the time, and is too large for there to be any procedure which predicts better than randomly.
The Benford test is extremely easy to pass if you are allowed to hard code into your algorithm. What is more difficult is finding an algorithm which passes the test in a natural way.
The weak Benford test will refer to the version of the test where the algorithm is allowed to know that it will only be judged on its answers to . This means that instead of trying to predict , the algorithm tries to predict the output of , which is defined to agree with on the th bit when and output a 0 for all other bits. The distinction between the Benford test and the weak Benford test is informal. The only difference is changing the bit string that the algorithm is “trying to predict.”
Next, we will present an algorithm which uses a strategy similar to Solomonoff induction to satisfy the weak Benford test.