Another introduction to this same topic, that goes much further and is better written:
Judging by the rest of the article, I would have won. I would have written "Ackermann function on Graham's number and Graham's number." For added enjoyment, add "Call this B_1. Define B_n = A(B_n-1,B_n-1) for n > 1. Now take B_(B_1)."
EDIT: Or I guess just:
Let G be Graham's number. Let B_n be G if n = 1 and A(B_n-1,B_n-1) if n > 1 (where A is Ackermann's function). Take B_B_2.
Only my second example was doing that recursively...oh the horror...
Specifically, by defining a sequence of numbers in terms of how much a program of given length can do, given that it halts, it turns out that you get a sequence that provably grows faster than any computable sequence. (It's actually traditional to do this with Turing machines rather than conventional programs.) This is in fact rather closely related to Chaitin's stuff at the start of this discussion.
He assumes that evolution is true, then therefor if we lived to 70,000,000 there would not be creationism. However if evolution wasn't real, but creationism was, and people lived to 70,000,000 year you could say the same thing: they saw creation happen, and no one would imagine such a thing as evolution.
Which makes his sentence effectively meaningless. And he "begged the question".
It's an interesting article, but it has a number of errors that severely diminish it. Plus he really needs to stop bashing on the bible and stuff (that myth that the bible says Pi is 3 isn't even true).
My biggest gripe with it is this:
"Take Goldbach’s conjecture, that every even number 4 or higher is a sum of two prime numbers: 10=7+3, 18=13+5. The conjecture has resisted proof since 1742. Yet we could design a Turing machine with, oh, let’s say 100 rules, that tests each even number to see whether it’s a sum of two primes, and halts when and if it finds a counterexample to the conjecture. Then knowing BB(100), we could in principle run this machine for BB(100) steps, decide whether it halts, and thereby resolve Goldbach’s conjecture."
That's WRONG! A turing machine that checks every single integer by definition never halts, so the entire exercise is pointless - you'll get no info. Yah, if it halts you know the answer, but if it doesn't you know nothing, so calculating BB(100) doesn't help you at all.
On top of that it's possible that BB's for large number don't exist - I don't mean that they can't be calculated, I mean that for whatever numbers of steps you chose you can make the machine halt in that number of steps, but there is no upper limit at all, and you can always create a machine that halts after more steps.
PS. If you want a really large number that ordinary students would understand try 9!!!!!!!!.... (repeated factorial).
The definition of BB(100) is the number below which all 100-rule TMs that halt will in fact halt. Everything that ever halts will halt before that number of steps, everything that continues one step past BB(100) will never halt. That's the definition. If you have a conjecture encoded into a 100-state TM and you know BB(100), then all you do is run the machine for BB(100)+1 steps. If it gets to BB(100)+1, then by the definition of BB(100), it will never halt. If it halts before that, well, it halted.
Of course BB(100) is incomprehensibly large, well beyond what the entire universe could possibly be used to execute. (Likely, BB(10) is already at that point.)
"On top of that it's possible that BB's for large number don't exist" - no it's not. It's perfectly well defined as the largest element from a well-defined finite set. There must be a maximum value.
If the only way to prove or disprove Goldbach’s conjecture is to try every integer forever until you find a counter example (i.e. you can never stop - there is no point at which you can say, I checked enough numbers).
Then the same would apply to calculating BB(100) - you can never actually calculate the value of it - you never know if you have run it long enough.
That's my point: there might not actually be a value for large BB's. It is simply impossible to know if you need to keep running the machine or not. You can only set a lower bound. You can't, even in principle, ever calculate it.
So you can define the meaning of BB, but you can't calculate the value of it. If you can't calculate the value of it, then it has no defined value.
That's what I am trying to say - it is impossible, no matter how many (finite) resources you have, to calculate large BB's. There is never the point at which you can say: this program is not infinite.
Edit: I just read the wikipedia page on it, and I'm not saying something new: it's well known that BB is not computable, and point is that if it _was_ computable then you could use it to calculate Goldbach’s conjecture and others.
He really should have made the point a little clearer than you can't actually calculate the value of BB(100) - he made it seem like it was hard and needed massive resources, but not that it was impossible even in principle.
And finally, I say that since you can not calculate the value of large BB's - they are not actual numbers, and thus can not be used for his large number game.
That's not true. The Busy Beaver function is a counterexample: it's possible to enumerate all n-rule Turing machines. Each such machine either halts after a finite number of steps or does not. We can list the number of steps that all the halting n-rule machines take to stop, and the largest number that we list is BB(n). That's defined.
I think your problem is that you don't understand what "computable" means. When we say that the Busy Beaver function is uncomputable, we mean that there is no halting algorithm that takes any natural number n as its input and always returns BB(n). There are algorithms that return BB(n) for any specific n: "return [BB(n)]" is an example.
The reason that no general (finite) algorithm exists that can compute the Busy Beaver function is this: there are some Turing machines that never halt but that cannot be proven to never halt; that is, there is no sequence of symbols and accompanying interpretive framework that proves that such a machine never halts. BUT THEY STILL DON'T HALT. So when our algorithm tries to compute BB(k), and there's a k-rule TM in the class that I described, the algorithm freaks out. It has no way of knowing that it should ignore this TM, because it's mathematically impossible to know that. But it can't wait forever either. So it watches the weird TM for an infinite amount of time. The only way to get around this is to hard-code in special case handling for these weird TMs; but you can only do that a finite number of times ('cause the algorithm's finite), and the class of weird TMs has no finite description.
To the person whose comment is above or below mine: that's the difference between BB(1 - 4) and BB(100). There are no weird TMs with less than 5 rules. But there are almost certainly some with 100 rules.