In the context of Turing machines, consider a $k$-sized macro machine (k-MM) which operates on groups of $k$ symbols at once. This is a common optimization in the search for Busy Beavers, explained e.g. by Holkner: Acceleration Techniques for Busy Beaver Candidates, 2004.

Holkner writes:

The number of shifts required to halt the macro-machine with an underlying machine $M$ halting in $s(M)$ shifts will be less than or equal to $$ \frac{s(M)}{k} $$ and is typically far less.

If the machine passes over a whole $k$ sized block in each step, this result it obvious, as it must (internally) perform at least 1 operation on each of the $k$ symbols in that group.

However, it might also, for instance, change directions early and step out of the block, using less than $k$ operations. Repeating this requires exactly two symbol groups. As there are already $|Q||\Gamma|^i$ distinct configurations of $i$ symbols and $Q$ states, this is not just a small constant, but may be substantial for $i = \Theta(k)$.

Considering this, how is $\frac{s(M)}{k}$ still an upper bound for the required shifts?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.