The maximum shifts function or frantic frog function[1], 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ó,[2] the name "frantic frog" was given by James Harland, as part of his Zany Zoo Turing machine research project.[3][4]

Some authors refer to \(S(n)\) as the busy beaver function.[5]

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.

Michael Buro proved in 1990 that \(S(n) < \Sigma(9n)\).[6] 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)\).[7]


It has been proven that \(S(1) = 1\), \(S(2) = 6\), \(S(3) = 21\), and \(S(4) = 107\). Some lower bounds for higher values are \(S(5) \geq 47,176,870\) and \(S(6) \geq 7.412 \cdot 10^{36,534}\).


See also

Community content is available under CC-BY-SA unless otherwise noted.