TREE(3) and impartial games

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:

3-labelled tree

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:

tree2

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.

Longest 2-labelled sequence

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:

first20

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:

lowerbound

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.

chocolate

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:

chocolate3

Then, the second player responds:

chocolate4

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:

chocolate2

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:

chocolate3

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 nth 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:

treegame

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:

first20

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

Inequality for x

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):

next6

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:

four-three

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.

Advertisements
This entry was posted in Activities, Fast-growing functions. Bookmark the permalink.

18 Responses to TREE(3) and impartial games

  1. wojowu says:

    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 🙂

    • apgoucher says:

      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.

      • wojowu says:

        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 😛

  2. Pingback: Busy beavers | Complex Projective 4-Space

  3. Danny says:

    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

    • apgoucher says:

      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).

  4. Pingback: Graph minors | Complex Projective 4-Space

  5. Decillion says:

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

    • apgoucher says:

      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.

    • apgoucher says:

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

  6. 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

  7. Anonymous says:

    YO NO ENTIENDO LO QUE TENGO QUE ACRE

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

  9. Anonymous says:

    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?

  10. Антон Изм says:

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

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

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

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

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

    1. Вы можете использовать их для обзвона потенциальных клиентов
    2. Для рассылки писем по email
    3. Для смс – рассылки
    4. Для почтовой рассылки на юридические адреса фирм
    5. Для поиска партнеров и новых клиентов в социальных сетях на страничках фирм
    6. Для написания Вашего предложения на сайтах фирм и т.д.

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

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

    В базах есть (формат Ексель): страна, регион, населенный пункт, адрес, телефон, email, сайт, город, (разделы и рубрики для выбора по фильтру),
    а так же странички или группы соцсетей фирм: ВК, Твиттер, Фейсбук, ОД

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

  11. itaibn says:

    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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s