News for hackers. Stuff that matters.
Re:Who Can Name the Bigger Number? by robinhouston on Thursday July 22, 2010 @06:39PM (#1539764)
“Who can name the bigger number? Whoever has the deeper paradigm.”

In 2001, David Moews ran a BIGNUM BAKEOFF competition on the comp.lang.c newsgroup, where each entry had to be a C program (512 non-whitespace characters or fewer) returning a number from main(). The winner is the program that returns the largest number, assuming an arbitrarily-large int type.

http://groups.google.com/group/comp.lang.c/browse_thread/thr...

After reading Scott Aaronson's wonderful essay, you won't be surprised to hear that the contest was won by a theoretical computer scientist, Ralph Loader. (Second place was taken by Heiner Marxen, who is mentioned in Scott's article in connection with the Busy Beaver problem.)

Ralph Loader's remarkable program is at http://homepages.ihug.co.nz/~suckfish/busy/reduced.c, and the documented and unmangled version in http://homepages.ihug.co.nz/~suckfish/busy/busy.tar.gz

David Moews' discussion of the entries is at http://djm.cc/bignum-results.txt

Re:Who Can Name the Bigger Number? by kd0amg on Friday July 23, 2010 @12:35PM (#1541652)
(I haven't read over the entries yet)

A coworker suggests a Whitespace[1] interpreter which applies the recursion theorem and then interprets a Whitespace program embedded in the source code, characters which do not count towards the size limit. We're not sure yet whether that can be done in 512 characters.

[1] http://en.wikipedia.org/wiki/Whitespace_(programming_languag...

Edit: "Wait... can you make a Quine without using a string literal?"

Re:Who Can Name the Bigger Number? by shasta on Friday July 23, 2010 @09:00PM (#1542817)
Why whitespace? Just pick the simplest to interpret Turing complete language with a two symbol alphabet.

Also: you're disqualified :)

Re:Who Can Name the Bigger Number? by tel on Thursday July 22, 2010 @10:35PM (#1540185)
I find it hilarious that three people thought to return the highest possible number by underflowing unsigned ints (that are being treated as arbitrarily large ints). It's a funny hack even if it doesn't teach you anything like Loader's does.
Re:Who Can Name the Bigger Number? by mseebach on Friday July 23, 2010 @06:44AM (#1540848)
I don't see how that is relevant when the problem assumes an arbitrarily large int-type. It's trivial to return the largest possible value (INT_MAX) for any fixed-size int-type, but a such does not exist.

Basically, many posters are missing the point that it's a mathematics challenge, not a C-challenge, which is excusable since it's posted in a C-group.

Re:Who Can Name the Bigger Number? by tel on Sunday July 25, 2010 @01:50PM (#1545954)
Exactly, which I find hilarious.
Re:Who Can Name the Bigger Number? by amalcon on Thursday July 22, 2010 @11:19PM (#1540235)
My first thought was along those lines: (int)((unsigned int)-1 >> 1)==INT_MAX
Re:Who Can Name the Bigger Number? by Eliezer on Thursday July 22, 2010 @08:52PM (#1540042)
What I'd want to say here is "the largest number nameable using 1000 symbols in second-order logic" (not original, I think someone else won a contest that way). But the fact that someone can ask "Which formulation of second-order logic?" probably defeats this unless you can also, in those fifteen seconds, cite a standard formulation of second-order logic and a standard axiomatization of number in that formulation, otherwise it's an ambiguous specification. HOL is a standard and formal formulation of higher-order logic that I can think of in fifteen seconds, but I wouldn't be able to think of a standard formulation of Peano Arithmetic that was already in HOL.

Actually, now that I think of it, "the largest number nameable using 1000 symbols in HOL plus a successor symbol" might work, since you can define addition, multiplication, etc. in higher-order logic using only a successor symbol.

Interesting fact: This is a fundamental jump up from first-order logic, which is a fundamental jump up from Busy Beaver, and then once you're there, it's operating at the highest level of abstraction that I know about or have ever heard of. There are things you can do to make that number bigger - picking a different ordinal for the order of logic, recursing over how you get the number of symbols - but they all amount to saying "plus one", and not jumping to a qualitatively different level of abstraction. Once you abstract over second-order logic you are, so far as I know, done.

Re:Who Can Name the Bigger Number? by shasta on Friday July 23, 2010 @09:38AM (#1541106)
I don't know what qualifies as a "qualitatively different levels of abstraction", but for all practical purposes, you're never done. Given a formal system for building numbers, you have a sequence B(n) of largest numbers created with n symbols in that formal system. You can always step outside that formal system and make a construction that leaves someone stuck in the formal system in the dust. For example, take B(B(n)). You could then formalize this process of stepping outside of formal systems, only to find yourself in a new formal system. The only limits on how fast you can "go meta" are limits of your mind.
Re:Who Can Name the Bigger Number? by Eliezer on Friday July 23, 2010 @05:51PM (#1542517)
You could always add one to the number, too. Turning B(n) into B(B(n)) is pretty much the same thing, it just takes B(n) and makes it the base function of ordinal recursions you already know how to construct. It doesn't jump outside the system by very much.

Going meta is really hard work. When people think they're "jumping out of the system" over and over again, they're usually actually playing in a pretty small sandbox. If you take someone who's naive about going meta and ask them to construct a large number, they often don't get anywhere close to Ackermann numbers. They think they're being brilliantly creative and recursing at the speed of light, while actually spending huge amounts of complexity to create much smaller numbers than a mathematician could describe in a few lines of code. Similarly, someone could play around all day with grand hierarchies of ordinal halting oracles, or "jump out of the system" for a billion years on end by applying the functions to themselves, and never get anywhere close to the size of the numbers that you could talk about by making the jump to first-order logic.

And after you make the jump to second-order logic, I don't know of any more other jumps like that of comparable size.

Re:Who Can Name the Bigger Number? by shasta on Friday July 23, 2010 @08:24PM (#1542779)
My point is that if two mathematicians play this game, there is still lots of room to be clever. Even though both will know the idea of looking at numbers nameable in a some formal logic, the more clever of the two will beat the one with fastest handwriting (I'm assuming hours or days - not seconds - to compete).
Re:Who Can Name the Bigger Number? by andrewljohnson on Thursday July 22, 2010 @10:03PM (#1540149)
Read, then comment.
Re:Who Can Name the Bigger Number? by Eliezer on Friday July 23, 2010 @12:10AM (#1540329)
I beg your pardon? What did I miss?

(In case it happens to be you and not I who missed something: the said number is formally specified though uncomputable, just as much as saying BusyBeaver(100); it is not paradoxical like using English to talk about English; and it is also vastly larger than anything you can express compactly by talking about Busy Beavers and oracle machines, which was the top level of the original article.)

Re:Who Can Name the Bigger Number? by codexon on Thursday July 22, 2010 @11:05PM (#1540215)
Very interesting that it was submitted so many times yet only now has it gotten this many votes.
Re:Who Can Name the Bigger Number? by ars on Friday July 23, 2010 @02:41AM (#1540528)
A comment with this link did get some interest though: http://news.ycombinator.com/item?id=378776
Re:Who Can Name the Bigger Number? by unwantedLetters on Friday July 23, 2010 @01:31AM (#1540445)
What surprises me is that hacker news still let these dupes get posted. I was under the impression that a URL once submitted cannot be resubmitted. I've submitted duplicate articles before (unknowingly) and it simply acts as an upvote for an article that has already been submitted. I was thinking perhaps it lets you re-post after a certain predefined amount of time, but between two of the postings, there were only 18 days.
Re:Who Can Name the Bigger Number? by astine on Friday July 23, 2010 @12:26PM (#1541619)
If you add URL parameters, you can bypass the uniqueness requirements. Theoretically, you could submit the same URL an infinite number of times, with different combinations of parameters and never trigger the uniqueness check.
Re:Who Can Name the Bigger Number? by Jun8 on Thursday July 22, 2010 @10:45PM (#1540194)
Surely not every day, but frequently enough, I read a submission and related comments on HN and say to myself, "Ahhh, this is why I continue to come to HN!".

This is definitely one of those.

Re:Who Can Name the Bigger Number? by Timothee on Thursday July 22, 2010 @11:45PM (#1540271)
I have seen it hovering here and there on the front page, and finally opened it. No regrets, it was probably the best submission I've read here.
Re:Who Can Name the Bigger Number? by arethuza on Thursday July 22, 2010 @06:46PM (#1539785)
Re:Who Can Name the Bigger Number? by robinhouston on Thursday July 22, 2010 @07:39PM (#1539904)
Aaronson is talking about Graham‘s number when he writes: “Recondite as it seems, the Ackermann sequence does have some applications. A problem in an area called Ramsey theory asks for the minimum dimension of a hypercube satisfying a certain property. The true dimension is thought to be 6, but the lowest dimension anyone’s been able is prove is so huge that it can only be expressed using the same ‘weird arithmetic’ that underlies the Ackermann sequence. Indeed, the Guinness Book of World Records once listed this dimension as the biggest number ever used in a mathematical proof.”

That‘s about a third of the way through the article. The numbers get a lot bigger after that.

As a footnote, the true dimension is no longer thought to be six — Aaronson’s essay was written in 1999 — and is now known to be at least 11. The Wikipedia article linked above has a reference for this improved lower bound.

Re:Who Can Name the Bigger Number? by arethuza on Friday July 23, 2010 @04:16AM (#1540670)
Yeah, it was probably the Guinness Book of World Records where I picked up the reference to Graham's Number.
Re:Who Can Name the Bigger Number? by baddox on Thursday July 22, 2010 @07:22PM (#1539866)
Let g = Graham's number. Then use Knuth's up arrow notation. Then (and this is perhaps cheating) use a non-computable function like the busy beaver function, which grows faster than ANY computable function. That last step may in fact not be cheating, because it might be possible to prove a lower bound and therefore prove that it's higher than the opponent's number.

Pretty notation here:

http://mathbin.net/50035

Re:Who Can Name the Bigger Number? by jmatt on Thursday July 22, 2010 @09:12PM (#1540078)
This is what I was thinking. Knuth's up arrow on Graham's number. I like the addition of the busy beaver function. A creative improvement for sure.

So far I think you win :)

for the lazy amongst us: http://en.wikipedia.org/wiki/Knuths_up-arrow_notation

Re:Who Can Name the Bigger Number? by Timothee on Thursday July 22, 2010 @11:05PM (#1540217)
If you use Busy Beavers, shouldn't you go all out and do something like that:

BB(BB(BB(BB(BB(…g↑↑↑↑g)))))

or a mix thereof?

edit: I'd actually try BB(BB(BB(BB(BB(…g↑↑↑↑g)))))+1, just in case.

Re:Who Can Name the Bigger Number? by baddox on Thursday July 22, 2010 @11:45PM (#1540272)
There's no end to that. You could define a function BZ(n) that equals BB(BB(BB...(g↑↑↑...g)...)) with n nested BB's and n up arrows. Then you could define a function RBB(n) that equals BZ(BZ(BZ...(g↑↑↑...g)...)) with n nested BZ's and n up arrows.
Re:Who Can Name the Bigger Number? by joe_the_user on Friday July 23, 2010 @02:27AM (#1540514)
If the busy beaver function runs on a computer, it is computable, unless I missed something pretty interesting.
Re:Who Can Name the Bigger Number? by prodigal_erik on Friday July 23, 2010 @02:59AM (#1540549)
A busy beaver is a Turing machine that runs for more steps than any other machine (having the same state machine size) but eventually halts (rather than looping forever). The busy beaver function measures the run times of all busy beavers, the maximum number of steps you can get out of each state machine size. Apparently Radó proved this value eventually grows larger than any computable function.

http://en.wikipedia.org/wiki/Busy_beaver#Non-computability_o...

Re:Who Can Name the Bigger Number? by baddox on Friday July 23, 2010 @07:21PM (#1542679)
The busy beaver function doesn't run on a computer. We only know Σ(n) for n < 5. I think you are missing out on something extremely interesting—that there are limits on what computers can compute, even given unbounded resources and time.
Re:Who Can Name the Bigger Number? by joe_the_user on Friday July 23, 2010 @01:53AM (#1540479)
One of the fundamental points of Kolmagorov's algorithmic information theory is that the function for the largest number algorithmically representable by n bits of information is incomputable.

http://en.wikipedia.org/wiki/Kolmogorov_complexity

Re:Who Can Name the Bigger Number? by diziet on Thursday July 22, 2010 @06:56PM (#1539800)
Something like

(9||||9)!

Using knuth's up arrow notation

http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation

And a factorial for good measure

Re:Who Can Name the Bigger Number? by baddox on Thursday July 22, 2010 @07:24PM (#1539871)
I certainly demolished your number in this post: http://news.ycombinator.com/item?id=1539866

Also, why use | when you can use ↑? ;)

Re:Who Can Name the Bigger Number? by diziet on Friday July 23, 2010 @12:37AM (#1540374)
You're right, you've got me certainly beat by unimaginable orders of magnitude.

How does g↑(sub_g)g compare with BB(g)?

Re:Who Can Name the Bigger Number? by baddox on Friday July 23, 2010 @01:50AM (#1540475)
I have no idea how they compare. The former is incomprehensible and the latter is both incomprehensible and non-computable. My intuition tells me the latter is much larger, because a computer could "easily" calculate the former.
Re:Who Can Name the Bigger Number? by exit on Friday July 23, 2010 @08:07AM (#1540943)
> 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.

but there isn't enough entropy left before cosmic heat death to evaluate 9^(9^9).

Re:Who Can Name the Bigger Number? by spoonboy on Thursday July 22, 2010 @06:01PM (#1539680)
Just for fun, here's my shot: The number of steps required to compute the solution to the travelling salesman problem for each quark of every subset of every permutation of quarks in the universe in space-time.
Re:Who Can Name the Bigger Number? by jerf on Thursday July 22, 2010 @10:34PM (#1540181)
Busy Beaver grows grotesquely faster than that.

Think of it this way. Imagine your scenario, like you just laid out. Now write a program to actually find the number in question, including all input (in this case, some representation of the number you gave, which itself can be encoded as something less than the raw base 2 representation). Now, convert that program to the most efficient possible representation in the Turing Machine encoding in question, which for these sorts of problems are often surprisingly small.

Your problem fits into a small handful of states, a few tens tops, and relatively small "input" too (as encoded by the states in some manner). Therefore BB(a few tens) is at least that large. In fact, that's an unbelievable underestimation of BB(a few tens).

While we humans are thinking we're all clever stacking exponentials on exponentials, the Busy Beavers are off doing things we can't even conceive. Arrow notation and hyper arrow notation and every other such bit of notation are all very, very small functions, and therefore well covered by BB(very small); what concept or concepts does BB(50) exploit? Certainly nothing that would fit into English very comfortably.

I think this helps a human to grasp BB() at least a little; the cleverest, biggest numbers we've ever managed to express without the BB notation are usually in the form of functions quite easy to express with Turing Machines of not that many states. BB grows fast.

Re:Who Can Name the Bigger Number? by vecter on Thursday July 22, 2010 @07:00PM (#1539816)
I'm not sure if quarks have "positions" in the exact sense of the word, so I don't think there's a metric you could apply here to get distances for which to solve TSP.

Suppose there was a metric between quarks. To be clear, are you saying: take all quarks in the universe. Take their powerset P. For each set S in P, create the complete graph K_{|S|} where edge lengths are distances. Let TSP(x, K_{|S|}) be the number of steps required to solve TSP. Sum TSP(K_{|S|}) for all S in P.

Let n be the number of quarks in the universe. The size of the powerset is 2^n. For each S in P, since TSP is solvable in exponential time, we'll upper bound the number of steps by 2^n. In other words, for each powerset, you're cost for solving TSP is at most 2^n. Therefore, the number of steps is at most 2^n * 2^n = 2^(2n), which is far smaller than say Ackermann(6, 6).

Re:Who Can Name the Bigger Number? by spoonboy on Thursday July 22, 2010 @08:31PM (#1540009)
Touche.
Re:Who Can Name the Bigger Number? by shalmanese on Thursday July 22, 2010 @06:19PM (#1539726)
That's just 2^10^83
Re:Who Can Name the Bigger Number? by InclinedPlane on Thursday July 22, 2010 @06:12PM (#1539706)
I think that breaks the rules.

Here's something simple I came up with:

P(1) = 10

P(n+1) = 10^P(n)

Q(n) = P(n)^P(n)

Z(1) = Q(1)

Z(n+1) = Q(Q(n))

And then: Z(10^100)

Re:Who Can Name the Bigger Number? by btilly on Thursday July 22, 2010 @06:55PM (#1539799)
In a somewhat restricted version of this contest some time ago the best entry was my:

B(b, c, 0) = 0

i < b => B(b, c, i + j * b) = i + B(b, c, j) * c

T(b, 0) = b * b

T(b, n+1) = T(T(b, n), B(b, T(b, n), n))

Z = T(2, T(2, T(2, 9)))

It is much, much larger than the number you just threw out. See http://bentilly.blogspot.com/2010/03/large-numbers.html for an explanation.

Re:Who Can Name the Bigger Number? by Rhapso on Thursday July 22, 2010 @08:39PM (#1540018)
"The traveling salesman problem asks for the shortest route connecting a set of cities, given the distances between each pair of cities. The rub is that the number of possible routes grows exponentially with the number of cities."

Is it just me or does the traveling salesman problem have (cities-1)! solutions? thus it is not exponential? and is in fact far more annoying?

Re:Who Can Name the Bigger Number? by baddox on Thursday July 22, 2010 @09:33PM (#1540112)
I think you mean that there are (cities-1)! total routes. Only the shortest one(s) are solutions.
Re:Who Can Name the Bigger Number? by thefool on Thursday July 22, 2010 @09:09PM (#1540072)
Factorial grows faster than exponential.
Re:Who Can Name the Bigger Number? by Rhapso on Thursday July 22, 2010 @09:17PM (#1540086)
This is my point, which I apparently failed at communicating.
Re:Who Can Name the Bigger Number? by thefool on Friday July 23, 2010 @12:49PM (#1541691)
Oops, I just failed at reading.

As the person below answered, there are less naive ways of doing it. Check out: http://www.tsp.gatech.edu/index.html if you are interested.

Re:Who Can Name the Bigger Number? by xtacy on Thursday July 22, 2010 @09:19PM (#1540093)
Using dynamic programming, you can solve the TSP problem in O(n^2 2^n) time with O(n 2^n) space, n = #cities.
Re:Who Can Name the Bigger Number? by Avshalom on Thursday July 22, 2010 @07:50PM (#1539933)
2 things

1) http://qntm.org/planar obviously not the largest number but pretty big.

2) http://www.ephraimkishon.de/en/my_favorite_stories.htm The story Jewish Poker is at least one take on the old joke mentioned in the intro, and a fun read.

Re:Who Can Name the Bigger Number? by rw on Thursday July 22, 2010 @10:54PM (#1540208)
Definitely check out his other essays too!
Re:Who Can Name the Bigger Number? by rookie on Thursday July 22, 2010 @06:20PM (#1539728)
a more interesting challenge would be the biggest number using each of the ten digits only once.

ready, go.

Re:Who Can Name the Bigger Number? by pmb on Thursday July 22, 2010 @06:43PM (#1539775)
9876543210!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Re:Who Can Name the Bigger Number? by die_sekte on Friday July 23, 2010 @12:06AM (#1540321)
10→9→8→7→6→5→4→3→2

Somehow I think that Conway's chained arrow notation is cheating.

Re:Who Can Name the Bigger Number? by kenjackson on Thursday July 22, 2010 @07:05PM (#1539830)
Or what if you restricted the number of symbols to be no more than 20 symbols total.
Re:Who Can Name the Bigger Number? by lakeeffect on Thursday July 22, 2010 @06:58PM (#1539809)
10!^2!^3!^4!^5!^6!^7!^8!^9!
Re:Who Can Name the Bigger Number? by Retric on Friday July 23, 2010 @10:40AM (#1541259)
HA! 2^3!^4!^5!^6!^7!^8!^9!^10! ;-) (2! = 2) and (2^x) > (x ^2) where x > 3.

Then again 2^3^4^5^6^7^8^9^(10!!!!!!!!!) is larger. Also if it's it's simply a question of symbols 9!! is larger than 9^9 so 9 followed by n ! is probably your best bet without going into higher level math like BB(BB(...(9))...)

Re:Who Can Name the Bigger Number? by sesqu on Thursday July 22, 2010 @06:28PM (#1539743)
9876543210

If I'm also allowed an operator, 3↑⁹⁸⁷⁶⁵⁴¹⁰2

Re:Who Can Name the Bigger Number? by rookie on Thursday July 22, 2010 @06:37PM (#1539759)
ha, yes allowed operators, as many as youd like.
Re:Who Can Name the Bigger Number? by sesqu on Thursday July 22, 2010 @07:01PM (#1539818)
Then the best I can come up with on no notice is 2 ↑^(4 ↑^(6 ↑^(8↑^(9↑10)) 7) 5) 3.

That would be trivial to increase substantially by using some other notation for the hyperoperation, but I'm going with the presumably most familiar one. I'm sure there are bigger numbers - specifically, Wikipedia mentions Conway chains, where a→b→c = a ↑^c b, and so 2→3→4→5→6→7→8→9→10 should be quite large indeed.

Re:Who Can Name the Bigger Number? by baddox on Thursday July 22, 2010 @07:27PM (#1539877)
Excellent! I hadn't thought about it, but at a glance I'm pretty sure your ordering and grouping does generate the maximal result. However, the parent comment said as much punctuation as you like, which allows for unbounded expressions with unary operators like the factorial!
Re:Who Can Name the Bigger Number? by dennisgorelik on Friday July 23, 2010 @12:02AM (#1540312)
It looks like many commentators did not bother to read the full article. Neither did I, but I remember not to use "infinity" and "number of atoms in universe".
Re:Who Can Name the Bigger Number? by lakeeffect on Thursday July 22, 2010 @06:53PM (#1539795)
Put the Factorial, exclamation mark after each exponent.
Re:Who Can Name the Bigger Number? by noonespecial on Thursday July 22, 2010 @08:28PM (#1540004)
/Eagles music, singing/

welcome to the hotel David Hilbert...

Re:Who Can Name the Bigger Number? by richieb on Friday July 23, 2010 @09:31AM (#1541090)
Aleph Null?
Re:Who Can Name the Bigger Number? by buzzblog on Thursday July 22, 2010 @06:58PM (#1539810)
My daughter at bedtime says she's giving me infinity times infinity time infinity kisses. That's the biggest number, I don't care what any of you math whizzes have to say about the matter. ... OK, let's call it the best not the biggest.
Re:Who Can Name the Bigger Number? by Angostura on Thursday July 22, 2010 @08:22PM (#1539989)
It's going to be a long night.
Re:Who Can Name the Bigger Number? by tman on Thursday July 22, 2010 @09:40PM (#1540121)
a1 = 10^10

a2 = a1^a1

...

a_n = a_(n-1)^a_(n-1)

My number is a_(a_(10^10))