Since TREE is a computable function the BB function grows faster than it, but TREE seems to grow much more quickly early on, so when does Busy Beaver surpass it?


closed as off-topic by user21820, Claude Leibovici, José Carlos Santos, Adrian Keister, Ali Caglayan Aug 13 '18 at 21:03

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user21820, Claude Leibovici, José Carlos Santos, Adrian Keister, Ali Caglayan
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ We don't know when it passes it, the largest value we know is $BB(4) = 13$. Furthermore $TREE(n)$ is so unfathomable large it is likely we cannot prove when they cross. $\endgroup$ – packetpacket Jul 31 '18 at 17:36
  • 3
    $\begingroup$ $TREE(n)$ is known to be a computable function. Therefore let $m$ be the number of states in a 2-color Turing machine, such that the Turing machine can compute $TREE(n)$. We now have $BB(m) \geq TREE(m)$ and certainly $BB(m+1) > TREE(m+1)$. So an upper bound to where they cross can be found by finding the minimum number of states required to compute $TREE(n)$ $\endgroup$ – packetpacket Jul 31 '18 at 17:54
  • 1
    $\begingroup$ It would be nice to give a lnik to TREE sequence. $\endgroup$ – Somos Jul 31 '18 at 18:00
  • 1
    $\begingroup$ This question seems somewhat related to MSE question 723286 "Milton Green's lower bounds of the busy beaver function". $\endgroup$ – Somos Jul 31 '18 at 18:18
  • 1
    $\begingroup$ It would seem that we have $$\Sigma(3350)>\operatorname{TREE}(n)$$for reasonably small $n$, thanks to @Somos 's link. A tighter bound may come from $$\Sigma(81,10)>f_{\text{BHO}}(2050)$$ where $\text{BHO}$ is the Bachmann-Howard ordinal, though I'm not familiar with how to convert this to the single argument $\Sigma$. $\endgroup$ – Simply Beautiful Art Aug 1 '18 at 3:12