4 ms·
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 a
by kevinventullo 3y ago
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?
- 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