Lower bound for $bb(7)$ - which one is true ? And what is the bound for $bb(6,3)$?

174 Views Asked by At
  • $bb(7)$ is already extremely large , but I found a discrepancy in the lower bound:
    In this survey the lower bound for $bb(7)$ is given as $$ BB(7) > 10^{10^{10^{10^7}}}, $$ hence four tens in the power tower followed by a 7.
    But here there are five tens in the power tower followed by a $7$. Which one is true ?

  • With $6$ states and $3$ symbols, the lower bound is HUGE, but I wonder whether I interprete the notation correctly :
    Is the bound here i.e. $$2\uparrow^6 8$$ in Knuth Arrow notation ?

A clarification would be appreciated.

1

There are 1 best solutions below

7
On BEST ANSWER

The lower bound for $BB(7)$ is the one given in the initial announcement

$$ BB(7) > 10^{10^{10^{10^{18705352}}}} > 10^{10^{10^{10^{10^7}}}}, $$

as confirmed by Cloudy176 and P. Michel in the links posted therein.

The notation used for $BB(6,3)$ is indeed $2 \uparrow^6 8$. The braces indicate Bowers' Exploding Array Notation, which up to three entries correspond with arrow notation as $\{a, b, c\} = a \uparrow^c b$. Also see the explanation posted below in the link, there some explanation is given using Knuth's arrow notation.