Who Can Name the Bigger Number? (1999) | Hacker News Reader

Who Can Name the Bigger Number? (1999)

scottaaronson.com

100 pointslelf43 comments

Open articleView on HN

A bit from 2018: https://news.ycombinator.com/item?id=18508471

A bit from 2016: https://news.ycombinator.com/item?id=11596059

Quite a lot from 2015: https://news.ycombinator.com/item?id=9058986

2013, despite subtle mistitling: https://news.ycombinator.com/item?id=5085463

2010: https://news.ycombinator.com/item?id=2024576

https://news.ycombinator.com/item?id=1539538

A tiny bit from 2009: https://news.ycombinator.com/item?id=951095

Glad this one pops up every so often.

Not a discussion of Scott Aaronson's blog, but a relevant bit from Mr. Show, "24 Is The Highest Number."

https://www.youtube.com/watch?v=RkP_OGDCLY0

I love Mr. Show!

He wrote this as a teenager. Then a new version of it in 2017: https://www.scottaaronson.com/blog/?p=3445.

"That essay might still get more views than any of the research I’ve done in all the years since."

Thanks for pointing this out. He mentions in this one that he didn’t have time to get into Graham’s number, but I still think TREE(3) is worth mentioning.

Fun fact: The Kruskal Tree Theorem has been extended to undirected graphs (they form a quasi-wellordered set wrt the graph minor relationship), giving rise to an even faster growing sequence called the "Friedman's SSCG function".

The theorem is interesting for other reasons though: It allows us to define graph families by forbidding certain substructures.

This latter version has quite a bit of extra content, particularly at the end where he is discussing how far it is possible to push the game within different axiom systems. The discussion of his proof on why BB(8000) can't be determined within ZF set theory is also very interesting.

>That essay might still get more views than any of the research I’ve done in all the years since.

Hey, it happened to Cicero, too!

> And in Go, which has a 19-by-19 board and over 10^150 possible positions, even an amateur human can still rout the world’s top-ranked computer programs.

Surprising, in retrospect, how fast that changed.

It was surprising at the time, too.

When I heard of the breakthrough in CNN's on imagenet the first thing I thought of was "wow I wonder if you can use them on Go". Of course I never executed on this idea. I'm mentioning to show that it was not that non-obvious.

It is interesting that it was solved in large part by not relying fully on brute force search.

208168199381979984699478633344862770286522453884530548425 639456820927419612738015378525648451698519643907259916015 628128546089888314427129715319317557736620397247064840935

positions, to be precise (over 2 * 10^170).

https://tromp.github.io/go/legal.html

Maybe I missed it, but it was interesting that tetration was mentioned without talking about Graham’s number g_64[0] or Kruskal’s tree theorem and TREE(3)[1], both have been quite popular huge numbers for quite a while now.

0: https://en.wikipedia.org/wiki/Graham's_number 1: https://en.wikipedia.org/wiki/Kruskal's_tree_theorem

I think the most fascinating bit about Grahams Number is, that is is used as an upper bound in a proof about colored subgraphs in a completely connected graph of dimension [n]. But this is only an upper bound... the actual number of dimensions [n] that satisfies the proof is unknown, but it could be as low as 13 for all we know...

The joke at the start is fun, I'd only heard a variant in Black Country dialect.

Aynuk: What do yow reckon the biggest number is?

Ayli: Ten thousand?

Aynuk: Worrabout ten thousand and one?

Ayli: Ar, I were close though, wor I?

OP is about natural numbers, but if the challenge is generalized to computable ordinal numbers, then it actually becomes a very interesting measurement in the area of AGI. There's no bound on how big of a natural number any particular AGI could name (because if an AGI can name N, then it can name N+1, and by repeating that process, all the naturals are covered). But the set of codes of computable ordinals is a non-computable set, so no AGI could ever name them all, every AGI necessarily would have an upper limit on how large of a computable ordinal it could ever name.

See my slides on the subject here: https://semitrivial.github.io/MeasuringIntelligence2019.pdf

How is this relevant to AGI?

How would you measure the intelligence of an AGI? Say you've got HAL in one corner of the room and The Terminator in the other, and you can ask them questions and ask them to perform computations, and they'll obey you. How can you make sense of which one is smarter?

A naive attempt would be to ask them to name the biggest (natural) number, but that's no good: HAL says 1000, Terminator says 1001, but of course HAL also knows 1001 is a number so Terminator only wins by dumb luck.

We can salvage the idea though by switching natural number for computable ordinal number, and instead of having them name a single number, have them enumerate computable ordinal numbers indefinitely. The set of codes of computable ordinals is Turing non-computable, so neither machine will succeed in enumerating all of them, and by comparing the size of the ordinals enumerated by the two machines, you get an elegant, parsimonious, not-too-contrived notion of which machine is (mathematically) smarter.

Read the slides I linked!

MIT ran this challenge as the 'Big Number Duel': http://web.mit.edu/arayo/www/bignums.html

Worth a read just to see the winner's solution, which I thought was rather ingenious.

Here's another treatment on the topic, and in particular, Graham's number:

https://waitbutwhy.com/2014/11/1000000-grahams-number.html

Regarding tetration, I wonder: is it ever used in physics/engineering contexts? If not, then why not? Is our universe too simple for more than 3 levels of arithmetic operations?

https://en.m.wikipedia.org/wiki/Graham%27s_number number may be larger?

From the link you provided:

> As there is a recursive formula to define it, it is much smaller than typical busy beaver numbers.

While I can't argue the specific details, I'm not surprised. BB numbers are not computable. Grahams number is.

Further ideas/concepts:

https://en.wikipedia.org/wiki/Large_numbers

Rather than the BB sub n definition proposed in the article, I propose a new notation BB^n( x ), which is to the Busy Beaver sequence what Knuth up-arrow notation is to the hyperoperation sequence. So you don't need to rely on the magic of a "super duper machine" to define the number, just recursive use of the Busy Beaver function. It's kind of tenuously on the boundary of the rules, since it uses a made-up notation.

There is a community of googologists who study, record and define the largest numbers ever described. If you want to bend your mind a bit around gargantuan numbers I suggest taking a casual walk down their list.

https://googology.wikia.org/wiki/List_of_googolisms/Uncomput...

Knuth wrote an interesting article on the topic, in 1976, because computers had become so powerful.

https://science.sciencemag.org/content/sci/194/4271/1235.ful...

he mentions population growth falling due to birth control as an unlikely prediction, but it seems to be where we’re actually headed! There’s a book with a lot of research on this called “ Empty Planet: The Shock of Global Population Decline” - they say we’ll hit peak human population in 2050 +/- 10years

Read that last month; actually very readable, I found, and the way the book tackles different parts of the world and suggest them to be essentially be on different parts of the same glidepath is not unconvincing.

This game is more about business/negotiation than math.

I'd only play this game if I get to reveal my number first and the opponent agrees to read aloud both numbers in decimal form one digit at a time. Then I'd write down Graham's number and leave the room.

Sorry, but this reminds me of Mr. Show's sketch "the highest number "https://m.youtube.com/watch?v=RkP_OGDCLY0

That's numberwang?

In fact, BB(k) is roughly equivalent to asking "what's the biggest non-infinity namable number in k characters".

That doesn’t sound right, because “BB(k) plus 1” is larger than BB(k) and has fewer than k characters for sufficiently large k.

That's why I say 'roughly'. Natural language is very vague and easy to be used to create illogical self-referential statements.

What you say is a Berry paradox. To be consistent we fix a programming language before any such definitions. So you have to count all characters in the BB(k) subprogram. Hence the total program for “BB(k) plus 1” definitely will have more than k characters.

I don't think my example (for example, "BB(11111) + 1") demonstrates the Berry paradox. The original comment "the biggest non-infinity namable number in k characters" is the Berry paradox, which is what I was pointing out.

But then you can have an even more powerful BB that has access to a halting oracle. Then you can have the oracle hierarchy. And then maybe there is another meta direction on top of that.

It seems there is no limit to metaness, and that unlimited nature cannot be captured by notation, otherwise one can go meta on whatever notation is used.

It is like the corollary to "there is no highest number," there is also no fastest growing function. Whatever function one names, it is always possible to use that function to define an even faster growing function.

All of this work on numbers and yet the incorrect use of the word decimated.

here's what I came up with in a few seconds:

let g(x) mean "x to the googolplex power"; my number is g(g(...g(googolplex) with a googolplex number of g's.

h(x): g(x) ^ g(x)

etc

Reply on news.ycombinator.com