“Graham’s number is effectively zero compared to TREE(3)”

February 17, 2022 1:43 PM

We’ve talked about Graham’s Number previously, most recently after Ron Graham’s death in 2020. Numberphile has several great videos about it: Graham’s Number; What is Graham’s Number? (featuring Ron Graham); How Big is Graham’s Number? (featuring Ron Graham). But we’re just getting started. The number TREE(3), which comes from a simple combinatorial problem in graph theory, is proven to be finite, but unimaginably larger than the already unimaginable Graham’s Number. Tony Padilla explains further in these Numberphile videos: The Enormous TREE(3); TREE(3) (extra footage); TREE vs Graham’s Number; TREE(Graham’s Number) (extra). There is an endless supply of even larger numbers defined by fast-growing computable sequences, but things get wilder in the realm of uncomputable numbers. The Busy Beaver function, related to the maximum number of steps taken by a halting Turing machine with a given number of states, provably grows faster than any computable function. David Brailsford explains in the Computerphile video Busy Beaver Turing Machines. And Rayo’s Number is “one of the largest named numbers in professional mathematics.” Tony Padilla is back to explain in The Daddy of Big Numbers (Rayo’s Number).

The Googology Wiki has much more about large finite numbers and fast-growing functions. (Including lists of specific large numbers with fanciful but apparently systematic names: within Bachmann’s Collapsing Level, we find numbers like Superior Grand Megaenormaquaxul and Goxxaquorg, which lie on opposite sides of a lower bound for TREE(3).)

John Baez [warning: homepage contains weeks of rabbitholes] on Enormous Integers. (Do read the comments on any of his blog posts.)

Many duplicate links thanks to #DoublesJubilee. Large finite numbers previously: Ron Graham obituary; On coming to grips with g_64; Graham’s Number [dead link, but apparently embedding the first Numberphile video]; Very Large Numbers; Who can name the bigger number?.

Note, the Googology Wiki says the Numberphile videos on TREE(3) include unproven and possibly incorrect results about the growth rate of the TREE(n) function vs. other fast-growing functions. However, this does not change the facts that TREE(3) is unimaginably larger than Graham’s Number, and that the function TREE(n) grows unimaginably faster than Graham’s G(n).

posted by mubba (24 comments total)

The ultimate question WRT numbers is, of course...

...same as in town?
posted by Halloween Jack at 1:48 PM on February 17, 2022 [1 favorite]

I love Numberphile so much -- the enthusiasm is so infectious and sincere that they draw me in even if a lot goes over my head. Looking forward to these!

My only complaint is that they always leave me feeling a bit said that I had such crappy and unenthusiastic math teachers throughout most of schooling that I wrote math off as boring and tedious until I was well into adulthood. Maybe one of these days I'll take some community college courses and finally re-learn algebra and, for the first time, calculus.
posted by myfavoriteband at 2:09 PM on February 17, 2022 [3 favorites]

I had the privilege to attend a talk by Ron Graham on (something like) Math that computer can never handle. I was surely the least of many attributes in the room, but he was clear, not at all esoteric/mathy, and I felt like I could follow a lot of his discussion. Boy it did not stick for more than a few minutes.
posted by sammyo at 3:25 PM on February 17, 2022

Wait'll they hear about TREE(4)
posted by mrnutty at 3:31 PM on February 17, 2022

"The Daddy of Big Numbers" sounds like the nickname of the guy who runs the backroom at Black Hole Dominance, the Thursday night party for mathematicians and physicists at the Eagle....
posted by GenjiandProust at 3:34 PM on February 17, 2022 [2 favorites]

Thanks for these. I was watching some of the Numberphile videos on Graham's number and TREE(3) recently, so this post is very serendipitous!

I'm inexplicably fascinated with large numbers and these videos really appeal to me. With my level of maths I'm perplexed by the difference between Graham's number, as although vast, has an understandable construction, and the fact that I don't have any way to reason about the size of TREE(3).

Looking forward to watching the rest of them.
posted by doozer_ex_machina at 3:54 PM on February 17, 2022

On the subject of disappointing math instruction: I first encountered this classic essay by Paul Lockhart around the time that my children were learning arithmetic and finding it terribly boring. I remember telling them that they were right: arithmetic is boring. Arithmetic is like the alphabet, which is also boring. We lie to children and tell them that the alphabet is interesting. When children start school, we have them sing songs about the alphabet and decorate their classrooms with the alphabet and give them alphabet-themed pouches to put their pencils in. Around third grade that all stops, and we never talk about the alphabet again, because we are too busy using the alphabet to read about DINOSAURS.

Arithmetic is mostly super-boring. But you can use arithmetic to do some really, really interesting things — that’s the math. Some of those interesting things run right up against questions of what arithmetic means, and what it is like to be a bag of meat that can think about arithmetic.

I told one of my children that the googol, 10¹⁰⁰, is a number that you can write down, but you could never count to, even if you spent the life of the universe counting. They were in first grade or thereabouts, and thought that was a neat idea. Then I told them about the googolplex, 10¹⁰¹⁰⁰, which has a googol’s worth of digits, so you could never even write it down. I remember they said, “Okay, that doesn’t make sense any more.” Always seemed to me like a very perceptive response. There is definitely a point in these large-number discussions where a switch flips in my head, and I think “gosh, I don’t have a space for this abstraction any more.” And sometimes I’ll revisit an old discussion and discover that the limits of my understanding have changed. Usually the change is that I understand more of it.
posted by fantabulous timewaster at 3:55 PM on February 17, 2022 [8 favorites]

You can't fool me. The biggest number is eleven.
posted by fallingbadgers at 4:29 PM on February 17, 2022 [1 favorite]

I think you mean 24. 24 is the highest number.
posted by The Great Big Mulp at 5:18 PM on February 17, 2022 [6 favorites]

Rayo's number uses 2nd order set theory to make a statement about 1st order set theory. I think the way to get bigger than Rayo is to let N=T̅R̅E̅E(10^100) [or any other 'conventionally very large number'] and then make a statement about the numbers that statements in N'th order set theory can make about (N-1)'th order set theory.
posted by the antecedent of that pronoun at 5:19 PM on February 17, 2022

Fuck Everything, We're Doing TREE(5)
posted by Stonestock Relentless at 5:46 PM on February 17, 2022 [3 favorites]

TREE(TREE(3))
posted by paper chromatographologist at 5:47 PM on February 17, 2022 [2 favorites]

...things get wilder in the realm of uncomputable numbers.

Sadly we may never know whether it is, or is not, numberwang.
posted by Western Infidels at 5:54 PM on February 17, 2022 [13 favorites]

I (a nonmathematician) have known about Graham's number since ~1990 due to having purchased The Penguin Dictionary of Curious and Interesting Numbers. Highly recommended if you like this sort of thing.
posted by neuron at 9:43 PM on February 17, 2022 [1 favorite]

When I was five, I decided to see how high I could count. I started in the morning, and counted all day in my head. And this was the really clever part: I counted by tens. Just to be more efficient.
posted by Nothing at 3:48 AM on February 18, 2022 [4 favorites]

Well, don't leave us hanging.
posted by ultraviolet catastrophe at 6:09 AM on February 18, 2022 [2 favorites]

Neat. This is the first time I've ever heard of up-arrow notation. As someone who only ever thinks about continuous functions, as far as we know, I don't immediately understand how to use any of it. But, it is neat! (And the post is really well constructed.)
posted by eotvos at 7:20 AM on February 18, 2022

I can’t imagine Graham gets too many phone calls, with a number like that.
posted by notoriety public at 9:44 AM on February 18, 2022 [1 favorite]

JENNY = TREE(867-5309)
posted by fantabulous timewaster at 11:45 AM on February 18, 2022 [2 favorites]

Anybody who hasn't should check out The Numberphile Podcast - YouTube on their second channel for longish audio only interviews with maths peoples about their life and work and thinking.
posted by zengargoyle at 6:30 PM on February 18, 2022

JENNY = TREE(867-5309)

Well, first you need to extend TREE to negative numbers...
posted by vernondalhart at 12:45 AM on February 19, 2022 [2 favorites]

The Great Big Mulp - sent me off on a tangent looking up more early Odenkirk - I had no idea he was in the same show as "Pre-taped call-in guy". Thank you.
posted by BCMagee at 1:55 AM on February 19, 2022 [1 favorite]

I know of Graham's number (though I feel like every time I've run into it, which isn't often, I have to relearn how Conway's arrow notation works), but I can't remember if I've really encountered TREE(n) as more than maybe a passing reference before. The maddening thing is that TREE(3) leaps to "impossibly, universally impractically huge" right at the moment that it also starts looking like—with the tree-creating game—exactly the sort of thing I'd usually enjoy playing at iterating on in a notebook or programmatically. Really takes the wind out of the sales of a math/art project to know up front that it'd take longer than the heat death of the universe before I could get a good start on it.
posted by cortex at 12:44 PM on February 19, 2022

So TREE(3), the biggest possible set of trees is big .. but if you cast about at random, are they big or small? Is there an algorithm for finding the biggest TREE(3) in some direct way, rather than enumerating all the possible games? How many games are there that end after just 31 moves? I'm not convinced there's not a reasonably sized generative art project "neighbor" to the tree game.
posted by the antecedent of that pronoun at 6:42 PM on February 19, 2022