The beeping busy beaver function is a relative of the maximum shifts function[note 1] proposed by Scott Aaronson in a conversation with Harvey Friedman[1]. Define a beep state as a state that is only exited a finite amount of times. Then for a Turing machine M, b(M) is the number of the last step on which it exits a beep state. BBB(n) is the maximum value of b(M) if M is a n-state Turing machine.
This function grows strictly faster than the standard busy beaver function. In particular, it cannot be computed even with a first-order oracle machine. The beeping busy beaver function is thus an explicitly constructed function equivalent to the second-order busy beaver function in growth rate.
Known values and bounds[]
Beeping booping busy beavers[]
An extension devised by Bram Cohen[4] goes as follows: a Turing machine has two special transitions, a beep transition and a boop transition, both of which repeat infinitely often. The machine outputs an integer sequence corresponding to the number of beeps between successive boops. The machine's number is the number of transitions it takes to finish the first output value that is repeated infinitely many times. These machines are considered equivalent to Turing machines with second-order oracles.
Footnotes[]
- ↑ Aaronson refers to the maximum shifts function as the "busy beaver function", a term which on this wiki usually refers to the sigma function.
References[]
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