Re:Who Can Name the Bigger Number? (1999)
by eindiran on Tuesday January 21, 2020 @08:32PM
(#22113702)
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.
Re:Who Can Name the Bigger Number? (1999)
by IHLayman on Tuesday January 21, 2020 @08:23PM
(#22113644)
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.
Re:Who Can Name the Bigger Number? (1999)
by ThreeFx on Wednesday January 22, 2020 @06:26AM
(#22116558)
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.
Re:Who Can Name the Bigger Number? (1999)
by mnemonicsloth on Tuesday January 21, 2020 @08:37PM
(#22113727)
> 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.
Re:Who Can Name the Bigger Number? (1999)
by im3w1l on Wednesday January 22, 2020 @03:54AM
(#22115811)
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.
Re:Who Can Name the Bigger Number? (1999)
by IHLayman on Tuesday January 21, 2020 @08:22PM
(#22113634)
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.
Re:Who Can Name the Bigger Number? (1999)
by maze-le on Wednesday January 22, 2020 @06:22AM
(#22116541)
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...
Re:Who Can Name the Bigger Number? (1999)
by xamuel on Wednesday January 22, 2020 @09:45AM
(#22117919)
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.
Re:Who Can Name the Bigger Number? (1999)
by xamuel on Thursday January 23, 2020 @09:18AM
(#22127689)
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.
Re:Who Can Name the Bigger Number? (1999)
by amelius on Wednesday January 22, 2020 @08:13AM
(#22117223)
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?
Re:Who Can Name the Bigger Number? (1999)
by eindiran on Tuesday January 21, 2020 @08:13PM
(#22113591)
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.
Re:Who Can Name the Bigger Number? (1999)
by ccvannorman on Wednesday January 22, 2020 @03:10AM
(#22115608)
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.
Re:Who Can Name the Bigger Number? (1999)
by jes5199 on Tuesday January 21, 2020 @11:18PM
(#22114585)
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
Re:Who Can Name the Bigger Number? (1999)
by EliRivers on Wednesday January 22, 2020 @01:45PM
(#22120606)
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.
Re:Who Can Name the Bigger Number? (1999)
by cryptica on Wednesday January 22, 2020 @10:10AM
(#22118133)
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.
Re:Who Can Name the Bigger Number? (1999)
by yters on Wednesday January 22, 2020 @08:31AM
(#22117345)
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.
Re:Who Can Name the Bigger Number? (1999)
by dandanua on Wednesday January 22, 2020 @09:11AM
(#22117640)
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.
Re:Who Can Name the Bigger Number? (1999)
by baddox on Wednesday January 22, 2020 @01:40PM
(#22120561)
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.
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
https://www.youtube.com/watch?v=RkP_OGDCLY0
"That essay might still get more views than any of the research I’ve done in all the years since."
The theorem is interesting for other reasons though: It allows us to define graph families by forbidding certain substructures.
Hey, it happened to Cicero, too!
Surprising, in retrospect, how fast that changed.
positions, to be precise (over 2 * 10^170).
https://tromp.github.io/go/legal.html
0: https://en.wikipedia.org/wiki/Graham's_number 1: https://en.wikipedia.org/wiki/Kruskal's_tree_theorem
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?
See my slides on the subject here: https://semitrivial.github.io/MeasuringIntelligence2019.pdf
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!
Worth a read just to see the winner's solution, which I thought was rather ingenious.
https://waitbutwhy.com/2014/11/1000000-grahams-number.html
> 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.
https://en.wikipedia.org/wiki/Large_numbers
https://googology.wikia.org/wiki/List_of_googolisms/Uncomput...
https://science.sciencemag.org/content/sci/194/4271/1235.ful...
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.
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.
let g(x) mean "x to the googolplex power"; my number is g(g(...g(googolplex) with a googolplex number of g's.
etc