[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)