On the hardness of knowing BB(15,2) and BB(5,4)

[Tristan Stérin]

Dear all,

I wanted to share with you a result that Damien and I worked on recently, available at https://arxiv.org/abs/2107.12475, and that we are currently submitting to conferences.

While doing some research on a set of 6 Wang tiles that can simulate the Collatz process (https://arxiv.org/abs/2106.12341, Appendix A), we stumbled across the following Collatz-related conjecture formulated by Erdõs in 1979: "For all n > 8, there is at least one 2 in the base-3 representation of 2^n".

While it looks inoffensive and simple, this conjecture is very hard because the patterns of digits in successive powers of 2 in base 3 are chaotic (as shown in the attached Figure 1 of the paper). The conjecture is Collatz related on an intuitive level rather than formal. Terrence Tao makes that connection on its blog (look for paragraph starting with "One possible toy model problem"): https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/. Our link to Collatz is that we can run both systems with the same 6 Wang tiles.

We noticed that this conjecture is very amenable to being encoded by Turing machines. In fact, there is a simple 5-state 4-symbol machine that halts if and only if the conjecture is false (i.e. if it found a counterexample): given in Figure 3 in https://arxiv.org/abs/2107.12475.

We then simulate this 5-state 4-symbol machine with a 15-state 2-symbol one by using a few tricks to reduce the number of states as much as we could (this is the code-golfing part). The 2-symbol machine is given in Figure 4.

Note that it was dear to our heart to give complete (and hopefully correct) proofs of correctness for these machines.

This result intuitively implies that knowing BB(15,2) is very hard, mathematically. Because you would have to settle the case of that particular machine, which amounts to solving a conjecture opened for decades. Hence, this gives a sense that the remaining knowable BB values (for 2-symbol) are really situated somewhere between BB(5) and BB(15). Finally, our simulation technique (starting from a 4-symbol machine), although it is conceptually simple, gives a general method to transfer hardness results between BB values.

Our work goes in the lineage of other results interested in this notion of "mathematical hardness" which were presented in a really cool paper by Scott Aaronson (https://www.scottaaronson.com/papers/bb.pdf) such as the 27-state machine for Goldbach's conjecture,  or the ~700-state machines for Riemann hypothesis and the consistency of ZFC, which, although not published, improve on the already impressive results of Yedidia & Aaronson, 2016, https://arxiv.org/abs/1605.04343.

I would happy to discuss this topic further with you, and Damien is persuaded that we can further reduce our 15 states so there is perhaps some room left for code-golfing here!

Sincerely yous,

Tristan Stérin

https://dna.hamilton.ie/tsterin/