I wonder if it's in NP?

February 3, 2007 7:43 AM

Blood, guts, and glory in no holds barred MIT number fight.
posted by Alex404 (14 comments total)

This was the killing blow:

The smallest number bigger than any number that can be named by an expression in the language of first order set-theory with less than a googol (10100) symbols.
posted by Alex404 at 7:44 AM on February 3, 2007

Bleh. This one is much better.
posted by Rhomboid at 7:54 AM on February 3, 2007 [2 favorites has favorites]

i hope that when i graduate from my philosophy degree i get those guys' superpowers
posted by cardamine at 7:54 AM on February 3, 2007

Scott Aaronson is a tool, and his article about large numbers is inaccurate. Spesifically he writes:

<sub>You might wonder why we can’t transcend the whole parade of paradigms, and name numbers by a system that encompasses and surpasses them all. Suppose you wrote the following in the biggest number contest:

The biggest whole number nameable with 1,000 characters of English text

Surely this number exists. Using 1,000 characters, we can name only finitely many numbers, and among these numbers there has to be a biggest. And yet we’ve made no reference to how the number’s named. The English text could invoke Ackermann numbers, or Busy Beavers, or higher-level Busy Beavers, or even some yet more sweeping concept that nobody’s thought of yet. So unless our opponent uses the same ploy, we’ve got him licked. What a brilliant idea! Why didn’t we think of this earlier?

Unfortunately it doesn’t work. We might as well have written

One plus the biggest whole number nameable with 1,000 characters of English text

This number takes at least 1,001 characters to name. Yet we’ve just named it with only 80 characters! Like a snake that swallows itself whole, our colossal number dissolves in a tumult of contradiction. What gives? ... but from the ambiguity inherent in the English language. There’s no surefire way to convert an English phrase into the number it names</sub>

Aaronson dismisses the entire idea 'the largest number produceable by a formula of length X' by dismissing 'the largest number expressible in English' In fact, his example of why English wouldn't work is flawed, the "the largest number plus one" argument is a recursive function that never halts It's expressed in English, but it could be expressed in unambiguous code. The problem is the program would never halt.

Aaronson basically says "This can't be the largest number, so it must be the BB number" He fails to imagine anything in between.

Ultimately what the MIT people used was a similar construction, rather then English they used "the language of first order set-theory". You could also use a "formalized" version of the English language.

The key to answering this question is to say "the largest number generated by some language by a string of length X" There is a lot of symmetry between that statement and the busy beaver number (they both involve the largest numbers generated by a program of a certain length). They might even be the same.

However, you can refine that into a number you can actually discover (unlike the BB numbers) by saying "the largest number generated by a program of length N which can be proven to halt by some algorithm." The Halting problem says you can't prove any arbitrary program will halt, but you can prove that some programs will halt.

It would be interesting to see the different "largest" numbers that can be calculated by algorithms of various complexity classes, like what's the largest number that you can provably calculate (i.e. decidable), what's the largest number you can calculate in NP, what's the largest number you can calculate in P time, etc.
posted by delmoi at 8:10 AM on February 3, 2007 [1 favorite has favorites]

How about "The smallest number bigger than any number that can be named by an expression in the language of first order set-theory with less than a googol plus one symbols"?
posted by demiurge at 8:23 AM on February 3, 2007

How about: The largest finite number.
posted by jimmythefish at 8:40 AM on February 3, 2007 [1 favorite has favorites]

Include: psuedocode.lib

Let opponentNumber = n
when opponentNumber > 0, -0 next print n+1
posted by loquacious at 8:43 AM on February 3, 2007

I don't think that number exists, Jimmy. Otherwise there would be no contest, really.
posted by demiurge at 9:01 AM on February 3, 2007

Numberwang!
posted by Kattullus at 10:25 AM on February 3, 2007 [1 favorite has favorites]

Obviously, neither Dr Evil nor The Mexican Multiplier had heard of googolplex. *shudders*
posted by carmina at 2:10 PM on February 3, 2007

googol order multifactorial of a googolplex. *faints*
posted by carmina at 2:19 PM on February 3, 2007

A(g₆₄,g₆₄)
posted by jewzilla at 3:49 PM on February 3, 2007

delmoi: Um. No.

People who live in glass houses shouldn't throw tools.
posted by erniepan at 8:09 PM on February 3, 2007

Elga is a friend of mine and despite his loss here I certainly wouldn't want to run into him in a dark alley without a truly enormous cardinal on hand. More enjoyable Elga: "I can't believe I'm stupid" and "Defeating Dr. Evil with self-locating belief."
posted by escabeche at 6:30 AM on February 4, 2007