2
$\begingroup$

It is known that $bb(23)$>Graham's number (I do not remember exactly, but $bb(21)$ could already be larger).

But what is the smallest number $n$, such that $bb(n)>f_{\epsilon_0}(5)$ is known ?

Here :

Milton Green's lower bounds of the busy beaver function

it is mentioned that $\Sigma(41,3)$ is much greater than $f_{\epsilon_0}(5)$, but I am looking for a binary machine.

$\endgroup$
  • 1
    $\begingroup$ Best known for Graham's number is $\Sigma(22)$. I also confirm the result that Deedlit mentions. $\endgroup$ – wythagoras May 29 '16 at 19:14
2
$\begingroup$

Wythagoras created an 85-state Turing machine that produced more than $f_{\varepsilon_0}(1907)$ ones, listed here. I believe it is based on an implementation of the Kirby-Paris hydra.

$\endgroup$
  • $\begingroup$ Very interesting! +1 $\endgroup$ – Peter May 16 '16 at 17:30
  • $\begingroup$ According to the link, $bb(85)$ is even largen than $f_{\epsilon_0}(1907)$ $\endgroup$ – Peter May 16 '16 at 17:38
  • $\begingroup$ whoops, 1905 was a typo. $\endgroup$ – Deedlit May 16 '16 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.