11,356
pages

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]

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