Incoming links: Conjecture
The busy beaver game consists in finding, for a given , the turing machine with states that writes the largest possible number of 1's on a tape initially filled with 0's. In other words, computing the busy beaver function for a given .
There are only finitely many Turing machines with states, so we are certain that there exists such a maxium. Computing the Busy beaver function for a given then comes down to solving the halting problem for every single machine with states.
Some variant definitions define it as the number of time steps taken by the machine instead. Wikipedia talks about their relationship, but no patience right now.
The Busy Beaver problem is cool because it puts the halting problem in a more precise numerical light, e.g.:
- the Busy beaver function is the most obvious uncomputable function one can come up with starting from the halting problem
- the Busy beaver scale allows us to gauge the difficulty of proving certain (yet unproven!) mathematical conjectures
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
A conjecture is an open problem in mathematics for which some famous dude gave heuristic arguments which indicate if the theorem is true or false.
A discussion on the Lean Zulip: leanprover.zulipchat.com/#narrow/stream/113488-general/topic/The.20Math.20Genome.20Project/near/352639129. Lean people are not convinced about the model in general it seems however.
TODO closed source? Really? www.themathgenome.com/pricing
TODO not viewable without login?
Has conjectures feature.
Built by this dude John Mercer: www.linkedin.com/in/johnmercer/. He must be independently wealthy or something? What a hero.
A failed Hacker News self post: news.ycombinator.com/item?id=35775071
Ciro Santilli asked: discord.com/channels/1096393420408360989/1096393420408360996/1137047842159079474Owner:So apparently there will be proof checking, but nodependencies between proofs, you still have to pull request everywhing back and face the pain.
Does the website actually automatically check the formal proofs, or is this intended to be implemented at some point? And if yes, is it intended to allow proofs to depend on other proofs of the website (possibly by other people)
Hi Ciro, yes we will be releasing in-browser proof assistant environments/checkers (e.g. Lean). Our goal is not to replace the underlying open-source repos (e.g. Mathlib) so the main dependency will be on the current repos; then when statement formalizations and proofs come in and are certified they can be PR'd to the respective repos. So we will be the source of truth for the informal latex code but only a stepping stone and orchestration layer on the way to the respective formal libraries.