FANDOM


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. James Harland. The Busy Beaver, the Placid Platypus and other Crazy Creatures
  5. https://www.scottaaronson.com/writings/bignumbers.html
  6. https://skatgame.net/mburo/ps/diploma.pdf
  7. http://www.logique.jussieu.fr/~michel/ha.html#dar

See also

Community content is available under CC-BY-SA unless otherwise noted.