Editing Busy beaver (section)

===Maximum shifts function ''S''===
In addition to the function Σ, Radó [1962] introduced another extreme function for Turing machines, the '''maximum shifts function''', ''S'', defined as follows:<ref name="rado" />

* {{math|''s''(''M'')}} = the number of shifts ''M'' makes before halting, for any {{math|''M'' ∈ ''E''<sub>''n''</sub>}},
* {{math|1=''S''(''n'') = max{{mset|''s''(''M'') | ''M'' ∈ ''E''<sub>''n''</sub>}}}} = the largest number of shifts made by any halting ''n''-state 2-symbol Turing machine.

Because normal 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''). Each shift may write a 0 or a 1 on the tape, while Σ counts a subset of the shifts that wrote a 1, namely the ones that hadn't been overwritten by the time the Turing machine halted; consequently, ''S'' grows at least as fast as Σ, which had already been proved to grow faster than any computable function.<ref name="rado" />

The following connection between Σ and ''S'' was used by Lin & Radó [''Computer Studies of Turing Machine Problems'', 1965] to prove that Σ(3) = 6 and that S(3)=21:  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 (after unsuccessfully conjecturing 18), then to simulate all the essentially different 3-state machines (82,944 machines, equal to 2{{sup|10}}3{{sup|4}}) for up to 21 steps. They found 26,073 machines that halted, including one that halted only after 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, most of them following a certain pattern. This proved the conjecture that ''S''(3) = 21, and also determined that Σ(3) = 6, which was attained by several machines, all halting after 11 to 14 steps.<ref name=":10" />

In 2016, Adam Yedidia and [[Scott Aaronson]] obtained the first (explicit) upper bound on the minimum ''n'' for which S(''n'') is unprovable in [[ZFC]]. To do so they constructed a 7910-state<ref>{{cite report |title=A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory |author=Adam Yedidia and Scott Aaronson |date=May 2016 |arxiv=1605.04343 |bibcode=2016arXiv160504343Y |institution=MIT |type=Technical Report}}</ref> Turing machine whose behavior cannot be proven based on the usual axioms of set theory ([[Zermelo–Fraenkel set theory]] with the [[axiom of choice]]), under reasonable consistency hypotheses ([[Ramsey cardinal|stationary Ramsey property]]).<ref>{{Cite web |last=Aron |first=Jacob |title=This Turing machine should run forever unless maths is wrong |url=https://newscientist.com/article/2087845-this-turing-machine-should-run-forever-unless-maths-is-wrong/ |access-date=2016-09-25 |website=NewScientist |language=en-US |archive-date=2016-10-20 |archive-url=https://web.archive.org/web/20161020113637/https://www.newscientist.com/article/2087845-this-turing-machine-should-run-forever-unless-maths-is-wrong/ |url-status=live }}</ref><ref name=":0">Version from May 3rd contained 7918 states: {{cite news |date=2016-05-03 |title=The 8000th Busy Beaver number eludes ZF set theory |url=https://scottaaronson.com/blog/?p=2725 |access-date=2016-09-25 |work=Shtetl-Optimized blog |archive-date=2016-09-27 |archive-url=https://web.archive.org/web/20160927020541/http://www.scottaaronson.com/blog/?p=2725 |url-status=live }}</ref> Stefan O'Rear then reduced it to 1919 states, with the dependency on the stationary Ramsey property eliminated,<ref name="Aaronson3">{{cite news |date=2016-05-03 |title=Three announcements |url=https://scottaaronson.com/blog/?p=2741 |access-date=2018-04-27 |work=Shtetl-Optimized blog}}</ref><ref>{{Cite web |date=2019-02-13 |title=GitHub - sorear/metamath-turing-machines: Metamath proof enumerators and other things. |url=https://github.com/sorear/metamath-turing-machines/blob/master/sample_out/zf.tm |website=[[GitHub]] |access-date=2018-05-19 |archive-date=2021-04-17 |archive-url=https://web.archive.org/web/20210417052518/https://github.com/sorear/metamath-turing-machines/blob/master/sample_out/zf.tm |url-status=live }}</ref> and later to 748 states.<ref name=":62" /> In July 2023, Riebel reduced it to 745 states.<ref name="AaronsonJuly2023">{{Cite web |date=2023-07-05 |title=Life, blogging, and the Busy Beaver function go on |url=https://scottaaronson.blog/?p=7388 |access-date=2023-08-27 |archive-date=2023-08-28 |archive-url=https://web.archive.org/web/20230828002248/https://scottaaronson.blog/?p=7388 |url-status=live }}</ref><ref name=":3" />