FANDOM


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

See also Edit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.