TREE(3) Is A Number Which Is Impossible To Contain

Humans may be the dominant species on the planet right now, but it wasn’t all that long ago, relatively speaking, that we were little more than a bunch of apes with a tendency to fall out of trees more than their cousins. Back in those days, the biggest numbers we had to deal with were things like “the number of goats that were eaten by wild bears overnight” or “how many more chunks of mammoth meat can Ogg cram in his mouth before it’s no longer rude to stab him with this Big Tusk?”

We’ve come a long way since then, but our understanding of numbers… well, that kind of hasn’t. Humans are really, really bad at understanding gigantic numbers – even the difference between a million and a billion is enough to befuddle most of us.

Of course, to googologists – that is, super-large number enthusiasts – a billion is not even small beans. You’ve got the googol, of course, and the googolplex above that; there’s Skewes’s number, and Graham’s number, each so much larger than its predecessor that everything below it may as well be zero.

Then, above even these monsters, there’s the infamous TREE(3).

Where does TREE(3) come from?

Much like Monopoly or Warhammer 40,000, the origin of TREE(3) is, basically, just a nerdy game that spiraled out of control very quickly. 

TREE(3) “comes from the Game of Trees,” says Tony Padilla, a physics professor at the University of Nottingham, in a video from mathtube favorite Numberphile.

“There are three different types of seeds,” he explains. “Mathematicians wouldn’t call these seeds, they’d call them nodes, but we’re going to call them seeds.”

From these “seeds” – one green, one black, and one red – the aim of the game is to build a “forest,” he continues. Like any game, there are certain rules we need to follow: “The first tree can’t have more than one seed,” Padilla instructs us; “the second tree can’t have more than two seeds; the third tree can’t have more than three seeds, and so on.”

Okay, so how do you lose the Game of Trees? That comes when a player builds a tree that contains another, earlier tree. At that point, Padilla explains, “the whole forest dies.”

Let’s ease ourselves into it with a simple example: instead of three types of seed, we’ll start with just one – let’s choose the green seed. According to our rules, the first tree in this green forest can have only one seed, and that makes our job very easy indeed.

What about a second tree in this forest? That would have either one or two seeds, and so we quickly find that we can’t go any further – we either get the tree we’ve already created or one which contains it.

In other words, Padilla explains, TREE(1) – the 1 here referring to the one type of seed, green, that’s been used to grow the forest – is equal to one. Simple.

TREE(2) is a little more tricksy. For this forest, we’re upping the number of seeds to two: green and red, and it turns out it’s possible to get a forest of three trees this time before the game’s up.

This one’s a little sneaky, but it’s legit. “Remember,” Padilla says, “the rule is, if you draw a tree that contains an earlier tree, that’s not allowed. But this [third] tree doesn’t contain either of these [previous] two.”

That puts TREE(2) at three – hardly more than its predecessor TREE(1). Hold on though, because things are about to get really gnarly.

“Now we’re going to use three different types of seeds,” Padilla says. “Red, black, and green… [Now] the longest game you could play is TREE(3).” 

But what exactly is TREE(3)? Surely it can’t be too huge – not coming directly after one and three. Right?

Oh, my sweet summer child.

How big is TREE(3)?

“I can’t express how really big it is,” Padilla says. “It’s off the scale big […] if you had Graham’s number of people and you said to them each, you know, just picture an equal amount of TREE(3), all of them would have their heads collapse into a black hole!”

If that sounds like hyperbole, believe us: it isn’t. It is physically impossible to contain all the digits of TREE(3) inside your brain – there’s a maximum amount of entropy that can be stored in our heads, and it’s way, way, way less than the information needed to contain TREE(3) would take up.

So, is there another way to envision the size of this massive number? Perhaps a comparison like we have with Graham’s number, which has more digits in it than there are Planck volumes in the universe?

Well, even here, there’s a problem. TREE(3) is so mind-meltingly big that not only can we not come up with a satisfactory comparison for how much time or space it would take to write out, but we don’t even know how many digits it has in total.

“It’s mad. It’s so big,” says Padilla. “There is a lower bound on it that involves Ackermann numbers – Ackermann numbers themselves are off the scale.”

But that “is just some rubbish lower bound on it,” he explains. “We don’t have an upper bound.”

Is TREE(3) just infinitely big, then?

We may not know how big TREE(3) is, and we may not be able to pinpoint any number bigger than it, but what we can say – kind of – is that it’s definitely not infinite.

How do we know that? It’s all thanks to a mathematician named Joseph Kruskal, who, back in 1960, proved what is now known (for obvious reasons) as Kruskal’s Tree Theorem.

It’s not easy to explain. “Basically he says, imagine the set of all the different combinations of seeds that you use, okay, and imagine there’s some sort of ordering […] it’s called well-quasi-ordering,” Padilla explains. 

“Then he said, the corresponding trees that you build out of those, the set of all of them, also has some sort of notion of ordering,” he continues. “And for us, the notion of ordering is this idea that eventually you’ll find one tree that contains a previous tree.”

In other words, if Kruskal’s Tree Theorem is correct, then any Game of Trees can only last a finite amount of time – even if that finite amount is far bigger than the amount of time, space, energy, and matter in the universe combined. But even here, there’s a catch.

“You can’t prove Kruskal’s Theorem using finite arithmetic,” Padilla points out – or to put it another way, “if you try to prove that TREE(n) was finite for all n, you can’t do that using finite arithmetic. It’s just not possible.”

Another dead end? Not quite. What we can do is something more specific. “Given any value of n, you can prove that TREE(n) is finite,” he explains – which is how we know that TREE(3), TREE(4), and so on are finite, albeit incredibly huge, numbers.

How to prove TREE(3) is finite

Great! You may be thinking – we finally have something firm we can say about this number that, so far, has defied every description we’ve tried to contain it with. TREE(3) is finite – it’s literally been proven to be true. So, how exactly does it work?

Well, we hate to be a party pooper, but this is yet another aspect of TREE(3) that’s simply far too big to handle. At least this time, however, we can actually describe just how large the proof would be to write out: in 2006, Ohio State mathematician Harvey Friedman, a pioneer in the super-abstract field now known as reverse mathematics, worked out that just the number of symbols needed to prove the finiteness of TREE(3) using finite arithmetic is at least 2↑↑1000.

If that notation, known as  Knuth’s up-arrow notation after its inventor, Donald Knuth, doesn’t look familiar to you, don’t worry: it’s pretty much unheard of outside the realm of these super-gigantic monster numbers. In short, though, it means a stack of powers of two, one thousand high: 

How big is that? Well, here’s a taste of how quickly these up-arrow values grow.

The next value in the series, 2↑↑5, is already so large as to be functionally incalculable without some kind of supercomputer: it’s close to 20,000 digits long. So you can imagine – or, more likely, you can’t – how long a proof that contains more than 2↑↑1000 symbols would be.

Padilla puts it into perspective. “The fastest you could write down any one symbol [is] a Planck time,” he says. “You definitely can’t write a symbol down faster than one Planck time, which is about 10^-43 seconds, it’s a tiny length of time.” 

“So let’s assume you can write down one symbol every Planck time,” he says. “Even if you’d started at the Big Bang […] you’d have got nowhere in this proof [by now].” 

Okay, but could you ever finish the proof? “Even the answer to that is no,” Padilla explains. “The universe is going to reset itself before [you] get a chance to finish it.” 

All of this really leaves us in a strange place, doesn’t it? TREE(3) is a number almost defined by its indefinability: it’s enormous, but we can’t say how enormous; it’s finite, and we can prove it – except, we can’t actually prove it, because the amount of time it would take is more than the life expectancy of existence itself.

Basically, what we’re saying is,

Source Link: TREE(3) Is A Number Which Is Impossible To Contain