The Busy Beaver Problem(catonmat.net)
catonmat.net
The Busy Beaver Problem
http://www.catonmat.net/blog/busy-beaver/
8 comments
This reminds me of an essay I really like (it covers what the busy beaver numbers are, and what their utility is): http://www.scottaaronson.com/writings/bignumbers.html
But do people fear big numbers? Certainly they do.
Apathy !== fear.
comforting smallness of mysticism?
In what way is mysticism small? It is bigger by most definitions than anything we're capable of being consciously aware of.
On topic, excellent; but the off-the-cuff remarks could have used a little more thought IMO.
Apathy !== fear.
comforting smallness of mysticism?
In what way is mysticism small? It is bigger by most definitions than anything we're capable of being consciously aware of.
On topic, excellent; but the off-the-cuff remarks could have used a little more thought IMO.
> In what way is mysticism small? It is bigger by most definitions
Saying "infinite" creates a vague sensation of bigness that isn't anywhere near as big as, say, 3^^^3 (http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation) to say nothing of really large numbers.
The idea of the night sky as "infinite" is nowhere near as shocking as the idea of galaxies a septillion meters away. It's like the difference between Thor, versus the machine superintelligences of Iain Banks's Culture or the Powers from Vernor Vinge's A Fire Upon the Deep. You can imagine the "infinite" Jehovah demanding the worship of Israelite tribespeople, but it's rather harder to visualize a mind 10^50 ops/sec large bothering to do so.
If you think of mystics as primitive amateur philosophers and science fiction writers who demand that their work be protected from ordinary criticism, you can see there's no way they'd be able to keep up with modern science fiction writers or modern mathematicians. In this light, words like "infinite" or "unimaginable" are just words - showing instead of telling, mere adjectives, a demand that we be impressed which isn't backed up by any actual ability to conceive of impressive things.
Saying "infinite" creates a vague sensation of bigness that isn't anywhere near as big as, say, 3^^^3 (http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation) to say nothing of really large numbers.
The idea of the night sky as "infinite" is nowhere near as shocking as the idea of galaxies a septillion meters away. It's like the difference between Thor, versus the machine superintelligences of Iain Banks's Culture or the Powers from Vernor Vinge's A Fire Upon the Deep. You can imagine the "infinite" Jehovah demanding the worship of Israelite tribespeople, but it's rather harder to visualize a mind 10^50 ops/sec large bothering to do so.
If you think of mystics as primitive amateur philosophers and science fiction writers who demand that their work be protected from ordinary criticism, you can see there's no way they'd be able to keep up with modern science fiction writers or modern mathematicians. In this light, words like "infinite" or "unimaginable" are just words - showing instead of telling, mere adjectives, a demand that we be impressed which isn't backed up by any actual ability to conceive of impressive things.
it's rather harder to visualize a mind 10^50 ops/sec large bothering to do so
How about a more Leibnizian idea of the Creator having designed into the primordial energy event all of the consequences of existence - some slight fluctuation or variation being ultimately responsible for this internet post ... is that a valid activity for your concept of a mystical supermind. Or consider that the realist approach to many worlds is true - is the awareness of every subatomic interaction in every one of an infinite array of possible worlds, is that enough processing for you? How about if that mystical being is responsible for an infinite number of such worlds?
You have a very large concept of the infinite aleph-0^^^...^^aleph-0 (I doubt you can verily comprehend those numbers though) or whatever but some numerological mystics would say those concepts are discovered from ideas embedded in the created order or inherited from a prime movers creative mind.
Your view of mysticism is narrow.
How about a more Leibnizian idea of the Creator having designed into the primordial energy event all of the consequences of existence - some slight fluctuation or variation being ultimately responsible for this internet post ... is that a valid activity for your concept of a mystical supermind. Or consider that the realist approach to many worlds is true - is the awareness of every subatomic interaction in every one of an infinite array of possible worlds, is that enough processing for you? How about if that mystical being is responsible for an infinite number of such worlds?
You have a very large concept of the infinite aleph-0^^^...^^aleph-0 (I doubt you can verily comprehend those numbers though) or whatever but some numerological mystics would say those concepts are discovered from ideas embedded in the created order or inherited from a prime movers creative mind.
Your view of mysticism is narrow.
Within each novel, the characters can debate the literary merits of any of the sub-novels. But, by analogy with classes of machines that can’t analyze themselves, the characters can never critique the novel that they themselves are in.
Clearly he's never seen Spaceballs. (Otherwise it's an excellent article.)
Clearly he's never seen Spaceballs. (Otherwise it's an excellent article.)
Yeah, that's a good one. The only complaint I have is that it contends that the Busy Beaver numbers grow faster than any computable sequence, but what it actually shows is that no computable sequence can be proven to grow faster than the Busy Beaver numbers. If a sequence happens to grow faster than the Busy Beaver sequence, but we can't prove it, then it doesn't help us prove anything about Turing machines.
Consider a Turing machine M1 of size X that, given an input value n, calculates a function f(n) such that O(f(n)) > O(BB(n)) and halts.
Consider a Turing machine M2 of size Y that calculates a number A and halts, where X + Y < A.
Combine the two machines, using the number calculated by M2 as the input for M1. The resulting Turing machine of size X + Y calculates a value f(A) such that f(A) > BB(A) > BB(X + Y) and then halts. This contradicts the definition of BB(X + Y), therefore no such computable function f can exist.
Consider a Turing machine M2 of size Y that calculates a number A and halts, where X + Y < A.
Combine the two machines, using the number calculated by M2 as the input for M1. The resulting Turing machine of size X + Y calculates a value f(A) such that f(A) > BB(A) > BB(X + Y) and then halts. This contradicts the definition of BB(X + Y), therefore no such computable function f can exist.
Alright, this is a good proof. I therefore concede the point regarding the values themselves.
It's more of a proof sketch, really--there's a few unexamined assumptions in there. It was the best I could do off the top of my head and typing on a smart phone, but I'm reasonably confident that the overall structure is valid.
I was actually kinda hoping someone who knows more than I do would chime in and clarify things...
I was actually kinda hoping someone who knows more than I do would chime in and clarify things...
Well, here's another approach. We can solve the halting problem for any finite TM (http://portal.acm.org/citation.cfm?id=1052796.1052798), so let's imagine we're looking at a possible BB, n. All we have to do is run all the possible programs, and see whether of the halting ones, one is bigger than n.
Outstanding introduction to this sort of thing, thanks for sharing.
You should submit this on it's own to HN. That was a great read.
This problem is what originally got me interested in computational complexity. Everybody knows about the halting problem; but the Busy Beaver, now that's a clever and weird idea! The growth rate of Sigma(n) is ridiculous. Studying this illuminated just how vast a problem-space can be (especially concerning the lack of knowledge we have by knowing a particular machine's configuration: we don't learn much by inspection, we just have to run the damn thing). I see the Busy Beaver "competition" as our more-interesting equivalent to searching for large primes.
Worth pointing out that busy beavers have the potential to be alot more than just 'interesting'. If you knew what the busy beaver numbers were for a given number of states, it could be used to solve various unsolved mathematical problems.
For example, Goldbach's conjecture states that every integer greater than 2 is the sum of 2 primes. So far it has been resistant to being proved. But if you could convert it to a computer program with say, 500 states, and you knew the busy beaver number for 500, you could check it by running the program that number of cycles. If you did and the program didn't halt, then it would NEVER halt, and Goldbach's conjecture would be proven true.
Of course, BB(500) would certainly be an unfathomably huge number, so there would be practical problems running a computer program that number of cycles. But if you had sufficient computing power, knowing the busy beaver numbers would be an amazing mathematical tool.
For example, Goldbach's conjecture states that every integer greater than 2 is the sum of 2 primes. So far it has been resistant to being proved. But if you could convert it to a computer program with say, 500 states, and you knew the busy beaver number for 500, you could check it by running the program that number of cycles. If you did and the program didn't halt, then it would NEVER halt, and Goldbach's conjecture would be proven true.
Of course, BB(500) would certainly be an unfathomably huge number, so there would be practical problems running a computer program that number of cycles. But if you had sufficient computing power, knowing the busy beaver numbers would be an amazing mathematical tool.
Yes. (Though you just proved that knowing the busy beaver numbers is as least as heard as knowing the truth-values of all those famous conjectures.)
I don't understand what the problem is asking.
It's basically asking, 'what's the biggest number a particular Turing Machine can compute?' (expressed in unary).
This is interesting as an upper bound - for example, if we have a Turing Machine and we know its Busy Beaver number _m_, we can run any of its programs and if the program fills more than _m_ while running, we know the program doesn't terminate! (Because if it did ever terminate, we would have a different Busy Beaver number, which is a contradiction.) In other words, the Busy Beaver lets us solve the Halting Problem for a specific Turing Machine; doesn't violate Turing, but is still very interesting.
As Wikipedia says, "This machine attains the limits on the amount of time and space that a halting Turing machine of the same class can consume." (This is terribly worded, so I'm going to go edit it now...)
This is interesting as an upper bound - for example, if we have a Turing Machine and we know its Busy Beaver number _m_, we can run any of its programs and if the program fills more than _m_ while running, we know the program doesn't terminate! (Because if it did ever terminate, we would have a different Busy Beaver number, which is a contradiction.) In other words, the Busy Beaver lets us solve the Halting Problem for a specific Turing Machine; doesn't violate Turing, but is still very interesting.
As Wikipedia says, "This machine attains the limits on the amount of time and space that a halting Turing machine of the same class can consume." (This is terribly worded, so I'm going to go edit it now...)
Here is a clearer explanation of the problem:
http://www.logique.jussieu.fr/~michel/tmi.html
My attempt at explaining it (I'm not sure I've understood it completely, though): Busy Beavers are Turing machines that eventually reach a halting state. The goal is to find the busy beaver, for a given number of states, that takes the longest to do so. This turns out to be a tricky problem for states >= 5. That is, there are solutions to n=5,..., but no one has formally proved that there isn't a busy beaver that will take longer to halt.
My attempt at explaining it (I'm not sure I've understood it completely, though): Busy Beavers are Turing machines that eventually reach a halting state. The goal is to find the busy beaver, for a given number of states, that takes the longest to do so. This turns out to be a tricky problem for states >= 5. That is, there are solutions to n=5,..., but no one has formally proved that there isn't a busy beaver that will take longer to halt.
The idea is to figure out how many cycles it takes before a 'beaver' halts, if at all (it is a given they should, but after how many cycles is an open problem for more than the smallest numbers of states).
They have extremely simple rules, yet take a very long time before they finally do come to a halt.
It's an interesting little problem, if such tremendously simple state machines can exhibit such complex behavior it gives you some indication of how hard it would be to answer those questions for more complicated state machines.
They have extremely simple rules, yet take a very long time before they finally do come to a halt.
It's an interesting little problem, if such tremendously simple state machines can exhibit such complex behavior it gives you some indication of how hard it would be to answer those questions for more complicated state machines.
[deleted]
Here is a fun thought.
There is no possible consistent axiom system understandable by humans in which it is possible to prove a specific number to be an upper bound for BB(1000000)!
Here is why. Suppose you have an axiom system. We can write a Turing machine that searches for proofs and disproofs of the consistency of this axiom system. If the axiom system is consistent the program will run forever. But if it is proven that BB(size of machine) has an upper limit then the program will eventually prove that the limit exists, and it has run past it, and therefore it will never halt, and therefore it will never find an inconsistency, and therefore the axiom system is consistent.
For the rest of my claim I claim that an axiom system that can be understood by humans can always be encoded in a Turing machine of size at most a million. I obviously have no proof of that, but it seems extremely likely to me.
For another fun thought, there is a school of mathematical philosophy in which BB(n) is not a well-defined function at all! (Look up the constructivists.)
There is no possible consistent axiom system understandable by humans in which it is possible to prove a specific number to be an upper bound for BB(1000000)!
Here is why. Suppose you have an axiom system. We can write a Turing machine that searches for proofs and disproofs of the consistency of this axiom system. If the axiom system is consistent the program will run forever. But if it is proven that BB(size of machine) has an upper limit then the program will eventually prove that the limit exists, and it has run past it, and therefore it will never halt, and therefore it will never find an inconsistency, and therefore the axiom system is consistent.
For the rest of my claim I claim that an axiom system that can be understood by humans can always be encoded in a Turing machine of size at most a million. I obviously have no proof of that, but it seems extremely likely to me.
For another fun thought, there is a school of mathematical philosophy in which BB(n) is not a well-defined function at all! (Look up the constructivists.)
The "tape changes for 4 state busy beaver" image is the Burj Dubai! :)
I was confused at first by the first paragraph since it didn't say the beavers _must_ stop. Once I figured that out the rest made sense.