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.

2, 7, 22, 72, 427, 8407

Offset

1,1

Comments

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.

Links

Table of n, a(n) for n=1..6.

Scott Aaronson, The Busy Beaver Frontier, 2020.

Scott Aaronson, The Busy Beaver Frontier (blog post)

The Busy Beaver Challenge Wiki, Lazy Beaver

Example

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.

Crossrefs

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

Sequence in context: A292230 A162770 A116387 * A294006 A322573 A294007

Adjacent sequences: A337802 A337803 A337804 * A337806 A337807 A337808

Keyword

nonn,more

Author

Zachary Vance, Sep 23 2020

Extensions

a(6) from bbwiki added by Tijn Caspar de Leeuw, Feb 04 2026

Status

approved