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.
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.
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.
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...
> 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.
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.
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.
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.
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.
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?
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.
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.
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.
46 comments
[ 0.24 ms ] story [ 95.9 ms ] thread"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!
0: https://en.wikipedia.org/wiki/Graham's_number 1: https://en.wikipedia.org/wiki/Kruskal's_tree_theorem
> 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.
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
Surprising, in retrospect, how fast that changed.
positions, to be precise (over 2 * 10^170).
https://tromp.github.io/go/legal.html
https://en.wikipedia.org/wiki/Large_numbers
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
https://googology.wikia.org/wiki/List_of_googolisms/Uncomput...
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?
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
https://science.sciencemag.org/content/sci/194/4271/1235.ful...
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!
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.