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

9, 7, 15, 3, 13, 13, 21, 3, 9, 11, 19, 3, 19, 19, 27, 3, 9, 7, 15, 3, 17, 17, 25, 3, 9, 17, 25, 3, 25, 25, 33, 3, 9, 7, 15, 3, 13, 13, 21, 3, 9, 15, 23, 3, 23, 23, 31, 3, 9, 7, 15, 3, 23, 23, 31, 3, 9, 23, 31, 3, 31, 31, 39, 3, 9, 7, 15, 3, 13, 13, 21, 3, 9, 11, 19, 3, 19, 19, 27

Offset

1,1

Comments

See A392245 for further details.

It could make sense to start with a(0) = 3. All terms are odd since position -1 can be reached from position 0 only with an odd number of +-1 steps. (This holds obviously for any 1-dimensional movement.) - M. F. Hasler, Feb 08 2026

Links

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

Michael S. Branicky, Python programs for Wolfram's 2-state 2-symbol TMs 1285, 3333 and 261.

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

Wolfram Research, The Wolfram Atlas of Simple Programs: Machine 1285.

Formula

a(n) = 3 iff n = 0 (mod 4); a(n) <> 5 for any n; a(n) = 7 iff n = 3 (mod 16); a(n) = 9 iff n = 1 (mod 8); a(n) = 11 iff n = 10 (mod 64): a(n) = 13 iff n = 5 or 6 (mod 32); a(n) = 15 iff n = 3 (mod 16), etc. - M. F. Hasler, Feb 08 2026

Mathematica

With[{lim = 74}, PacletSymbol["WolframInstitute/TuringMachine", "OneSidedTuringMachineFunction"][{1285, 2, 2}, {1, lim}, lim, "Steps"] ] (* Michael De Vlieger, Feb 06 2026, after 5th example in "The Basic Setup" in "P vs. NP ..." *)

Prog

(Python) # see linked program
(Python)
def A393103(n, rule=1285, pos=0, state=0):
  for i in range(1, 1<<53):
    bit = (n>>pos) & 1; p = (2-state*2+bit)*3; state = (rule >> p+2) & 1
    if (rule >> p+1) & 1 != bit: n ^= 1<<pos
    if 0 > (pos := pos+(-1 if (rule>>p)&1 else 1)): return i
[A393103(n) for n in range(1, 99)] # M. F. Hasler, Feb 08 2026
(PARI) A393103(n, rule=1285, pos=0, state=0)={for(i=1, oo, my(in=bittest(n, pos), p=(!state*2+in)*3); bittest(rule, p+1)!=in && n=bitxor(n, 1<<pos); state = bittest(rule, p+2); (0 > pos += (-1)^bittest(rule, p))&& return(i))}
[A393103(n)| n<-[1..99]] \\ M. F. Hasler, Feb 08 2026

Crossrefs

Cf. A392245 (result computed by this TM for input n), A393106 (halting time for rule 261), A393146 (halting time for rule 3333).

Sequence in context: A011405 A268228 A131724 * A190995 A186830 A124050

Adjacent sequences: A393100 A393101 A393102 * A393104 A393105 A393106

Keyword

nonn

Author

Sean A. Irvine, Feb 01 2026

Status

approved