A393640 Halting time for Wolfram's 1-state 3-symbol Turing machine 29 when started with n on the tape.

7, 3, 1, 17, 9, 1, 11, 5, 1, 13, 3, 1, 31, 19, 1, 21, 11, 1, 9, 3, 1, 23, 13, 1, 15, 7, 1, 7, 3, 1, 27, 15, 1, 17, 5, 1, 23, 3, 1, 49, 33, 1, 35, 21, 1, 15, 3, 1, 37, 23, 1, 25, 13, 1, 7, 3, 1, 21, 11, 1, 13, 5, 1, 17, 3, 1, 39, 25, 1, 27, 15, 1, 11, 3, 1, 29

Offset

1,1

Comments

All numbers on the tape are interpreted as ternary.

This machine has asymptotic quadratic runtime.

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.

Crossrefs

Cf. A393639.

Sequence in context: A397198 A176435 A389745 * A133722 A204155 A363232

Adjacent sequences: A393637 A393638 A393639 * A393641 A393642 A393644

Keyword

nonn

Author

Sean A. Irvine, Feb 23 2026

Status

approved