A393210 Halting time for Wolfram's 2-state 2-symbol Turing machine 3626 when started with n on the tape.

1, 5, 1, 13, 1, 5, 1, 29, 1, 5, 1, 13, 1, 5, 1, 61, 1, 5, 1, 13, 1, 5, 1, 29, 1, 5, 1, 13, 1, 5, 1, 125, 1, 5, 1, 13, 1, 5, 1, 29, 1, 5, 1, 13, 1, 5, 1, 61, 1, 5, 1, 13, 1, 5, 1, 29, 1, 5, 1, 13, 1, 5, 1, 253, 1, 5, 1, 13, 1, 5, 1, 29, 1, 5, 1, 13, 1, 5, 1, 61

Offset

1,2

Comments

Machine 3626 computes the identity function. This machine exhibits exponential growth in halting time and should be compared with machine 3589 (linear time) and machine 3197 (constant time) which both also compute the identity function.

Links

Sean A. Irvine, Table of n, a(n) for n = 1..1000

Stephen Wolfram, P vs. NP and the Difficulty of Computation: A Ruliological Approach, 2026.

Mathematica

With[{lim = 120}, PacletSymbol["WolframInstitute/TuringMachine", "OneSidedTuringMachineFunction"][{3626, 2, 2}, {1, lim}, lim, "Steps"] ] (* Michael De Vlieger, Feb 07 2026, after 5th example in "The Basic Setup" in the Wolfram article *)

Crossrefs

Cf. A392245, A010684 (halting time for machine 3197), A037227 (halting time for machine 3589).

Sequence in context: A327797 A062264 A276738 * A094049 A286254 A322664

Adjacent sequences: A393207 A393208 A393209 * A393211 A393212 A393213

Keyword

nonn

Author

Sean A. Irvine, Feb 05 2026

Status

approved