Incoming links: BB(5)
Project trying to compute BB(5) once and for all. Notably it has better presentation and organization than any other previous effort, and appears to have grouped everyone who cares about the topic as of the early 2020s.
Very cool initiative!
By 2023, they had basically decided every machine: discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141
The Busy beaver scale allows us to gauge the difficulty of proving certain (yet unproven!) mathematical conjectures!
To to this, people have reduced certain mathematical problems to deciding the halting problem of a specific Turing machine.
A good example is perhaps the Goldbach's conjecture. We just make a Turing machine that successively checks for each even number of it is a sum of two primes by naively looping down and trying every possible pair. Let the machine halt if the check fails. So this machine halts iff the Goldbach's conjecture is false! See also Conjecture reduction to a halting problem.
Therefore, if we were able to compute , we would be able to prove those conjectures automatically, by letting the machine run up to , and if it hadn't halted by then, we would know that it would never halt.
Of course, in practice, is generally uncomputable, so we will never know it. And furthermore, even if it were computable, it would take a lot longer than the age of the universe to compute any of it, so it would be useless.
However, philosophically speaking at least, the number of states of the equivalent Turing machine gives us a philosophical idea of the complexity of the problem.
The busy beaver scale is likely mostly useless, since we are able to prove that many non-trivial Turing machines do halt, often by reducing problems to simpler known cases. But still, it is cute.
But maybe, just maybe, reduction to Turing machine form could be useful. E.g. The Busy Beaver Challenge and other attempts to solve BB(5) have come up with large number of automated (usually parametrized up to a certain threshold) Turing machine decider programs that automatically determine if certain (often large numbers of) Turing machines run forever.
So it it not impossible that after some reduction to a standard Turing machine form, some conjecture just gets automatically brute-forced by one of the deciders, this is a path to
The only cases where formal proof of theorems seem to have had actual mathematical value is for theorems that require checking a very large number of case, so much so that no human can be fully certain that no mistakes were made. Some examples:
Once you hear about the uncomputability of such problems, it makes you see that all Diophantine equation questions risk being undecidable, though in some simpler cases we manage to come up with answers. The feeling is similar to watching people trying to solve the Halting problem, e.g. in the effort to determine BB(5).
The following things come to mind when you look into research in this area, especially the search for BB(5) which was hard but doable:
- it is largely recreational mathematics, i.e. done by non-professionals, a bit like the aperiodic tiling. Humbly, they tend to call their results lemmas
- complex structure emerges from simple rules, leading to a complex classification with a few edge cases, much like the classification of finite simple groups
Bibliography:
The step busy beaver is a variant of the busy beaver game counts the number of steps before halt, instead of the number of 1's written to the tape.
As of 2023, it appears that BB(5) the same machine, , will win both for 5 states. But this is not always necessarily the case.
A Turing machine decider is a program that decides if one or more Turing machines halts of not.
Of course, because what we know about the halting problem, there cannot exist a single decider that decies all Turing machines.
E.g. The Busy Beaver Challenge has a set of deciders clearly published, which decide a large part of BB(5). Their proposed deciders are listed at: discuss.bbchallenge.org/c/deciders/5 and actually applied ones at: bbchallenge.org.
But there are deciders that can decide large classes of turing machines.
Many (all/most?) deciders are based on simulation of machines with arbitrary cutoff hyperparameters, e.g. the cutoff space/time of a Turing machine cycler decider.
The simplest and most obvious example is the Turing machine cycler decider
Turing machine regex tape notation is Ciro Santilli's made up name for the notation used e.g. at:Most of it is just regular regular expression notation, with a few differences:
- denotes the right or left edge of the (zero initialized) tape. It is often omitted as we always just assume it is always present on both sides of every regex
A,B,C,DandEdenotes the current machine state. This is especially common notation in the context of the BB(5) problem<and>next to the state indicate if the head is on top of the left or right element. E.g.:indicates that the head11 (01)^n <A 00 (0011)^{n+2}Ais on top of the last1of the last sequence of n01s to the left of the head.
This notation is very useful, as it helps compress long repeated sequences of Turing machine tape and extract higher level patterns from them, which is how you go about understanding a Turing machin in order to apply Turing machine acceleration.