Summary: brute force search of the space of 4-state TM programs yielded a BB champion with an initially mysterious structure. Careful examination and reverse engineering showed that the program turns out to compute a variant of the Collatz function, where instead of C(n:odd)=3n+1, we have L(3k)=0 and L(3k+r)=L(5k+r+3). There is discussion of a "spaghetti conjecture" that BB champions are likely to be "messes" (i.e. have complete control flow graphs), but this Collatz example doesn't satisfy that criterion. Thus the author suggests that the spaghetti conjecture is false.<p>Discussion: the whole thing is very encoding dependent, but if you figure the BB machine on N states is randomly distributed on all the N-state machines, then for the types of encodings being discussed, for large N, the flow graph has (I think) a high chance of being complete but that is not guaranteed. So that's a reason to think the conjecture is strictly false but approximately true.<p>The BB champ being a Collatz variant is iirc a well known approach to manually constructed BB champs. That is inspired by an old result (Conway's?) found in Jeff Lagarias's book on the 3n+1 problem. It says the generalized Collatz conjecture is Pi-0-2 complete so specific instances sound like a good place to look for functions that are on the edge of undecidability.<p>I wonder if anything is known about the arithmetic (not computational) complexity of random programs like that. I'm imaginging e.g. Shannon's theorem that most boolean functions on N inputs require exponentially many gates to compute. The analogy would be with the likelihood of functions on some parameter, expressed as N-state programs, being Pi-0-2 complete.
Great writeup! I ended up following a few of the links and came across perhaps my favorite hand waving of all time for the validity of "The Spaghetti Code Conjecture"[1]. Basically:<p>For N=0,1: the problem is trivaial/degenerate.<p>For N=2: the Turing machine must go back and forth between states or else it'd just be stuck in one state forever, which wouldn't be very busy beaverish.<p>For N=n+1: well we just proved it up till n, so it seems pretty unlikely that n+1 would be different, things don't really just suddenly change like that y'know?<p>QED<p>So I'm not too surprised that this conjecture is being called into question.<p>[1]: <a href="https://nickdrozd.github.io/2021/01/26/spaghetti-code-conjecture.html" rel="nofollow">https://nickdrozd.github.io/2021/01/26/spaghetti-code-conjec...</a>
Cool post. Moving the goalposts a little bit, since it's not the same Busy Beaver problem that's normally considered. I think that its an interesting problem in its own right, but deserves a different label, since the beaver never halts but rather gets bored and wanders off.
Can something really be called a Turing machine if it's not able to halt (or continue going) by itself?<p>In this case it appears that the author considers halting to be decided externally to the program, which is not the mechanism Turing machines use.