Which Collatz numbers do Busy Beavers simulate (if any)?

https://gbragafibra.github.io/2025/10/16/collatz_ant11.html

by Fibra • 9 months ago

43 3 9 months ago

gbragafibra.github.io

To the extent that some champion machines have Collatz-like behavior, it's usually not by iterating a function with randomized scale factors until the value hits zero (like in the original Collatz iteration), but instead by iterating a function with a fixed scale factor until it hits a certain modular value.

E.g., the BB(5) machine [0] repeatedly multiplies a unary counter by 5/3 and adds a small offset, until the value becomes 2 mod 3 and the machine halts. In further domains, these kinds of "halt once a certain modular value is reached" conditions are used to terminate iterated exponentiation and higher operations.

The main similarity with the original Collatz iteration is that the machines repeatedly divide out a certain factor to produce a pseudorandom stream of remainders. In some cases, a machine measures a statistical property of the stream that is expected to hold forever, but cannot easily be proven to do so, as in the infamous Hydra/Antihydra machines [1].

Somewhat curiously, a candidate for the BB(3,3) champion machine [2] does not use any sort of Collatz-like modular-value conditions. Instead, it repeatedly samples points and compares them against the subdivisions of a sort of Cantor set, until one of the points perfectly hits the edge of a subdivision. It's expected to halt after roughly 10^135 iterations.

[0] https://wiki.bbchallenge.org/wiki/5-state_busy_beaver_winner

[1] https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html

[2] https://wiki.bbchallenge.org/wiki/1RB2LC1RC_2LC---2RB_2LA0LB...

pclalv• 9 months ago

It's interesting that the Collatz tapes look like wavy sheets, like a photo of a curtain with a shadow cast over one half. I wonder if there is such a higher-dimensional shape that's underlying these 2D plots, and what that shape might look like from different points of view.

rcxdude• 9 months ago

I think a large part of that is the read head wandering left and right. For any machine that halts in a nontrivial number of steps it would be expected that the head doesn't move monotonically.

Which Collatz numbers do Busy Beavers simulate (if any)?

Related Stories