5
$\begingroup$

I have recently begun getting interested in the field of googology, or as your tags list it, "big numbers." One of the first things I saw mentioned was the famous TREE(3) function. I am at a high school math level, and most of it was incomprehensible to me, so I did some side research trying to understand it, but it all seems to rely on math knowledge I don't have. Can someone explain TREE(3) to me? How does the function work? Keep it VERY simple. If you can't explain it, what resources should I look at to understand it? Keep in mind that we are just learning logarithms in high school, so I have a very small amount of mathematical knowledge. I do not believe this to be a duplicate of Why is TREE(3) so big? (Explanation for beginners), mostly due to the difference in knowledge. They had prior understanding of some of the concepts, and I do not, and as such require a very different answer because of the difference in mathematical comprehension.

$\endgroup$
4

1 Answer 1

8
$\begingroup$

Consider strings of matched brackets which are allowed to use three kinds of brackets, say (), [], and {}. Each open bracket must be closed by a bracket of the same kind, for example ([]) is a legal string but ([)] is not. Also, we require that there must be a single outermost bracket pair, so ()() is not a legal string, but [()()] is.

If you have two strings $s$ and $t$, say that $t$ is deletion-obtainable from $s$ if there is a way to get $t$ by starting from $s$ and repeatedly deleting some matching pairs of brackets.

Here are two examples:

  • ([]) is deletion-obtainable from (({})[]{}), because by starting from (({})[]{}), you can get ([]) by deleting matching pairs of brackets in this way: (({})[]{}) --> (()[]{}) --> ([]{}) --> ([]).
  • {[]} is deletion-obtainable from {({[()]})}, because by starting from {({[()]})}, you can get {[]} by deleting matching pairs of brackets in this way: {({[()]})} --> {{[()]}} --> {[()]} --> {[]}.
    • You can also do it this way: {({[()]})} --> ({[()]}) --> {[()]} --> {[]}.
  • On the other hand, ({}{}) is not deletion-obtainable from ({{{}}}): there is no way to delete any of the curly bracket pairs such that the resulting string has two {} pairs side-by-side.

Starting from a legal string, you can play a solitaire game with these rules:

  1. No illegal strings may be played.
  2. The string you play on the $i$th turn of the game can have at most $i$ pairs of brackets.
  3. No string you play on an earlier turn may be deletion-obtainable from a string you play on a later turn.

If at some point any of these rules are broken, then the game is over at that turn.


To understand this game better, here are some examples of games that end, and things about the solitaire game that can be learned from each one:

  • Turn 1: (()). This ends on the very first turn because rule 2 is broken right away, (()) has more than 1 bracket pair.

So it turns out that on the first turn, you have to play a string with only one bracket pair. How about some other games?

  • Turn 1: {}, Turn 2: (()), Turn 3: {[]}. This game ends on the third turn, because rule 3 is broken. {} is deletion obtainable from {[]}.
  • Turn 1: {}, Turn 2: {[]}. Rule 3 is broken on the second turn, because {} is deletion-obtainable from {[]}.

This suggests a strict property that the games must have: once you play that one bracket pair for the first turn, you are forbidden from using that type of bracket again. Some more games:

  • Turn 1: {}, Turn 2: [], Turn 3: (()), Turn 4: (()[]). The game ends at turn 4, because rule 3 is broken again. [] is deletion-obtainable from (()[]).

It seems to be a good strategy to play as long a string as you can on each turn, in order to prevent that string from showing up in a later turn. In this game [] was quite short for turn 2, having only one bracket pair while a string with a whole extra bracket pair could have been played.

There are other kinds of things you can find out from playing this game, pieces of strategy, changing the number of kinds of brackets available, changing rule 2's restriction on how many bracket pairs are allowed on turn $i$, etc.


As it turns out, this game is not very fun to play: you will always lose! This can be proven using Kruskal's tree theorem, a bit of mathematics about abstract structures called trees. Some games may persist for a very (very, very, very...) long finite number of turns, but in these games the player is just prolonging the inevitable. TREE(3) is then defined as the longest possible number of turns of one of these games.

Even knowing that each game is finite, it's not immediate that TREE(3) is finite. We have not ruled out the case that there is a game that lasts 1 turn, one lasting 2 turns, one that lasts 3 turns, etc. for every finite length, in each game the player prolonging the inevitable loss for an arbitrary, but finite, length of time. But it turns out the player doesn't even get that solace: Adam P. Goucher used another bit of math known as Kőnig's lemma to show that not only is every game is finite, but that there's a single finite number that upper-bounds them. Fortunately for us (but unfortunately for the player!) this means that TREE(3) exists and is finite.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .