Advertisement
20,406
pages

View full site to see MathJax equation

Not to be confused with Busy beaver function.

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, to disambiguate from the busy beaver function defined in terms of the score, and as part of his Zany Zoo Turing machine research project.[3][4]

Recently, it has became more common for authors to refer to $$S(n)$$ as the busy beaver function. [5] In particular, when the news broke out about the confirmation of the fifth busy beaver, the value of $$\text{BB}(5)$$ refers to the frantic frog function.[6][7]

## 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. Tibor Rado remarked that $$S(n) \leq (n + 1)\Sigma(5n)2^{\Sigma(5n)}$$.

Michael Buro proved in 1990 that $$S(n) < \Sigma(9n)$$.[8] 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)$$.[9]

A machine that produces $$\Sigma(n)$$ is not necessarily the same machine that produces $$S(n)$$. For example, the following 3-state, 2-symbol busy beaver produces the maximum of six 1's but performs only 14 moves:[10]

A B C
0 1RB 0RC 1LC
1 1RH 1RB 1LA

In comparison, the following busy beaver runs for the maximum of 21 moves but produces only five 1's:[10]

A B C
0 1RB 1LB 1LC
1 1RH 0RC 1LA

## Values

It has been proven that $$S(1) = 1$$, $$S(2) = 6$$, $$S(3) = 21$$, $$S(4) = 107$$ and $$S(5) = 47,176,870$$ [11] . We also know that $$S(6) \geq 10 \uparrow \uparrow 15$$[12]. See the Busy Beaver page for more information.

## 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. The Busy Beaver Challenge. Story. Retrieved 2023-04-09.
6. https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/
7. https://skatgame.net/mburo/ps/diploma.pdf
8. http://www.logique.jussieu.fr/~michel/ha.html#dar
9. P. Michel (2009) The Busy Beaver Competition: a historical survey arxiv. Update on 2022-12-14.
10. The Busy Beaver Challenge. We have proved "BB(5) = 47,176,870". Retrieved 2024-07-02.
11. Shawn Ligocki, BB(6, 2) > 10↑↑15, sligocki, Jun 21, 2022. (Retrieved at UTC 2024/06/06/15:56)

## See also

Large numbers in computers
Advertisement