How do we know that Loader is bigger or grows faster than TREE or SSCG?

313 Views Asked by At

From what I have gathered online about these numbers, they say that Loader's Number is larger than TREE(3) or SSCG(3) or similar. The reasoning I have seen goes is that Loader's Number is the largest computable number and TREE(3) and SSCG(3) are ostensibly computable numbers. But how do we know that:

  • Loader's Number is larger than TREE(3) or SSCG(3) (to which we have only a weak lower bound of 187196 nested Ackermann functions) assuming they are computable?
  • TREE(3) or SSCG(3) are computable in the first place? As far as I can tell these are just the longest potential game one could play given a certain number of node colors or maximum nodes. How do we know that these are computable functions? How could we solve the numbers besides brute forcing every possible game which would make them noncomputable functions?
1

There are 1 best solutions below

0
On BEST ANSWER

More or less, the reasoning is that all both $\mathrm{TREE}(3)$ and $\mathrm{SSCG}(3)$ are about finite objects, thus you can enumerate all these objects. For $\mathrm{TREE}(3)$, you can test all possible sequences of length $n$ for the desired property, and if such a sequence exists, determine that $\mathrm{TREE}(3) \ge n$. This makes them computable. Since the calculus of constructions is quite strong, the tree theorem (hopefully, I doubt anyone has checked) holds within it, and thus the $\mathrm{TREE}$ function is definable within, say, $10^9$ symbols. Since Loader's number is defined to be the largest one definable in the calculus of constructions in so-and-so ($> 10^9$) many symbols, so is $\mathrm{TREE}(3)$ and more generally, $\mathrm{TREE}(n)$ for some very large $n$.