FANDOM


We know the weak tree function has growth rate \(\vartheta(\Omega^\omega)\) in FGH or HH. However, to find a good bound of TREE(3), it's not enough that we just know tree(n) is comparable to \(H_{\vartheta(\Omega^\omega)}(n)\). We should know how it works. Here I found some results about tree function.

  • Sequences whose length comparable to \(H_{\vartheta(\Omega^\omega)}(n)\) (maybe not the winning sequences)
  • A better bound for growth rate of TREE(n)
  • A sequence of TREE(3) and a bound

We need a definition here for the second question.

tree(n)

Sequences started with (()()()...()()) can have length comparable to \(H_{\vartheta(\Omega^\omega)}(n)\). Now vertices have at most n children. Then it'll reduce to "all vertices have at most n-1 children", then "all vertices have at most n-2 children". Finally become a binary tree (but not ordered). It's at \(\varepsilon_0\) level (in HH).

If we get (()()) and at most n vertices, the next tree is ((...(())...)) with n+1 vertices. At the end we get () and at most 2n+1 vertices, at the same time \(H_{\omega}(n)=2n\), so we call (()()) has level \(\omega\).

More comparisons:

tree level
(()()) \(\omega\)
((()())) \(\omega+1\)
(((()()))) \(\omega+2\)
((())()) \(\omega2\)
(((()))()) \(\omega3\)
((()())()) \(\omega^2\)
(((()())())) \(\omega^2+1\)
(((()()))()) \(\omega^2+\omega\)
(((())())()) \(\omega^22\)
((((()))())()) \(\omega^23\)
(((()())())()) \(\omega^3\)
((((()())())())()) \(\omega^4\)
((())(())) \(\omega^\omega\)
(((())(()))) \(\omega^\omega+1\)
(((())(()))()) \(\omega^\omega+\omega\)
((((())(())))()) \(\omega^\omega+\omega2\)
((((())(()))())()) \(\omega^\omega+\omega^2\)
(((()))(())) \(\omega^\omega2\)
((((())))(())) \(\omega^\omega3\)
((()())(())) \(\omega^{\omega+1}\)
(((()()))(())) \(\omega^{\omega+1}+\omega^\omega\)
(((())())(())) \(\omega^{\omega+1}2\)
(((()())())(())) \(\omega^{\omega+2}\)
((((()())())())(())) \(\omega^{\omega+3}\)
(((())(()))(())) \(\omega^{\omega2}\)
((((())(())))(())) \(\omega^{\omega2}+\omega^\omega\)
((((()))(()))(())) \(\omega^{\omega2}2\)
((((())(()))(()))(())) \(\omega^{\omega3}\)
(((()))((()))) \(\omega^{\omega^2}\)
((((())))((()))) \(\omega^{\omega^2}2\)
(((()()))((()))) \(\omega^{\omega^2+1}\)
(((())(()))((()))) \(\omega^{\omega^2+\omega}\)
((((()))((())))((()))) \(\omega^{\omega^22}\)
((((())))(((())))) \(\omega^{\omega^3}\)
((()())(()())) \(\omega^{\omega^\omega}\)
(((()()))(()())) \(\omega^{\omega^\omega}2\)
(((())())(()())) \(\omega^{\omega^\omega+1}\)
(((())(()))(()())) \(\omega^{\omega^\omega+\omega}\)
(((()())(()()))(()())) \(\omega^{\omega^\omega2}\)
(((()()))((()()))) \(\omega^{\omega^{\omega+1}}\)
((((()())))(((()())))) \(\omega^{\omega^{\omega+2}}\)
(((())())((())())) \(\omega^{\omega^{\omega2}}\)
((((()))())(((()))())) \(\omega^{\omega^{\omega3}}\)
(((()())())((()())())) \(\omega^{\omega^{\omega^2}}\)
((((()())()))(((()())()))) \(\omega^{\omega^{\omega^2+1}}\)
((((()()))())(((()()))())) \(\omega^{\omega^{\omega^2+\omega}}\)
((((())())())(((())())())) \(\omega^{\omega^{\omega^22}}\)
((((()())())())(((()())())())) \(\omega^{\omega^{\omega^3}}\)
(((())(()))((())(()))) \(\omega^{\omega^{\omega^\omega}}\)
((((()))(()))(((()))(()))) \(\omega^{\omega^{\omega^\omega2}}\)
((((())(()))(()))(((())(()))(()))) \(\omega^{\omega^{\omega^{\omega2}}}\)
((((()))((())))(((()))((())))) \(\omega^{\omega^{\omega^{\omega^2}}}\)
(((((())))(((()))))((((())))(((()))))) \(\omega^{\omega^{\omega^{\omega^3}}}\)
(((()())(()()))((()())(()()))) \(\omega^{\omega^{\omega^{\omega^\omega}}}\)
((((())(()))((())(())))(((())(()))((())(())))) \(\omega^{\omega^{\omega^{\omega^{\omega^\omega}}}}\)
((((()())(()()))((()())(()())))(((()())(()()))((()())(()())))) \(\omega^{\omega^{\omega^{\omega^{\omega^{\omega^\omega}}}}}\)

Then, the first tree that has 3-children vertices is (()()()), which has level \(\varepsilon_0\). From \(\varepsilon_0\) to \(\varepsilon_1\) the (()()()) has no changes.

tree level
(()()()) \(\varepsilon_0\)
((()()())) \(\varepsilon_0+1\)
((()()())()) \(\varepsilon_0+\omega\)
((()()())(()())) \(\varepsilon_0+\omega^{\omega^\omega}\)
((()()())(()()())) \(\varepsilon_02\)
(((()()()))(()()())) \(\varepsilon_03\)
(((()()())())(()()())) \(\varepsilon_0\omega=\omega^{\varepsilon_0+1}\)
((((()()())()))(()()())) \(\omega^{\varepsilon_0+1}+\varepsilon_0\)
((((()()()))())(()()())) \(\omega^{\varepsilon_0+1}2\)
((((()()())())())(()()())) \(\omega^{\varepsilon_0+2}\)
(((()()())(()))(()()())) \(\omega^{\varepsilon_0+\omega}\)
(((()()())((())))(()()())) \(\omega^{\varepsilon_0+\omega^2}\)
(((()()())(()()))(()()())) \(\omega^{\varepsilon_0+\omega^\omega}\)
(((()()())(()()()))(()()())) \(\omega^{\varepsilon_02}\)
((((()()())(()()())))(()()())) \(\omega^{\varepsilon_02}+\varepsilon_0\)
((((()()()))(()()()))(()()())) \(\omega^{\varepsilon_02}2\)
((((()()())())(()()()))(()()())) \(\omega^{\varepsilon_02+1}\)
((((()()())(()()()))(()()()))(()()())) \(\omega^{\varepsilon_03}\)
(((((()()()))(()()()))(()()()))(()()())) \(\omega^{\varepsilon_03}2\)
(((((()()())(()()()))(()()()))(()()()))(()()())) \(\omega^{\varepsilon_04}\)
(((()()()))((()()()))) \(\omega^{\omega^{\varepsilon_0+1}}\)
((((()()())))((()()()))) \(\omega^{\omega^{\varepsilon_0+1}}2\)
(((()()())(()()()))((()()()))) \(\omega^{\omega^{\varepsilon_0+1}+\varepsilon_0}\)
((((()()())(()()()))(()()()))((()()()))) \(\omega^{\omega^{\varepsilon_0+1}+\varepsilon_0}2\)
((((()()()))((()()())))((()()()))) \(\omega^{\omega^{\varepsilon_0+1}2}\)
(((((()()()))((()()())))((()()())))((()()()))) \(\omega^{\omega^{\varepsilon_0+1}3}\)
((((()()())))(((()()())))) \(\omega^{\omega^{\varepsilon_0+2}}\)
(((()()())())((()()())())) \(\omega^{\omega^{\varepsilon_0+\omega}}\)
((((()()())()))(((()()())()))) \(\omega^{\omega^{\varepsilon_0+\omega+1}}\)
((((()()()))())(((()()()))())) \(\omega^{\omega^{\varepsilon_0+\omega2}}\)
(((()()())(()()))((()()())(()()))) \(\omega^{\omega^{\varepsilon_0+\omega^{\omega^\omega}}}\)
(((()()())(()()()))((()()())(()()()))) \(\omega^{\omega^{\varepsilon_02}}\)
((((()()())(()()())))(((()()())(()()())))) \(\omega^{\omega^{\varepsilon_02+1}}\)
((((()()()))(()()()))(((()()()))(()()()))) \(\omega^{\omega^{\varepsilon_03}}\)
((((()()())(()()()))(()()()))(((()()())(()()()))(()()()))) \(\omega^{\omega^{\omega^{\varepsilon_02}}}\)
((((()()())(()()()))((()()())(()()())))(((()()())(()()()))((()()())(()()())))) \(\omega^{\omega^{\omega^{\omega^{\varepsilon_02}}}}\)

Next ((())()()) has level \(\varepsilon_1\). 

tree level
((())()()) \(\varepsilon_1\)
(((()))()()) \(\varepsilon_2\)
((()())()()) \(\varepsilon_\omega\)
(((()())(()()))()()) \(\varepsilon_{\omega^{\omega^\omega}}\)
((()()())()()) \(\varepsilon_{\varepsilon_0}\)
(((()()())(()()()))()()) \(\varepsilon_{\varepsilon_02}\)
(((())()())()()) \(\varepsilon_{\varepsilon_1}\)
(((()()())()())()()) \(\varepsilon_{\varepsilon_{\varepsilon_0}}\)
((())(())()) \(\zeta_0\)
(((())(())())()()) \(\varepsilon_{\zeta_0+1}\)
((((())(())()))()()) \(\varepsilon_{\zeta_0+2}\)
((((())(())())((())(())()))()()) \(\varepsilon_{\zeta_02}\)
((((())(())())()())()()) \(\varepsilon_{\varepsilon_{\zeta_0+1}}\)
(((()))(())()) \(\zeta_1\)
(((())(())())(())()) \(\zeta_{\zeta_0}\)
(((()))((()))()) \(\varphi(3,0)\)
((()())(()())()) \(\varphi(\omega,0)\)
((()()())(()()())()) \(\varphi(\varepsilon_0,0)\)
(((()()())(()()())())((()()())(()()())())()) \(\varphi(\varphi(\varepsilon_0,0),0)\)
((())(())(())) \(\Gamma_0\)
(((())(())(()))()()) \(\varepsilon_{\Gamma_0+1}\)
((((())(())(())))()()) \(\varepsilon_{\Gamma_0+2}\)
((((())(())(()))()())()()) \(\varepsilon_{\varepsilon_{\Gamma_0+1}}\)
(((())(())(()))(())()) \(\zeta_{\Gamma_0+1}\)
(((())(())(()))(()()())()) \(\varphi(\varepsilon_0,\Gamma_0+1)\)
(((())(())(()))((())(())(()))()) \(\varphi(\Gamma_0,1)\)
((((())(())(()))((())(())(()))())(()()())()) \(\varphi(\varepsilon_0,\varphi(\Gamma_0,1)+1)\)
((((())(())(())))((())(())(()))()) \(\varphi(\Gamma_0,2)\)
((((())(())(()))((())(())(())))((())(())(()))()) \(\varphi(\Gamma_0,\Gamma_0)\)
((((())(())(()))()())((())(())(()))()) \(\varphi(\Gamma_0,\varepsilon_{\Gamma_0+1})\)
((((())(())(()))((())(())(()))())((())(())(()))()) \(\varphi(\Gamma_0,\varphi(\Gamma_0,1))\)
((((())(())(())))(((())(())(())))()) \(\varphi(\Gamma_0+1,0)\)
((((())(())(()))()())(((())(())(()))()())()) \(\varphi(\varepsilon_{\Gamma_0+1},0)\)
((((())(())(()))((())(())(()))())(((())(())(()))((())(())(()))())()) \(\varphi(\varphi(\Gamma_0,1),0)\)
(((()))(())(())) \(\Gamma_1\)
(((())(())(()))(())(())) \(\Gamma_{\Gamma_0}\)
(((()))((()))(())) \(\varphi(1,1,0)\)
(((())(())(()))((())(())(()))(())) \(\varphi(1,\Gamma_0,0)\)
(((()))((()))((()))) \(\varphi(2,0,0)\)
((()()())(()()())(()()())) \(\varphi(\varepsilon_0,0,0)\)
(((()()())(()()())(()()()))((()()())(()()())(()()()))((()()())(()()())(()()()))) \(\varphi(\varphi(\varepsilon_0,0,0),0,0)\)
(()()()()) \(\varphi(1,0,0,0)\)
((()()()())()()) \(\varepsilon_{\varphi(1,0,0,0)+1}\)
((()()()())(())()) \(\zeta_{\varphi(1,0,0,0)+1}\)
((()()()())(()()()())()) \(\varphi(\varphi(1,0,0,0),1)\)
((()()()())(())(())) \(\Gamma_{\varphi(1,0,0,0)+1}\)
((()()()())(()()()())(()()()())) \(\varphi(\varphi(1,0,0,0),0,1)\)
((())()()()) \(\varphi(1,0,0,1)\)
((())(())()()) \(\varphi(1,0,1,0)\)
((())(())(())()) \(\varphi(1,1,0,0)\)
((())(())(())(())) \(\varphi(2,0,0,0)\)
((()()()())(()()()())(()()()())(()()()())) \(\varphi(\varphi(1,0,0,0),0,0,0)\)
(()()()()()) \(\varphi(1,0,0,0,0)\)
(()()()()()()) \(\varphi(1,0,0,0,0,0)\)

So that is a way up to SVO. Start with (()()...()()) then reduce them from bottom to top in those tables.

TREE(m,n) and TREE(n)

The weak tree function tree(n)=TREE(1,n). But what about TREE(2,n), TREE(3,n) and more? Here I found a way to reduce them. Use (), [] and {} for different color of vertices.

A [] can reduce to (()()...()()) so it has level SVO. And more,

tree level
[] \(\vartheta(\Omega^\omega)\)
([]) \(\vartheta(\Omega^\omega)+1\)
(([])) \(\vartheta(\Omega^\omega)+2\)
([]()) \(\vartheta(\Omega^\omega)+\omega\)
([](()()()())) \(\vartheta(\Omega^\omega)+\varphi(1,0,0,0)\)
([][]) \(\vartheta(\Omega^\omega)2\)
(([][])(()()())) \(\vartheta(\Omega^\omega)2+\varepsilon_0\)
(([])[]) \(\vartheta(\Omega^\omega)3\)
(([]())[]) \(\omega^{\vartheta(\Omega^\omega)+1}\)
(([][])[]) \(\omega^{\vartheta(\Omega^\omega)2}\)
(([])([])) \(\omega^{\omega^{\vartheta(\Omega^\omega)+1}}\)
(([][])([][])) \(\omega^{\omega^{\vartheta(\Omega^\omega)2}}\)
([]()()) \(\varepsilon_{\vartheta(\Omega^\omega)+1}\)
([](())()) \(\zeta_{\vartheta(\Omega^\omega)+1}\)
([][]()) \(\varphi(\vartheta(\Omega^\omega),1)\)
([](())(())) \(\Gamma_{\vartheta(\Omega^\omega)+1}\)
([][][]) \(\varphi(\vartheta(\Omega^\omega),0,1)\)
([]()()()) \(\varphi(1,0,0,\vartheta(\Omega^\omega)+1)\)
([][][][]) \(\varphi(\vartheta(\Omega^\omega),0,0,1)\)
([][][][][]) \(\varphi(\vartheta(\Omega^\omega),0,0,0,1)\)
[()] \(\theta(\Omega^\omega,1)\)
[(())] \(\theta(\Omega^\omega,2)\)
[(()()())] \(\theta(\Omega^\omega,\varepsilon_0)\)
[[]] \(\theta(\Omega^\omega,\vartheta(\Omega^\omega))\)
[([])] \(\theta(\Omega^\omega,\vartheta(\Omega^\omega)+1)\)
[([][][])] \(\theta(\Omega^\omega,\varphi(\vartheta(\Omega^\omega),0,1))\)
[[()]] \(\theta(\Omega^\omega,\theta(\Omega^\omega,1))\)
[[[]]] \(\theta(\Omega^\omega,\theta(\Omega^\omega,\vartheta(\Omega^\omega)))\)
[()()] \(\vartheta(\Omega^\omega+1)\)
[[()()]] \(\theta(\Omega^\omega,\vartheta(\Omega^\omega+1)+1)\)
[([()()][()()][()()])] \(\theta(\Omega^\omega,\varepsilon_{\vartheta(\Omega^\omega+1)+1})\)
[[[()()]]] \(\theta(\Omega^\omega,\theta(\Omega^\omega,\vartheta(\Omega^\omega+1)+1))\)
[(())()] \(\theta(\Omega^\omega+1,1)\)
[[]()] \(\theta(\Omega^\omega+1,\vartheta(\Omega^\omega))\)
[[()()]()] \(\theta(\Omega^\omega+1,\vartheta(\Omega^\omega+1))\)
[[[()()]()]()] \(\theta(\Omega^\omega+1,\theta(\Omega^\omega+1,\vartheta(\Omega^\omega+1)))\)
[(())(())] \(\vartheta(\Omega^\omega+2)\)
[(()()())(()()())] \(\vartheta(\Omega^\omega+\varepsilon_0)\)
[[][]] \(\vartheta(\Omega^\omega+\vartheta(\Omega^\omega))\)
[[[][]][[][]]] \(\vartheta(\Omega^\omega+\vartheta(\Omega^\omega+\vartheta(\Omega^\omega)))\)
[()()()] \(\vartheta(\Omega^\omega+\Omega)\)
[(())()()] \(\vartheta(\Omega^\omega+\Omega,1)\)
[(())(())()] \(\vartheta(\Omega^\omega+\Omega+1)\)
[(())(())(())] \(\vartheta(\Omega^\omega+\Omega2)\)
[[][][]] \(\vartheta(\Omega^\omega+\Omega\vartheta(\Omega^\omega))\)
[()()()()] \(\vartheta(\Omega^\omega+\Omega^2)\)
[[][][][]] \(\vartheta(\Omega^\omega+\Omega^2\vartheta(\Omega^\omega))\)
[[][][][][]] \(\vartheta(\Omega^\omega+\Omega^3\vartheta(\Omega^\omega))\)
{} \(\vartheta(\Omega^\omega2)\)

So I get some bound for TREE(m,n) functions:

Growth rate of TREE(2,n)\(\geq\vartheta(\Omega^\omega2)\)

Growth rate of TREE(3,n)\(\geq\vartheta(\Omega^\omega3)\)

and so on.

TREE(n) go across all the TREE(m,n) for constant m, so growth rate of TREE(n)\(\geq\vartheta(\Omega^\omega\omega)\).

However, those sequences are not the winning sequence, so I've no idea about the upper bound of TREE(n).

TREE(3)

While evaluating TREE(3) (not TREE(n)), it's important to have a good beginning. After some comparisons, I found that sequence as follow. Some parts are not the same as the order in the tables in part 1 and 2.

(And thanks to Deedlit's idea, I get a new version.)

  1. {}
  2. [[]]
  3. [()()]
  4. [(()())] - Notice that [()()] isn't a minor of [(()())], and this can improve a lot.
  5. [(((())))]
  6. (([((()))]))
  7. ([((()))][][])
  8. ([((()))][]()()) - Not the same as in the table.
  9. ([((()))]()()()())
  10. ([((()))](())(())())
  11. ([((()))](()()())()()) - Then reduce the (()()()) only. This will take tree(3) steps.

tree(3)+10. ([((()))]()()())

tree(3)+11. ([((()))][((()))](()tree(3)+1)) - Here the superscript means there're tree(3)+1 ()'s as children in a (()()...()()).

tree(tree(3)+1)+tree(3)+10. ([((()))][((()))]())

tree(tree(3)+1)+tree(3)+11. ([((()))][](()tree(tree(3)+1)+tree(3)+4))

tree(tree(3)+1)+tree(3)+12. ([((()))][]((())(())()tree(tree(3)+1)+tree(3)+1))

tree(tree(3)+1)+tree(3)+13. ([((()))][]((()()())()tree(tree(3)+1)+tree(3)+2))

tree(tree(3)+1)+tree(3)+14. ([((()))][](((())(()))()tree(tree(3)+1)+tree(3)+2))

tree(tree(3)+1)+tree(3)+15. ([((()))][]((((())())())()tree(tree(3)+1)+tree(3)+2))

tree(tree(3)+1)+tree(3)+16. ([((()))][](((((()())))())()tree(tree(3)+1)+tree(3)+2))

tree(tree(3)+1)+tree(3)+17. ([((()))][]((((((()()))())))()tree(tree(3)+1)+tree(3)+2))

tree(tree(3)+1)+tree(3)+18. ([((()))][]((((((()()))()))()tree(tree(3)+1)+tree(3)+2)()))

tree(tree(3)+1)+tree(3)+19. ([((()))][]((((((((()()))()))()tree(tree(3)+1)+tree(3)+2)))))

tree(tree(3)+1)+tree(3)+20. ([((()))][(())](((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+tree(3)+21. ([((()))](([()]))(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+tree(3)+22. ([((()))]([()][()])(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+tree(3)+23. ([((()))]([()][][][])(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+tree(3)+24. ([((()))]([()][][]()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+tree(3)+25. ([((()))]([()][]()()()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+tree(3)+26. ([((()))]([()]()()()()()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+tree(3)+27. ([((()))]([()](())(())()()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+tree(3)+28. ([((()))]([()](()()())()()()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2)))) - Again, the (()()()) takes tree(3) steps.

tree(tree(3)+1)+2tree(3)+27. ([((()))]([()]()()()()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+2tree(3)+28. ([((()))]([()][](()tree(3)+4)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+2tree(3)+29. ([((()))]([()][]((())(())()tree(3)+1)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+2tree(3)+30. ([((()))]([()][]((()()())()tree(3)+2)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+2tree(3)+31. ([((()))]([()][](((())(()))()tree(3)+2)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+2tree(3)+32. ([((()))]([()][]((((())())())()tree(3)+2)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+2tree(3)+33. ([((()))]([()][](((((()())))())()tree(3)+2)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+2tree(3)+34. ([((()))]([()][]((((((()()))())))()tree(3)+2)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+2tree(3)+35. ([((()))]([()][]((((((()()))()))()tree(3)+2)())()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+2tree(3)+36. ([((()))]([()][]((((((((()()))()))()tree(3)+2))))()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

tree(tree(3)+1)+2tree(3)+37. ([((()))]([()]([][])(((((((()()))()))()tree(3)+2)))()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))

Then, changes happen on the subtree ([][]), and this part will be

tree(tree(3)+1)+2tree(3)+38. ([]()())

tree(tree(3)+1)+2tree(3)+39. ([](()()))

tree(tree(3)+1)+2tree(3)+40. ([](((()))))

tree(tree(3)+1)+2tree(3)+41. (([]())((())))

tree(tree(3)+1)+2tree(3)+42. (((([])))((())))

tree(tree(3)+1)+2tree(3)+43. (((([]))((())))())

tree(tree(3)+1)+2tree(3)+44. (((((([]))((()))))))

tree(tree(3)+1)+2tree(3)+45. ((((([]))((())))))

tree(tree(3)+1)+2tree(3)+46. (((([]))((()))))

tree(tree(3)+1)+2tree(3)+47. ((([]))((())))

tree(tree(3)+1)+2tree(3)+48. ((((([])((())))())(()))(()))

tree(tree(3)+1)+2tree(3)+49. ((((((([])((()))))))(()))(()))

tree(tree(3)+1)+2tree(3)+50. ((((((([])((())))))(()))())(()))

tree(tree(3)+1)+2tree(3)+51. ((((((((([])((())))))(())))))(()))

tree(tree(3)+1)+2tree(3)+52. ((((((((([])((())))))(()))))(()))())

tree(tree(3)+1)+2tree(3)+53. ((((((((((([])((())))))(()))))(())))))

tree(tree(3)+1)+2tree(3)+54. (((((((((([])((())))))(()))))(()))))

tree(tree(3)+1)+2tree(3)+55. ((((((((([])((())))))(()))))(())))

tree(tree(3)+1)+2tree(3)+56. (((((((([])((())))))(()))))(()))

tree(tree(3)+1)+2tree(3)+57. ((((((((((([])((())))))(())))(()))())())())())

tree(tree(3)+1)+2tree(3)+58. ((((((((((((([])((())))))(())))(())))))())())())

tree(tree(3)+1)+2tree(3)+59. (((((((((((((([])((())))))(())))(()))))())))())())

tree(tree(3)+1)+2tree(3)+60. ((((((((((((((([])((())))))(())))(()))))()))())))())

tree(tree(3)+1)+2tree(3)+61. (((((((((((((((([])((())))))(())))(()))))()))()))())))

tree(tree(3)+1)+2tree(3)+62. ((((((((((((((([])((())))))(())))(()))))()))()))()))

tree(tree(3)+1)+2tree(3)+63. (((((((((((((([])((())))))(())))(()))))()))()))())

tree(tree(3)+1)+2tree(3)+64. ((((((((((((((((((([])((())))))(())))(()))))()))())())))))))

tree(tree(3)+1)+2tree(3)+70. ((((((((((((([])((())))))(())))(()))))()))())())

tree(tree(3)+1)+2tree(3)+71. (((((((((((((((((((((((((([])((())))))(())))(()))))())())))))))))))))))())

tree(tree(3)+1)+2tree(3)+72. ((((((((((((((((((((((((((([])((())))))(())))(()))))())()))))))))))))))())))

tree(tree(3)+1)+2tree(3)+74. ((((((((((((((((((((((((([])((())))))(())))(()))))())()))))))))))))))())

tree(tree(3)+1)+2tree(3)+75. (((((((((((((((((((((((((((((([])((())))))(())))(()))))())())))))))))))))())))))))

tree(tree(3)+1)+2tree(3)+81. (((((((((((((((((((((((([])((())))))(())))(()))))())())))))))))))))())

tree(tree(3)+1)+2tree(3)+96. ((((((((((((((((((((((([])((())))))(())))(()))))())()))))))))))))())

tree(tree(3)+1)+2tree(3)+127. (((((((((((((((((((((([])((())))))(())))(()))))())())))))))))))())

tree(tree(3)+1)+2tree(3)+65589. (((((((((((([])((())))))(())))(()))))())())())

Now I start using Hardy hierarchy. Notice that it need one step to "expand" so in that hierarchy it's actually \(H_\alpha(n)=H_{\alpha[n]}(n)+1>H_{\alpha[n]}(n)\). So HH is actually slightly smaller.

\(>tree(tree(3)+1)+H_{\omega^3}(65534)\). ((((((((((([])((())))))(())))(())))())())())

\(>tree(tree(3)+1)+H_{\omega^32}(65534)\). (((((((((([])((())))))(())))(()))())())())

\(>tree(tree(3)+1)+H_{\omega^33}(65534)\). ((((((([])((())))))(())))(()))

\(>tree(tree(3)+1)+H_{\omega^\omega+\omega^33}(65534)\). (((((([])((())))))(()))(()))

\(>tree(tree(3)+1)+H_{\omega^{\omega2}+\omega^\omega+\omega^33}(65534)\). ((((([])((()))))(()))(()))

\(>tree(tree(3)+1)+H_{\omega^{\omega2}2+\omega^\omega+\omega^33}(65534)\). (((([])((())))(()))(()))

\(>tree(tree(3)+1)+H_{\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). (([])((())))

\(>tree(tree(3)+1)+H_{\omega^{\omega^2}+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). ([]((())))

\(>tree(tree(3)+1)+H_{\omega^{\omega^2}2+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). []

Now the whole tree becomes ([((()))]([()][](((((((()()))()))()tree(3)+2)))()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2)))). Then changes happen on the ([()][](((((((()()))()))()tree(3)+2)))()()). Notice that the subtree (((((((()()))()))()tree(3)+2))) has level \(\vartheta(\Omega^{tree(3)+1})\times(\omega^2+\omega+1)+2\), and once it decreases one vertix the [] will change into ([][]...[][]) with as many []'s as possible - at level \(\theta(\Omega^\omega,1)\). So

\(>H_{\theta(\Omega^\omega,1)\vartheta(\Omega^{tree(3)+1})\times(\omega^2+\omega+1)+\theta(\Omega^\omega,1)2+\omega^{\omega^2}2+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). ([()][]()()())

Then it reduce to ([()][][](()()...())) with as many ()'s as possible - at level \(\vartheta(\Omega^\omega)\), so

\(>H_{\theta(\Omega^\omega,1)^2\vartheta(\Omega^\omega)+\theta(\Omega^\omega,1)\vartheta(\Omega^{tree(3)+1})\times(\omega^2+\omega+1)+\theta(\Omega^\omega,1)2+\omega^{\omega^2}2+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). [()]

Now the whole tree becomes ([((()))][()](((((((()()))()))()tree(tree(3)+1)+tree(3)+2)))). Notice that the subtree (((((((()()))()))()tree(tree(3)+1)+tree(3)+2))) has level \(\vartheta(\Omega^{tree(tree(3)+1)+tree(3)+1})\times(\omega^2+\omega+1)+2\), and once it decreases one vertix the [()] will change into ([(())][][]...[][]) with as many []'s as possible - at level \(\theta(\Omega^\omega,3)\), so

\(>H_{\theta(\Omega^\omega,3)\vartheta(\Omega^{tree(tree(3)+1)+tree(3)+1})\times(\omega^2+\omega+1)+\theta(\Omega^\omega,3)2+\theta(\Omega^\omega,1)^2\vartheta(\Omega^\omega)+\theta(\Omega^\omega,1)\vartheta(\Omega^{tree(3)+1})\times(\omega^2+\omega+1)+\theta(\Omega^\omega,1)2+\omega^{\omega^2}2+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). ([((()))][()]())

At last the tree reduce to ([((()))][]()), ([((()))]()()), ([((()))]([(())][][][]...[][])), ([((()))]()), ([((()))]), [((()))], (). But those are only at level \(\theta(\Omega^\omega,3)2\), which is nothing comparing to \(\theta(\Omega^\omega,3)\vartheta(\Omega^{tree(tree(3)+1)+tree(3)+1})\times(\omega^2+\omega+1)\).

Finally, I get TREE(3)>\(H_{\theta(\Omega^\omega,3)\vartheta(\Omega^{tree(tree(3)+1)+tree(3)+1})\times(\omega^2+\omega+1)+\theta(\Omega^\omega,3)2+\theta(\Omega^\omega,1)^2\vartheta(\Omega^\omega)+\theta(\Omega^\omega,1)\vartheta(\Omega^{tree(3)+1})\times(\omega^2+\omega+1)+\theta(\Omega^\omega,1)2+\omega^{\omega^2}2+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\), and a more simple but slightly weaker bound is TREE(3)>\(H_{\theta(\Omega^\omega,3)\vartheta(\Omega^\omega)}(tree(tree(3)))\).

Who has a better idea?

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.