A386859 Sum of the number of steps taken by all n-state Turing machines that halt.

32, 13504, 13141792, 23076152576

Offset

1,1

Comments

max(A004147(n), A060843(n)) <= a(n) <= A004147(n)*A060843(n).

This sequence is noncomputable, because its computability would allow to solve the undecidable halting problem by letting a given n-state Turing machine run for up to a(n) steps.

Turing machines are n-state, 2-symbol, with movement in {left, right}.

Links

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

Example

a(1) = 32, because there are 32 1-state Turing machines that halt after 1 step each.
a(2) = 13504 = 1*6912 + 2*2304 + 3*384 + 4*128 + 5*16 + 6*40, the total steps from 9784 halting 2-state Turing machines, grouped by runtime.

Crossrefs

Cf. A004147, A060843.

Sequence in context: A069444 A280100 A187240 * A062315 A221254 A159384

Adjacent sequences: A386856 A386857 A386858 * A386860 A386861 A386862

Keyword

nonn,hard,more

Author

Carlos Moya Garcia, Aug 05 2025

Status

approved