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…
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…
We now know definitively that
Note: All Discord links are for the https://bbchallenge.org/ Discord server.
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: A Reversal Turing Machine with fractal behavior. 1RB0RF_1LC0RB_1RD0LC_1LE0RD_1RA0LE_1LD--- Images courtesy of @mxdys on bbchallenge Discord. These visual representation can give a lot of hints about the large-scale behavior of the…
Pavel has found a new 3-state 4-symbol Busy Beaver champion which can compute an “Ackermann-level” function and halts with exactly
Consider the Collatz-like function:
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…
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.”
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.