A028444 -id:A028444 - cp's OEIS frontend

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

Brian Galebach, Jun 09 2025

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.

			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.

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

Cf. A028444, A384629

A118874 A halting sequence: let f_n be the n-th recursive function, relative to the Godel numbering given in Cutland, then a(n) is f_n(n)+1 if the corresponding program halts on input n, 0 otherwise.

Original entry on oeis.org

1, 3, 1, 4, 2, 1, 1, 0, 1, 12, 2, 1, 1, 1, 1, 16, 0, 19, 1, 21, 3, 2, 2, 0, 1, 1, 1, 1, 1, 1, 1, 32, 1, 0, 0, 36, 2, 1, 1, 0, 2, 45, 3, 2, 2, 2, 2, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 64, 1, 67, 1, 0, 0, 0, 0, 0, 1, 76, 2, 1, 1, 1, 1, 81, 0, 84, 2, 86, 4, 3, 3, 0, 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0

Offset: 0

Sam Alexander, May 24 2006

nonn

The prototypical example of a noncomputable sequence.

			Using Cutland's Godel numbering, 80 corresponds to the URM program "Z(1) J(1,1,1) S(1)", which clearly loops forever on any input, so a(80)=0. On the other hand, 17 corresponds to the URM program "S(1) T(1,1)", which, on input 17, produces 18. So a(17)=18+1=19.

Nigel Cutland, "Computability: An introduction to recursive function theory". Cambridge University Press, 1980. p. 78.

Ramin Naimi, URM Simulator

Cf. A004147, A028444, A052200, A060843, A081419.

A119683 Maximal number of steps that an n-state Turing machine can make which was started on an initially blank tape before halting on the blank tape again.

Original entry on oeis.org

1, 4, 12, 34

Offset: 1

Christian Hercher (ch(AT)wurzel.org), Jun 08 2006

Cf. A060843, A028444.

A337805 Lazy Beaver Problem: a(n) is the smallest positive number of steps a(n) such that no n-state Turing machine halts in exactly a(n) steps on an initially blank tape.

Original entry on oeis.org

2, 7, 22, 72, 427

Offset: 1

Zachary Vance, Sep 23 2020

This sequence and the Busy Beaver (A060843) problem are closely related. Turing machines and the number of steps taken by a Turing machine on an initially blank tape are defined in A060843.
This sequence is computable, while the Busy Beaver problem is uncomputable.
a(n) - 1 <= BB(n), where BB(n) = A060843(n).
a(n) - 1 <= A107668 * 4^(2n), the number of uniquely behaving n-state Turing machines with 2 symbols, by the pigeonhole principle.

			For n = 2, there exist 2-state Turing machines which halt in exactly {1, 2, 3, 4, 5, 6} steps (and for no other number of steps) given an initially empty input tape. a(2) = 7 is defined as the lowest positive integer not present in that set of possible step lengths.

Scott Aaronson, The Busy Beaver Frontier, 2020.
Scott Aaronson, The Busy Beaver Frontier (blog post)

Known upper bounds of a(n) - 1 are A028444, A004147, and A141475.

A368006 Rayo's function: smallest natural number larger than any number uniquely defined by an n-symbol formula in First Order Set Theory.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2

Offset: 0

John Tromp, Dec 07 2023

The alphabet consists of the 7 symbols ∈, =, (, ), ~, ∧, ∃, plus infinitely many variables x_i, for i >= 0, each considered one symbol.
"x_i∈x_j" and "x_i=x_j" are atomic formulas.
If θ is a formula, then "(~θ)" is a formula (the negation of θ).
If θ and ξ are formulas, then "(θ∧ξ)" is a formula (the conjunction of θ and ξ).
If θ is a formula, then "∃x_i(θ)" is a formula (existential quantification).
A formula having x_0 as its only free variable defines a number m if it has a satisfying assignment, and all such assignments assign m to x_0.
Mexican philosophy professor Agustín Rayo defined a nondecreasing version of this function in a "big number duel" at MIT on 26 January 2007.
Its value at n=10^100 is known as Rayo's number.
This is a set theoretic analog of the busy beaver function, which it easily outgrows.

			a(30)=2, since the 30 symbol formula "(∃x_1(x_1∈x_0)∧(¬∃x_1(∃x_2((x_2∈x_1∧x_1∈x_0)))))" uniquely defines the number 1, while smaller formulae can only define the number 0, the smallest being the 10 symbol "(¬∃x_1(x_1∈x_0))".

Googology Fandom, Low-level Rayo bounds
Googology Fandom, Proof that Rayo(n) is 1 for n between 10 to 19
Wikipedia, Rayo's Number

Cf. A028444.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A118874 A halting sequence: let f_n be the n-th recursive function, relative to the Godel numbering given in Cutland, then a(n) is f_n(n)+1 if the corresponding program halts on input n, 0 otherwise.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A119683 Maximal number of steps that an n-state Turing machine can make which was started on an initially blank tape before halting on the blank tape again.

Views

Author

Keywords

Crossrefs

A337805 Lazy Beaver Problem: a(n) is the smallest positive number of steps a(n) such that no n-state Turing machine halts in exactly a(n) steps on an initially blank tape.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A368006 Rayo's function: smallest natural number larger than any number uniquely defined by an n-symbol formula in First Order Set Theory.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs