- Not to be confused with Busy beaver function.
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, to disambiguate from the busy beaver function defined in terms of the score, and as part of his Zany Zoo Turing machine research project.[3][4]
Recently, it has became more common for authors to refer to \(S(n)\) as the busy beaver function. [5] In particular, when the news broke out about the confirmation of the fifth busy beaver, the value of \(\text{BB}(5)\) refers to the frantic frog function.[6][7]
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. Tibor Rado remarked that \(S(n) \leq (n + 1)\Sigma(5n)2^{\Sigma(5n)}\).
Michael Buro proved in 1990 that \(S(n) < \Sigma(9n)\).[8] 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)\).[9]
A machine that produces \(\Sigma(n)\) is not necessarily the same machine that produces \(S(n)\). For example, the following 3-state, 2-symbol busy beaver produces the maximum of six 1's but performs only 14 moves:[10]
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:[10]
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\), \(S(4) = 107\) and \(S(5) = 47,176,870\).[11] We also know that \(S(6) \geq 10 \uparrow \uparrow 15\).[12] See the Busy Beaver page for more information.
\(S(643)\) is the smallest known number undecidable in ZFC generated by maximum shifts function in the sense that the equality \(\underbrace{1+ \cdots +1}_m = S(643)\) is unprovable in ZFC set theory for any meta-theoretic natural number \(m\) as long as it is consistent. According to Scott Aaronson, it was shown by Rohan Ridenour.[13]
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
- ↑ The Busy Beaver Challenge. Story. Retrieved 2023-04-09.
- ↑ https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/
- ↑ https://skatgame.net/mburo/ps/diploma.pdf
- ↑ http://www.logique.jussieu.fr/~michel/ha.html#dar
- ↑ 10.0 10.1 P. Michel (2009) The Busy Beaver Competition: a historical survey arxiv. Update on 2022-12-14.
- ↑ The Busy Beaver Challenge. We have proved "BB(5) = 47,176,870". Retrieved 2024-07-02.
- ↑ Shawn Ligocki, BB(6, 2) > 10↑↑15, sligocki, Jun 21, 2022. (Retrieved at UTC 2024/06/06/15:56)
- ↑ https://scottaaronson.blog?p=8131 (Retrieved Sep 21 2024)
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