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 En,
- 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,
Read more about this topic: Busy Beaver
Famous quotes containing the words max, shifts and/or function:
“Music’s a wonderful background for our thoughts, isn’t it?”
—Arnold Phillips, Max Nosseck (1902–1972)
“The flattering, if arbitrary, label, First Lady of the Theatre, takes its toll. The demands are great, not only in energy but eventually in dramatic focus. It is difficult, if not impossible, for a star to occupy an inch of space without bursting seams, cramping everyone else’s style and unbalancing a play. No matter how self-effacing a famous player may be, he makes an entrance as a casual neighbor and the audience interest shifts to the house next door.”
—Helen Hayes (1900–1993)
“Our father has an even more important function than modeling manhood for us. He is also the authority to let us relax the requirements of the masculine model: if our father accepts us, then that declares us masculine enough to join the company of men. We, in effect, have our diploma in masculinity and can go on to develop other skills.”
—Frank Pittman (20th century)