Googology Wiki
Register
Advertisement
Googology Wiki

View full site to see MathJax equation

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[]

See also[]

Advertisement