Comment by jerf
11 years ago
So this turns out to be less interesting mathematically than you might think, because the entire thing about Busy Beaver numbers is that it is using the full power of computation available to it for a given number of states, so as soon as the "normal" Busy Beaver reaches a number of states sufficient to describe whatever trick you're interested in pulling, the Busy Beaver sequence itself already uses that trick!
One of the most important sentences in understanding them is one that's easy to pass by in the original work: "Indeed, already the top five and six-rule contenders elude us: we can’t explain how they ‘work’ in human terms."
That is, while we humans are thinking we're all clever by defining repeated iterations of the BB ruleset itself, all of these things that we think we are being so clever with are actually very very compactly described by Turing Machine states. Meanwhile, even by BB(6) the TM is metaphorically "using" incomprehensible tricks to be larger than we'd even dream. If repeated iterations of BB'ness can be trivially described in, say, 10 states, and let's say we reserve 4 states for BB(4) to describe the number of times to iterate, our hand-constructed "clever" re-iteration of the BB procedure will be blown away by some other 10-state machine that we can't even imagine would ever terminate.
So on the one hand, yes, BB(BB(20)) is incomprehensibly larger than merely BB(20), and yet, on the other hand, in a profound way, it also doesn't matter. Busy Beaver in a sense shows us numbers that have all the practical properties of infinity, even if they are not technically infinite. In a sense BB(30) < BB(31) is obviously true, yet, ultimately, a humanly meaningless statement, since grasping either number in any sense beyond its mere definition is impossible. We might as well say that "blibble" is less than "bloo". And not merely impossible in the sense that it is impossible to even really properly grasp just how far it is to Alpha Centauri, but impossible in the sense that we are literally incapable of even constructing mathematical tools that will let us grab on to and manipulate such numbers... deeply, profoundly, computationally impossible for us to understand, not merely "mind-blowing", but impossible for us to understand in the absolute strongest sense of the term.
Similarly for trying to catch up to BB with yet more iterations of exponentiation... the procedure we humans use is shockingly, shockingly simple to describe programmatically, which means that BB automatically already encompasses practically all such tricks very early in its sequence, which means you can't defeat it that way.
Busy Beaver is metaphorically (again) much smarter than you, and it's not worth your time to try to outsmart it to make yet again bigger numbers.
This also, probably correctly, implies that attempting to adjudicate some contest in which some people write BB(BB(BB(x)))) vs some other BB-based notation is also impossible and you'd actually fail out of the contest for writing an ill-defined number, as if we can't compare the two numbers for which is larger, even in principle, it is for the purposes of this contest, ill-defined. Busy Beaver in a sense also sets the limit of what a well-defined number even can be, and is thus in some sense the natural limit of this contest by virtue of simply transcending through sheer incomprehensible size all our computationally-naive human tricks for making big numbers, or even just numbers of any size at all.
It's really a profound sequence.
> we are literally incapable of even constructing mathematical tools that will let us grab on to and manipulate such numbers
I think this is really the key to your point. Part of me wonders whether this should even make the example in the essay, BB(111), invalid. If there is no way in our universe to ever know exactly what BB(111) is, can it really be considered a well-defined number? That said, I'm no mathematician, so I'm probably off-base here.
My first though reading the challenge was a series of 7^7^7^7... since the 7s would nest together nicely (unlike 9s) :P
> If there is no way in our universe to ever know exactly what BB(111) is, can it really be considered a well-defined number?
There's a branch of Maths called constructivism which requires values/proofs/etc. to be "constructable" in principle. For example, the law of the excluded middle ('for all X, either X is true or (not X) is true') is not constructive, since it doesn't give us a value: we don't know whether we're dealing with X or (not X).
http://en.wikipedia.org/wiki/Constructivism_(mathematics)
Constructive mathematics turns out to be very closely related to computation, and is one reason why functional programming gets so much research attention.
Constructivists don't have a problem with infinite objects, like the set of all Natural numbers, if they can be represented in a finite way (eg. as a function). There's another branch of Mathematics knows as finitism, which regards infinities as not existing. What you're describing is ultrafinitism, which regards really big things as not existing: http://en.wikipedia.org/wiki/Ultrafinitism
It is well defined - it's "just" a matter of computation. There are a small number of possible 111-state turing machines - well, ok, there's actually a very large number, since it's one of those things that grows exponentially, but still, it's very much a finite number. For each of those possible turing machines, either it halts or it doesn't, something a programmer should be able to grind out; if it halts then it necessarily does so after some finite number of steps. So in principle we could compute all of those and then take the max of them. In practice it's a lot of steps - but we understand all the steps, so it would just be a matter of "cranking it out".
Conversely if you want to insist on a "constructible" number then you kind of have to insist on unary notation. Maybe a computer can give you a numerical value for "11^11^11^11", but can you really consider it well-defined if you can't put that many pebbles in a row? There are a few mathematicians who take this kind of view - see http://en.wikipedia.org/wiki/Ultrafinitism - but it's very much an extreme position.
I have some issue with how you're generating the BB numbers, though it's not necessarily mathematical. Fundamentally, "cranking it out" is exactly what you cannot do to generate the BBs: following any one specific set of instructions for generating the BBs is a futile exercise.
The problem arises when you say that "a programmer should be able to grind out" whether or not a TM halts or not, which you use to get around the fact that a TM cannot solve the halting problem. However, I'd question if this is a trivial exercise: while we certainly are capable of recognizing infinite loops in the code we write, I'm not certain that humans can identify arbitrary infinite loops. Obviously, whether or not we can isn't a trivially answerable question, as it comes down to whether or not our brain's neural networks can be modeled by a sufficiently large TM, and even if it cannot be modeled by a sufficiently large TM, what differences between our brains and a TM exist and why those would effectively allow us to solve the halting problem.
So I'd question whether finding the BBs is "'just' a matter of computation", because I'm not convinced that humans can solve the TM halting problem.
4 replies →
BB(111) is not computable by "just computation". The issue is you have to prove that the programs that don't halt, don't halt. There is no general way to do this (Halting Problem). In fact once you get to a large enough n, BB(n) will be undecidable in whatever axioms you're using. We already have a simple proof of this by taking any known undecidable statement and turning it into a Turing machine halting problem.