alan2here
commented
2 years ago I've been thinking about this in other computational environments, such as some very minimal esoteric programming languages (programs of a given size outputting the largest integer or having the longest runtime). Like turing machines, these languages are designed to have very few and simple instructions that do not do much individually, making programs extremely long.
The advantage of this length is that it's like being able to have a fractional numbers of states in a turing machine, giving more resolution as to what is gained with longer programs, or in your case more complicated machines.
Finding busy beavers by hand in collaboration with others, as longer programs were included, I saw liner growth in the size of the output, followed by polynomial, and then exponential, as well as less tidy iterative polynomial/exponentials, and finally higher ranking hyper-operations.
This function (of program length to output length) grows too quickly to be computable, but it strikes me that eventually it runs into some difficulty with things like the collatz conjecture, especially if the conjecture proves to be provably unprovable.
Many mathematical sequences have properties that may or may not hold, despite having been tested up to truly huge numbers, it's hard to test larger busy beavers when even very short programs can test theorems that may need to be run to beyond the heat death of the universe to yeild a result.
sligocki
About the author
My name is Shawn Ligocki. I am a recreational mathematician and professional software engineer. Over the past 15+ years I've been working on the Busy Beaver problem on my free time. At this point, I think I can confidently say that I am a domain expert in many aspects of this niche area.
My non-traditional credentials are:
Quick Summary
What is the limit to what small programs can compute? This is the basic question of the Busy Beaver game.
The Busy Beaver game is a competition to find a Turing Machine which does a huge amount of work and then halts. There are many fascinating directions that you can go from this problem. It is intricately connected to The Halting Problem, Computability theory, Godel incompleteness, the Collatz conjecture, etc.
It has also been framed (since its creation in the 1960s) as a game in which recreational challengers try to find champions. There is a website which keeps track of the history of current and former champions, etc. For this reason, I think it is a great topic for popular math media.
One aspect that I think might be of general interest is the close connection between the Busy Beaver function and the Collatz Conjecture (3n + 1 problem). It turns out that basically all current Busy Beaver champions (and top runners up) simulate "Collatz-like" behavior. The Collatz conjecture is (in)famous for being extremely easy to describe and completely daunting to attempt to prove. It appears that small Turing Machines have effectively "taken advantage" of this fact to produce complex behavior from very small description.
Target medium
I'm open to any medium. I've published many static blog posts for a technical audience. I'm imagining adapting some of these ideas into a higher production value piece for a (somewhat) more general audience.
More details
I wrote a blog post last year spelling out the basic connection between Busy Beaver and the Collatz Conjecture: https://www.sligocki.com/2021/07/17/bb-collatz.html I can imagine this as a prototype for a video/dynamic website which describes this connection to a more general audience.
However, I'm also open to many other directions to take this if any sound more interesting to you. For example, we could discuss the connection to Godel's Incompleteness theorem or how Pavel Kropitz and I recently found (and simulated) machines which run for
10^10^10^...^10steps, etc. There are many possible directions to go with this.Contact details
If you are interested please respond to this github issue or email me at sligocki@gmail.com . I would be glad to chat with anyone interested in collaborating.