5 ms·
Really big numbers
- lisper 10y agoThe ultimate discussion of big numbers: http://mrob.com/pub/math/largenum.html http://mrob.com/pub/math/largenum.html This too: https://johncarlosbaez.wordpress.com/2016/06/29/large-countable-ordinals-part-1/ https://johncarlosbaez.wordpress.com/2016/06/29/large-counta... Literally to infinity and beyond! :-)
- tromp 10y agoNotably absent from that first link is mention of the elegantly fast-growing Goodstein sequences [1] [1] http://tromp.github.io/pearls.html#goodstein http://tromp.github.io/pearls.html#goodstein
- pavel_lishin 10y agoThat seems a little bit like cheating, in that you can calculate the number in the third turn - e.g., 111! - but as I understand it, to calculate Rayo's number, you basically have to calculate all the numbers that it's not.
- stouset 10y agoIf you restrict yourself to calculable numbers, you're capped at the busy beaver number[1] for the number of rules you're willing to allow in your Turing machine. [1]: http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html
- zeroer 10y ago> 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. History
- deleted 10y ago[deleted]
- tromp 10y agoThe write-up manages to misquote Rayo's huge entry "The smallest number bigger than any finite number named by an expression in the language of set theory with a googol symbols or less" into the relatively minute "The least number that cannot be uniquely described by an expression of first-order set theory that contains no more than a googol (10^100) symbols." by leaving out the crucial "bigger than". The latter is no more than #symbols ^ googol since any N descriptions cannot describe all of the first N+1 numbers... Similarly, the proposed function F(n) is merely exponential in n.
- codeflo 10y agoI think you're correct. For the same reason, the proposed "more quickly" growing G(n) is bounded by (constant + n)^n, which is not much of an improvement.
- ggchappell 10y agoThe post takes comments. Write one?
- tromp 10y agoThanks for pointing that out. Awaiting moderation... (the lack thereof makes HN's commenting much more satisfying:-)
- Patient0 10y agoAlso worth a read (and also in the original articles comments): http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html
- deleted 10y ago[deleted]
- cafebabbe 10y agoNo graham's number ? that one is so big it's scary.
- contravariant 10y agoIt's tiny compared to the numbers described in the article.
- cobbzilla 10y agoIt seems composition would yield ever larger numbers. If Rayo's number is F(10^100), then wouldn't F(F(10^100)) be even larger? OK, now repeat that nesting F(10^100) times (maybe use Knuth's up-arrow notation?) and now you have something even bigger. Now call that whole thing G, and start over from the top. There is no end to how many times you can do this.
- jamesjyu 10y agoThat violates rule #3: "Each new answer had to involve some new notion – it couldn’t be reachable in principle using methods that appeared in previous answers"
- cobbzilla 10y agothanks, missed that part.
- psyc 10y agoIn Googology, these kinds of operations are viewed almost the same as multiplying by a large constant. The result of everything you just did would be considered still in the neighborhood of Rayo's number, even if you did it rn^^^rn times. These people have a whole other notion of what "order of magnitude" means.
- cobbzilla 10y agoI think I get it, the trick is to find a wholly "new dimension" of hugeness. My solution just continues going bigger in a known direction/dimension.
- gamina 10y agoAlso worth a read (it makes you try to grasp how enormous is Graham's number): http://waitbutwhy.com/2014/11/1000000-grahams-number.html http://waitbutwhy.com/2014/11/1000000-grahams-number.html
- brownbat 10y agoThe use of constants without any actual representation is a bit sneaky. You might apply a ceiling assuming constants are limited to, say, 16x16 pixels, with each pixel marked or unmarked. That gives you 2^256 constants to play with (minus those that are already taken), probably many more than the human mind can effectively remember or distinguish without confusion. I could be bargained into more pixels per symbol, but let's consider this case to start... H(2^256, 10^100) would still be quite large. Considerably less so than G(10^100), but I think it might be more fair (for some arbitrary definition of fair). Of course, pixels per character can vary wildly, based on display size, and even on simple displays often contain more than 256 pixels. A more reasonable assumption for very simple displays might be 32x48. At that large, you're over 10^100, because your options with that much of a canvas have already shot over 400 digits. You can get many more pixels if you assume your constants are a word, but I think Rayo's constraints would start counting subscripts and word-like constants as multiple "symbols". Then again, we usually don't just flip a single pixel to switch symbols either, so I'm being too generous there. I'm not sure anyone's done a study on how many potential single-width characters might be reasonably distinguishable... Studies on human perception seem like a much needed prerequisite for further classification of large numbers!