Skip to content(if available)orjump to list(if available)

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

LegionMammal978

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...

null

[deleted]