https://www.sligocki.com//2024/09/20/collatz-coincidence.html sligocki [ ] About One Collatz Coincidence Sep 20, 2024 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. But this is not a very satisfying answer. The real meaning of this question is not to get the "smallest" explanation, but one that is more coherent or insightful to us as humans. However, must there be a more insightful description of behavior of these champion machines? Before getting into Busy Beaver analysis, I would have expected that they would not generally have such an insightful description. And I was not alone here: In his 2020 survey "The Busy Beaver Frontier" Scott Aaronson conjectures: 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. And yet, as many readers of this blog will be well aware, we can actually describe the behavior of most known Busy Beaver champions in a way that seems relatively simple mathematically. 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. This result led Nick Drozd to claim that Maybe the Spaghetti Code Conjecture is False in 2021. But is this just the streetlight effect? Presumably we are biased towards discovering Turing machines and proving they halt when they have simpler abstractions.^1 With the recent solution of BB(5) and BB (2,4) problems, we now know with certainty that the S(5) and S(2,4) champions are both described by Collatz-like trajectories. ... or perhaps I should say Collatz-like trajectory. Because fellow Discord user Racheline discovered on 4 Sep 2024 (Discord) that they are both effectively simulating the same Collatz-like trajectory! In fact, this Collatz-like trajectory appears to be ubiquitous among Turing machines around this size. Collatz Analyses S(5) Champion The S(5) champion 1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA runs for 47,176,870 steps and leaves 4098 marks on the tape.^2 It was discovered by Heiner Marxen and Jurgen Buntrock in 1989. Pascal Michel provided the following analysis in 1993: Let \[M(n) = 0^\infty \; \text{} \;\; 01 \;\; {(001)}^{k+1} \;\; 1 \;\; 0^\infty \\ \end{array}\] The full trajectory from M(0) is: \[\begin{array}{l} M(0) & \to & M(6) & \to & M(16) & \to & M(34) & \ to & M(64) & \to & \\ M(114) & \to & M(196) & \to & M(334) & \to & M (564) & \to & M(946) & \to & \\ M(1584) & \to & M(2646) & \to & M (4416) & \to & M(7366) & \to & M(12284) & \to & \text{HALT} \end {array}\] S(5) Runner Up The second longest running BB(5) TM 1RB0LD_1LC1RD_1LA1LC_1RZ1RE_1RA0RB runs for 23,554,764 steps and leaves 4097 marks on the tape. It was also discovered by Marxen and Buntrock in 1989. Pascal Michel also provided the following analysis in 1993: Let \[B(n) = 0^\infty \; \text{} \;\; 0^\infty \\ B(3k+2) & \to & B(5k+7) \\ \end{array}\] The full trajectory from B(0) is: \[\begin{array}{l} B(0) & \to & B(3) & \to & B(8) & \to & B(17) & \to & B(32) & \to & \\ B(57) & \to & B(98) & \to & B(167) & \to & B(282) & \to & B(473) & \to & \\ B(792) & \to & B(1323) & \to & B(2208) & \ to & B(3683) & \to & B(6142) & \to & \text{HALT} \end{array}\] If you compare this with the M trajectory, a pattern immediately jumps out. You can directly convert between these trajectories by replacing \(B(n)\) with \(M(2n)\)! And, in fact, we can prove this: \[\begin{array}{lcl} M(2(3k)) & = & M(3(2k)) & \to & M(5(2k) + 6) & = & M(2(5k + 3)) \\ M(2(3k + 1)) & = & M(3(2k) + 2) & \to & \text{Halt} \\ M(2(3k + 2)) & = & M(3(2k+1) + 1) & \to & M(5(2k+1) + 9) & = & M(2 (5k + 7)) \\ \end{array}\] Therefore: \[\begin{array}{lcl} M(2a) \to M(2b) & \iff & B(a) \to B(b) \\ M(2a) \to \text{Halt} & \iff & B(a) \to \text{Halt} \\ \end{array}\] But wait, there's more! 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! Pascal analyzed the other S(5) champion (1RB1RA_1LC1LB_1RA1LD_1RA1LE_1RZ0LC) in his 1993 paper and showed that it simulates the exact same function. I haven't analyzed the rest of them, but I'd gues that they are all taking advantage of equivalent Collatz-like trajectories as well (since they are clumped so tightly). BBB(4) Champion The current 4-state Beeping Busy Beaver (and also Blanking Beaver) champion 1RB1LD_1RC1RB_1LC1LA_0RC0RD runs 32,779,478 steps before becoming a trivial Translated Cycler with period 1. It was discovered by Nick Drozd in 2021. I first analyzed it way back as my second Busy Beaver related blog post here. I actually forgot about that analysis (oops) and re-analyzed it last week! Racheline discovered the connection with the S(5) champion's iteration. Let \[D(n) = 0^\infty \; 1^n \; 0^4 \; \text{D>} \; 0^\infty\] then \[\begin{array}{lcl} 0^\infty \; \text{ 0 \\ \end {array}\] This second rule is where the magic is! Note that the \(R(a+1, b)\) rule effectively combines the two \(L(a+1, b, c)\) cases above. Now, we can simplify this to: \[\begin{array}{lcl} R(0, 3k) & \to & \text{Halt} \\ R(0, 3k+r) & \to & R(0, 5k+5+r) & \text{if } r > 0 \\ \end{array}\] let \(R(n) = R(0, n)\) then \[\begin{array}{lcl} 0^\infty \; \text{