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ó, the name "frantic frog" was given by James Harland, as part of his Zany Zoo Turing machine research project.

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

## 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)$$. 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)$$.

## Values

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}$$.