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 A384766 #4 Jun 15 2025 22:31:33 %S A384766 0,1,2,4,5,9 %N A384766 Maximum number of non-blank symbols that an n-instruction Turing machine (allowing any number of states and symbols) can leave on an initially blank tape before eventually halting. %C A384766 This sequence is uncomputable. %C A384766 No halt state is required. The machine halts whenever the current state/tape symbol combination does not have a corresponding instruction. For example, if the machine is in state B at a tape symbol 1, but there is no instruction for B1, the machine halts. As a specific example, the 2-instruction machine defined by A0:0RB, B0:1LA halts after 3 steps when the machine enters state B at a tape symbol 1. A halt state can be effectively simulated by transitioning to a state not included in the machine's instructions. As another 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". So the machine becomes a 3-state 2-symbol machine, but with no instructions for the third state "C". %C A384766 This sequence effectively combines the various Busy Beaver Sigma functions Sigma(states,symbols) into a single sequence defined only by number of allowable instructions Sigma_i(inst). It is very interesting to observe the number of states and symbols associated with the champion machine for each number of instructions. %H A384766 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 A384766 Pascal Michel, <a href="https://bbchallenge.org/~pascal.michel/bbc">The Busy Beaver Competitions</a>. %e A384766 a(0)=0. No instructions means machine instantly halts, writing no symbols. %e A384766 a(1)=1. A0:1RB %e A384766 a(2)=2. A0:1RB, B0:1LA - One of 8 2-instruction machines writing 2 non-blank symbols. %e A384766 a(3)=4. A0:0RB, A1:1LB, B0:1LA - One of 5 3-instruction machines writing 4 non-blank symbols. %e A384766 a(4)=5. A0:1RB, A1:0LB, B0:1LA, B1:2RA - One of 41 4-instruction machines writing 5 non-blank symbols. %e A384766 a(5)=9. A0:1RB, A1:2LB, B0:2LA, B1:2RB, B2:1LB %e A384766 a(6)=14? A0:1RB, A1:3LA, A2:1RA, A3:0LA, B0:2LA, B3:3RA - No 6-instruction machine halting sooner than 50000 steps writes more than 14 non-blank symbols, but this does not prove that a(6)=14. %e A384766 a(7)>=2050. Must be at least Sigma(2,4), which has 7 non-halting instructions. %e A384766 a(8)>=374676382. Must be at least candidate Sigma(3,3), which has 8 non-halting instructions. a(8) will not easily be proven because a different 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 A384766 Cf. A028444, A384629 %K A384766 hard,more,nonn %O A384766 0,3 %A A384766 _Brian Galebach_, Jun 09 2025