from Hacker News

Striking new Beeping Busy Beaver champion

by bdr on 7/28/21, 1:36 AM with 13 comments

• by suyjuris on 7/28/21, 9:29 AM

  Busy Beaver-type functions (counting how long a program runs, provided that it terminates) might look like a mere curiosity, but they make interesting statements about the power of different systems of computation. For Turing machines it grows quicker than any computable function – and Turing machines are quite powerful!

  If you consider a finite-state automaton, you might define a similar problem: What is the longest word that automaton accepts, provided that it accepts only finitely many words? This you can answer directly: it is n-1, where n is the number of states. And finite-state automata are not very powerful.

  Here is another system: I give you a list of transactions, where each transaction consists of multiple instructions of the form “add/remove x units from account y”. You may only execute a transaction if no account goes negative. Here, a Busy Beaver-type question would be “What is the longest sequence of transactions that move one unit from the first account to the second, where all the others must start and end empty?” This is actually a somewhat powerful system, and here the answer grows at the rate of the Ackermann function – extremely fast (and, if you have never heard of it, probably faster than any computable function you can think of), but still computable. [1]

  Recently we have shown a Busy Beaver-type result for a certain distributed computation model, where many (very limited) participants interact to compute things as a group. There the question was about counting how large the group is, but each participant can only count to n. So given a protocol that reliably recognises certain group sizes, what is the largest size it accepts? (Again, provided that it accepts only finitely many.) We proved that it is at most 2^(2^(2^n)) – so in some sense that model is very weak, but nevertheless much more powerful that finite state automata.

  [1] I did not think to carefully about this, some details might be wrong.

• by alanbernstein on 7/28/21, 5:01 AM

  I wasn't aware of the "Collatz-like iterative process" for BB lower bounds.

  That seems to suggest that the collatz conjecture sits somewhere close to the "edge of computability", which really fits well with Erdos' quote "Mathematics may not be ready for such problems."

• by 6nf on 7/28/21, 6:36 AM

      A0 -> 1RB
      A1 -> 1LC
      B0 -> 1RD
      B1 -> 1RB
      C0 -> 0RD
      C1 -> 0RC
      D0 -> 1LD
      D1 -> 1LA
  

  I'm guessing A0 -> 1RB means 'If the state is A and the symbol read from tape is 0 then change the tape symbol to 1, move right, and change the state to B'

• by isoprophlex on 7/28/21, 5:26 AM

  > The first three of these, I managed to get on my own, with the help of a QBasic program I wrote.

  Amazing :)

• by galaxyLogic on 7/28/21, 6:44 AM

  Looks like great fun with very big numbers.

  I wonder can something similar be defined in terms of Lambda Calculus?

• by fjfaase on 7/28/21, 8:02 AM

  There is also a Busy Beaver like problem with respect to (a modified version of) Brainfuck: https://www.iwriteiam.nl/Ha_bf_numb.html