# On large numbers **URL:** \ **Category:** Miscellaneous and Personal Stuff I Must Share\ **Created:** [December 10, 2002, 5:57am UTC](https://boards.straightdope.com/t/on-large-numbers/141721 "2002-12-10T05:57:56Z")\ **Posts on this page:** 20\ **Page:** 2
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [December 10, 2002, 11:45pm UTC](https://boards.straightdope.com/t/on-large-numbers/141721/21 "2002-12-10T23:45:37Z")
> [@](#): > > \*Originally posted by ultrafilter \* > \*\*There’s a very rough sketch of a proof in [this pdf document](http://www-2.cs.cmu.edu/afs/andrew.cmu.edu/course/15/354/Lecture/assgn2-sol.pdf). \*\* 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! ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [December 10, 2002, 11:49pm UTC](https://boards.straightdope.com/t/on-large-numbers/141721/22 "2002-12-10T23:49:59Z")
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](http://home.earthlink.net/~mrob/pub/math/largenum.html) on large numbers that should provide some interesting reading. ---
**Author:** ![iampunha](https://avatars.discourse-cdn.com/v4/letter/i/74df32/32.png) [@iampunha](https://boards.straightdope.com/u/iampunha)\ **Post date:** [December 11, 2002, 12:04am UTC](https://boards.straightdope.com/t/on-large-numbers/141721/23 "2002-12-11T00:04:57Z")
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?😉 ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [December 11, 2002, 12:52am UTC](https://boards.straightdope.com/t/on-large-numbers/141721/24 "2002-12-11T00:52:44Z")
> [@](#): > > \*Originally posted by Tyrrell McAllister \* > \*\*Would someone be able to give me some idea of why the function B, as defined, need exist? Why can’t an n-state Turing machine produce any arbitrary finite number of **1** ’s, and then halt? Why need there be a particular (very large) number B(n), such that it can produce B(n) **1** ’s before halting, but if it produces B(n) + 1 **1** ’s, then it must go one forever? \*\* 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? ---
**Author:** ![Tyrrell\_McAllister](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tyrrell_mcallister/32/16772_2.png) [@Tyrrell\_McAllister](https://boards.straightdope.com/u/Tyrrell_McAllister)\ **Post date:** [December 11, 2002, 1:13am UTC](https://boards.straightdope.com/t/on-large-numbers/141721/25 "2002-12-11T01:13:57Z")
Sounds good to me. Thanks. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [December 11, 2002, 1:32am UTC](https://boards.straightdope.com/t/on-large-numbers/141721/26 "2002-12-11T01:32:18Z")
> [@](#): > > \*Originally posted by mkl12 \* > \*_I guess that log_(googolplex) is somewhere around 5. Or is it still 4? \*\* log[sup]\*/sup is in fact equal to 5. Now you know. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [December 11, 2002, 1:52am UTC](https://boards.straightdope.com/t/on-large-numbers/141721/27 "2002-12-11T01:52:04Z")
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. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [December 11, 2002, 3:03am UTC](https://boards.straightdope.com/t/on-large-numbers/141721/28 "2002-12-11T03:03:09Z")
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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [December 11, 2002, 4:31am UTC](https://boards.straightdope.com/t/on-large-numbers/141721/29 "2002-12-11T04:31:49Z")
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? ---
**Author:** ![MaxTheVool](https://avatars.discourse-cdn.com/v4/letter/m/9fc29f/32.png) [@MaxTheVool](https://boards.straightdope.com/u/MaxTheVool)\ **Post date:** [December 11, 2002, 8:55am UTC](https://boards.straightdope.com/t/on-large-numbers/141721/30 "2002-12-11T08:55:22Z")
> [@](#): > > \*Originally posted by ultrafilter \* > \*\*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? \*\* 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? ---
**Author:** ![Flymaster](https://avatars.discourse-cdn.com/v4/letter/f/c4cdca/32.png) [@Flymaster](https://boards.straightdope.com/u/Flymaster)\ **Post date:** [December 11, 2002, 9:05am UTC](https://boards.straightdope.com/t/on-large-numbers/141721/31 "2002-12-11T09:05:07Z")
> [@](#): > > \*Originally posted by MaxTheVool \* > \*\*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. ---
**Author:** ![RTFirefly](https://avatars.discourse-cdn.com/v4/letter/r/c77e96/32.png) [@RTFirefly](https://boards.straightdope.com/u/RTFirefly)\ **Post date:** [December 11, 2002, 3:58pm UTC](https://boards.straightdope.com/t/on-large-numbers/141721/32 "2002-12-11T15:58:05Z")
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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [December 11, 2002, 4:39pm UTC](https://boards.straightdope.com/t/on-large-numbers/141721/33 "2002-12-11T16:39:29Z")
> [@](#): > > \*Originally posted by RTFirefly \* > **Cool thread, ultrafilter.** Thanks. > [@](#): > > **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. \*\* 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”. ---
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [December 11, 2002, 5:50pm UTC](https://boards.straightdope.com/t/on-large-numbers/141721/34 "2002-12-11T17:50:13Z")
> [@](#): > > Cause you see, this machine can’t calculate it’s own busy beaver function. Ha! 😃 ---
**Author:** ![Derleth](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@Derleth](https://boards.straightdope.com/u/Derleth)\ **Post date:** [December 11, 2002, 6:00pm UTC](https://boards.straightdope.com/t/on-large-numbers/141721/35 "2002-12-11T18:00:18Z")
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.) ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [December 11, 2002, 7:58pm UTC](https://boards.straightdope.com/t/on-large-numbers/141721/36 "2002-12-11T19:58:15Z")
> [@](#): > > \*Originally posted by Derleth \* > \*\*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? ---
**Author:** ![Lockz](https://avatars.discourse-cdn.com/v4/letter/l/f4b2a3/32.png) [@Lockz](https://boards.straightdope.com/u/Lockz)\ **Post date:** [December 11, 2002, 9:47pm UTC](https://boards.straightdope.com/t/on-large-numbers/141721/37 "2002-12-11T21:47:19Z")
> [@](#): > > \*Originally posted by Flymaster \* > \*\*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. \*\* Is it the same TM if δ is different? I may be wrong, but wouldn’t the transition function be changing? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [December 11, 2002, 11:22pm UTC](https://boards.straightdope.com/t/on-large-numbers/141721/38 "2002-12-11T23:22:52Z")
They’re isomorphic. They look different, but for all intents and purposes, they’re the same. ---
**Author:** ![MaxTheVool](https://avatars.discourse-cdn.com/v4/letter/m/9fc29f/32.png) [@MaxTheVool](https://boards.straightdope.com/u/MaxTheVool)\ **Post date:** [December 12, 2002, 4:36am UTC](https://boards.straightdope.com/t/on-large-numbers/141721/39 "2002-12-12T04:36:32Z")
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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [December 12, 2002, 5:19am UTC](https://boards.straightdope.com/t/on-large-numbers/141721/40 "2002-12-12T05:19:24Z")
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. [Previous page](https://boards.straightdope.com/t/on-large-numbers/141721.md?page=1) [Next page](https://boards.straightdope.com/t/on-large-numbers/141721.md?page=3)