March 16, 2006 12:16 AM Subscribe

Who can name the bigger number? I guarantee you will lose to the Busy Beavers. (No, infinity is not allowed, the bigger infinity is a different game.) The author also debunks in very simple terms the recent story that quantum computers perform calculations without being turned on. My first post and disclaimer: I know the author from our mutual field of quantum information.

posted by gregv (113 comments total) 13 users marked this as a favorite

posted by gregv (113 comments total) 13 users marked this as a favorite

Great post.

posted by null terminated at 12:40 AM on March 16, 2006

posted by null terminated at 12:40 AM on March 16, 2006

Add one to each of the first k digits of pi, then raise the first to the second to the third to the fourth, etc.

By choosing k much greater than the number of digits that the average person can write under the time limit, you should be able to win against anyone who uses a string of exponentials.

The number of digits of pi is explicitly illegal under the rules.

posted by agent at 12:43 AM on March 16, 2006

By choosing k much greater than the number of digits that the average person can write under the time limit, you should be able to win against anyone who uses a string of exponentials.

The number of digits of pi is explicitly illegal under the rules.

posted by agent at 12:43 AM on March 16, 2006

Thanks null, good one agent.

I should clarify: what is debunked is the wording of a press release, not the content of the paper on which the press release was based. As so often happens, popularizing a science story led to more misunderstanding than anything.

posted by gregv at 1:00 AM on March 16, 2006

I should clarify: what is debunked is the wording of a press release, not the content of the paper on which the press release was based. As so often happens, popularizing a science story led to more misunderstanding than anything.

posted by gregv at 1:00 AM on March 16, 2006

Outstanding post. Thank you.

When posed the question in the headline and before reading the article, I initially imagined "googleplex, raised to the googleplex power, result raised to the googleplex power, result raised to the googleplex power, with this operation repeated googleplex times."

The essay was an excellent read just to learn about Ackermann numbers, when it dawned on me that they essentially codified what I'd imagined. I could alternately write my number "googleplex googleplexated"!

Oh, and the Busy Beaver numbers are cool, too. Can't say I completely grasp them, though!

posted by darkstar at 1:00 AM on March 16, 2006

When posed the question in the headline and before reading the article, I initially imagined "googleplex, raised to the googleplex power, result raised to the googleplex power, result raised to the googleplex power, with this operation repeated googleplex times."

The essay was an excellent read just to learn about Ackermann numbers, when it dawned on me that they essentially codified what I'd imagined. I could alternately write my number "googleplex googleplexated"!

Oh, and the Busy Beaver numbers are cool, too. Can't say I completely grasp them, though!

posted by darkstar at 1:00 AM on March 16, 2006

You have fifteen seconds. Using standard math notation, English words, or both, name a single whole number—not an infinity—on a blank index card. Be precise enough for any reasonable modern mathematician to determine exactly what number you’ve named, by consulting only your card and, if necessary, the published literature.

Whilst pi itself is irrational (i.e., not a whole number), the number of digits in pi is certainly a whole number. The fact that pi can be expressed as an infinite value of non-repeating digits, does not make the of digits in pi equal to infinity.

*Hopes for partial credit on answer.*

posted by three blind mice at 1:08 AM on March 16, 2006

Hmm...googleplex googleplexated, result googleplexated, operation repeated googleplex googleplexated times...

...result googleplexated...

...operation repeated googleplex googleplexated googleplexated time....

/me goes and sits in the corner for a while...

posted by darkstar at 1:10 AM on March 16, 2006

...result googleplexated...

...operation repeated googleplex googleplexated googleplexated time....

/me goes and sits in the corner for a while...

posted by darkstar at 1:10 AM on March 16, 2006

pi is not just irrantional, it's transcendtal meaning it can't be expressed algebaically. There are no whole numbers, nor finite number of combinations of whole numbers by which one can define pi. The number of digits fails to be expressed as a whol,e numer or, really, any number at all. It is an infinity.

posted by mce at 1:33 AM on March 16, 2006

posted by mce at 1:33 AM on March 16, 2006

TBM: Heh, I realized after I posted that that may come off as a bit snappish...sorry about that!

Do you mean the number of digits in pi as the number of unique digits (10 in base 10, 16 in hex, etc)? Otherwise I'm not following; if you pick a number k, I can give you (in theory) the k+1th digit of pi, so there is no whole number that describes the number of digits in pi.

On preview, mce fielded it.

More on topic, two different computability classes and this is the first I've seen of the Busy Beaver numbers. Mathworld provides a bit more background on the type of Turing machines used to (try to) derive these numbers.

posted by agent at 1:44 AM on March 16, 2006

Do you mean the number of digits in pi as the number of unique digits (10 in base 10, 16 in hex, etc)? Otherwise I'm not following; if you pick a number k, I can give you (in theory) the k+1th digit of pi, so there is no whole number that describes the number of digits in pi.

On preview, mce fielded it.

More on topic, two different computability classes and this is the first I've seen of the Busy Beaver numbers. Mathworld provides a bit more background on the type of Turing machines used to (try to) derive these numbers.

posted by agent at 1:44 AM on March 16, 2006

However, most of the Busy Beaver numbers *themselves* do not qualify, since "any reasonable modern mathematician" cannot necessarily "determine exactly what number you’ve named, by consulting only your card and, if necessary, the published literature".

They're theoretical numbers, the values of which have not yet been precisely determined beyond the first few. His argument that they're allowable because they're "well-defined mathematically" violates his own rules. He didn't say the number had to be "well-defined", he said it had to be *exactly determinable* by any reasonable modern mathematician. They're not. He cheated. :)

Also, a lot of the numbers he brings up are fairly easy to defeat by working from the angle of number of digits rather than algorythmic calculation, in the same way that a googol (one followed by a hundred zeroes) is considerably smaller than one followed by a googol zeroes.

Given the 15-second rule, it'd probably be best to use something quickly nameable and easily identifiable for ease of writing, so maybe ...

"9 followed by a number of nines equal to (the largest known Mersenne Prime) (raised to the power of the largest known Mersenne Prime) (the largest known Mersenne Prime times)."

I brought that in under 15 seconds. Essentially, that uses an Ackermann number, but instead of using the number itself, it uses that number to determine the number of digits. The number I named itself has 6,321,430 digits. I like that it's always precisely defined at any given time, but it will actually grow as knowledge increases ...

On the other hand, I have absolutely no idea whatsoever if that number is higher or lower than agent's pi-based algorythm, or darkstar's repeated googolplexalating ... I'm not a mathematician. Anyone care to make the comparison?

Naturally, whatever you've written, if you've got a fraction of a second left, you'd add "^9!" to the end of it or something. But at that point, I wonder if it would really matter unless you were coincidentally using the same technique ...

posted by kyrademon at 2:24 AM on March 16, 2006

They're theoretical numbers, the values of which have not yet been precisely determined beyond the first few. His argument that they're allowable because they're "well-defined mathematically" violates his own rules. He didn't say the number had to be "well-defined", he said it had to be *exactly determinable* by any reasonable modern mathematician. They're not. He cheated. :)

Also, a lot of the numbers he brings up are fairly easy to defeat by working from the angle of number of digits rather than algorythmic calculation, in the same way that a googol (one followed by a hundred zeroes) is considerably smaller than one followed by a googol zeroes.

Given the 15-second rule, it'd probably be best to use something quickly nameable and easily identifiable for ease of writing, so maybe ...

"9 followed by a number of nines equal to (the largest known Mersenne Prime) (raised to the power of the largest known Mersenne Prime) (the largest known Mersenne Prime times)."

I brought that in under 15 seconds. Essentially, that uses an Ackermann number, but instead of using the number itself, it uses that number to determine the number of digits. The number I named itself has 6,321,430 digits. I like that it's always precisely defined at any given time, but it will actually grow as knowledge increases ...

On the other hand, I have absolutely no idea whatsoever if that number is higher or lower than agent's pi-based algorythm, or darkstar's repeated googolplexalating ... I'm not a mathematician. Anyone care to make the comparison?

Naturally, whatever you've written, if you've got a fraction of a second left, you'd add "^9!" to the end of it or something. But at that point, I wonder if it would really matter unless you were coincidentally using the same technique ...

posted by kyrademon at 2:24 AM on March 16, 2006

(Admittedly, I'm not sure the eventual number mine generates is really "precisely determinable" rather than simply being "well defined". I suspect it would take rather more computing power than currently exists to calculate it, although I could be wrong. Possibly googleplexelating *is* actually the way to go, using the repeatedly googleplexated number to determine the number of zeroes after an initial 1. That's much easier to "lump" into simpler terms, meaning it can be precisely determined with significantly less computing power.)

posted by kyrademon at 2:32 AM on March 16, 2006

posted by kyrademon at 2:32 AM on March 16, 2006

This is probabilistically a good post.

posted by srboisvert at 2:56 AM on March 16, 2006

posted by srboisvert at 2:56 AM on March 16, 2006

Ooo! And for added fun, you can change the base without eating up too much of your time ... in base googleplex, after all, 10 = a googleplex, and 100 = a googleplex times a googleples ... much better than adding that largely pointless "^9!" rider or whatever.

So, bearing in mind written in 15 seconds and "precisely determinable", perhaps ...

"One followed by a number of zeroes equal to [A(A(A(A ... (googleplex total A's) ... (A(googolplex)) ... ))) where A(1)=1, A(2)=2^2, A(3)=3^3^3], in base googolplex."

Hmm. Not sure I could really get that all out in 15 seconds.

Um ... I should really go to bed now, shouldn't I.

posted by kyrademon at 3:04 AM on March 16, 2006

So, bearing in mind written in 15 seconds and "precisely determinable", perhaps ...

"One followed by a number of zeroes equal to [A(A(A(A ... (googleplex total A's) ... (A(googolplex)) ... ))) where A(1)=1, A(2)=2^2, A(3)=3^3^3], in base googolplex."

Hmm. Not sure I could really get that all out in 15 seconds.

Um ... I should really go to bed now, shouldn't I.

posted by kyrademon at 3:04 AM on March 16, 2006

kyrademon: If googolplex googolplexated is meant as the googolplexeth Ackerman operator applied to googolplex and googolplex (as 3 + 3 is the first Ackerman operator applied to 3 and 3), then that alone has either your algorithm or mine beat even before applying more googolplexating. Exponentiation increases the magnitude of numbers (number of digits) linearly, tetration appears to blow up quadratically (since a^b^c = 9^(b * c)). The fifth order operator must blow up even faster. Never mind how the googolpexeth order operator behaves...

The pi algorithm and your algorithm are both using the same tetration operator, so it comes down to the choice of k (although at a guess I would think that it has to be at least k > the largest mersenne prime squared).

posted by agent at 3:12 AM on March 16, 2006

The pi algorithm and your algorithm are both using the same tetration operator, so it comes down to the choice of k (although at a guess I would think that it has to be at least k > the largest mersenne prime squared).

posted by agent at 3:12 AM on March 16, 2006

Ach, just realized that the first Ackerman operator applied to 3 and 3 is 3 + 3 + 3. The pi algorithm doesn't really use tetration, although the output number is bounded above by 9 tetrated by k. Your first algorithm is 9^(largest mersenne prime tetrated by the largest mersenne prime). I'm not sure how to think about your second number.

Moral: no more mathing around until after I've seen the sun again.

posted by agent at 3:26 AM on March 16, 2006

Moral: no more mathing around until after I've seen the sun again.

posted by agent at 3:26 AM on March 16, 2006

Using more mundane functions, factorial blows up extremely fast. How about (googleplex!!!!!!!!!!!!!!!!!! ... as many factorials as you can write in the 15 seconds)?

posted by raygirvan at 4:52 AM on March 16, 2006

posted by raygirvan at 4:52 AM on March 16, 2006

Okay, I'm back from my corner.

If I had 15 seconds, I'd spend the first ten seconds defining a new term:

"Let a HyperAckermann be an Ackermann sequence performed on a number, recursively a number of times equal to the result of the Ackermann sequence."

I'd then spend the final five seconds to write:

"A HyperAckermanned googolplex."

If I could propose that a googleplex googleplexated be called a "darkstarplex", the result would be a darkstarplex darkstarplexated.

-- And on preview, taking a tip from raygirvan, you could write: A HyperAckermanned googolplex!!!!!!!

I'm going back to my corner, now.

posted by darkstar at 4:54 AM on March 16, 2006

If I had 15 seconds, I'd spend the first ten seconds defining a new term:

"Let a HyperAckermann be an Ackermann sequence performed on a number, recursively a number of times equal to the result of the Ackermann sequence."

I'd then spend the final five seconds to write:

"A HyperAckermanned googolplex."

If I could propose that a googleplex googleplexated be called a "darkstarplex", the result would be a darkstarplex darkstarplexated.

-- And on preview, taking a tip from raygirvan, you could write: A HyperAckermanned googolplex!!!!!!!

I'm going back to my corner, now.

posted by darkstar at 4:54 AM on March 16, 2006

I just noticed that what I proposed is only a second order Hyperackermann of googleplex. You could surely have higher orders...

Giddy!

posted by darkstar at 4:59 AM on March 16, 2006

Giddy!

posted by darkstar at 4:59 AM on March 16, 2006

His most recent blog post about the essay is really touching (albeit kind of depressing to a wannabe math nerd like me who found the essay fascinating).

posted by miagaille at 5:11 AM on March 16, 2006

posted by miagaille at 5:11 AM on March 16, 2006

Folks, you're playing with the wrong tools.

The number of digits of pi is illegal, because it is infinite, and that's another game.

Ackermann numbers and the Hyper operator are good. Knuth's arrows are better, in that they're a faster way to write the hyper operator.

But for Fucking BIg™, you need Chained Arrows. Because I'll take 3→2→2→2 over anything up there, and if that's not enough, 3→2→2→200 is so large that you cannot possibly write it down, given the size of the universe and the Planck Length. Yet, using number theory, you can figure out as many of the digits as you desire (and can fit on the page.)

And, of course, there's the definition trick. I hereby define Wowza as equal to 1+N, where N is equal to the sum of the absolute value of all the other numbers entered into the competition.

Thus, I enter Wowza, and look forward to the infinite loop.

posted by eriko at 5:29 AM on March 16, 2006

The number of digits of pi is illegal, because it is infinite, and that's another game.

Ackermann numbers and the Hyper operator are good. Knuth's arrows are better, in that they're a faster way to write the hyper operator.

But for Fucking BIg™, you need Chained Arrows. Because I'll take 3→2→2→2 over anything up there, and if that's not enough, 3→2→2→200 is so large that you cannot possibly write it down, given the size of the universe and the Planck Length. Yet, using number theory, you can figure out as many of the digits as you desire (and can fit on the page.)

And, of course, there's the definition trick. I hereby define Wowza as equal to 1+N, where N is equal to the sum of the absolute value of all the other numbers entered into the competition.

Thus, I enter Wowza, and look forward to the infinite loop.

posted by eriko at 5:29 AM on March 16, 2006

24's the highest number. (scroll down to "Mafia Mathematicians)

posted by TheWash at 5:42 AM on March 16, 2006

posted by TheWash at 5:42 AM on March 16, 2006

I think Wowza would be disqualified, according to the FPP.

Arrow notation was what I was thinking, but it looks like the Beaver numbers (heh) would beat that.

posted by justkevin at 5:46 AM on March 16, 2006

Arrow notation was what I was thinking, but it looks like the Beaver numbers (heh) would beat that.

posted by justkevin at 5:46 AM on March 16, 2006

Heh.

Thank god someone debunked that idiotic quantum computer story. I can't belive anyone thought that was real and not idiotic science writing.

posted by delmoi at 5:51 AM on March 16, 2006

Great post.

And that blog is excellent - bookmarked.

posted by thatwhichfalls at 5:58 AM on March 16, 2006

And that blog is excellent - bookmarked.

posted by thatwhichfalls at 5:58 AM on March 16, 2006

Wait a minute, can you define recursive functions?

If not why not do something like:

f(x) = f(x + f(x-1)^{(f(x-1)})

then, insanciate f(x) with some large number 10^{100}. I'm pretty sure f(10^{100}) beats anything posted on the page so far, and that's without using any exotic operators or funky numbers no one's heard of.

And of course, you could define some exotic operators and put them in this sort of function if you wanted too.

posted by delmoi at 6:03 AM on March 16, 2006

If not why not do something like:

f(x) = f(x + f(x-1)

then, insanciate f(x) with some large number 10

And of course, you could define some exotic operators and put them in this sort of function if you wanted too.

posted by delmoi at 6:03 AM on March 16, 2006

Actually you'd want to do something like f(0) = 0, f(x | x ≠ 0) = f(x + f(x-1)(f(x-1)).

If you don't want logic in your function you could do f(x) = f(x + f(x/2)(f(x/2)), which is smaller, but f(0) = 0 'naturally'.

posted by delmoi at 6:06 AM on March 16, 2006

Aha! The Hyper operator and the Knuth up-arrows reflect the 2nd order HyperAckermann I suggested above. Using Conway chained arrow notation allows you to represent higher orders. Excellent!

So, let's say we have an Ackermann of googleplex, whch is googleplex --> googleplex = darkstarplex. The HyperAckermann of googleplex I proposed would be written darkstarplex --> darkstarplex. Or, a 4th order chained Ackermann of googleplex, I guess.

This provides the notation for what I was getting at Using this notation, you could just write:

"Conway notation: googleplex-->googleplex-->googleplex-->googleplex-->googleplex--> ..." as many times as you could in 15 seconds. However, at this point the winner would be based on how fast you could write "googleplex", compared to how fast you could write a simpler number (a digit) instead of "googleplex", and making up the difference in being able to write more links in the Conway chain.

I suspect that, by being able to use this notation, you would probably get more mileage out of the latter. Pick a simple digit to write (other than 1), such as 7, and you've got a winner, I think.

posted by darkstar at 6:18 AM on March 16, 2006

So, let's say we have an Ackermann of googleplex, whch is googleplex --> googleplex = darkstarplex. The HyperAckermann of googleplex I proposed would be written darkstarplex --> darkstarplex. Or, a 4th order chained Ackermann of googleplex, I guess.

This provides the notation for what I was getting at Using this notation, you could just write:

"Conway notation: googleplex-->googleplex-->googleplex-->googleplex-->googleplex--> ..." as many times as you could in 15 seconds. However, at this point the winner would be based on how fast you could write "googleplex", compared to how fast you could write a simpler number (a digit) instead of "googleplex", and making up the difference in being able to write more links in the Conway chain.

I suspect that, by being able to use this notation, you would probably get more mileage out of the latter. Pick a simple digit to write (other than 1), such as 7, and you've got a winner, I think.

posted by darkstar at 6:18 AM on March 16, 2006

They're theoretical numbers, the values of which have not yet been precisely determined beyond the first few. His argument that they're allowable because they're "well-defined mathematically" violates his own rules. He didn't say the number had to be "well-defined", he said it had to be *exactly determinable* by any reasonable modern mathematician. They're not. He cheated. :)

They are exactly determined. The arabic numeral base-10 place-value specification is no more a specific representation of "the number" than BusyBeaver(100).

posted by sonofsamiam at 6:45 AM on March 16, 2006

On gregv's entry in the MeFi record book, there will be the footnote: "HR first time at bat."

Truly a magnificent post. A fair number of posts interest or amuse me for a moment before I go on to the next; very, very few get me to spend a significant amount of time reading a long piece of writing with such absorption I'm sorry when I come to the end (and this when I've got a ton of work to do!). That "bigger number" paper awakened the sense of wonder I felt back when I was a math major (and which the math department ground out of me with endless calculus courses, driving me into the arms of the linguistics department). Many thanks.

When I read the challenge, my first impulse was to write "Googol to the googol to the googol to the..." as many times as I could in 15 seconds; I was humbled to discover what a puny number that was in the scheme of things.

I loved this (from the "debunks" link):

Readers,**my sole ambition in life, outside the purely personal, is to prevent stuff like this from being spouted.**

Mine too, except that "this" in my case refers to misunderstandings about language and how it works.

posted by languagehat at 6:47 AM on March 16, 2006

Truly a magnificent post. A fair number of posts interest or amuse me for a moment before I go on to the next; very, very few get me to spend a significant amount of time reading a long piece of writing with such absorption I'm sorry when I come to the end (and this when I've got a ton of work to do!). That "bigger number" paper awakened the sense of wonder I felt back when I was a math major (and which the math department ground out of me with endless calculus courses, driving me into the arms of the linguistics department). Many thanks.

When I read the challenge, my first impulse was to write "Googol to the googol to the googol to the..." as many times as I could in 15 seconds; I was humbled to discover what a puny number that was in the scheme of things.

I loved this (from the "debunks" link):

Readers,

Mine too, except that "this" in my case refers to misunderstandings about language and how it works.

posted by languagehat at 6:47 AM on March 16, 2006

geez, you guys are so wedded to your akermans. Fine

z(0) = 0

z(x ≠ 0) = z(x → z(x-1))

z(10^{1010}) is larger then any number so far presented. I still think my above recursive fnction is larger then anything posted before it or after it. And yeah you could start with an ackerman in there as well z(100→100) or whatever.

posted by delmoi at 6:55 AM on March 16, 2006

z(0) = 0

z(x ≠ 0) = z(x → z(x-1))

z(10

posted by delmoi at 6:55 AM on March 16, 2006

Oops, turned out I was using ackermann functions incorrectly in my above post. they work like this:

x→y→3 = x^{yyy}

just the first numer to the second number over and over again n times, where n is the third number.

My initial function with a large parameter, such as f(10^{100}) is in fact much, much larger then darkstar's solution.

Yes, you could make it larger by using Ackermann's in the definition, but not by so much that you couldn't make my function come out ahead using a larger, yet still easily expressible number (I think).

No obviously I'm not going to try to prove that...

posted by delmoi at 7:05 AM on March 16, 2006

x→y→3 = x

just the first numer to the second number over and over again n times, where n is the third number.

My initial function with a large parameter, such as f(10

Yes, you could make it larger by using Ackermann's in the definition, but not by so much that you couldn't make my function come out ahead using a larger, yet still easily expressible number (I think).

No obviously I'm not going to try to prove that...

posted by delmoi at 7:05 AM on March 16, 2006

Lol.

posted by delmoi at 7:13 AM on March 16, 2006

mce, I think you're confusing imaginary numbers (such as the square root of negative one) with irrational numbers (those that cannot be expressed as a ratio of integers.)

In Euclidean gemoetry, me, Pi is a constant defined as the ratio of a circle's circumference to its diameter. Nothing could be easier simpler to express algabraically: pi=C/d.

The number of digits in pi is as precise as I need to be for a modern, or ancient, mathematician to know exactly what I mean. It is believed to be infinite, but I did not claim it as such in my answer and as far as I know there is no mathematical proof that it is.

*still hanging in for partial credit*

posted by three blind mice at 7:14 AM on March 16, 2006

Let a1(x,f) = f(f(f(...))) such that f is applied to x x times.

Let a2(x,f) = a(x,a(x,a(x,...))) such that a(x,.) is self-applied x times.

...

Let an(x,f) = nth-order self-application as above.

Let my entry = a1000(1000, x^x)

posted by sonofsamiam at 7:15 AM on March 16, 2006

Let a2(x,f) = a(x,a(x,a(x,...))) such that a(x,.) is self-applied x times.

...

Let an(x,f) = nth-order self-application as above.

Let my entry = a1000(1000, x^x)

posted by sonofsamiam at 7:15 AM on March 16, 2006

three blind mice: the problem is that one of C or d is itself necessarily transcendental. pi is definitely transcendental.

posted by sonofsamiam at 7:16 AM on March 16, 2006

posted by sonofsamiam at 7:16 AM on March 16, 2006

What a great, rich post. Thanks, gregv. I especially appreciated the highly readable introduction to quantum computing; bookmarked for later.

Yes, please do add some tags so folks will be able to find this post easily once it scrolls off the front page.

posted by mediareport at 7:18 AM on March 16, 2006

Yes, please do add some tags so folks will be able to find this post easily once it scrolls off the front page.

posted by mediareport at 7:18 AM on March 16, 2006

Not Wowza, by definition. ;)

Of course, we can break things. What is z(Wowza) ?

posted by eriko at 7:20 AM on March 16, 2006

See, eriko, that's what happens when you use meta-mathematical stuff that steps outside the domain of statements derivable from the ZF axioms. It blows up!

"All is number" is wrong. All is metanumber :)

posted by sonofsamiam at 7:27 AM on March 16, 2006

"All is number" is wrong. All is metanumber :)

posted by sonofsamiam at 7:27 AM on March 16, 2006

sonofsamiam: cute.

Anyway, going back to my f(), f(3) would actually be:

3 + (2 + 1^{1})^{(2+11)}

f(4) would be

4 + (3 + (2 + 1^{1})^{(2+11)})^{(3 + (2 + 11)(2+11))})

Which could be more simply written as

4 + ((3^{3})^{(33)})

f(5) would then be

5+(4 + (9^{9})^{(4 + (99)}) = 5+387420493^{387420493}

And so on.

posted by delmoi at 7:39 AM on March 16, 2006

Anyway, going back to my f(), f(3) would actually be:

3 + (2 + 1

f(4) would be

4 + (3 + (2 + 1

Which could be more simply written as

4 + ((3

f(5) would then be

5+(4 + (9

And so on.

posted by delmoi at 7:39 AM on March 16, 2006

3 Blind Mice:

You'll get your credit as soon as someone finishes counting the number of digits in pi.

Fair?

posted by empath at 7:47 AM on March 16, 2006

You'll get your credit as soon as someone finishes counting the number of digits in pi.

Fair?

posted by empath at 7:47 AM on March 16, 2006

If you'd read the article, you'd see that Wowza was an invalid entry...

posted by delmoi at 7:47 AM on March 16, 2006

O^{MG} W^{TF} B^{BQ} !^{1!}

p.s. fantastic post!

posted by furtive at 7:48 AM on March 16, 2006 [1 favorite]

p.s. fantastic post!

posted by furtive at 7:48 AM on March 16, 2006 [1 favorite]

Pi, btw, is a transcendental number.

The number of digits in pi is infinite. It would be the equivilent of giving the answer of 'whatever number you can think of +1'

posted by empath at 7:53 AM on March 16, 2006

The number of digits in pi is infinite. It would be the equivilent of giving the answer of 'whatever number you can think of +1'

posted by empath at 7:53 AM on March 16, 2006

three blind mice: The decimal expansion of pi certainly has an infinite number of digits. If it had a finite (whole) number of digits, then it would be rational. If it were rational, then it could not be transcendental. But pi is transcendental, so it cannot be rational, and hence must have an infinite number of digits in its decimal expansion. There is your proof, though the linked part is where most of the work occurs.

posted by warcode at 7:56 AM on March 16, 2006

posted by warcode at 7:56 AM on March 16, 2006

From the article:

*Turing answered using an idealized computing machine—the Turing machine—that, in essence, is equivalent to every Compaq, Dell, Macintosh, and Cray in the modern world. Turing’s paper describing his machine, "On Computable Numbers," is rightly celebrated as the founding document of computer science.*

Sort of, a turing machine could emulate a modern PC, and a PC can emulate a turing machine, but they are not at all alike other then that they can do the same things

posted by delmoi at 8:01 AM on March 16, 2006

Sort of, a turing machine could emulate a modern PC, and a PC can emulate a turing machine, but they are not at all alike other then that they can do the same things

posted by delmoi at 8:01 AM on March 16, 2006

Oh, also Turing machines have unlimited tape, and PCs have limited RAM, so while a Turing machine can run forever, a PC program will *eventually* stop or get stuck into a infinite loop. And so you can actually answer the halting problem for any actual computer program, although doing so on a modern PC would take until the end of the universe.

Basically just take every bit of memory on the computer, so if you have a 99gb hard drive, and 1gb of RAM. You have 2^{100*30*8} bits of memory. That means you have 2^{2100*30*8} possible states. If any state is repeated, you'll know that the machine is stuck in a loop, and will never halt.

posted by delmoi at 8:08 AM on March 16, 2006

Basically just take every bit of memory on the computer, so if you have a 99gb hard drive, and 1gb of RAM. You have 2

posted by delmoi at 8:08 AM on March 16, 2006

Ack, sorry, I meant 100*2^{30*8} states and 2^{100*230*8} states.

In other words, a PC with 100 gigs of memory is can be thought of as a finite state machine with 2^{100*230*8} states.

posted by delmoi at 8:11 AM on March 16, 2006

In other words, a PC with 100 gigs of memory is can be thought of as a finite state machine with 2

posted by delmoi at 8:11 AM on March 16, 2006

Hmm, the busy beaver thing takes advantage of the fact that Turing machines have infinite tape. The largest number you can express by that method on a real computer is equal to the number of states.

posted by delmoi at 8:16 AM on March 16, 2006

posted by delmoi at 8:16 AM on March 16, 2006

It's no wonder the article on quantum computing was so poorly written, the reporter was talking to a guy who wrote this:

posted by Chuckles at 8:17 AM on March 16, 2006

d. By putting the Zeno effect inside of another Zeno effect, you can work it so that even if you are looking to exclude a particular database element, and the answer *is* that element, then the computer doesn’t run (but you still get the answer). Therefore, you can now check each of the elements one by one, to find the answer without the computer running. This was the first main theoretical point of the paper. Contrary to some popular press descriptions, we did not implement this experimentally (nor do we intend to, as it’s likely to be inconveniently difficult).In responce to this:

I'll end with the clearest account of counterfactual computing I've seen, courtesy of one Homer J. Simpson.And, his only justification is, the idea is too complicated for regular people to understand.Dear Lord, the gods have been good to me. As an offering, I present these milk and cookies. If you wish me to eat them instead, please give me no sign whatsoever.

posted by Chuckles at 8:17 AM on March 16, 2006

hows about:

(10,10^2,10^3,10^4,....10^googleplex)!

where my notation indicates each term is raised by the previous term factorial

(a,b,c,d,...)! == (a!^(b!^(c!^(d!^...))))!

who knows how big that is.

posted by ozomatli at 8:21 AM on March 16, 2006

(10,10^2,10^3,10^4,....10^googleplex)!

where my notation indicates each term is raised by the previous term factorial

(a,b,c,d,...)! == (a!^(b!^(c!^(d!^...))))!

who knows how big that is.

posted by ozomatli at 8:21 AM on March 16, 2006

Well, the factorial of a number is less then that number rased to it's own power. So your numbers is less then

(a^(a+b^(b+c)...))). Since a, b, and c and so on are 10

g(x < 0)=0 g(0)=10; g(x> 0) = g(x-1)

Which is almost exactly the same thing as f, but with the addition in the exponent. However, since you used fractorals it's much, much smaller then f.

I still win :)

That said, obvoiusly you can modify f by using a multiplication or a exponentiation (or even an ackermann, or even f(x-1) again). The point is though that it's the recursive explosion that generates the huge number.

posted by delmoi at 8:43 AM on March 16, 2006

Oh, but since no one has done it I propose a new recursive function q such that q(x) = q(x-1)*BB(x-1) where BB is the busy beaver function :)

posted by delmoi at 8:46 AM on March 16, 2006

posted by delmoi at 8:46 AM on March 16, 2006

I think he's incorrect about super-busy bever numbers. Since no computer can, in the real world, ever solve the halting problem BB_{n}(X) for any number is undefined and can never be computed for any n other then 1.

posted by delmoi at 8:52 AM on March 16, 2006

posted by delmoi at 8:52 AM on March 16, 2006

posted by delmoi at 10:43 AM CST on March 16 [!]

Oh but wait there's still a factorial at the end of my number! ;)

Goddamn mathematicians... there's no need for numbers that big!

Ok how about the number of terms needed in the harmonic series needed to add up to your crazy q function. Ha!

posted by ozomatli at 8:58 AM on March 16, 2006

Could God name a number so big that even he couldn't name a bigger number?

posted by langedon at 9:02 AM on March 16, 2006

posted by langedon at 9:02 AM on March 16, 2006

The part at the end, to social consequences of big numbers is interesting. It is a big problem in our society that people can't grasp the difference between a million and a billion or a trillion of something, yet there are millions of people, and trillions of dollars. Etc.

Ah well.

posted by delmoi at 9:02 AM on March 16, 2006

Ah well.

posted by delmoi at 9:02 AM on March 16, 2006

Wow, great post. The discussion lost me a long time ago, but it;s neat to see which MeFites are mathematically accomplished.

posted by arcticwoman at 9:03 AM on March 16, 2006

posted by arcticwoman at 9:03 AM on March 16, 2006

ozo: you're right, I think if you solved your function for five, it would be bigger then f(5) which I claculated above as being

5+(4+9^{9})^{(4+99)} = 5+387420493^{387420493}.

Anyway, try it and see if it's bigger then f(5).

posted by delmoi at 9:06 AM on March 16, 2006

5+(4+9

Anyway, try it and see if it's bigger then f(5).

posted by delmoi at 9:06 AM on March 16, 2006

Anyway, try it and see if it's bigger then f(5).

posted by delmoi at 11:06 AM CST on March 16 [!]

To be honest, I don't really know what tricks to do to be able to simplify my function down to a single exponentiated number.

(10!^{100!1000!10000!10000!})! = ?

(10!^{(100!(1000!(10000!(10000!)!)!)!})! = ?

posted by ozomatli at 9:20 AM on March 16, 2006

posted by delmoi at 11:06 AM CST on March 16 [!]

To be honest, I don't really know what tricks to do to be able to simplify my function down to a single exponentiated number.

(10!

(10!

posted by ozomatli at 9:20 AM on March 16, 2006

Well, while we know that 10! is *less* then 10^{10} we also know it's *more* then 10. So we can say that your function is definetly *more* then

(10^{(100(1000(10000(100000)))})

Now, we know that

100^{10000100000} can be restated as

100^{1000010000*10} = 100^{1000000000000000000000000000000 0000000000000000000000000000000000000000 00000000000000000000000001000010000}

Which is obviously more then

5+387420493^{387420493}

So yeah, your function(5) is greater then that for sure, and thus greater then my function f(5) :P

but not more then f(f(5) :) One thing about the factorial is that it's really easy to write

posted by delmoi at 9:40 AM on March 16, 2006

(10

Now, we know that

100

100

Which is obviously more then

5+387420493

So yeah, your function(5) is greater then that for sure, and thus greater then my function f(5) :P

but not more then f(f(5) :) One thing about the factorial is that it's really easy to write

posted by delmoi at 9:40 AM on March 16, 2006

Really excellent post. Thanks, I really enjoyed it.

posted by crunchyk9 at 10:04 AM on March 16, 2006

posted by crunchyk9 at 10:04 AM on March 16, 2006

Thanks everyone, awesome comments. I added some tags.

I agree that factorials were under used for a symbol that can be written down very quickly. 9!!!!!!!!!!!!!!!!!!! must be pretty big but I'm not sure how it fits in with the others.

9!<9^9, but to beat 9!! you need 9!^9! which is beat by 9^9^9^9. So for every extra factorial you have to double your number of exponentials to beat it. So in terms of speed writing, I think factorials beat repeated exponentiation (But not tetration obviously!).

posted by gregv at 10:05 AM on March 16, 2006

I agree that factorials were under used for a symbol that can be written down very quickly. 9!!!!!!!!!!!!!!!!!!! must be pretty big but I'm not sure how it fits in with the others.

9!<9^9, but to beat 9!! you need 9!^9! which is beat by 9^9^9^9. So for every extra factorial you have to double your number of exponentials to beat it. So in terms of speed writing, I think factorials beat repeated exponentiation (But not tetration obviously!).

posted by gregv at 10:05 AM on March 16, 2006

I still think y'all are hobbling yourselves by attempting to calculate numbers rather than meta-numbers. Any system that generates a digit placement set and base value which is based on a number is going to be immensely larger than the number itself.

posted by kyrademon at 10:18 AM on March 16, 2006

posted by kyrademon at 10:18 AM on March 16, 2006

Actually, you could define an operator, say ⊥. such that x⊥ = f(x) and x⊥⊥ = f(f(x)) then just write:

x⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥

as fast as you can. (I mean you would pick an easier symbol to write, but that was one of the simplest html entities)

posted by delmoi at 10:19 AM on March 16, 2006

x⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥⊥

as fast as you can. (I mean you would pick an easier symbol to write, but that was one of the simplest html entities)

posted by delmoi at 10:19 AM on March 16, 2006

Absolutely fabulous post. Sidebar it to show people what posts (especially first posts) should look like.

(Too bad it seems like a lot of the bigger-number comments didn't read the linked article).

posted by klangklangston at 10:52 AM on March 16, 2006

(Too bad it seems like a lot of the bigger-number comments didn't read the linked article).

posted by klangklangston at 10:52 AM on March 16, 2006

Thanks to delmoi, I went back and read the second part of the lead link.. It truly is a brilliant article. However, I think there are some interesting problems with his view of big numbers as they relate to the real world.

But first a question:

Back to the big numbers vs. real world thing:

The lens as computer notion relates directly to the problem I have with the authors practical interpretations, because it computes using continuous values - real numbers, if you prefer.

I think the above colours all of his practical interpretations.

The author keeps looking for a larger and larger scale on which to view things, without ever concerning himself with resolution. The assumption is that the resolution is always a single unit - one (1) - that is the part which is hard to grasp.

This is why I'm an engineer and not a mathematician :)

posted by Chuckles at 10:56 AM on March 16, 2006

But first a question:

Turing proved that this problem, called the Halting Problem, is unsolvable by Turing machines. The proof is a beautiful example of self-reference. It formalizes an old argument about why you can never have perfect introspection: because if you could, then you could determine what you were going to do ten seconds from now, and then do something else. Turing imagined that there was a special machine that could solve the Halting Problem. Then he showed how we could have this machine analyze itself, in such a way that it has to halt if it runs forever, and run forever if it halts.This doesn't sound like a traditional proof by contradiction. Can anyone help me out here?

Back to the big numbers vs. real world thing:

To exceed higher-level Busy Beavers, we’d presumably need some new computational model surpassing even Turing machines. I can’t imagine what such a model would look like.The focal plane of a lens produces the fourier transform of the object plane. Surely that is a non-turing computation? Isn't this analogous to the reason quantum computing is interesting - quantum computing can do calculations that 'normal' computers can't? Well, I really have no idea..

The lens as computer notion relates directly to the problem I have with the authors practical interpretations, because it computes using continuous values - real numbers, if you prefer.

You might also wonder why we can’t use infinity in the contest. The answer is, for the same reason why we can’t use a rocket car in a bike race. Infinity is fascinating and elegant, but it’s not a whole number. Nor can we ‘subtract from infinity’ to yield a whole number. Infinity minus 17 is still infinity, whereas infinity minus infinity is undefined: it could be 0, 38, or even infinity again. Actually I should speak of infinities, plural. For in the late nineteenth century, Georg Cantor proved that there are different levels of infinity:The real world is continuous. To think in discrete quantities - whole numbers - we must sample, and the process of sampling itself invokes infinity.

I think the above colours all of his practical interpretations.

If Dehaene et al.’s hypothesis is correct, then which representation do we use for big numbers? Surely the symbolic one—for nobody’s mental number line could be long enough to contain 99^9, 5 pentated to the 5, or BB(1000). And here, I suspect, is the problem. When thinking about 3, 4, or 7, we’re guided by our spatial intuition, honed over millions of years of perceiving 3 gazelles, 4 mates, 7 members of a hostile clan. But when thinking about BB(1000), we have only language, that evolutionary neophyte, to rely upon.People can adjust scale in visualization quite easily. Look at a logarithmic graph, or consider the powers of ten demonstration. Many practical problems require zooming in and out rapidly - how precise does an angle need to be if we want the other end of a pole in the right place.. Once you can change scale, you can easily visualise big numbers. Perhaps not fully as large as the authors, but certainly much larger than 3, 4 and 7.

The author keeps looking for a larger and larger scale on which to view things, without ever concerning himself with resolution. The assumption is that the resolution is always a single unit - one (1) - that is the part which is hard to grasp.

This is why I'm an engineer and not a mathematician :)

posted by Chuckles at 10:56 AM on March 16, 2006

That's hardly settled.

posted by sonofsamiam at 10:59 AM on March 16, 2006 [1 favorite]

Ok, here's another answer, similar to the BB function but simpler and *more* powerful.

We start by defining an alphabet a =

"+*^-()01A{}xf|,"

then we define a language, which we'll call 'splody' as follows:

the mathimatical operators mean the same thing * means times, + means adition, and ^ means exponent. Same thing with parenthises. the {} mean 'define function' so to write

f(x)=x-1*2 in splody we write {x-1*10}. With the special cavat that any function f() defined in splody returns 0 on an input of 0 (oh, and it uses binary numbers). If you want to change that, you can put in a pipe after the first formula for the output on zero.

So, the statement

f(x) = (x + f(x-1)^{f(x-1)}) my orgional formulation of f() could be described in this language as:

{x+f(x-1)^f(x-1)}

Then f(5) could be described as:

{x+f(x-1)^f(x-1)}(101).

The character 'A' is equal to ten. That's just a constant I've thrown in to make things a little easier.

f(10^{10}) would be:

{x+f(x-1)^f(x-1)}(A^A).

So now I define a new function v(n) and v(n) is the largest number you can define in splody using y characters.

I think v grows faster then BB even. I could throw the ackermann in there as well, but I won't, because the ackermann function can actually be defined in splody, so can the factorial

v(1) = 10

v(2) = 100 (AA = A*A)

v(3) = 1000 (AAA = A*A*A)

Once you get a string long enough to define a recursive function, you're pretty much good to go and come up with all sorts of crazy stuff.

In fact, the BB problem*itself* can be encoded as a splody string of a certan length. That part is left as an excersize to the reader :)

posted by delmoi at 10:59 AM on March 16, 2006

We start by defining an alphabet a =

"+*^-()01A{}xf|,"

then we define a language, which we'll call 'splody' as follows:

the mathimatical operators mean the same thing * means times, + means adition, and ^ means exponent. Same thing with parenthises. the {} mean 'define function' so to write

f(x)=x-1*2 in splody we write {x-1*10}. With the special cavat that any function f() defined in splody returns 0 on an input of 0 (oh, and it uses binary numbers). If you want to change that, you can put in a pipe after the first formula for the output on zero.

So, the statement

f(x) = (x + f(x-1)

{x+f(x-1)^f(x-1)}

Then f(5) could be described as:

{x+f(x-1)^f(x-1)}(101).

The character 'A' is equal to ten. That's just a constant I've thrown in to make things a little easier.

f(10

{x+f(x-1)^f(x-1)}(A^A).

So now I define a new function v(n) and v(n) is the largest number you can define in splody using y characters.

I think v grows faster then BB even. I could throw the ackermann in there as well, but I won't, because the ackermann function can actually be defined in splody, so can the factorial

v(1) = 10

v(2) = 100 (AA = A*A)

v(3) = 1000 (AAA = A*A*A)

Once you get a string long enough to define a recursive function, you're pretty much good to go and come up with all sorts of crazy stuff.

In fact, the BB problem

posted by delmoi at 10:59 AM on March 16, 2006

Nope, quantum computers can't do anything normal computers can't do, but they can do some of the things normal computers do quicker, not that quicker though, the cannot (for example) solve NP problems in P time. In theory they can maybe run a problem in sqrt(O(n) time, though (IIRC).

That's sort of beside the point. We don't have to sample anything went we think of a discrete object. I see 4 empty cans of cherry 7-up plus in front of me. Even though each can is slightly different, and contains a different amount of aluminum, there are still four cans.

Exactly, this problem can be solved by people visualizing

The other thing is money: I can easily visualize what could be done with a thousand dollars, or with a million dollars, and a billion is just one thousand times that, another number I can imagine.

I don't think it's that hard to train people to have an intuitive grasp of orders of magnitude; it's just not done that commonly in a normal education (sadly).

posted by delmoi at 11:07 AM on March 16, 2006

I'll beat that, delmoi.

Define a function big(a,l) that accepts an axiomatic system a and an integer l such that big(a,l) = the largest number representable in system a with l characters.

Since the entire thing is formalizable in ZF a la Goedel-numbering, I submit that this is a valid entry

So, let splody = the set of possible statements derivable in splody.

Let metasplody = splody union big(.)

Let my new entry = big (metasplody, big(splody))

One of the coolest things about math is that this kind of metamathematical stuff is provably non-recursive, which means that no computer can continue this sort of level-upping as far as a human can. It's not a matter of physical impossibility, it's a matter of logical impossibility. There's a section in GEB that talks about this.

posted by sonofsamiam at 11:10 AM on March 16, 2006

Define a function big(a,l) that accepts an axiomatic system a and an integer l such that big(a,l) = the largest number representable in system a with l characters.

Since the entire thing is formalizable in ZF a la Goedel-numbering, I submit that this is a valid entry

So, let splody = the set of possible statements derivable in splody.

Let metasplody = splody union big(.)

Let my new entry = big (metasplody, big(splody))

One of the coolest things about math is that this kind of metamathematical stuff is provably non-recursive, which means that no computer can continue this sort of level-upping as far as a human can. It's not a matter of physical impossibility, it's a matter of logical impossibility. There's a section in GEB that talks about this.

posted by sonofsamiam at 11:10 AM on March 16, 2006

first of all what does big(.) mean? big(splody)?

Anyway, maybe not. I think splody is Turing complete, so big, as a function, big could be expressed in splody.

Both splody and big can run programs which will never halt. big(splody), as expressed in splody will probably not halt.

posted by delmoi at 11:17 AM on March 16, 2006

Anyway, maybe not. I think splody is Turing complete, so big, as a function, big could be expressed in splody.

Both splody and big can run programs which will never halt. big(splody), as expressed in splody will probably not halt.

posted by delmoi at 11:17 AM on March 16, 2006

delmoi: I think that your scheme is a context free grammar; if so, it can be simulated on a finite turing machine. The upshot is that

v(n) would be a lower bound on BB(m), if m is the size of a turing machine that simulates push-down automata.

posted by agent at 11:20 AM on March 16, 2006

v(n) would be a lower bound on BB(m), if m is the size of a turing machine that simulates push-down automata.

posted by agent at 11:20 AM on March 16, 2006

Mmm. But the problem isn't simply to come up with the biggest possible number. It's to come up with the biggest possible number you can write down in 15 seconds. Defining splody would take a significant chunk of your time.

It's also a problem with the Ackermann numbers. It was pointed out in the article that you have to jot in a quick definition, because they're not necessarily universally accepted mathemtical terms.

That's why I've been trying to focus on predefined terms like the big Mersenne prime, and manipulate it using recursion, metanumbers, and basing. But even that takes a while to jot down.

The chained arrows, which seem to be pretty well defined and very quick to jot down, may be the key here. It shouldn't be too difficult to create a Conway chain of even ten or so numbers, set it up as a metanumber, and redefine the base, all within 15 seconds. I think that would handily blow away most people who had to spend most of their time jotting down a definition, because they won't have enough time left to set up enough recursion afterwards.

posted by kyrademon at 11:22 AM on March 16, 2006

It's also a problem with the Ackermann numbers. It was pointed out in the article that you have to jot in a quick definition, because they're not necessarily universally accepted mathemtical terms.

That's why I've been trying to focus on predefined terms like the big Mersenne prime, and manipulate it using recursion, metanumbers, and basing. But even that takes a while to jot down.

The chained arrows, which seem to be pretty well defined and very quick to jot down, may be the key here. It shouldn't be too difficult to create a Conway chain of even ten or so numbers, set it up as a metanumber, and redefine the base, all within 15 seconds. I think that would handily blow away most people who had to spend most of their time jotting down a definition, because they won't have enough time left to set up enough recursion afterwards.

posted by kyrademon at 11:22 AM on March 16, 2006

delmoi:

big(.) means the function big as an object, without evaluating any arguments. This convention arose because it just looks ugly to leave facing parenthesis: big()

I screwed up, though. My entry should be big(metasplody, big(splody,1000))

It doesn't run into halting problems, because we provide an upper limit on the specification.

*So now I define a new function v(n) and v(n) is the largest number you can define in splody using y characters.*

If this function is computable, then v(n)=big(splody,n) is computable.

If big(splody,n) is computable then big(metasplody, big(splody,1000)) is computable.

But it did take me longer than 15 seconds :)

posted by sonofsamiam at 11:25 AM on March 16, 2006

big(.) means the function big as an object, without evaluating any arguments. This convention arose because it just looks ugly to leave facing parenthesis: big()

I screwed up, though. My entry should be big(metasplody, big(splody,1000))

It doesn't run into halting problems, because we provide an upper limit on the specification.

If this function is computable, then v(n)=big(splody,n) is computable.

If big(splody,n) is computable then big(metasplody, big(splody,1000)) is computable.

But it did take me longer than 15 seconds :)

posted by sonofsamiam at 11:25 AM on March 16, 2006

Sublime post. I was efb'ed on my "9!!!!!!!!" idea, so here are some math anecdotes instead:

- any result with more than 9 digits was pronounced "the national debt" in 10th-grade math

- The factorial button on a calculator was to be used if you were excited about a number ("6!") - trig class

- still not sure where in the 10^{x} 's "a brazilian" fits.

... and in the early 1980s, the biggest possible number was 655,360. At least, Bill Gates said there was no use for anything higher. (As it turns out, there's no proof of him saying that.)

posted by kurumi at 11:41 AM on March 16, 2006

- any result with more than 9 digits was pronounced "the national debt" in 10th-grade math

- The factorial button on a calculator was to be used if you were excited about a number ("6!") - trig class

- still not sure where in the 10

... and in the early 1980s, the biggest possible number was 655,360. At least, Bill Gates said there was no use for anything higher. (As it turns out, there's no proof of him saying that.)

posted by kurumi at 11:41 AM on March 16, 2006

I messed up on labelling splody a CFG. I assume that splody's grammar would be a context free, but the language's computational power is equivalent to a subset of Turing machines.

posted by agent at 11:42 AM on March 16, 2006

posted by agent at 11:42 AM on March 16, 2006

Infinity minus (one over infinity) to the "HL," where HL is the "Huey Lewis" constant. That's the power of love.

posted by It's Raining Florence Henderson at 11:44 AM on March 16, 2006

posted by It's Raining Florence Henderson at 11:44 AM on March 16, 2006

Chuckles: *This doesn't sound like a traditional proof by contradiction. Can anyone help me out here?*

I'm a bit rusty, but I hope this will explain it:

1. Assume there exists a program, Al, that can take a program as input, and tell you if it will run forever, or will stop at some point.

2. Based on that assumption, we can write a new program Oops that does this:

- If Al(input) says it will run forever, stop.

- If Al(input) says it will stop, run a loop forever.

In other words, Oops will do the opposite of the function we give it.

3. Run Oops with Oops as the input. One of two things will happen:

a. Al tells us that Oops will stop. Oops (as we created it) will now loop forever. Which means Al was wrong.

b. Al tells us that Oops will run forever. Oops (as we created it) will now stop. Al is wrong again.

We've now found a contradiction. If Al could do what we assumed, we just proved that it can't. Thus our original assumption, that Al exists, must be false.

posted by Sibrax at 11:47 AM on March 16, 2006 [1 favorite]

I'm a bit rusty, but I hope this will explain it:

1. Assume there exists a program, Al, that can take a program as input, and tell you if it will run forever, or will stop at some point.

2. Based on that assumption, we can write a new program Oops that does this:

- If Al(input) says it will run forever, stop.

- If Al(input) says it will stop, run a loop forever.

In other words, Oops will do the opposite of the function we give it.

3. Run Oops with Oops as the input. One of two things will happen:

a. Al tells us that Oops will stop. Oops (as we created it) will now loop forever. Which means Al was wrong.

b. Al tells us that Oops will run forever. Oops (as we created it) will now stop. Al is wrong again.

We've now found a contradiction. If Al could do what we assumed, we just proved that it can't. Thus our original assumption, that Al exists, must be false.

posted by Sibrax at 11:47 AM on March 16, 2006 [1 favorite]

How did I figure Douglas Hofstadter’s name would come up?

Nifty post. Quantum information is teh shit.

...But why would quantum computers have to be sexually excited in order to work?

/btw X + Y where X is your number and Y is whatever value required to make my number larger - given that we’re not allowing language ambiguity, but we are allowing ignorance of number systems (or deeper paradigms) in our opponant in the contest ‘Y’ is derived from any greater but undiscovered system of computing larger numbers without language ambiguity.

posted by Smedleyman at 11:56 AM on March 16, 2006

Nifty post. Quantum information is teh shit.

...But why would quantum computers have to be sexually excited in order to work?

/btw X + Y where X is your number and Y is whatever value required to make my number larger - given that we’re not allowing language ambiguity, but we are allowing ignorance of number systems (or deeper paradigms) in our opponant in the contest ‘Y’ is derived from any greater but undiscovered system of computing larger numbers without language ambiguity.

posted by Smedleyman at 11:56 AM on March 16, 2006

Thanks Sibrax, I can see it now.

It's funny, I just had this massive sense of deja-vu, like I just read that exact example somewhere.. Then I found it (from the debunk link, and obviously not the exact example):

It's funny, I just had this massive sense of deja-vu, like I just read that exact example somewhere.. Then I found it (from the debunk link, and obviously not the exact example):

In this case, the catch is simple. Say you've got two programs, Dif and Doof, running in the Windows taskbar. Dif is performing some enormous calculation, while Doof (being a Doof) is doing nothing. If Dif's calculation returns any answer other than 5, then Dif closes Doof. You come back to your computer and find that Doof is still running. Even though Doof didn't calculate anything, and even though Dif never did anything to Doof, you can immediately conclude -- from Doof alone -- that the answer you wanted was 5. Mindblowing! Unbelievable!posted by Chuckles at 12:19 PM on March 16, 2006

Now let Dif and Doof run, not in different windows, but in different branches of the wavefunction -- that is, in quantum superposition. And instead of Dif using an operating system to close Doof, have Dif's branch of the wavefunction interfere destructively with Doof's branch, thereby preventing Doof's branch from being observed. That's the idea of counterfactual quantum computing.

I finally managed to read through all the comments despite the fact that I barely passed calculus. You bastards broke my brain.

posted by Pontius Pilate at 12:37 PM on March 16, 2006

posted by Pontius Pilate at 12:37 PM on March 16, 2006

Excellent, delmoi! Writing it as a recursive function addresses the challenge of writing all of those Conway chain elements out by hand (and being limited to how many iterations you could write in 15 seconds).

Put the Conway chained, Ackermanned googleplex inside a recursive function like you suggested and voila! You get an inconceivable number of iterations of Conwayed, Ackermanned googleplex, without having to write them all on the page.

This seems to be the largest so far (other than the Busy Beaver numbers, which I confess I still don't understand all that well).

posted by darkstar at 12:43 PM on March 16, 2006

Put the Conway chained, Ackermanned googleplex inside a recursive function like you suggested and voila! You get an inconceivable number of iterations of Conwayed, Ackermanned googleplex, without having to write them all on the page.

This seems to be the largest so far (other than the Busy Beaver numbers, which I confess I still don't understand all that well).

posted by darkstar at 12:43 PM on March 16, 2006

In some medieval kabbalah texts (reference is at home), God is described as being like 144,000 somethings from the foot to the knee, 288,000 somethings long from the knee to the groin, etc. Then the "somethings" are revealed to each be 144,000 otherthings and the otherthings are 144,000 miles.

It is intended as a meditative aid. I'll try to find a Linklater.

posted by sonofsamiam at 12:49 PM on March 16, 2006

It is intended as a meditative aid. I'll try to find a Linklater.

posted by sonofsamiam at 12:49 PM on March 16, 2006

I stopped understanding the comments some time ago, but I love this thread with an unholy love.

posted by languagehat at 1:35 PM on March 16, 2006

posted by languagehat at 1:35 PM on March 16, 2006

yes, this is great stuff, i bookmarked the large numbers essay to read at leisure.

posted by jcruelty at 1:47 PM on March 16, 2006

posted by jcruelty at 1:47 PM on March 16, 2006

I got a big number for ya

/sexually.

AouRight.

*quagmires*

posted by Smedleyman at 2:03 PM on March 16, 2006

/sexually.

AouRight.

*quagmires*

posted by Smedleyman at 2:03 PM on March 16, 2006

Hmm....would knowlege of the biggest number be empirical or inferential?

Ultimately, I mean. Because it is a real number, it exists, it can be obtained, but is known only by inference and probably will always be. And even if we do name it, is there any possibility to truly experiance the number (given the workings of the brain as commented above)?

posted by Smedleyman at 2:10 PM on March 16, 2006

Ultimately, I mean. Because it is a real number, it exists, it can be obtained, but is known only by inference and probably will always be. And even if we do name it, is there any possibility to truly experiance the number (given the workings of the brain as commented above)?

posted by Smedleyman at 2:10 PM on March 16, 2006

Excellent links. I read it all the way through too, the guy can explain well which is no small task for my rapidly putrifying IQ.

posted by Sparx at 2:18 PM on March 16, 2006

posted by Sparx at 2:18 PM on March 16, 2006

I was thinking that, too, Smedleyman.

We can talk about and describe big numbers like googleplex (and the larger ones we've mentioned), but they really have no empirical meaning to us. Even a relatively smaller number like a trillion has to be predominately inferred, even though we interact with the consequences of it as a measurement: a trillion cells, a trillion dollars of national debt, a terabyte of storage space, (etc.).

It's all inference after a point, even if it refers to a discrete number. The inferring is bliss, though!

posted by darkstar at 2:22 PM on March 16, 2006

We can talk about and describe big numbers like googleplex (and the larger ones we've mentioned), but they really have no empirical meaning to us. Even a relatively smaller number like a trillion has to be predominately inferred, even though we interact with the consequences of it as a measurement: a trillion cells, a trillion dollars of national debt, a terabyte of storage space, (etc.).

It's all inference after a point, even if it refers to a discrete number. The inferring is bliss, though!

posted by darkstar at 2:22 PM on March 16, 2006

Infer a dime, infer a googleplex.

posted by It's Raining Florence Henderson at 2:38 PM on March 16, 2006 [1 favorite]

posted by It's Raining Florence Henderson at 2:38 PM on March 16, 2006 [1 favorite]

I could go for a can of Miller High Life right about now.

posted by mcsweetie at 3:29 PM on March 16, 2006

posted by mcsweetie at 3:29 PM on March 16, 2006

alright, here's what I'd write if I actually had 15 seconds

f(x) = f(x+f(x-1)^{f(x-1)})

x~ = f(x).

Number:

10~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

posted by delmoi at 4:20 PM on March 16, 2006

f(x) = f(x+f(x-1)

x~ = f(x).

Number:

10~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

posted by delmoi at 4:20 PM on March 16, 2006

We've kinda touched the face of God in this thread, a little bit, you know?

posted by darkstar at 4:27 PM on March 16, 2006

posted by darkstar at 4:27 PM on March 16, 2006

And He kinda needs a shave.

/"We really shook the pillars of heaven, didn't we, Wang?"

posted by It's Raining Florence Henderson at 5:04 PM on March 16, 2006

/"We really shook the pillars of heaven, didn't we, Wang?"

posted by It's Raining Florence Henderson at 5:04 PM on March 16, 2006

Nice thread, long time lurker first time 'mefite'. I must say, the concept of the "busy beaver" number is quite intriguing. At a certain level, it can define language and mathematics. At another (probably higher) one, it can define itself. Somehow I don't think we can create a bigger number than it without referring to it, or one of the Alephs...

posted by Tzarius at 2:37 AM on March 17, 2006

posted by Tzarius at 2:37 AM on March 17, 2006

The Penguin Book of Curious and Interesting Numbers is essentially a small encyclopedia of numbers that are, well, curious and interesting. It includes some really big ones. Highly recommended.

posted by neuron at 8:26 PM on March 17, 2006

posted by neuron at 8:26 PM on March 17, 2006

Man, turns out Scott Aaronson is a complete wanker. Too bad. (btw "delmoi" = "Chad Okere", if you hadn't realized that)

posted by delmoi at 7:55 PM on March 18, 2006

posted by delmoi at 7:55 PM on March 18, 2006

Don't you have to show the existence of an oracle before you can rely on it to prove a further conjecture?

I mean, in order to invoke BB_2's you have to show that a solution to the turing machine halting problem 'exists', but that is unproven - presumably for good reason.

Is there such thing as a stupor turing machine? A set of rules that has a halting problem, for which a standard turing machine has an oracle?

posted by Chuckles at 10:28 PM on March 18, 2006

I mean, in order to invoke BB_2's you have to show that a solution to the turing machine halting problem 'exists', but that is unproven - presumably for good reason.

Is there such thing as a stupor turing machine? A set of rules that has a halting problem, for which a standard turing machine has an oracle?

posted by Chuckles at 10:28 PM on March 18, 2006

I can't tell if he's a wanker or not, but he's certainly a jerk. (Or does *wanker = jerk*? My command of Brit slang is pretty shaky.) Anyway, I don't understand any of the stuff you guys are arguing about (to me, oracle = that thing at Delphi), but reading his contemptuous rants certainly doesn't make me interested in understanding his point of view. I'm sure he'd sneer that that makes me unworthy of his attention. And they wonder why people hate math class...

posted by languagehat at 5:51 AM on March 19, 2006

posted by languagehat at 5:51 AM on March 19, 2006

No, not at all. That's why we postulate oracles instead of deriving them. Turing himself was the first to study Turing machines plus oracles.

They can be practically implementable (the oracle function that returns sonofsamiam's personal opinion on whether or not any particular program halts, implemented as a user prompt) or not (the function that returns the nth bit of Chaitin's Omega).

Now, these mayn't exist, but neither do Turing machines in the physical universe. In fact, once you add interaction of any kind to a system, you're already in supra-Turing computable territory.

All these machines are ideal, not physically real. If you wanna get pedantic, we don't even have finite-state machines, only stochastic finite-state machines.

posted by sonofsamiam at 1:40 PM on March 19, 2006

« Older Robotic Sea Serpent.... | The first clip... Newer »

This thread has been archived and is closed to new comments

posted by three blind mice at 12:37 AM on March 16, 2006