Maximum shifts function

The maximum shifts function or frantic frog functionhttp://titan.csit.rmit.edu.au/~e24991/busybeaver/ Homepage of James Harland, Dec 2019, denoted \(S(n)\) or \(\text{FF}(n)\), is a cousin of the busy beaver function. \(S(n)\) is defined as the maximum number of state transitions made by an n-state, 2-color Turing machine before halting, given blank input.
While first discussed by Tibor Radó,Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962. the name "frantic frog" was given by James Harland, to disambiguate from the busy beaver function defined in terms of the score, and as part of his Zany Zoo Turing machine research project.James Harland (2016) Busy beaver machines and the observant otter heuristic (or how to tame dreadful dragons) Theoretical Computer Science 646, 20: 61-85. (Preprint at arxiv)James Harland. The Busy Beaver, the Placid Platypus and other Crazy Creatures
Recently, it has became more common for authors to refer to \(S(n)\) as the busy beaver function. https://www.scottaaronson.com/writings/bignumbers.html In particular, when the news broke out about the confirmation of the fifth busy beaver, the value of \(\text{BB}(5)\) refers to the frantic frog function.https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/
== Relations between functions S and \(\Sigma\) ==
Clearly \(S(n) \geq \Sigma(n)\), since printing \(\Sigma(n)\) ones from a blank tape requires at least \(\Sigma(n)\) steps. Therefore the frantic frog function is uncomputable, and eventually dominates all computable functions. Tibor Rado remarked that \(S(n) \leq (n + 1)\Sigma(5n)2^{\Sigma(5n)}\).
Michael Buro proved in 1990 that \(S(n) < \Sigma(9n)\).https://skatgame.net/mburo/ps/diploma.pdf There is an unverified statement on Pascal Michel's page that Ben-Amram and Petersen proved in 2002 that there is a constant c such that \(S(n) < \Sigma(n + \frac{8n}{\text{log}_2(n)} + c)\).http://www.logique.jussieu.fr/~michel/ha.html#dar
A machine that produces \(\Sigma(n)\) is not necessarily the same machine that produces \(S(n)\). For example, the following 3-state, 2-symbol busy beaver produces the maximum of six 1's but performs only 14 moves:P. Michel (2009) The Busy Beaver Competition: a historical survey arxiv. Update on 2022-12-14.
:
 	A 	B 	C
0	1RB	0RC	1LC
1	1RH	1RB	1LA
In comparison, the following busy beaver runs for the maximum of 21 moves but produces only five 1's:
:
 	A 	B 	C
0	1RB	1LB	1LC
1	1RH	0RC	1LA
== Values ==
It has been proven that \(S(1) = 1\), \(S(2) = 6\), \(S(3) = 21\), \(S(4) = 107\) and \(S(5) = 47,176,870\). We also know that \(S(6) \geq 10 \uparrow \uparrow 15\).Shawn Ligocki, BB(6, 2) > 10↑↑15, sligocki, Jun 21, 2022. (Retrieved at UTC 2024/06/06/15:56) See the Busy Beaver page for more information.
\(S(643)\) is the smallest known number undecidable in ZFC generated by maximum shifts function in the sense that the equality \(\underbrace{1+ \cdots +1}_m = S(643)\) is unprovable in ZFC set theory for any meta-theoretic natural number \(m\) as long as it is consistent. According to Scott Aaronson, it was shown by Rohan Ridenour.https://scottaaronson.blog?p=8131 (Retrieved Sep 21 2024)
== Sources ==
== See also ==
ru:Функция максимального сдвига
Category:Functions
Category:Zany Zoo
Category:Uncomputable