A393317 Maximum halting time for any of the 4096 Wolfram 2-state 2-symbol Turing machines across all n-bit inputs.

17, 31, 49, 71, 125, 253, 509, 1021, 2045, 4093, 8189, 16381, 32765, 65533, 131069, 262141, 524285, 1048573

Offset

1,1

Comments

Computations that do not halt are excluded.

Wolfram notes that these values are dominated by machines 378 and 1351.

We conjecture that the maximum runtime for machine #378 and #1351 is 2^(n+2)-3 = A036563(n+2) for the n-bit input 2^n-1, while for machine #1447 it is 2*(n+2)^2-1 = A056220(n+2), for the same input. M. F. Hasler, Feb 12 2026

Links

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

Robert P. P. McKone, Python program to exhaustively compute a(n).

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

Formula

a(n) = 2*(n+2)^2 - 1 = A056220(n+2) for n < 5, a(n) = 2^(n+2) - 3 = A036563(n+2) for n > 4 (conjectured). - M. F. Hasler, Feb 12 2026

Example

From M. F. Hasler, Feb 12 2026: (Start)
For n = 1, we get the maximum runtime a(1) = 17 for TM #1447 and input 1.
For n = 2, we get the maximum runtime a(2) = 31 for TM #1447 and input 3.
For n = 3, we get the maximum runtime a(3) = 49 for TM #1447 and input 7.
For n = 4, we get the maximum runtime a(4) = 71 for TM #1447 and input 15.
For n = 5, we get the maximum runtime a(5) = 125 for TM #378 and input 31.
For n = 6, we get the maximum runtime a(6) = 253 for TM #378 and input 63.
For n = 7, we get the maximum runtime a(7) = 509 for TM #378 and input 127.
For n = 8, we get the maximum runtime a(8) = 1021 for TM #378 and input 255. (End)

Crossrefs

Cf. A391977.

Cf. A393103, A393106, A393146, A393190, A393209, A393210, A393212, A393232, A393233, A393234.

Sequence in context: A160961 A260805 A267781 * A270441 A256374 A286512

Adjacent sequences: A393314 A393315 A393316 * A393318 A393319 A393320

Keyword

nonn,hard,more

Author

Sean A. Irvine, Feb 10 2026

Extensions

a(13)-a(18) from Robert P. P. McKone, Feb 12 2026

Status

approved