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 $M (n)$ denote the $n$ th bit output by the Turing machine $M$ .

Let $A (n) = n ↑^{n} n$ be the $n$ th Ackermann number as defined in Conway and Guy’s “The Book of Numbers.” Let $ϕ_{1}, ϕ_{2}, \dots$ be a simple enumeration of sentences in first order logic over ZFC. Let $L$ be a deterministic Turing machine such that $L (n) = 1$ if and only if $ϕ_{n}$ is provable with proof length at most $A (n)$ . We will be discussing Turing machines which are designed to try to guess the output of $L$ in a very limited time. It will be clear later why we need $L$ to be computable, and therefore must define $L$ using bounded proofs.

Given a probabilistic Turing machine $M$ , and a Time complexity function $T$ , we define an infinite collection of dependent random variables $M^{T} (n)$ for $n \geq 1$ . $M^{T} (n)$ is defined to be $M (n)$ if $M$ outputs the first $n$ bits in time at most $T (n)$ . If $M$ does not output $n$ bits in time $T (n)$ , then $M^{T} (n)$ is either 0 or 1 uniformly at random. These random variables are dependent, because we only run $M$ once to determine $M^{T} (n)$ for all $n$ .

Let $M$ be a probabilistic Turing machine designed to try to guess the output of $L$ in time at most $T (n) = 2^{n}$ . Let $S = {s_{1}, s_{2}, \dots}$ be the subset of natural numbers defining the sentences $ϕ_{s_{n}} =$ “The first digit of $A (n)$ in base 10 is 1.” Let $B (n)$ be defined to be 1 if $n$ is a power of 10, and $\frac{1}{log 10}$ otherwise. We say that $M$ satisfies the Benford test if

${lim}_{n \to \infty} | P (M^{T} (s_{n}) = 1) - B (n) | = 0.$

The Benford test is a desired property, because we believe that $ϕ_{s_{n}}$ is always true when $n$ is a power of 10, and otherwise is pseudorandomly true with probability $\frac{1}{log 10}$ . Formally, we are making the assumption that for any probabilistic Turing machine $M$ , the probability that $M^{T} (s_{i}) = L (s_{i})$ for all $1 \leq i \leq n$ is in $O (\prod_{i = 1}^{n} | L (s_{i}) + B (i) - 1 |)$ .

The number $\frac{1}{log 10}$ comes from Benford’s Law. Intuitively, we expect that when $n$ is not a power of 10, $ϕ_{s_{n}}$ is true $\frac{1}{log 10}$ of the time, and $A (n)$ is too large for there to be any procedure which predicts $ϕ_{s_{n}}$ better than randomly.

The Benford test is extremely easy to pass if you are allowed to hard code $B (i)$ 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 $ϕ_{s_{n}}$ . This means that instead of trying to predict $L$ , the algorithm tries to predict the output of $L_{S}$ , which is defined to agree with $L$ on the $n$ th bit when $n \in S$ 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.