Im talking about the tree function, the famous function whose value TREE(3) is enormous. I know it is computable. Given that the function definition is rather simple, does there exist an algorithm of non pathological size that computes the function?
1
-
$\begingroup$ Generally questions here are often improved if you provide motivation (why it is an question that might be relevant to others) and some indication of what difficulty you are having (e.g., what progress you've made; what approaches you've considered and rejected and why you've rejected them). $\endgroup$– D.W. ♦Commented Aug 6 at 18:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Sure. The definition of the TREE function is "the largest $m$ so that... there is a sequence $T_1,\dots,T_m$..." So it suffices to build an algorithm to iterate over $m:=1,2,3,\dots$, and for each $m$, search over all possible combinations $T_1,\dots,T_m$ to see if there is any that meets the criteria, stopping at the first $m$ where no such combination exists. For any $m$, there are only finitely many combinations, so this algorithm is guaranteed to terminate. And it can be implemented fairly concisely.
