Busy Beaver - Max Shifts Function

Max Shifts Function

In addition to the function Σ, Radó introduced another extreme function for the BB-class of Turing machines, the maximum shifts function, S, defined as follows:

• the number of shifts M makes before halting, for any M in E_n,
• the largest number of shifts made by any halting n-state 2-symbol Turing machine.

Because these Turing machines are required to have a shift in each and every transition or "step" (including any transition to a Halt state), the max-shifts function is at the same time a max-steps function.

Radó showed that S is noncomputable for the same reason that Σ is noncomputable — it grows faster than any computable function. He proved this simply by noting that for each n, S(n) ≥ Σ(n), because a shift is required to write a 1 on the tape; consequently, S grows at least as fast as Σ, which had already been proved to grow faster than any computable function.

The following connection between Σ and S was used by Lin & Radó to prove that Σ(3) = 6: For a given n, if S(n) is known then all n-state Turing machines can (in principle) be run for up to S(n) steps, at which point any machine that hasn't yet halted will never halt. At that point, by observing which machines have halted with the most 1s on the tape (i.e., the busy beavers), one obtains from their tapes the value of Σ(n). The approach used by Lin & Radó for the case of n = 3 was to conjecture that S(3) = 21, then to simulate all the essentially different 3-state machines for up to 21 steps. By analyzing the behavior of the machines that had not halted within 21 steps, they succeeded in showing that none of those machines would ever halt, thus proving the conjecture that S(3) = 21, and determining that Σ(3) = 6 by the procedure just described.

Inequalities relating Σ and S include the following (from ), which are valid for all n ≥ 1:

and an asymptotically improved bound (from ): there exists a constant c, such that for all n ≥ 2,