FANDOM


The 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.

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 47176870\) and \(S(6) \geq 7.412 \cdot 10^{36534}\).

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

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.