This is post is part of the Asymptotic Logical Uncertainty series. This is about a failed attempt to satisfy the Benford test. I will not prove things about this approach. The only reason I am including this approach is because the fact that it does not work is surprising and insightful.
Let Geometric(12) be the function which outputs n∈N with probability 2−m.
Fix a prefix-free encoding of probabilistic Turing machines, and let ℓ(M) denote the number of bits used to encode M. Let RTM(k) be the function which outputs the Turing machine M with probability proportional to 2−kμ(M).
Fix E, a deterministic Turing Machine (for example E=L). Fix a time complexity function T(n) and another time complexity function R(n)∈o(T(n)logT(n)). Consider the following algorithm.
SIA(E,T,R)
1: n=0
2: N=1
3: M=RTM(3)
4: g=Geometric(1/2)
5: loop
6: if 4^n*R(N)*log(R(N))*N<T(N) then
7: run E for one more time step
8: if E outputs another bit then
9: n=n+1
10: repeat
11: M=RTM(3)
12: g=Geometric(1/2)
13: until M^{gR}(i)=E(i) for all i<=n
14: output M^{gR}(N)
15: N=N+1
This code is inspired by Solomonoff Induction. We cannot directly apply Solomonoff induction, because the lack of a time bound. Solomonoff induction would pick out the program E, but that will not allow us to predict E quickly. We have to restrict the run times of the programs to ensure that they can compute their Nth bit in time T(N).
When trying to predict E(N), we compute the first n values of E for some n much smaller than N. We then sample probabilistic Turing machines until we find one that quickly gets all of these first n bits correct. We use that Turing machine to compute our guess at E(N).
The purpose of the geometric random variable g is to make the time we allow the sampled Turing machines to run more flexible. The sampled Turing machines can take any amount of time in O(T(i)) but get an extra penalty for the size of the constant. The fact that we use RTM(3) instead of RTM(1) is to make the proof that it satisfies the weak Benford test work, RTM(1) would probably work too. Line 6 is only to make sure it runs in time R(N).
SIA(L,T,R) passes the weak Benford test, but probably fails the Benford test.
First, let me explain why we thought this approach would work. If you sample a Turing machine M that is very likely to get all of the bits correct, but gives suboptimal probabilities on the Benford test sentences, then you can modify that program to form a program that outputs 1 with probability B(n) for the Benford test sentences, and follows M otherwise.
This modified program M′ will be just as likely to get all the non-Benford sentences correct, and more likely to get the the Benford sentences correct. Further, this improvement on the Benford sentences is unbounded as you consider more and more sentences, and therfore eventually pays for all of the cost associated with replacing M with M′.
The problem is that while M′ is more likely to get the Benford sentences correct, we are not optimizing for programs that are likely to get the Benford sentences correct. Instead, we are optimizing for programs that are likely to get the Benford sentences correct conditioned on getting all the other questions correct.
At first, this may not seem like much of problem. The programs are entangling their results on some inputs with their results on other inputs. The problem comes from the fact that sometimes the program tries to entangle its results with a much much earlier sentence, and when the program was answering that earlier sentence it had much less time to think.
To give a concrete example of why this is a problem, consider the sentence: tn=”The first digit of A(n) is a 1 if and only if the first digit of A(A(n)) is a 1.”
The probability we should assign to this sentence is (1log10)2+(1−1log10)2. However, by the time we have to assign a probability to the A(n)th Benford sentence, we may have already calculated the first digit of A(n) and seen that it is a 1. In which case, to maximize the probability of getting all the bits correct, we have to have our answer to the A(n)th Benford sentence match our answer to tn.
The correct thing to do would be to update the probability assigned to tn when observing that the first digit of A(n) is a 1. However, that is not possible, so the next best thing is to change the answer to the A(n)th Benford sentence, which causes it to give the wrong answer.
I believe that the fact that this program does not work can be extended to an impossibility result saying that any program which loops through Turing machines, gives them a score based on how many answers they get correct, and samples according to their complexity and their score, must fail the Benford test.
Asymptotic Logical Uncertainty: Solomonoff Induction Inspired Approach
This is post is part of the Asymptotic Logical Uncertainty series. This is about a failed attempt to satisfy the Benford test. I will not prove things about this approach. The only reason I am including this approach is because the fact that it does not work is surprising and insightful.
Let Geometric(12) be the function which outputs n∈N with probability 2−m.
Fix a prefix-free encoding of probabilistic Turing machines, and let ℓ(M) denote the number of bits used to encode M. Let RTM(k) be the function which outputs the Turing machine M with probability proportional to 2−kμ(M).
Fix E, a deterministic Turing Machine (for example E=L). Fix a time complexity function T(n) and another time complexity function R(n)∈o(T(n)logT(n)). Consider the following algorithm.
This code is inspired by Solomonoff Induction. We cannot directly apply Solomonoff induction, because the lack of a time bound. Solomonoff induction would pick out the program E, but that will not allow us to predict E quickly. We have to restrict the run times of the programs to ensure that they can compute their Nth bit in time T(N).
When trying to predict E(N), we compute the first n values of E for some n much smaller than N. We then sample probabilistic Turing machines until we find one that quickly gets all of these first n bits correct. We use that Turing machine to compute our guess at E(N).
The purpose of the geometric random variable g is to make the time we allow the sampled Turing machines to run more flexible. The sampled Turing machines can take any amount of time in O(T(i)) but get an extra penalty for the size of the constant. The fact that we use RTM(3) instead of RTM(1) is to make the proof that it satisfies the weak Benford test work, RTM(1) would probably work too. Line 6 is only to make sure it runs in time R(N).
SIA(L,T,R) passes the weak Benford test, but probably fails the Benford test.
First, let me explain why we thought this approach would work. If you sample a Turing machine M that is very likely to get all of the bits correct, but gives suboptimal probabilities on the Benford test sentences, then you can modify that program to form a program that outputs 1 with probability B(n) for the Benford test sentences, and follows M otherwise.
This modified program M′ will be just as likely to get all the non-Benford sentences correct, and more likely to get the the Benford sentences correct. Further, this improvement on the Benford sentences is unbounded as you consider more and more sentences, and therfore eventually pays for all of the cost associated with replacing M with M′.
The problem is that while M′ is more likely to get the Benford sentences correct, we are not optimizing for programs that are likely to get the Benford sentences correct. Instead, we are optimizing for programs that are likely to get the Benford sentences correct conditioned on getting all the other questions correct.
At first, this may not seem like much of problem. The programs are entangling their results on some inputs with their results on other inputs. The problem comes from the fact that sometimes the program tries to entangle its results with a much much earlier sentence, and when the program was answering that earlier sentence it had much less time to think.
To give a concrete example of why this is a problem, consider the sentence: tn=”The first digit of A(n) is a 1 if and only if the first digit of A(A(n)) is a 1.”
The probability we should assign to this sentence is (1log10)2+(1−1log10)2. However, by the time we have to assign a probability to the A(n)th Benford sentence, we may have already calculated the first digit of A(n) and seen that it is a 1. In which case, to maximize the probability of getting all the bits correct, we have to have our answer to the A(n)th Benford sentence match our answer to tn.
The correct thing to do would be to update the probability assigned to tn when observing that the first digit of A(n) is a 1. However, that is not possible, so the next best thing is to change the answer to the A(n)th Benford sentence, which causes it to give the wrong answer.
I believe that the fact that this program does not work can be extended to an impossibility result saying that any program which loops through Turing machines, gives them a score based on how many answers they get correct, and samples according to their complexity and their score, must fail the Benford test.