New Busy Beaver Turing Machine program

[Nicholas Drozd]

I recently discovered a remarkable 2-state 4-color Turing machine
program:

  A0 -> 1RB
  A1 -> 2RA
  A2 -> 1RA
  A3 -> 2RB

  B0 -> 2LB
  B1 -> 3LA
  B2 -> 0RB
  B3 -> 0RA

When started on the blank tape, this program runs for
1,367,361,263,049 steps before the tape becomes blank again.

The classic Busy Beaver (BB) problem asks how long an N-state K-color
TM program started on the blank tape can run before executing a halt
instruction. The Blanking Beaver (BLB) problem is similar, except that
instead of requiring programs to execute a halt instruction, programs
are required to wipe the tape clean.

It has been known since 2005 that BB(2, 4) >= 3,932,964, and it is now
known that

  * BLB(2, 4) >= 1,367,361,263,049

About seven million steps before the blank tape is reached, the
program gets into state B and never reaches state A again. That is to
say, it quasihalts, and so this program is also a candidate for Scott
Aaronson's Beeping Busy Beaver problem, with

  * BBB(2, 4) >= 1,367,354,345,128

My feeling, which is by no means a proof, is that the BLB bound here
is tight but the BBB bound may not be. Quasihalting is a slippery
termination predicate. In fact, it is impossible to detect in general,
and that makes BBB a super-uncomputable function. In contrast, the
blank tape is easy to detect. So even though BLB seems to grow faster
than BB, BLB is "just regular" uncomputable, co-computable with BB.

Shawn Ligocki analyzed the program and found that, as is typical for
long-running short TM programs, it implements a Collatz-like function.
This time it is a parameterized Collatz function.

Let h : (a, b : Nat) -> Nat be defined as follows:

  * h(a, 2n + 1) = h(a + 1, 5n + 2)
  * h(2m + 1, 2n) = h(1, 5m + 5n + 3)
  * h(2m, 2n) = 0

This program, describable with just 32 bits, calculates
h(1, 2), which has a rather long trajectory:

  h(1, 2)
  h(1, 8)
  h(1, 23)
    h(2, 57)
      h(3, 142)
  h(1, 363)
    h(2, 907)
      h(3, 2267)
        h(4, 5667)
          h(5, 14167)
            h(6, 35417)
              h(7, 88542)
  h(1, 221373)
    h(2, 553432)  ;; both args even
  0

Is this function total? That is, do we have h(a, b) = 0 for all a, b?

Can the Collatz function be proved total by assuming that this one is?

Nobody knows!

Here is a blog post with more context:

  - https://nickdrozd.github.io/2022/01/10/another-self-cleaning-turing-machine.html

And here is the FOM posting from July 2021 to announce the discovery
of the (presumed) 4-state 2-color BLB / BBB champion:

  - https://cs.nyu.edu/pipermail/fom/2021-July/022743.html