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.

0, 1, 2, 4, 5, 9

Offset: 0

Author

Brian Galebach, Jun 09 2025

Keywords

• hard
• more
• nonn

Comments

This sequence is uncomputable.

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".

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.

Examples

			a(0)=0. No instructions means machine instantly halts, writing no symbols.
a(1)=1.  A0:1RB
a(2)=2.  A0:1RB, B0:1LA - One of 8 2-instruction machines writing 2 non-blank symbols.
a(3)=4.  A0:0RB, A1:1LB, B0:1LA - One of 5 3-instruction machines writing 4 non-blank symbols.
a(4)=5.  A0:1RB, A1:0LB, B0:1LA, B1:2RA - One of 41 4-instruction machines writing 5 non-blank symbols.
a(5)=9.  A0:1RB, A1:2LB, B0:2LA, B1:2RB, B2:1LB
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.
a(7)>=2050. Must be at least Sigma(2,4), which has 7 non-halting instructions.
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.
		

Links

• S. Ligocki, BB(3,3) is Hard (Bigfoot).
• Pascal Michel, The Busy Beaver Competitions.

Crossrefs

Cf. A028444, A384629