This article was originally supposed to be about TREE(3) and the busy beaver function. However, I realised the potential of turning TREE(3) into a two-player finite game, which is surprisingly fun and means that I’ve ended up leaving uncomputable functions until a later post.

Last time, we explored a fast-growing hierarchy of functions. We considered the Goodstein sequence (or rather, the essentially equivalent problem C8′) to produce a function approximately equal to *f*_(ε_0), where ε_0 is a rather large countable ordinal. Applying this construction recursively would correspond to ordinals such as ε_0 + ω, which are not much larger than ε_0. So, if we want faster functions, we need more powerful ideas.

### Friedman’s TREE(3)

Usually, we expect fast-growing functions to have a relatively smooth, steady start. For instance, the Ackermann function begins {3, 4, 8, 65536, 2↑↑(2↑↑65536), …}, and the first four terms are quite small. By contrast, the function TREE begins with TREE(1) = 1, TREE(2) = 3 and TREE(3) is so vastly, incredibly large that it greatly exceeds anything you can express in a reasonable amount of space with iteration, recursion and everything else mentioned in the previous post, including C8′ and the Goodstein function.

So, what exactly is TREE? The definition is quite simple, once we’ve defined a few terms along the way. We consider rooted *k*-labelled trees, which are connected acyclic graphs where one vertex is identified as the ‘root’, and each vertex can have one of *k* colours. An example is shown below:

There is a binary operator, *inf* (not related to the infimum of a set), which returns the latest common ancestor of two vertices. Consider the tree above. If the blue vertex is called *x* and the green vertex is called *y*, then *x *inf* y = y*. Similarly, the inf of the two non-root red vertices is the root vertex.

We say that a tree *S* is *homeomorphically embeddable* into a tree *T* if there is an injection φ from the vertices of *S* to the vertices of *T* such that:

- φ(
*z*) and*z*have the same colour, for all*z*in*S*; - φ(
*x*inf*y*) = φ(*x*) inf φ(*y*), for all*x,y*in*S*.

Equivalently, this means that *T* is a topological minor of *S* (where we direct the edges to respect the root vertex). The first tree is homeomorphically embeddable into this one:

Proof: Delete the two green leaves, then contract the double-edge containing a blue vertex.

If we have an infinite sequence of *k*-labelled trees {*T*_1, *T*_2, *T*_3, …}, where each *T*_*n* has at most *n* vertices, then Kruskal’s tree theorem states that some *T*_*i* can be homeomorphically embedded into a later *T*_*j*. Hence, by compactness, there exists some value TREE(*k*), which is the length of the longest possible sequence of *k*-labelled trees {*T*_1, *T*_2, …, *T*_TREE(*k*)} such that |*T_n*| ≤ *n* (for all n)* *and no earlier tree can be homeomorphically embedded into a later tree.

The sequence above is the longest such sequence of 2-labelled trees, so TREE(2) = 3. For any sequence, the first tree must be a single isolated vertex, and that colour is not allowed to occur in any later tree. The proof follows trivially. Now consider 3-labelled trees. We can have an extremely long sequence, such as one which starts like this:

As you can see, by *T*_20 it’s getting difficult to draw the trees. A much more efficient notation is to use balanced parentheses:

T1 {} T2 [[]] T3 [()()] T4 [((()))] T5 ([(())][]) T6 ([(())](())) T7 ([(())]()()()) T8 ([(())]()()) T9 ([(())]()) T10 ([(())]) T11 [(())] T12 ([()][()][()][()][()][]) T13 ([()][()][()][()][()](())) T14 ([()][()][()][()][()]()()()) T15 ([()][()][()][()][()]()()) T16 ([()][()][()][()][()]()) T17 ([()][()][()][()][()]) T18 ([()][()][()][()][][][][][][][][][]) T19 ([()][()][()][()][][][][][][][][](())) T20 ([()][()][()][()][][][][][][][][]()()()) ...

A related function, *tree*, asks for the longest sequence {*U*_1, *U*_2, …, *U*_tree(*r*)} of 1-labelled trees such that |*U_n*| ≤ *n + r* (for all *n*) and no tree is homeomorphically embeddable into a later tree. By extending the sequence shown above, it can be proved that TREE(3) has the following (weak) lower bound:

Note that the tree function is roughly equivalent to *f*_ψ(Ω^ω), the *small Veblen ordinal*. This is infinitely greater than ε_0, so tree(*n*) > G(*n*) for all *n* ≥ *N*, where *N* is some constant. This constant is almost certainly surpassed by the arguments given in the lower bound, so TREE(3) is very much larger than any reasonable expression involving recursion and diagonalisation of Goodstein functions. Indeed, it’s *unimaginably* large.

Harvey Friedman demonstrated that the smallest proof in Peano arithmetic that TREE(3) exists requires far more symbols than atoms in the universe.

### The game of Chomp

For a quick and refreshing detour from large numbers, we’ll consider the game of *Chomp*. We begin with a rectangular chocolate bar of size *m* by *n*, the bottom-left corner of which has been laced with cyanide.

Players alternate turns, eating a square of chocolate together with everything above and to the right of it. For instance, after the first move the resulting configuration might resemble this:

Then, the second player responds:

This continues until some unlucky person is left with the cyanide-laced square of chocolate and endures a slow, painful death. Who has the winning strategy? Without explicitly constructing a winning streategy, it’s possible to prove that the first player can force a win through an argument known as *strategy stealing*.

Assume that the second player has a winning strategy, with the intention of deriving a contradiction. Let the first player (I generally use Gabriel and Vishal as example names in combinatorial game theory, and we’ll use alphabetical order, so Gabriel) eat the top-right square of chocolate:

Now, Vishal has a winning strategy at this point. Let’s assume (without any real loss of generality) that he can force a win by making this move:

Gabriel could have made this move to begin with, so Vishal can’t possibly have a winning strategy. Reductio ad absurdum. As the game cannot terminate in a draw, we conclude that Gabriel has the winning strategy. This proof is heavily non-constructive, and no-one knows what this winning strategy is for arbitrary positive integers *m,n*.

Chomp is called an *impartial game*, since the same moves are theoretically available to each player, and it just depends on whose turn it is. *Nim* is another example. Both of these can be expressed as *poset games*, where players take turns to remove any element of a partially-ordered set together with all greater elements.

### Making a game out of TREE(3)

That was a well-deserved distraction, but let’s return to TREE(3). We can define a two-player impartial game (which is, incidentally, a poset game) with the following rules:

- Players alternate taking turns.
- On the
*n*th turn (odd for Gabriel, even for Vishal), each player draws a 3-labelled tree with at most*n*vertices. - If you draw a tree such that an earlier tree is homeomorphically embeddable into it, you lose.

By definition, such a game lasts at most TREE(3) turns and can never result in a draw. I don’t know what the parity of TREE(3) is, so I don’t know who wins the longest game. Indeed, I don’t even know which player has the winning strategy in TREE(3), and an exhaustive search is impractical. An example game is this one, which Vishal wins after 8 turns:

Believe it or not, all reasonably-sized games of Chomp can occur as positions in natural games of TREE(3). Firstly, we return to the previous scheme for getting really long sequences:

Now, we can continue this for a very long time (*x* moves, where *x* has this unimaginably large lower bound):

After this incredibly long sequence of moves, the next six moves might be these (let *m* and *n* be positive integers where *m* + *n* < *x*; in practice, *x* is so large that it is unrestrictive):

This might not seem like a particularly poor move on Vishal’s part, but it transpires that Gabriel now has a definite winning strategy. If a player plays a single vertex (blue or green, since red was exhausted on the first move), the opponent can win by playing the single vertex of the other colour. Also note that no blue node can have a child, and no tree can have a depth more than three. In other words, subsequent moves resemble this:

This particular move is abbreviated to (4,3). Due to the ‘forbidden’ trees which appeared first, all moves must be of the form (*a,b*), where *a < m* and *b < n*. Interpreting these as coordinates, you may notice that this is precisely emulating the game of Chomp on a *m* by *n* grid! Exciting!

Consequently, Gabriel can force Vishal to ultimately play (0,0), which is a single green vertex. Gabriel immediately wins by playing a single blue vertex, leaving Vishal with no legal moves.

Some time ago I read that paper: ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal1.pdf

It’s said there that Kruskal’s Theorem and Friedman’s Finite Form of it can be proven to be true by equiping ourselves with Γ_0 well ordering statement. If so, we can use it to prove that TREE function is total, without need to use ordinal as enormous as Veblen ordinal. Doesn’t that imply that TREE(x) is of order f_Γ_0(x)?

Also, you didn’t write about n(x) function 🙂

I read elsewhere (in Harvey Friedman’s notes, if I remember correctly) that the strength of Kruskal’s tree theorem is measured by the small Veblen ordinal, which is greater than the Feferman-Schütte ordinal.

As for the n() function, it was too slow-growing for this post (it’s dominated by f_(omega^3), so pales in comparison with the Goodstein function mentioned at the end of the previous post).

Uncomputable functions should follow shortly.

Ah, sorry, you are right. What paper actually said (second part of paper) is that Kruskal’s theorem implies Γ_0 well ordering, not vice versa, as I understood it. So that theorem must be strictly stronger than Γ_0 well ordering statement, thus TREE function can be such fast-growing. Sorry, my bad 😛

Pingback: Busy beavers | Complex Projective 4-Space

Friedman has also described a number called SCG(13) that is far larger than TREE(3): http://www.cs.nyu.edu/pipermail/fom/2006-April/010362.html

Interesting. I was wondering about whether one could define a finite form of the graph minor theorem to obtain a fast-growing function.

I can believe that SSCG greatly exceeds TREE (in the same way that TREE exceeds tree(), even though they’re all measured by the small Veblen ordinal). Friedman doesn’t appear to have provided a proof of this, although I imagine one could use different induced subgraphs to represent different ‘labels’ to directly emulate the TREE function.

Chris Bird defined a function indexed by the Bachmann-Howard ordinal, which therefore grows much more quickly than any of these functions (but still very computable).

There’s some talk that Bird’s function is only at the level of Γ0 at most: http://forums.xkcd.com/viewtopic.php?f=14&t=7469&p=2191420

I have no idea if that’s true, however.

Also, “Deedlit” gives a nice explanation of subcubic graph numbers here: http://googology.wikia.com/wiki/Talk:Subcubic_graph_number

More specifically, he shows that SCG(0) = 6 and SCG(1) > fε04(29), and that the growth rate is at least the level of ψΩ1 (Ωω). I may be wrong, but I believe that is larger than the Bachman-Howard ordinal.

In the subsequent post ‘graph minors’, I’ve investigated values of the related function SSCG (*simple* subcubic graph numbers, where you’re not allowed multigraphs). TREE(3) is much smaller than SSCG(3), and much larger than SSCG(2):

https://cp4space.wordpress.com/2013/01/13/graph-minors/

There’s no qualitative difference between the asymptotic growth rates of SSCG and SCG. It’s clear that SCG(n) >= SSCG(n), but I can also prove SSCG(4n + 3) >= SCG(n).

Pingback: Graph minors | Complex Projective 4-Space

Has Friedman an upper bound for the number of elementary particles in the entire Universe?

In the observable universe, I seem to recall that there are about 10^80 elementary particles. In the entire (possibly infinite) universe, there are at most aleph_one (the first uncountable cardinal), assuming the following:

1. Space is locally R^3;

2. Elementary particles are open sets.

Equality occurs, for example, in the case where space is (Alexandroff line)^3 and particles are positioned in each (unit interval)^3.

Sorry, I forgot to mention that I’m also implicitly assuming the Universe is path-connected.

Good article i lobe it. But i always forgot it, after i remember but i always get a mistake on my self alat bantu sex

YO NO ENTIENDO LO QUE TENGO QUE ACRE

Might it be better to say “Ackermann function begins {3, 4, 8, 2↑↑4 (=65536), 2↑↑(2↑↑(2↑↑4)), …}”

Great article, but I’m still unclear on how Kruskal’s tree theorem implies that there is a single upper bound for all sequences of k-labelled trees without a homeomorphic embedding. The article states compactness and references the Bolzano-Weierstrass article but how do we invoke compactness here?

Все Ваши клиенты и партнеры для Вашего бизнеса уже есть в наличии!!!

Предлагаем базы данных фирм России, Украины, Белоруссии и Казахстана.

Для заказа баз данных фирм писать ТОЛЬКО на эту почту: baza-gorodov(собака)yandex.ru

БАЗЫ СОБИРАЕМ СРАЗУ ПОСЛЕ ЗАКАЗА – БЕЗ ПРЕДОПЛАТЫ!

ПРЕДОСТАВЛЯЕМ СКРИНЫ ДЛЯ ПРОСМОТРА И ДЕМО ВЕРСИИ БАЗ!

Спектр применения баз фирм огромный:

1. Вы можете использовать их для обзвона потенциальных клиентов

2. Для рассылки писем по email

3. Для смс – рассылки

4. Для почтовой рассылки на юридические адреса фирм

5. Для поиска партнеров и новых клиентов в социальных сетях на страничках фирм

6. Для написания Вашего предложения на сайтах фирм и т.д.

Стоимость базы фирм 1 города – от 700 до 1200 рублей! По стране 1 вид деятельности – 2000 рублей!

В базах есть фильтр и поиск, с их помощью найдете именно то, ЧТО Вам надо!

В базах есть (формат Ексель): страна, регион, населенный пункт, адрес, телефон, email, сайт, город, (разделы и рубрики для выбора по фильтру),

а так же странички или группы соцсетей фирм: ВК, Твиттер, Фейсбук, ОД

Для заказа баз данных фирм писать ТОЛЬКО на эту почту: baza-gorodov(собака)yandex.ru

The restriction that on the nth turn a player must pick a tree with at most n vertices is neither necessary nor natural. The Kruskal tree theorem shows that the game must end even if the players play arbitrarily large trees. Of course, without such a rule there’s no upper bound on how the game will last, making this an infinite game. All the more fun!