## FANDOM

10,503 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}$$.

## Sources

1. http://titan.csit.rmit.edu.au/~e24991/busybeaver/ Homepage of James Harland, Dec 2019
2. Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.
3. James Harland (2016) Busy beaver machines and the observant otter heuristic (or how to tame dreadful dragons) Theoretical Computer Science 646, 20: 61-85. (Preprint at arxiv)
4. https://www.scottaaronson.com/writings/bignumbers.html
5. https://skatgame.net/mburo/ps/diploma.pdf
6. http://www.logique.jussieu.fr/~michel/ha.html#dar