There is a 5% chance that we have a new BB(6) champion! It’s a machine discovered by Racheline which she’s named “Lucy’s Moonlight”. It is a probviously halting tetrational Cryptid. In other words, it’s a machine that we believe will eventually halt (with 100% chance via a probabilistic approximation), yet proving it requires either solving a Collatz-like problem or simulating it for a “tetrational” number of steps. This is very similar to the Mother of Giants with the excepti...| sligocki
A common question people have about Busy Beaver champions is: “What are they doing?” This question sounds sort of objective, but is really a subjective philosophical question. Objectively, the TM is repeatedly evaluating the specific transition table rules until it halts, that’s all. In a sense, this is the “simplest” (smallest) explanation because these champions are literally the ones that “do the most” based on the smallest description.| sligocki
We now know definitively that| sligocki
Note: All Discord links are for the https://bbchallenge.org/ Discord server.| sligocki
When we think about interpreting a Turing Machine’s behavior, we often think about visualizing the configuration history, for example in a space-time diagram like:| sligocki
Consider the Collatz-like function:| sligocki
In 1964 (only 2 years after Tibor Radó first described the Busy Beaver game), Milton W. Green of the Stanford Research Institute hand-crafted a family of fast-growing Turing Machines with \(n\) states, 2 symbols for all \(n \ge 4\).1 At the time of publication, Green’s Machines were the Busy Beaver champions for \(BB(n)\) for all \(n \ge 6\). This family grows roughly as fast as the Ackermann function Milton W. Green. “A Lower Bound on Rado’s Sigma Function for Binary Turing Machines...| sligocki
I’m excited to share a 3 state, 3 symbol Turing Machine that cannot be proven to halt or not (when starting on a blank tape) without solving a Collatz-like problem. Therefore, solving the \(BB(3, 3)\) problem is at least as hard as solving this Collatz-like problem, a class of problem for which Paul Erdős famously said: “Mathematics may not be ready for such problems.”| sligocki
Pavel has found a 3-state 4-symbol TM which can compute an “Ackermann-level” function and halts with exactly| sligocki
I just enjoyed an excellent YouTube video, My honest attempt at the Collatz Conjecture, made by Fernando Franco Félix (Fer / @Highly Entropic Mind) as part of the third Summer of Math (#SoME3). He also wrote it up as a PDF. This blog post is a response to that video and paper.| sligocki