Striking new Beeping Busy Beaver champion | Hacker News Reader

Striking new Beeping Busy Beaver champion

scottaaronson.com

91 pointsbdr13 comments

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.

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."

The "generalized collatz conjecture" (rather than 3n+1 and n/2 we use some a*n+k) was proven by the wonderful John Conway to be undecidable [0] by inventing a toy language called FRACTRAN [1] and showing that it was turing complete.

It would be so wonderful to show that 3n+1 and n/2 are enough to compute anything - writing "programs" this way would be fun to look at.

[0]: https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable...

[1]: https://en.wikipedia.org/wiki/FRACTRAN

There’s another possible explanation: Collatz-type recurrences are the most complex behaviors that can be encoded using a tiny number of Turing machine states, due to the way TMs access memory. From another comment, it turns out you can apply similar busy-beaver definitions to the lambda calculus, but you get very different results for small structures due to the innate recursive structure of the lambda calculus.

Of course, if you have enough states in your Turing machine, or enough terms in your lambda expression, you can express any computation. The interesting thing is what happens when you look at small instances of each.

    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'

This should help: https://nickdrozd.github.io/2020/10/04/turing-machine-notati...

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

Amazing :)

Yes, I loved it. Anyway uncomputable functions find all languages weak.

Looks like great fun with very big numbers.

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

Indeed it can:

https://mathoverflow.net/questions/353514/whats-the-smallest...

https://oeis.org/A333479

When I was working on a similar problem with respect to calculating numbers with a version of Brainfuck where each cell can contain any natural number, I remember feeling some kind of mental nausea about how big numbers can get.

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

For Brainfuck one could also define a Busy Beaver problem like the maximum number of steps before a given Brainfuck program stops. But you need to define what counts as a step. I would say that executing a command from the program counts as one step, meaning that the interpretation of '[' does not count all the commands that are skipped when the current memory cell is 0.

Reply on news.ycombinator.com