## FANDOM

10,003 Pages

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.

## Values Edit

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

## Sources Edit

1. Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.
2. http://www.crpit.com/confpapers/CRPITV51Harland.pdf