New Busy Beaver Turing Machine program

[Nicholas Drozd]

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

  A0 -> 1RB
  A1 -> 1LC
  B0 -> 1RD
  B1 -> 1RB
  C0 -> 0RD
  C1 -> 0RC
  D0 -> 1LD
  D1 -> 1LA

The classic Busy Beaver problem asks: what is the longest that a
program of N states and K colors can run when started on the blank
tape before executing a halt instruction? This program lacks a halt
instruction, and therefore obviously does not halt, and so it cannot
be a Busy Beaver candidate. (Solving certain instances of the halting
problem is easy!)

But this program does have a certain Busy Beaver-like quality: when
started on the blank tape, it runs for 32,779,477 steps before leaving
the tape blank again. If we modify the Busy Beaver problem to require
leaving the tape blank instead of requiring the execution of a halt
instruction, we get the Blanking Beaver problem, for which this
program is the reigning 4-state 2-color champion.

When the tape becomes blank, the machine is in state C. After one more
step it will be in state D on the blank tape, and thereafter it will
never reach any of its other states again. That is to say, the machine
quasihalts, and so this program is also the reigning 4-state 2-color
champion for Scott Aaronson's Beeping Busy Beaver problem.

Here is a blog post with some additional context:

  - https://nickdrozd.github.io/2021/07/11/self-cleaning-turing-machine.html

Shawn Ligocki has examined the program and determined that it is a
"textbook example of Collatz-like behavior". In particular, it can be
modeled by iterations of the following Collatz-like function:

  * f(3k)     = stop
  * f(3k + 1) = 5k + 4
  * f(3k + 2) = 5k + 5

His analysis is here:

  - https://www.sligocki.com/2021/07/17/bb-collatz.html

For the classic Busy Beaver function BB, it's known that BB(4, 2) =
107 and it's generally believed that BB(5, 2) = 47,176,870. Thus it
appeared that there was a sharp jump in complexity going from four
states to five states. This discovery shows that four states can
already be quite complex, and therefore the jump occurs between three
and four states.

Nick Drozd