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

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.

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


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}\).


  1. Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.

See also