Hacker News Reader

Comment by Scarblac | Hacker News Reader

Graham's Number used to be the biggest number I could name, but now I understand that TREE(3) ( https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem ) is bigger still by a truly incredible amount (and TREE(1) = 1, and TREE(2) = 3).

Unfortunately I don't understand that Wiki page.

The page links to https://en.wikipedia.org/wiki/Friedman%27s_SSCG_function , which is supposedly even bigger but I can't follow the text of the first page so won't attempt to read that.

View on HN

I will take this opportunity to promote the YouTube channels of Brady Haran[0], Numberphile specifically. It has all sorts of interesting videos, including Graham's number [1] (one of the videos featuring Ron Graham) and TREE(3) [2].

His other channels are worth checking out too, Sixty Symbols and Deep Sky Videos being my favorites. To be clear, I have no affiliation with this, just a fan.

[0] http://bradyharan.com/

[1] https://www.youtube.com/watch?v=HX8bihEe3nA&list=PLt5AfwLFPx...

[2] https://www.youtube.com/watch?v=3P6DWAwwViU&t=54s

Numberphile is one of those series that makes me like math again. That strange, crazy, extreme logic is just great. Then I try to work with it, and I am made glad that I didn't pursue that career.

I especially like the intro to Graham's number and the rough proof that it is unthinkably large, that your head would literally implode into a black hole an uncountable amount of times over.

Math is so boggling. Numbers that are literally super-natural exist and are 'useful' at the same time, yet are impossible to mortals all the same. It's this weird end-around we manage with math/logic. That 'floor falling out from underneath you' feeling, a happy giddiness and smallness.

Sorry, Graham's Number does something fierce to my head, it seems.

TREE(3) is indistinguishable from zero compared to Loader's number[1], which basically takes every bit pattern up to some n and expresses this as a program in the Calculus of Constructions. This system is a bit weaker than being Turing complete, but the programs do always terminate (this makes the number computable compared with, say, the Busy Beaver number which does a similar thing with Turing complete programs).

It also has the geek cred of being represented by an obfuscated C program (the unobfuscated verson is also available[2]).

[1] http://googology.wikia.com/wiki/Loader%27s_number

[2] https://github.com/rcls/busy

I can trivially define a function that's vastly larger than that. What's interesting is when these numbers are useful for something.

k(1) = TREE(1), K(2) = TREE(TREE(2)), K(3) = TREE(TREE( <(repeats (TREE(3) time (TREE(3)))

Sequence 1, 2, non comprehensibly large number.

Now define m(x) in terms of k and m(x-1).

> k(1) = TREE(1), K(2) = TREE(TREE(2)), K(3) = TREE(TREE( <(repeats (TREE(3) time (TREE(3)))

What you've made here is what's known in googology circles as a 'salad number'. It doesn't make a conceptual leap above what the TREE function can do anyway and is kind of similar to saying TREE(3) + 1.

SCG(13) is much bigger than your K(3) and Loader's number is much bigger than SCG(13). There are (computable) numbers bigger than Loader's number which are mentioned in the googology link in my previous post (Greedy clicque sequences and finite promise games).

Yea, the point was to pick something trivial. K(3) is larger than TREE( any obvious function to a non mathematician of any printable number).

But it's the m(x) that's actually large in that example.

> But it's the m(x) that's actually large in that example.

Sure, it's large (mindblowingly so), although I'm not quite clear exactly how you define m(x).

It's hard to get a grasp on just how much vastly larger each of these 'rockstar' numbers is to the previous one when you ascend this conceptual hierachy. (To a certain extent, that's the point of the article.)

You could make a K(K(K(...(n)...) function where you painted a K on each particle in the visible universe (about 10^80) and it still wouldn't come close to Loader's number. The point is that you can't simply recurse TREE and hope to get a number that's conceptually any bigger than TREE itself.

Yea, at some point you really can't tell if function 1 grows faster than function 2. Anyway to pick a large m(x).

m(0) = 1; m(x) is the recursion of all finite functions defined using k(m(x-1)) symbols that produce larger numbers than their input defined at stage m(x-1).

So a 1 step function F1(x) = X + X and F2(x) = X ^ X,... including any function that has been included in a mathematical paper to this point that takes one ore more finite numbers as an input.

And because these are all finite functions call them recursively in whatever order produces the largest output starting with the initial input (x). Now, to size this depends on what initial notations are allowed, so m(1) is a finite number.

Next level could then include F#(x) where F1(F2(x)) etc.

PS: The above is roughly equivalent to saying infinity +1 and is not interesting IMO. I can also drop the k from the above, but again the point is to use the dumbest approach that works.

Sounds a bit like Yudkowsky's number[1] (your main step is the first one, everything else is salad), which is a computable version of Rayo's number[2])

[1] http://googology.wikia.com/wiki/Yudkowsky%27s_Number

[2] https://en.wikipedia.org/wiki/Rayo%27s_number

Sure, but you need a large seed number at some point for functions like this. ex: Rayo's used 10^100.

So, they are all going to be take large value and use it to boost some other function m(x). I just happen to pick a large f(x).

I think the distinction is that Graham's Number is a "useful" number; i.e. it was used to help answer a problem. As you note, G + 1 is larger than G but G + 1 has (so far) no known significance.

BTW, I totally geeked out reading about Graham's Number. Thanks to the OP!

As the article states, it wasn't actually used in the proof where it's credited. Graham later cited it because it was easier to describe than his actual upper bounds.

I'm a big fan of the busy beaver family of problems and the halting problem is particularly interesting.

Naturally, the definition of the numbers and thought process used to describe them is orders of magnitude more interesting than the numbers themselves.

I've wondered about this. It's interesting that no matter how powerful the function, this sort of thing can always be done.

yeah but +1 is interesting if applied to the argument, not the function. TREE(3+1) instead of TREE(3)+1. In essence, +1 is all you have to work with if you want to stay in a sound logic, the question is just where to apply it. The logical conclusion would be op[TREE+1](3) in array notation.

Ah, I was wondering where the Busy Beaver idea came into this. The computability thing makes sense, ie. we can define a number using Busy Beavers but we can't ever really even reason about how big it is.

unless we're able to simply try all the required Turing machines.

The tricky bit isn't running the ones that halt and noticing when, but reasoning about all the ones that _don't_ halt in order to convince ourselves that they really never halt. The larger and more complex the machine, the harder it may be for a human to reason about it in this way.

For example, suppose it's 1985 and you are examining a machine which seems to be checking all integers X above 204 to see if it can find a^X + b^X = c^X. Does it halt? Unfortunately the only way to answer that question is to wait until 1996 when a proof is published which says Fermat was right, there are no values of X for which this is true. So the machine never halts.

[Edited to try to get HN to format the question properly]

recall this classic:

https://blog.regehr.org/archives/140

C Compilers Disprove Fermat’s Last Theorem

I don't think that's a helpful way to think about the Busy Beaver or non-computability. We know S(2,2) is exactly six, even though the function S is non-computable.

That SSCG function is pretty astonishing:

> SSCG(3) is not only larger than TREE(3), it is much, much larger than TREE(TREE(…TREE(3)…)) where the total nesting depth of the formula is TREE(3) levels of the TREE function.

notwithstanding that TREE(3) is pretty crazy in itself:

> an extremely weak lower bound for TREE(3), is A(A(...A(1)...)), where the number of A's is A(187196), and A() is a version of Ackermann's function. Graham's number, for example, is approximately A^64(4)

Reply on news.ycombinator.com