A project for the board: Finding Monroe's Number

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
dhokarena56
Posts: 179
Joined: Fri Mar 27, 2009 11:52 pm UTC

A project for the board: Finding Monroe's Number

Postby dhokarena56 » Wed Oct 12, 2011 1:25 am UTC

This is from strip 207, "What does XKCD mean?"

what does xkcd mean.png
what does xkcd mean.png (21.2 KiB) Viewed 3723 times


So, here's my question: is it possible to take this unimaginably vast number and describe it in a way that's more than just "the product of the Ackermann function with Graham's number as both inputs"? I think it is, but I don't know where to start. However, if any of you guys are bored...it might be fun.
Come join Dadapedia- the open-source Dadaist novel that anyone can edit.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: A project for the board: Finding Monroe's Number

Postby skeptical scientist » Wed Oct 12, 2011 2:24 am UTC

You could write out its decimal expansion. Have fun.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
dhokarena56
Posts: 179
Joined: Fri Mar 27, 2009 11:52 pm UTC

Re: A project for the board: Finding Monroe's Number

Postby dhokarena56 » Wed Oct 12, 2011 2:51 am UTC

skeptical scientist wrote:You could write out its decimal expansion. Have fun.

Except that even Graham's number itself is so big that it's got more digits than there are atoms in the universe.
Come join Dadapedia- the open-source Dadaist novel that anyone can edit.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A project for the board: Finding Monroe's Number

Postby Yakk » Wed Oct 12, 2011 3:19 am UTC

At the scales that number exists at, low-information descriptions of numbers are few and far between. I'd say that the odds that there is a different way to describe that particular number using any reasonable number of bits that do not end up being A(G_64, G_64) dressed up in drag are low. Of course, I could be surprised!
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: A project for the board: Finding Monroe's Number

Postby skeptical scientist » Wed Oct 12, 2011 8:19 am UTC

dhokarena56 wrote:
skeptical scientist wrote:You could write out its decimal expansion. Have fun.

Except that even Graham's number itself is so big that it's got more digits than there are atoms in the universe.
Similarly, your odds of getting struck by lightning indoors on a sunny day are so low that they are less than 1%!
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Waterice man
Posts: 10
Joined: Wed Oct 12, 2011 2:50 pm UTC

Re: A project for the board: Finding Monroe's Number

Postby Waterice man » Wed Oct 12, 2011 2:58 pm UTC

Here's a definition. Let W_IM = sup{numbers people have ever seen represented in any way} I will call this number Waterice Man's Number. Then W_IM = f(A(g_64,g_64)), for some unknown function f such that W_IM > A(g_64,g_64)

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26740
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: A project for the board: Finding Monroe's Number

Postby gmalivuk » Wed Oct 12, 2011 9:54 pm UTC

skeptical scientist wrote:
dhokarena56 wrote:
skeptical scientist wrote:You could write out its decimal expansion. Have fun.

Except that even Graham's number itself is so big that it's got more digits than there are atoms in the universe.
Similarly, your odds of getting struck by lightning indoors on a sunny day are so low that they are less than 1%!
Yeah, and even that analogy pales in comparison.

In order to get to a number smaller than the number of particles in the universe, you'd have to iterate "the number of digits in the number of digits in ... the number of digits in the xkcd number" more times than there are particles in the universe.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Waterice man
Posts: 10
Joined: Wed Oct 12, 2011 2:50 pm UTC

Re: A project for the board: Finding Monroe's Number

Postby Waterice man » Wed Oct 12, 2011 10:31 pm UTC

Or in order to get a number smaller than the number of particles in the universe, you could try 1

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26740
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: A project for the board: Finding Monroe's Number

Postby gmalivuk » Wed Oct 12, 2011 10:33 pm UTC

Sure, but then we'd cut your arm off to teach you a lesson.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Timefly
Posts: 56
Joined: Sun Nov 14, 2010 7:30 pm UTC

Re: A project for the board: Finding Monroe's Number

Postby Timefly » Wed Oct 12, 2011 10:49 pm UTC


Deveno
Posts: 29
Joined: Thu Oct 06, 2011 10:14 pm UTC

Re: A project for the board: Finding Monroe's Number

Postby Deveno » Thu Oct 13, 2011 8:24 am UTC

Timefly wrote:http://en.wikipedia.org/wiki/TREE(3)

DUM DUM DUM DUM


wikipedia says: no page for TREE(3....did you mean TREE(3)?

but i've got that beat:

floor(1/ε), where ε is an infinitesimal.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: A project for the board: Finding Monroe's Number

Postby skeptical scientist » Thu Oct 13, 2011 8:37 am UTC

gmalivuk wrote:Yeah, and even that analogy pales in comparison.

In order to get to a number smaller than the number of particles in the universe, you'd have to iterate "the number of digits in the number of digits in ... the number of digits in the xkcd number" more times than there are particles in the universe.

My analogy wasn't supposed to give any idea of the size of Graham's number—a hopeless task if there ever was one—but just point out that his analogy was a laughable underestimate. Your analogy is no better than his, as the difference between 1010^100* and 10 ↑↑ 10100** is already completely meaningless at the scale of g1 = 3 ↑↑↑↑ 3.

*A number with more digits than there are particles in the universe.
**A number where you'd have to iterate "the number of digits in the number of digits in ... the number of digits in this number" more times than there are particles in the universe to get a number smaller than the number of particles in the universe.




Interestingly, according to Wikipedia, there's a simple polynomial-time* algorithm for computing the last n digits in the decimal expansion of Graham's number.

*Well, technically it's constant time, as there are only log(Graham's number) digits to compute. But for all intents and purposes, it's a non-constant polynomial time algorithm.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

topspin
Posts: 1
Joined: Tue Oct 25, 2011 9:11 pm UTC

Re: A project for the board: Finding Monroe's Number

Postby topspin » Tue Oct 25, 2011 9:43 pm UTC

Hi there guys! Long time reader, first time poster here.
I've been thinking about the following back when the strip came out originally, but as this thread brought it back (almost) alive I finally decided to ask. (Although I'm probably off or somebody much smarter would have already pointed it out)

Is putting Graham's number into the Ackermann function really that large of a step, considering how both of them are/grow incomprehensibly huge already??

So we know the Ackermann function grows faster than any primitive recursive function, because of its recursive definition. And the definition of Graham's Number doesn't look too different, either. I've been of the impression that you don't get any significantly faster growth without resorting to uncomputable functions (BB).

Straight from Wikipedia:

[math]A(m, n) = 2\uparrow^{m-2} (n+3) - 3[/math]
[math]G = g_{64},\text{ where }g_1=3\uparrow\uparrow\uparrow\uparrow 3,\ g_n = 3\uparrow^{g_{n-1}}3[/math]

So putting the two together gets you:
[math]A(g_{64}, g_{64}) = 2\uparrow^{g_{64}-2} (g_{64}+3) - 3 \approx 2\uparrow^{g_{64}} (g_{64})[/math]
Per the definition of [imath]x\uparrow^n y[/imath], isn't that approximately on the same order (very loosely speaking) as [imath]g_{65}[/imath]? (or maybe [imath]g_{66}[/imath]??)

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26740
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: A project for the board: Finding Monroe's Number

Postby gmalivuk » Wed Oct 26, 2011 2:51 am UTC

topspin wrote:isn't that approximately on the same order (very loosely speaking) as [imath]g_{65}[/imath]?
Yeah, I think I calculated once that A(gn,gn)<gn+1
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A project for the board: Finding Monroe's Number

Postby Yakk » Wed Oct 26, 2011 4:06 am UTC

Topspin, there are a number of threads on this board that deal with "who has the larger number".

Some of them restrict you to various computable subsets of number descriptions, to rule out BB(n) and the like.

The functions described grow more than slightly faster than g_n.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

mfb
Posts: 948
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: A project for the board: Finding Monroe's Number

Postby mfb » Wed Oct 26, 2011 12:52 pm UTC

To get larger numbers, you can just increase the depth of the recursions:
c=g g_64...
Define f(n,m)=g_f(n-1,m) and f(0,m)=g_m, so f(1,64)=c, and f(g_64,64) is way larger than any non-recursive use of g_n will ever be.
Note that it is pointless to increase the second value, as f(g_64,g_64)=f(g_64+1,64).

Define fk(n,m)=fk-1(fk(n,m),m) with f1=f as defined above, so k is the level of recursion of the definition.
Look at fg_64(64,64) ;)
If that is not enough, build another recursion for ff(...), build a function that handles n levels of recursive definitions at once, use recursion on that and so on.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A project for the board: Finding Monroe's Number

Postby Yakk » Wed Oct 26, 2011 1:59 pm UTC

mfb, there are a number of threads on this board that deal with "who has the larger number".

The functions described therein grow more than slightly faster than your means of describing getting larger numbers. Go read them. In order, because the later pages won't make much sense.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: A project for the board: Finding Monroe's Number

Postby WarDaft » Thu Oct 27, 2011 5:22 am UTC

And they might not make much sense anyway. Considering how thoroughly we chewed it up and pushed it, it's remarkable that there's sense to be made of it at all.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: A project for the board: Finding Monroe's Number

Postby Yakk » Thu Oct 27, 2011 2:10 pm UTC

WarDaft wrote:And they might not make much sense anyway. Considering how thoroughly we chewed it up and pushed it, it's remarkable that there's sense to be made of it at all.

Ya, but you can easily get to parts where you are dealing with ridiculously ridiculous (actually, I don't think I can use enough adjectives without referring back to a function in the threads in question, so two will do) growth rates before every post is unreadable.

Note that many posts will be junk in those threads, but distinguishing is difficult (much as determining which huge number is more huge...).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests