Continuing the discussion about the limits of computation, which I started with the recent article on The Halting Problem, let me tell you about one of the most fascinating number sequences ever discovered, the sequence of Busy Beaver Numbers.
As you know, every computer program is ultimately stored as just a finite sequence of 0′s and 1′s. It has a certain size measured in bytes. For a given number of bytes, there are only finitely many possible programs of that exact size. For example, how many programs can there be of size 100 bytes? Well, each byte can hold one out of 256 possible values, so the number of possible 100-byte programs is at most 256 to the power 100– a giant number, for sure, but still finite.
Consider the set of all possible computer programs of a certain size, say N bytes. This set has 256N programs, but that’s not important, all that matters is that it’s finite. Note that the vast majority of these executables will behave very strangely– it amounts to executing totally random code, so I wouldn’t recommend running all these gibberish files on a real computer 
But again, that doesn’t really matter. What matters is that for every particular piece of code, it will either run forever, freezing your computer, or it will eventually stop.
The question is, out of all those random N-byte programs which do eventually halt, what’s the maximum number of steps any one of them takes to halt? This number is well-defined: there are only finitely many N-byte blocks of code, and if we throw away the ones which get stuck in infinite loops, that still leaves a finite number, each of which stops in some finite number of steps. And out of finitely many finite numbers, you can always find the largest one. We call that number the Nth Busy Beaver Number: thus, the Nth Busy Beaver number is the absolute maximum number of steps for which an N-byte program can continue running and yet eventually stop.
This defines a number sequence: the 1st B.B. number, the 2nd, the 3rd, and so on. This sequence is quite well-defined, it certainly exists, and yet it’s absolutely impossible to actually calculate. That’s because if we could compute the sequence, then we could calculate whether programs halt or not, solving the Halting Problem, which the previous article showed can’t happen.
I’ll be more precise. Suppose, for the sake of argument, that there is some ingenious program which takes input N and spits out the Nth Busy Beaver number. Given an executable A and an input x, here’s how to check whether A runs forever on input x (thus solving The Halting Problem). First, generate a new executable B which takes no input and just runs A with input x. The only reason we need this new B.exe is because the Busy Beaver Numbers are only defined in terms of programs which ignore their input. An input-using-program on a specific input is equivalent to a no-input-program with the specific input built-in, and we can certainly program a process to translate the former into the latter. The important thing is, checking whether A loops forever on input x is the same exact thing as checking whether B loops forever on null input.
And here’s how to check whether B loops forever: first, measure how many bytes large B is. Then compute the corresponding Busy Beaver Number: so if B is, say, 100 megabytes, compute the 100 megabyte B.B. number. Call it N. We can calculate it because we assumed there’s some clever algorithm which does exactly that. Now, emulate B for N steps. Either it terminates within those N steps, or it does not. If it does, then we can happily report that A terminates. But if B doesn’t stop within those first N steps, we can conclude that it never will. For, if B did eventually halt after some higher number of steps, that would contradict the fact that N is the maximum number of steps a program the same size as B can run and yet still halt.
So I’ve described a mechanical, systematic means of checking whether or not programs get stuck in infinite loops. Unfortunately that’s impossible. Since I assumed it was possible to calculate the Busy Beaver Numbers and I deduced something impossible, that proves that it is not possible to calculate that sequence.
But we can say a lot more. In order to solve the Halting Problem above, I didn’t really need the exact Busy-Beaver number: anything greater than or equal to it would have worked just as well. This shows a remarkable property about this crazy sequence: not only can we not calculate it, no sequence we can calculate is bigger.
A calculable sequence might start out bigger than the Sequence of the Beaver, but eventually it must succumb. The cool thing is that most sequences we can come up with using elementary concepts, are computable, hence eventually eclipsed by one of those hard-working mammals. 1, 10, 100, 1000, 10000…? Eventually this sequence is dominated by mine. How about 1010, 10100, 101000, 1010000,…? Again, the Busy Beaver numbers will trump it sooner or later. What about 99, 9999, 999999, 99999999, …? Even these numbers are eventually bounded by the uncomputable super-growers. Anything you can program in a computer– even a computer with unlimited time and unlimited processor speed 
– will eventually cower before the shadow of those tireless beavers.
FURTHER READING
The Halting Problem
My Experience with Computer Programming
Katamari Growth — a katamari is the only thing which outgrows the busy beaver sequence
Mathematical Ambiguities