2018-11-29
Basic understanding of Turing machines required to follow along. Check out this post if you're new to it.
What is a busy beaver?
Basically you're trying to find the Turing machine with n states that writes that largest possible number of ones on the tape before halting.
Halting is important because, of course an infinite loop is easy to write.
This maximum number of ones is denoted sigma(n). And sigma(n) grows ridiculously quickly.
sigma(2) = 4 sigma(3) = 6 sigma(4) = 13 sigma(5) ≥ 4098 sigma(6) ≥ 3.5 * 10^18267 sigma(7) >> 10^10^10^10^18705352
Yep. In fact it's proven that busy beavers grow faster than any computable sequence of numbers. Meaning if you take any sequence of numbers f(n) then there exists an N such that sigma(n) > f(n) for all n>N
And your sequence could be anything that can be computed using infinite memory and finite time. So exponentation, factorial, double exponentation, up arrow notation, g sequence (if you've read my post on graham's number), sigma(n) grows faster than all of them.
The intuitive idea is basically that if a sequence is computable (say, the g sequence), there exists a Turing machine that can compute that sequence. And that naturally implies there exist larger Turing machines that can produce larger outputs. The exact proof is not as simple though, unlike what I initially thought
sigma(5) = 4098 is yet to be proven as true because of the existence of 42 rogue Turing machines that have yet to be proven as non-halting. They are the machines marked HNR in this post.
sigma(n) is an example of a non-computable function, meaning there exists no algorithm that can determine sigma(n). You might argue that we could write an algorithm that runs all possible n state TMs simultaneously ... But some of those might never halt and we cannot write an algorithm that determines if a TM halts or not, as per the halting problem.
Here's an article that compiles existing research on busy beavers.
sigma(n) also is a function that will eventually produce unprovable values. It has been proved that value of sigma(n) for all n≥1919 is unprovable.
This is different from just saying sigma(1919) is unknown, it's more along the lines of we will never be able to know with certainty what sigma(1919) is.
But how does one prove that something is unprovable? You start off with formalising the notion of what does and does not constitute a proof. There are existing axiomatic systems (zermelo fraenkel, peano arithmetic, etc) that attempt to provide a base set of axioms from which all of mathematics follows.
Recently a 1919-state machine has been created that verifies the consistency of zf from within zf, which is an impossible task if zf is indeed consistent. Hence sigma(1919) is unprovable using zf if zf is consistent (and most mathematicians believe it is).
The lower limit on the unprovable values of sigma(n) is unknown. It is even possible that 42 rogue 5-state machines (which are the reason sigma(5) has not yet been proved to be equal to 4098) are indeed unprovable as non-halting.
See the second half of this post.
Kolgromov complexity is a related topic that you might also like. Check out this blog post.
Enter email or phone number to subscribe. You will receive atmost one update per month
Enter comment