Skip
# I wonder if it's in NP?

Post

# I wonder if it's in NP?

February 3, 2007 7:43 AM Subscribe

Blood, guts, and glory in no holds barred MIT number fight.

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

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:

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

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]

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_{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}

*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]

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

posted by demiurge at 8:23 AM on February 3, 2007

**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]

posted by jimmythefish at 8:40 AM on February 3, 2007 [1 favorite]

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

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

posted by demiurge at 9:01 AM on February 3, 2007

Obviously, neither Dr Evil nor The Mexican Multiplier had heard of googolplex.

posted by carmina at 2:10 PM on February 3, 2007

**shudders**posted by carmina at 2:10 PM on February 3, 2007

googol order multifactorial of a googolplex.

posted by carmina at 2:19 PM on February 3, 2007

**faints**posted by carmina at 2:19 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

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

posted by escabeche at 6:30 AM on February 4, 2007

« Older Murder | "This is a baby. This is a... Newer »

This thread has been archived and is closed to new comments

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