4 ms·
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
by sebzim4500 3y ago
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
- kevinventullo 3y agoHm, 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?
- nyssos 3y agoIt seems very unlikely: the full joint state space has n*m states, so you're throwing away almost everything for large n and m.
- sebzim4500 3y agoYou can, but BB(1) = 1 so that doesn't help with BB(n + 1) > BB(n) + 1
- deleted 3y ago[deleted]
- Someone 3y agoTake 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)?
- sebzim4500 3y agoyeah, 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.
- Someone 3y agoOops. Reversing your “BB(n) + 1 < BB(n + 1)” turned out to be too difficult for me today. Thanks for the reply.