[HN Gopher] A Busy Beaver champion derived from scratch ___________________________________________________________________ A Busy Beaver champion derived from scratch Author : nickdrozd Score : 43 points Date : 2021-11-17 21:16 UTC (1 hours ago) (HTM) web link (nickdrozd.github.io) (TXT) w3m dump (nickdrozd.github.io) | Y_Y wrote: | 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. | robbedpeter wrote: | ADHD Aardvark, maybe? | codeulike wrote: | Makework Manatee? | throwaway81523 wrote: | Summary: brute force search of the space of 4-state TM programs | yielded a BB champion with a 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(3k+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. | | 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. | | 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. | | 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 functions on some parameter, expressed as N-state | programs, being Pi-0-2 complete. | codeulike wrote: | So what does "colour" means with regards to Turing Machines? | brilee wrote: | a typo in the collatz description: | | C (2k + 1) = C (3k + 2) | | should be | | C (2k + 1) = C (6k + 4) | mattashii wrote: | yes, but note that those two are the same when C (2k) is | applied as well. C (2k + 1) = C (3k + 2) saves you one step of | computation, which can save you a lot of time if you're | applying the steps. ___________________________________________________________________ (page generated 2021-11-17 23:00 UTC)