6
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.