Mixing
When does the busy beaver function surpass TREE(n)?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
1
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?
trees turing-machines upper-lower-bounds big-numbers
edited Aug 1 at 3:15
Simply Beautiful Art
49.1k572169
asked Jul 31 at 17:29
user1488
161
 |Â
show 3 more comments
up vote
3
down vote
favorite
1
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?
trees turing-machines upper-lower-bounds big-numbers
edited Aug 1 at 3:15
Simply Beautiful Art
49.1k572169
asked Jul 31 at 17:29
user1488
161
1
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.
– packetpacket
Jul 31 at 17:36
2
$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)$
– packetpacket
Jul 31 at 17:54
1
It would be nice to give a lnik to TREE sequence.
– Somos
Jul 31 at 18:00
1
This question seems somewhat related to MSE question 723286 "Milton Green's lower bounds of the busy beaver function".
– Somos
Jul 31 at 18:18
1
It would seem that we have $$Sigma(3350)>operatornameTREE(n)$$for reasonably small $n$, thanks to @Somos 's link. A tighter bound may come from $$Sigma(81,10)>f_textBHO(2050)$$ where $textBHO$ is the Bachmann-Howard ordinal, though I'm not familiar with how to convert this to the single argument $Sigma$.
– Simply Beautiful Art
Aug 1 at 3:12
 |Â
show 3 more comments
up vote
3
down vote
favorite
1
up vote
3
down vote
favorite
1
1
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?
trees turing-machines upper-lower-bounds big-numbers
edited Aug 1 at 3:15
Simply Beautiful Art
49.1k572169
asked Jul 31 at 17:29
user1488
161
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?
trees turing-machines upper-lower-bounds big-numbers
edited Aug 1 at 3:15
Simply Beautiful Art
49.1k572169
asked Jul 31 at 17:29
user1488
161
edited Aug 1 at 3:15
Simply Beautiful Art
49.1k572169
edited Aug 1 at 3:15
Simply Beautiful Art
49.1k572169
edited Aug 1 at 3:15
Simply Beautiful Art
49.1k572169
49.1k572169
asked Jul 31 at 17:29
user1488
161
asked Jul 31 at 17:29
user1488
161
asked Jul 31 at 17:29
user1488
161
161
1
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.
– packetpacket
Jul 31 at 17:36
2
$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)$
– packetpacket
Jul 31 at 17:54
1
It would be nice to give a lnik to TREE sequence.
– Somos
Jul 31 at 18:00
1
This question seems somewhat related to MSE question 723286 "Milton Green's lower bounds of the busy beaver function".
– Somos
Jul 31 at 18:18
1
It would seem that we have $$Sigma(3350)>operatornameTREE(n)$$for reasonably small $n$, thanks to @Somos 's link. A tighter bound may come from $$Sigma(81,10)>f_textBHO(2050)$$ where $textBHO$ is the Bachmann-Howard ordinal, though I'm not familiar with how to convert this to the single argument $Sigma$.
– Simply Beautiful Art
Aug 1 at 3:12
 |Â
show 3 more comments
1
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.
– packetpacket
Jul 31 at 17:36
2
$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)$
– packetpacket
Jul 31 at 17:54
1
It would be nice to give a lnik to TREE sequence.
– Somos
Jul 31 at 18:00
1
This question seems somewhat related to MSE question 723286 "Milton Green's lower bounds of the busy beaver function".
– Somos
Jul 31 at 18:18
1
It would seem that we have $$Sigma(3350)>operatornameTREE(n)$$for reasonably small $n$, thanks to @Somos 's link. A tighter bound may come from $$Sigma(81,10)>f_textBHO(2050)$$ where $textBHO$ is the Bachmann-Howard ordinal, though I'm not familiar with how to convert this to the single argument $Sigma$.
– Simply Beautiful Art
Aug 1 at 3:12
1
1
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.
– packetpacket
Jul 31 at 17:36
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.
– packetpacket
Jul 31 at 17:36
2
2
$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)$
– packetpacket
Jul 31 at 17:54
$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)$
– packetpacket
Jul 31 at 17:54
1
1
It would be nice to give a lnik to TREE sequence.
– Somos
Jul 31 at 18:00
It would be nice to give a lnik to TREE sequence.
– Somos
Jul 31 at 18:00
1
1
This question seems somewhat related to MSE question 723286 "Milton Green's lower bounds of the busy beaver function".
– Somos
Jul 31 at 18:18
This question seems somewhat related to MSE question 723286 "Milton Green's lower bounds of the busy beaver function".
– Somos
Jul 31 at 18:18
1
1
It would seem that we have $$Sigma(3350)>operatornameTREE(n)$$for reasonably small $n$, thanks to @Somos 's link. A tighter bound may come from $$Sigma(81,10)>f_textBHO(2050)$$ where $textBHO$ is the Bachmann-Howard ordinal, though I'm not familiar with how to convert this to the single argument $Sigma$.
– Simply Beautiful Art
Aug 1 at 3:12
It would seem that we have $$Sigma(3350)>operatornameTREE(n)$$for reasonably small $n$, thanks to @Somos 's link. A tighter bound may come from $$Sigma(81,10)>f_textBHO(2050)$$ where $textBHO$ is the Bachmann-Howard ordinal, though I'm not familiar with how to convert this to the single argument $Sigma$.
– Simply Beautiful Art
Aug 1 at 3:12
 |Â
show 3 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Â
draft saved
draft discarded
Â
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868281%2fwhen-does-the-busy-beaver-function-surpass-treen%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
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.
– packetpacket
Jul 31 at 17:36
2
$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)$
– packetpacket
Jul 31 at 17:54
1
It would be nice to give a lnik to TREE sequence.
– Somos
Jul 31 at 18:00
1
This question seems somewhat related to MSE question 723286 "Milton Green's lower bounds of the busy beaver function".
– Somos
Jul 31 at 18:18
1
It would seem that we have $$Sigma(3350)>operatornameTREE(n)$$for reasonably small $n$, thanks to @Somos 's link. A tighter bound may come from $$Sigma(81,10)>f_textBHO(2050)$$ where $textBHO$ is the Bachmann-Howard ordinal, though I'm not familiar with how to convert this to the single argument $Sigma$.
– Simply Beautiful Art
Aug 1 at 3:12