Get the latest tech news
One Collatz Coincidence
A common question people have about Busy Beaver champions is: “What are they doing?” This question sounds sort of objective, but is really a subjective philosophical question. Objectively, the TM is repeatedly evaluating the specific transition table rules until it halts, that’s all. In a sense, this is the “simplest” (smallest) explanation because these champions are literally the ones that “do the most” based on the smallest description.
A related intuition, though harder to formalize, is that Busy Beavers shouldn’t be “cleanly factorizable” into main routines and subroutines—but rather, that the way to maximize runtime should be via “spaghetti code,” or a single n-state amorphous mass. In fact, Pascal Michel discovered in 1993 that many of the top BB(5) TMs simulate iterations of relatively simple Collatz-like functions and he has extended this analysis to many other champions with different numbers of states and symbols on his Behavior of busy beavers website. In fact, there is actually a giant clump of 19 distinct BB(5) TMs that run > 10 million steps and all leave between 4096-4098 marks on the tape!
Or read this on Hacker News