Comment by meric
11 years ago
If BB is the highest paradigm published, and it is assumed BB numbers, given enough time and resources, can be computed, and you can't use BB2, why can't you simply go:
BB(BB(BB(BB(BB(11111)))))
Repeat as many BB's as you have space on your 1000 character card. You might even use math notation to define a new function where
BB-(n) = [BB(BB(.......]
<---- n ----->
And then you might have:
BB-(BB-(BB-(1111)))(BB-(BB-(BB-(1111)))(11111))
Or some such monstrosity.
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.
6 replies →
Define C(n) = [BB-(BB-(BB-....] And define D(n) = [C(C(C(C(...n)] And define E(n), and so on.
Then make the Greek letters the entire alphabet iteration process (meaning BB-n through Z(n)). And then make the Hebrew letters the entire Greek letter process.
Look at how much fun we're having!
> and it is assumed BB numbers, given enough time and resources, can be computed
They can't be computed - they can only, at best, be proven to be within some bounds.
But it's unimportant since it's not really required in order to do what you said.
The logical conclusion of this is considering all general computations that can be done with a BB calculator in hand, which leads you to the hyper BB numbers that he refers to, or BB_2.
I got the idea his BB_2 is different. He's referring to a super Turing machine that can solve the halting problem for non-super Turing machines.
The BB-2 used in an iterative algorithm is talking about "A busy beaver number of (A busy beaver number of 10)", no need for super machines here. The iterative algorithm is short enough you can define it in your 1000 characters, no need for additional publication.
But the super Turing machines busy beaver numbers vastly outgrow your iterated busy beaver very quickly. It doesn't take that many states to write a program that can do an iterated function application, and to a super Turing machine, it's easy to write the busy beaver function.
1 reply →