New Busy Beaver Turing Machine program
Nicholas Drozd
nicholasdrozd at gmail.com
Mon Jul 19 12:45:03 EDT 2021
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
More information about the FOM
mailing list