Boy, was I wrong about that. Not only is that not a rough sketch of a proof, but it’s a proof of the wrong statement.
I’d use an embarassed smilie here, but it doesn’t suggest embarassment to me. So, oops!
I can’t seem to find a proof that B is well-defined, but I can find a lot of sources that say it is. Meanwhile, here’s a page on large numbers that should provide some interesting reading.
Oddly enough, ultrafilter, three or four years ago I would have understood everything you’ve written here.
Four years away from the language has done UnWonders to my math abilities:(
I probably missed it in the OP, but why do scientists care about Graham’s number, and why don’t they just make Graham figure it out his own damn self?
I can’t believe I missed this…
The proof is not difficult, or long, or even very deep. There are a finite number of Turing machines with n states. Some of them run forever–don’t count those. Of the remaining ones, one of them produces an output of maximum length given a fixed input. And for our case, the input is “”, or no 1’s.
That work?
Sounds good to me. Thanks.
log[sup]*/sup is in fact equal to 5. Now you know.
This reminds me of a game I would play with people to pass the time. The rules were that we’d both think of an integer. Then we’d say what we were thinking of. Whosever was higher won that round. The first time I would play it with people, it would go something like this:
Them: 10 trillion.
Me: 10[sup]500[/sup]. I guess I win.
Me: 10[sup]10[sup]500[/sup][/sup].
Them: Ah, I was only thinking of a googolplex. You win.
Them: 10 to the 10 to the 10 to the googolplex.
Me: Ooh, I win. I was thinking of 10 with a googolplex factorial symbols after it.
At about this point, we both get pretty creative, and it becomes more or less impossible to tell who wins. So my games only ever last about three rounds with any given person.
That reminds me of a contest some magazine (Scientific American?) had several years ago.
The prize was $1,000,000 (*). To play, all you had to do was send in a postcard with an integer on it. Whoever sent the highest integer wins.
(*) However, the prize money would first be divided by the highest integer sent in. Once someone submitted 1,000,000 as an integer, the prize money is down to $1 or less.
I don’t know if they ever determined a winner (not that it really mattered, since the prize had become essentially nonexistent by that point). People came up with all kinds of different efficient notations to write large numbers with, and they couldn’t always determine which numbers were bigger than which.
Here’s what I was going to tell erislover about the busy beaver function.
Let’s take an n-state Turing machine, and let’s give it a subroutine that allows it to write B(n) 1’s in a row. All of a sudden, it seems like everything’s possible! A whole new world of fast-growing functions is opened up to us. The sky’s the limit!
Well, maybe not. Cause you see, this machine can’t calculate it’s own busy beaver function.
Let’s call that B’(n). By the same proof as before, B’(n) grows faster than any newly computable function.
Add on the capacity to write B’(n) 1’s in a row, and you get B’’(n). Still too fast.
Amazing, isn’t it?
OK, something still isn’t kosher…
here’s as turing machine with 1 state:
whatever it sees, it writes a 1 and moves to the right, remaining in its same state. (It will obviously never halt)
here’s another one:
whatever it sees, it writes a 2 and moves to the right
etc.
how are there not an infinite number of 1-state turing machines, and thus an infinite number of 2-state turing machines?
Because, the tape alphabets of both of those TMs are the same: character x. It doesn’t matter what it writes, it’s still the same TM.
Cool thread, ultrafilter.
To me, the fun part is one of perspective. The smallest infinity, the cardinality of the positive integers, seems pretty small and tame to a student of mathematics. But these f[sub]k**'s and B(n)'s seem (are!) pretty damn mindbogglingly immense, even though they’re finite, and any finite number is dwarfed by the smallest infinity.
I think the late Douglas Adams once said something to the effect that really big finite things get across the idea of infinity much better than infinity itself does. I think he had a point.
Thanks.
Sure. We all know that infinity is incomprehensibly large. There’s no issue there.
But finite numbers, we think we understand them, and that it’s no issue to deal with them. That’s only cause we don’t deal with the large ones.
And I still hate seeing “late” in front of “Douglas Adams”.
Ha! 
Ape brains max out at about the number seven. That’s as high as our brains want to count. We can use our fingers, toes, and various other body parts, but that’s enlisting other parts of the body to offload storage. As far as the cerebrum is concerned, seven is as big as it gets.
Considering that, it’s damned impressive we’ve managed to work ourselves up to being stumped by the Halting Problem. 
(It’s always more interesting to judge a culture by what problems give it troubles than by what problems it thinks it’s mastered.)
Formalism’s a wonderful thing, ain’t it?
By the way, the halting problem doesn’t really have us stumped. We just know that it’s not possible to solve.
Even if you give your Turing machine the ability to solve the halting problem (never mind how), that machine can’t decide its own halting problem. Same proof as before.
Or am I misinterpreting you?
Is it the same TM if δ is different? I may be wrong, but wouldn’t the transition function be changing?
They’re isomorphic. They look different, but for all intents and purposes, they’re the same.
I’m still unconvinced.
Here’s a TM with 1 state:
if it sees a 0, it writes a 1, and moves to the right.
Otherwise, it halts.
Here’s a TM with 1 state:
If it sees a 0, it writes a 1, and moves to the right.
If it sees a 1, it writes a 2, and moves to the right.
Otherwise, it halts
Here’s a TM with 1 state:
If it sees a 0, it writes a 1, and moves to the right.
If it sees a 1, it writes a 2, and moves to the right.
If it sees a 2, it writes a 3, and moves to the right
Otherwise, it halts.
And so forth… I think you still need to set some additional restrictions before you can claim there are a finite number of n-state turing machines.
There are a finite number of Turing machines with an alphabet of k characters. Sorry if that wasn’t clear.
And since every number can be written in binary, you never need to consider a Turing machine with more than two characters in its alphabet.