Take the machine for BB(n) with non-end states {1,2,3,…n} and end state E.
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)?
Take the machine for BB(n) with non-end states {1,2,3,…n} and end state E.
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)?
yeah, that shows BB(n+1) >= BB(n) + 1, but if you want to make the inequality strict you need to find a way to add another step.
Oops. Reversing your “BB(n) + 1 < BB(n + 1)” turned out to be too difficult for me today. Thanks for the reply.
Hm, is there some way to “concatenate” Turing machines which would let you prove something like
BB(n) + BB(m) <= BB(n+m+c)
for some fixed c independent of n and m?
It seems very unlikely: the full joint state space has n*m states, so you're throwing away almost everything for large n and m.
You can, but BB(1) = 1 so that doesn't help with BB(n + 1) > BB(n) + 1