Skip to content

The largest number game

April 24, 2012

TLDR: “Name the largest number” sounds like a silly game. But you can turn it into a game/exercise that’s fun to play/do once.

———-

Consider the following game, a standard example of a game with no Nash Equilibrium:

  • Each player writes down an integer, without revealing it.
  • All numbers are revealed.  Whoever wrote down the largest number wins!

Obviously, there is no rationalizable strategy, since you can always choose a larger number.

So to make it more playable, we might put a time bound on how long you get to write the number for.  We’d assuming some reasonable ground rules for what it means to write a number, in terms of representation, visibility, medium, etc.  Now, if the time bound is a minute, you probably just want to write down 1s, as quickly as possible (since 1 is the easiest digit to write).  If the time bound is a month, then you might want to somehow quickly borrow a lot of money, and get access to a lot of fast printers.  If the time bound is a normal lifetime, you might want to gain lots of money/power, or find a way to advocate/advance good printing technology…

This game is still not something fun, or particularly practical to play with friends, at any of these timescales. So let’s make an innovative tweak, as suggested by Scott Aaronson:

  • Each player writes down a well-defined mathematical definition of some integer, without revealing it, within a certain time limit.  We allow reference to existing literature, but the definition should otherwise be self-contained (so you can’t say, “The max of everyone else’s number, plus one”)
  • All numbers are revealed.  Whoever defined the largest number wins!

This the door for creativity – anyone who defines the Ackermann function immediately beats anyone who only used things they learned in grade school (factorial, exponential, etc).  Determining who actually won seems quite hard (indeed, it can be shown to be impossible).  But in practice, you should find that it’s easy to tell whose definition was better.

My friends and I once played this game, with a twenty minute limit.  It was quite interesting, though it’s probably only fun once.  You should try playing with your friends!   (If you plan on doing that don’t read ahead!  I will be discussing a solution.  Some theoretical computer science background is required starting now.)

After trying, check out what Scott Aaronson has to say about the problem.  My friends and I were (independently) on the same path Aaronson was on, a very natural one. But he says

To exceed higher-level Busy Beavers, we’d presumably need some new computational model surpassing even Turing machines.

If I’m interpreting correctly, he’s wrong on this account.  We can build things which go past the Kleene hierarchy.  In particular, we can consider an oracle which gives access to BB_n(x) (the busy-beaver function for the nth level of the Kleene hierarchy), for all n (you simply ask the oracle both n and x).  Now the busy beaver function for Turing Machines with this oracle now grows faster than BB_n(x) for any n.  We can think of this as BB_\omega.  (This is essentially where I had gotten to, when I played this game.   I had defined f(n) = BB_n(n), which we can think of as BB_\omega.)

But this clearly isn’t enough.  Minimally, we can get BB_{\omega + 1} by considering oracle access to BB_\omega.  Continuing, we can define BB_{\omega + n} for all n, and then BB_{\omega \cdot 2}. After defining BB_{\omega \cdot n} for all n, we can define BB_{\omega^2}.  You can see that we can essentially build increasingly larger busy-beaver-like functions, which correspond to increasingly large ordinals.  You can certainly get to BB_{\epsilon_0}.  (I believe my friend Paul got at least this far, during the contest.  He won decisively…)

Can we do better?  Also, this amusingly touches upon the related question, “Define the largest ordinal”, which is a pretty interesting problem independently.  How is that game played?  (I haven’t thought about either question much past this).  I agree with Scott, though, that at some point we should probably define a new computational model.

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: