It's actually really hard to come up with an interesting lower bound that value.
IIRC no one has proven that BB(n) + 1 < BB(n + 1) for large 2
IIRC no one has proven that BB(n) + 1 < BB(n + 1) for large 2
In its program, change every transition that goes to state E to go to a new state n+1 instead.
Add transitions “when in state n+1 and on a 1, move right” and “when in state n+1 and on a 0, write a 1 and stop”.
Doesn’t that give you a Turing machine with n+1 states that stops after writing one more 1 than BB(n) writes, thus proving that BB(n+1) is at least one more than BB(n+1)?
BB(n) + BB(m) <= BB(n+m+c)
for some fixed c independent of n and m?