This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A384629 #35 Aug 13 2025 21:28:39 %S A384629 0,1,3,5,16,37,123,3932963 %N A384629 Instruction-Limited Busy Beaver Sequence BBi(n): Maximum number of steps that an n-instruction Turing machine (allowing any number of states and symbols) can take on an initially blank tape before eventually halting. %C A384629 This sequence is uncomputable. %C A384629 No halting instruction is required, as a Turing machine halts whenever the current state/tape symbol combination does not have a corresponding instruction. However, a halting instruction can be implemented by transitioning to a state which has no instructions. For example, the 2-state 2-symbol busy beaver can be given as A0:1RB, A1:1LB, B0:1LA, B1:1RC, where "C" effectively substitutes for "H". %C A384629 This sequence effectively combines the various Busy Beaver step functions BB(states,symbols) into a single sequence defined only by number of allowable instructions BBi(inst). It is very interesting to observe the number of states and symbols associated with the champion machine for each number of instructions. %C A384629 a(6)=123 confirmed by Shawn Ligocki on bbchallenge discord on Jul 12 2025. %C A384629 a(7)=3932963 confirmed and announced on discord on Jul 23 2025. Two different Turing machines - one a 2-state, 4-symbol machine, and the other a 3-state, 3-symbol machine - each take 3932963 steps, writing 2050 non-blank symbols to tape. %C A384629 A new champion machine for a(8) was discovered by Nick Drozd and confirmed by Shawn Ligocki on Jul 26 2025. This machine takes around 6.889 x 10^1565 steps before halting. %H A384629 bbchalenge Wiki, <a href="https://wiki.bbchallenge.org/wiki/Instruction-Limited_Busy_Beaver">Instruction-Limited Busy Beaver</a>. %H A384629 discord, <a href="https://discord.com/channels/960643023006490684/1084047886494470185/1397751750169067580">Announcement of BBi(7).</a>. %H A384629 N. Drozd, <a href="https://discord.com/channels/960643023006490684/1084047886494470185/1398753236835635252">New BBi(8) champion machine found</a>. %H A384629 S. Ligocki, <a href="https://discord.com/channels/960643023006490684/1084047886494470185/1398857599935578303">BBi(8) steps value confirmed</a>. %H A384629 S. Ligocki, <a href="https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html">BB(3,3) is Hard (Bigfoot)</a>. %H A384629 Pascal Michel, <a href="https://bbchallenge.org/~pascal.michel/bbc">The Busy Beaver Competitions</a>. %e A384629 a(0)=0. No instructions means machine instantly halts. (Philosophical question: Can something that was never moving actually "halt"?) %e A384629 a(1)=1. A0:0RB - One of two 1-instruction machines taking 1 step. %e A384629 a(2)=3. A0:0RB, B0:1LA %e A384629 a(3)=5. A0:0RB, B0:1LA, B1:1RB - One of 14 3-instruction machines taking 5 steps. %e A384629 a(4)=16. A0:1RB, B0:0RC, C0:1LC, C1:0LA %e A384629 a(5)=37. A0:1RB, A1:2LB, B0:2LA, B1:2RB, B2:1LB - BB(2,3) minus the halt instruction for A2. %e A384629 a(6)=123. A0:1RB, A1:3LA, A2:1RA, A3:0LA, B0:2LA, B3:3RA %e A384629 a(7)=3932963. A0:1RB, A1:2LA, A2:1RA, A3:1RA, B0:1LB, B1:1LA, B2:3RB - BB(2,4) minus the halt instruction for B3, and A0:1RB, A1:2LA, A2:1RA, B0:1LC, B1:1LA, B2:2RB, C1:1LA - A 3-state, 3-symbol Turing machine with two empty instructions. %e A384629 a(8)>=6.889 x 10^1565. Must be at least the number of steps taken by the following 3-state, 4-symbol machine discovered by Nick Drozd: A0:1RB, A1:1LA, B0:1RC, B1:3LB, B2:1RB, C0:2LA, C1:2LC, C3:0LC. a(8) will not easily be proven because a 3-state, 3-symbol machine "Bigfoot", having 8 non-halting instructions, must first be proven never to halt, requiring solving a Collatz-like problem. %Y A384629 Cf. A060843, A384766. %K A384629 hard,more,nonn %O A384629 0,3 %A A384629 _Brian Galebach_, Jun 05 2025 %E A384629 a(6) added by _Brian Galebach_, Jul 15 2025 %E A384629 a(7) added by _Brian Galebach_, Aug 05 2025