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]
A machine that produces is not necessarily the same machine that produces . For example, the following 3-state, 2-symbol busy beaver produces the maximum of six 1's but performs only 14 moves:[8]
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:[8]
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\), 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[]
- ↑ http://titan.csit.rmit.edu.au/~e24991/busybeaver/ Homepage of James Harland, Dec 2019
- ↑ Rado, T. "On Non-Computable Functions." Bell System Technical J. 41, 877-884, May 1962.
- ↑ 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)
- ↑ James Harland. The Busy Beaver, the Placid Platypus and other Crazy Creatures
- ↑ https://www.scottaaronson.com/writings/bignumbers.html
- ↑ https://skatgame.net/mburo/ps/diploma.pdf
- ↑ http://www.logique.jussieu.fr/~michel/ha.html#dar
- ↑ 8.0 8.1 P. Michel (2009) The Busy Beaver Competition: a historical survey arxiv. Update on 2022-12-14.
See also[]
Bignum Bakeoff contestants: pete-3.c · pete-9.c · pete-8.c · harper.c · ioannis.c · chan-2.c · chan-3.c · pete-4.c · chan.c · pete-5.c · pete-6.c · pete-7.c · marxen.c · loader.c
Channel systems: lossy channel system · priority channel system
Concepts: Recursion