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

Offset

1,1

Comments

This sequence and the Busy Beaver (A028444) problem are closely related. Turing machines and the number of steps taken by a Turing machine on an initially blank tape are defined in A028444.

This sequence is computable, while the Busy Beaver problem is noncomputable.

a(n) - 1 <= BB(n), where BB(n) = A028444(n).

a(n) - 1 <= (4n+1)^(2n), the number of n-state Turing machines with 2 symbols, by the pigeonhole principle. (4n+1)^(2n) is nearly A141475 (slightly different formalisms are used).

Links

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

Scott Aaronson, The Busy Beaver Frontier, 2020.

Scott Aaronson, The Busy Beaver Frontier (blog post)

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

Status

approved