Theory Multitape_Alphabet_Reduction.AlphabetReduction_Reverse

theory AlphabetReduction_Reverse
  imports AlphabetReduction_Theorems
begin

section ‹Alphabet reduction: reverse language inclusion›

text ‹The reverse leg of ‹alphabet_reduce_language›:
  ‹encode_input_ar (Γ_ktm M) (bl_ktm M) w ∈ Lang_ktm (alphabet_reduce M)
   ⟹ w ∈ Lang_ktm M›, the converse of the proven
  ‹alphabet_reduce_language_forward›.

  This holds for deterministic and nondeterministic ‹M› alike, and
  the proof is direct, with no argument about the uniqueness of
  validation chains as in AE's reverse direction, because AR's only
  nondeterministic substep, ‹ar_delta_compute›, is a direct
  single-step embedding of ‹delta_ktm M› (one substrate tuple per
  ‹M›-tuple, no AE-style ‹m_steps_buffered› slack), so every
  accepting ‹M'›-path decodes branch-by-branch to a genuine
  accepting ‹M›-path.

  The proof inverts the simulation directly: a per-cycle
  backward step lemma reads the ‹M›-transition straight off the
  compute tuple on the given ‹M'›-path and reuses the forward
  direction's invariants ‹ar_simulates›, ‹ar_posk_consistent›,
  ‹ar_at_read_boundary› read backward; a backward chunked engine
  aggregates the per-cycle steps into an ‹M›-run.
  Throughout, ‹b› abbreviates ‹block_width Γ› (the per-symbol cell width).›

subsection ‹Terminal accept configuration›

text ‹Base case of the backward engine: the accept state
  ‹t_ktm (alphabet_reduce M)› is terminal.  A valid machine never
  steps from its accept state (substrate ‹ktm_step_src_neq_t›),
  and ‹alphabet_reduce M› is valid by ‹alphabet_reduce_wf›;
  its accept state is ‹(t_ktm M, ar_accept_stage (bl_ktm M))› by
  ‹alphabet_reduce_accept›.

  Not used below: the reverse induction needs only the reject case,
  ‹ar_reject_terminal›, to rule out a rejecting configuration in the
  middle of a path; this lemma is its accepting counterpart.›

lemma ar_accept_terminal:
  fixes M :: "('q, 'a) ktm"
    and c c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes vM:      "valid_ktm M"
      and card_ge: "card (Γ_ktm M) ≥ 4"
      and step:    "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
  shows "ktc_state c ≠ (t_ktm M, ar_accept_stage (bl_ktm M))"
proof -
  let ?M' = "alphabet_reduce M :: ('q × 'a ar_stage, sym4) ktm"
  have valM': "valid_ktm ?M'" by (rule alphabet_reduce_wf[OF vM card_ge])
  have step': "(c, c') ∈ ktm_step (delta_ktm ?M')" using step by simp
  have "ktc_state c ≠ t_ktm ?M'" by (rule ktm_step_src_neq_t[OF valM' step'])
  thus ?thesis by simp
qed

text ‹Reject companion of ‹ar_accept_terminal›: the reject state
  ‹r_ktm (alphabet_reduce M) = (r_ktm M, ar_reject_stage (bl_ktm M))›
  (by ‹alphabet_reduce_reject›) is terminal too (substrate
  ‹ktm_step_src_neq_r›).  The backward engine uses it to kill a
  reject boundary reached mid-trace: the trace runs to the accept
  config, so a reject config can carry no outgoing step.›

lemma ar_reject_terminal:
  fixes M :: "('q, 'a) ktm"
    and c c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes vM:      "valid_ktm M"
      and card_ge: "card (Γ_ktm M) ≥ 4"
      and step:    "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
  shows "ktc_state c ≠ (r_ktm M, ar_reject_stage (bl_ktm M))"
proof -
  let ?M' = "alphabet_reduce M :: ('q × 'a ar_stage, sym4) ktm"
  have valM': "valid_ktm ?M'" by (rule alphabet_reduce_wf[OF vM card_ge])
  have step': "(c, c') ∈ ktm_step (delta_ktm ?M')" using step by simp
  have "ktc_state c ≠ r_ktm ?M'" by (rule ktm_step_src_neq_r[OF valM' step'])
  thus ?thesis by simp
qed

subsection ‹Source substep-tags partition the substep relations›

text ‹Each of the five substep relations carries a uniform source
  substep-tag (‹fst (snd s)› for a source state ‹s = (q, stg)›),
  and the five tags are pairwise distinct datatype constructors.  This
  is the structural fact every step-inversion lemma rests on: a step
  whose source is at substep ‹X› can only come from the relation
  whose sources carry tag ‹X›.›

lemma ar_delta_read_src:
  "(s, a, s', a', d) ∈ ar_delta_read M ⟹ fst (snd s) = AR_SimRead"
  by (auto simp: ar_delta_read_def)

lemma ar_delta_compute_src:
  "(s, a, s', a', d) ∈ ar_delta_compute M ⟹ fst (snd s) = AR_SimCompute"
  by (auto simp: ar_delta_compute_def)

lemma ar_delta_write_src:
  "(s, a, s', a', d) ∈ ar_delta_write M ⟹ fst (snd s) = AR_SimWrite"
  by (auto simp: ar_delta_write_def)

lemma ar_delta_advance_src:
  "(s, a, s', a', d) ∈ ar_delta_advance M ⟹ fst (snd s) = AR_SimAdvance"
  by (auto simp: ar_delta_advance_def)

lemma ar_delta_next_src:
  "(s, a, s', a', d) ∈ ar_delta_next M ⟹ fst (snd s) = AR_SimNext"
  by (auto simp: ar_delta_next_def)

subsection ‹Where each substep can lead›

text ‹Each substep relation's destination tag is confined to a
  small set: read loops to itself or transitions to compute; compute
  is the unique non-deterministic step and lands at write; write
  loops or advances; advance loops or hands off to next; next closes
  the cycle (back to read) or dispatches to a halt-coerced
  configuration.  These five facts encode the substep transition
  graph, and the reverse direction's arguments about the shape of a
  path rest on them.›

lemma ar_delta_read_dest:
  "(s, a, s', a', d) ∈ ar_delta_read M ⟹
     fst (snd s') = AR_SimRead ∨ fst (snd s') = AR_SimCompute"
  by (auto simp: ar_delta_read_def)

lemma ar_delta_compute_dest:
  "(s, a, s', a', d) ∈ ar_delta_compute M ⟹ fst (snd s') = AR_SimWrite"
  by (auto simp: ar_delta_compute_def)

lemma ar_delta_write_dest:
  "(s, a, s', a', d) ∈ ar_delta_write M ⟹
     fst (snd s') = AR_SimWrite ∨ fst (snd s') = AR_SimAdvance"
  by (auto simp: ar_delta_write_def)

lemma ar_delta_advance_dest:
  "(s, a, s', a', d) ∈ ar_delta_advance M ⟹
     fst (snd s') = AR_SimAdvance ∨ fst (snd s') = AR_SimNext"
  by (auto simp: ar_delta_advance_def)

lemma ar_delta_next_dest:
  "(s, a, s', a', d) ∈ ar_delta_next M ⟹
     fst (snd s') = AR_SimRead ∨ fst (snd s') = AR_HaltAccept
        ∨ fst (snd s') = AR_HaltReject"
  by (auto simp: ar_delta_next_def ar_accept_stage_def ar_reject_stage_def)

text ‹Union-disambiguation: a tuple in ‹alphabet_reduce_delta M›
  whose source is at ‹AR_SimCompute› must lie in the compute
  relation ‹ar_delta_compute M›.  The intersection filters of
  ‹alphabet_reduce_delta› (‹δLE› and the valid-stage
  guards) only shrink the union, so membership of the union is all we
  need; the other four source-tag lemmas rule out the other disjuncts
  by constructor-distinctness.›

lemma ar_delta_compute_from_src:
  assumes mem: "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
      and src: "fst (snd s) = AR_SimCompute"
  shows "(s, a, s', a', d) ∈ ar_delta_compute M"
proof -
  from mem
  have u: "(s, a, s', a', d) ∈ ar_delta_read M ∪ ar_delta_compute M
              ∪ ar_delta_write M ∪ ar_delta_advance M ∪ ar_delta_next M"
    unfolding alphabet_reduce_delta_def by blast
  have nr: "(s, a, s', a', d) ∉ ar_delta_read M"
  proof
    assume "(s, a, s', a', d) ∈ ar_delta_read M"
    from ar_delta_read_src[OF this] src show False by simp
  qed
  have nw: "(s, a, s', a', d) ∉ ar_delta_write M"
  proof
    assume "(s, a, s', a', d) ∈ ar_delta_write M"
    from ar_delta_write_src[OF this] src show False by simp
  qed
  have nad: "(s, a, s', a', d) ∉ ar_delta_advance M"
  proof
    assume "(s, a, s', a', d) ∈ ar_delta_advance M"
    from ar_delta_advance_src[OF this] src show False by simp
  qed
  have nx: "(s, a, s', a', d) ∉ ar_delta_next M"
  proof
    assume "(s, a, s', a', d) ∈ ar_delta_next M"
    from ar_delta_next_src[OF this] src show False by simp
  qed
  from u nr nw nad nx show ?thesis by blast
qed

subsection ‹Compute-step inversion›

text ‹The central lemma of the reverse direction: a single ‹M'›-step out of
  an ‹AR_SimCompute› configuration reads the simulated
  ‹M›-transition straight off the compute tuple.  Because
  ‹ar_delta_compute› is a direct single-step embedding of
  ‹delta_ktm M›, the inversion yields a genuine
  ‹(q, buf, q', m_a', m_d) ∈ delta_ktm M› with no chain-uniqueness
  or determinism assumption — this is where AR's ND-generality is
  earned.  Compute neither writes nor moves: the tape and head
  positions are unchanged (read symbol equals write symbol, direction
  ‹N›).›

lemma ar_compute_step_inv_sub:
  fixes M :: "('q, 'a) ktm"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes step: "(c', c'') ∈ ktm_step (ar_delta_compute M)"
      and stg:  "ktc_state c' = (q, AR_SimCompute, tk, i, buf, dvec, posk)"
  obtains q' m_a' m_d where
      "(q, buf, q', m_a', m_d) ∈ delta_ktm M"
    and "ktc_state c'' = (q', AR_SimWrite, 0, 0, m_a', m_d, posk)"
    and "ktc_tape c'' = ktc_tape c'"
    and "ktc_pos c'' = ktc_pos c'"
proof -
  from step obtain S ts n S'' aw move where
      c'_eq:   "c' = KConfig S ts n"
    and c''_eq: "c'' = KConfig S'' (λk. (ts k)(n k := aw k))
                        (λk. go_move (move k) (n k))"
    and rel:   "(S, (λk. ts k (n k)), S'', aw, move)
                   ∈ ar_delta_compute M"
    by (auto elim: ktm_step.cases)
  have S_eq: "S = (q, AR_SimCompute, tk, i, buf, dvec, posk)"
    using stg c'_eq by simp
  have crel: "((q, AR_SimCompute, tk, i, buf, dvec, posk),
                 (λk. ts k (n k)), S'', aw, move) ∈ ar_delta_compute M"
    using rel S_eq by simp
  from crel obtain q' m_a' m_d where
      mdelta:  "(q, buf, q', m_a', m_d) ∈ delta_ktm M"
    and S''_eq: "S'' = (q', AR_SimWrite, 0, 0, m_a', m_d, posk)"
    and aw_eq: "aw = (λk. ts k (n k))"
    and dir_eq: "move = (λ_. MoveN)"
    unfolding ar_delta_compute_def by auto
  have state: "ktc_state c'' = (q', AR_SimWrite, 0, 0, m_a', m_d, posk)"
    using c''_eq S''_eq by simp
  have tape: "ktc_tape c'' = ktc_tape c'"
  proof -
    have "ktc_tape c'' = (λk. (ts k)(n k := aw k))" using c''_eq by simp
    also have "… = ts" by (simp add: aw_eq fun_upd_triv)
    finally show ?thesis using c'_eq by simp
  qed
  have pos: "ktc_pos c'' = ktc_pos c'"
  proof -
    have "ktc_pos c'' = (λk. go_move (move k) (n k))" using c''_eq by simp
    also have "… = n" by (simp add: dir_eq)
    finally show ?thesis using c'_eq by simp
  qed
  show ?thesis by (rule that[OF mdelta state tape pos])
qed

text ‹The union-step face of the inversion: lift the union step into
  the compute sub-relation (‹ar_step_compute_lift›) and invert there.
  Used by the preservation lemma ‹ar_walker_step_from_at_compute›
  below; the lemma that closes a cycle inverts the compute step of the
  sub-relation directly, via ‹ar_compute_step_inv_sub›.›

lemma ar_compute_step_inv:
  fixes M :: "('q, 'a) ktm"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
      and stg:  "ktc_state c' = (q, AR_SimCompute, tk, i, buf, dvec, posk)"
  obtains q' m_a' m_d where
      "(q, buf, q', m_a', m_d) ∈ delta_ktm M"
    and "ktc_state c'' = (q', AR_SimWrite, 0, 0, m_a', m_d, posk)"
    and "ktc_tape c'' = ktc_tape c'"
    and "ktc_pos c'' = ktc_pos c'"
proof -
  from step obtain S ts n S'' aw move where
      c'_eq:   "c' = KConfig S ts n"
    and c''_eq: "c'' = KConfig S'' (λk. (ts k)(n k := aw k))
                        (λk. go_move (move k) (n k))"
    and rel:   "(S, (λk. ts k (n k)), S'', aw, move)
                   ∈ alphabet_reduce_delta M"
    by (auto elim: ktm_step.cases)
  have src: "fst (snd S) = AR_SimCompute" using stg c'_eq by simp
  have crel: "(S, (λk. ts k (n k)), S'', aw, move) ∈ ar_delta_compute M"
    by (rule ar_delta_compute_from_src[OF rel src])
  have step_explicit:
      "(KConfig S ts n, KConfig S'' (λk. (ts k)(n k := aw k))
          (λk. go_move (move k) (n k))) ∈ ktm_step (ar_delta_compute M)"
    using crel by (rule ktm_step.step)
  have sub: "(c', c'') ∈ ktm_step (ar_delta_compute M)"
    using step_explicit c'_eq c''_eq by simp
  show thesis
  proof (rule ar_compute_step_inv_sub[OF sub stg])
    fix q' m_a' m_d
    assume "(q, buf, q', m_a', m_d) ∈ delta_ktm M"
       and "ktc_state c'' = (q', AR_SimWrite, 0, 0, m_a', m_d, posk)"
       and "ktc_tape c'' = ktc_tape c'"
       and "ktc_pos c'' = ktc_pos c'"
    thus thesis by (rule that)
  qed
qed

subsection ‹Inverting the closing substep: next cycle or halt›

text ‹Source disambiguation for ‹AR_SimNext›, mirroring
  ‹ar_delta_compute_from_src›.›

lemma ar_delta_next_from_src:
  assumes mem: "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
      and src: "fst (snd s) = AR_SimNext"
  shows "(s, a, s', a', d) ∈ ar_delta_next M"
proof -
  from mem
  have u: "(s, a, s', a', d) ∈ ar_delta_read M ∪ ar_delta_compute M
              ∪ ar_delta_write M ∪ ar_delta_advance M ∪ ar_delta_next M"
    unfolding alphabet_reduce_delta_def by blast
  have nr: "(s, a, s', a', d) ∉ ar_delta_read M"
  proof
    assume "(s, a, s', a', d) ∈ ar_delta_read M"
    from ar_delta_read_src[OF this] src show False by simp
  qed
  have nc: "(s, a, s', a', d) ∉ ar_delta_compute M"
  proof
    assume "(s, a, s', a', d) ∈ ar_delta_compute M"
    from ar_delta_compute_src[OF this] src show False by simp
  qed
  have nw: "(s, a, s', a', d) ∉ ar_delta_write M"
  proof
    assume "(s, a, s', a', d) ∈ ar_delta_write M"
    from ar_delta_write_src[OF this] src show False by simp
  qed
  have nad: "(s, a, s', a', d) ∉ ar_delta_advance M"
  proof
    assume "(s, a, s', a', d) ∈ ar_delta_advance M"
    from ar_delta_advance_src[OF this] src show False by simp
  qed
  from u nr nc nw nad show ?thesis by blast
qed

text ‹A single ‹M'›-step out of an ‹AR_SimNext›
  configuration neither writes nor moves, and dispatches on the
  simulated ‹M›-state ‹q›: continue to the next
  ‹AR_SimRead› boundary when ‹q› is non-halting, or land
  in the accept/reject halt stage when ‹q› is ‹M›'s
  accept/reject state.  The accept landing is exactly
  ‹t_ktm (alphabet_reduce M)›.›

lemma ar_next_step_inv:
  fixes M :: "('q, 'a) ktm"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
      and stg:  "ktc_state c' = (q, AR_SimNext, tk, i, buf, dvec, posk)"
  shows "ktc_tape c'' = ktc_tape c' ∧ ktc_pos c'' = ktc_pos c'
         ∧ ((q ∉ {t_ktm M, r_ktm M}
               ∧ ktc_state c'' = (q, AR_SimRead, 0, 0, buf, dvec, posk))
            ∨ (q = t_ktm M
               ∧ ktc_state c'' = (t_ktm M, ar_accept_stage (bl_ktm M)))
            ∨ (q = r_ktm M
               ∧ ktc_state c'' = (r_ktm M, ar_reject_stage (bl_ktm M))))"
proof -
  from step obtain S ts n S'' aw move where
      c'_eq:   "c' = KConfig S ts n"
    and c''_eq: "c'' = KConfig S'' (λk. (ts k)(n k := aw k))
                        (λk. go_move (move k) (n k))"
    and rel:   "(S, (λk. ts k (n k)), S'', aw, move)
                   ∈ alphabet_reduce_delta M"
    by (auto elim: ktm_step.cases)
  have S_eq: "S = (q, AR_SimNext, tk, i, buf, dvec, posk)"
    using stg c'_eq by simp
  have src: "fst (snd S) = AR_SimNext" using S_eq by simp
  have nrel: "((q, AR_SimNext, tk, i, buf, dvec, posk),
                 (λk. ts k (n k)), S'', aw, move) ∈ ar_delta_next M"
    using ar_delta_next_from_src[OF rel src] S_eq by simp
  have core: "aw = (λk. ts k (n k)) ∧ move = (λ_. MoveN)
       ∧ ((q ∉ {t_ktm M, r_ktm M}
              ∧ S'' = (q, AR_SimRead, 0, 0, buf, dvec, posk))
          ∨ (q = t_ktm M ∧ S'' = (t_ktm M, ar_accept_stage (bl_ktm M)))
          ∨ (q = r_ktm M ∧ S'' = (r_ktm M, ar_reject_stage (bl_ktm M))))"
    using nrel
    unfolding ar_delta_next_def ar_accept_stage_def ar_reject_stage_def
    by auto
  have tape: "ktc_tape c'' = ktc_tape c'"
  proof -
    have "ktc_tape c'' = (λk. (ts k)(n k := aw k))" using c''_eq by simp
    also have "… = ts" using core by (simp add: fun_upd_triv)
    finally show ?thesis using c'_eq by simp
  qed
  have pos: "ktc_pos c'' = ktc_pos c'"
  proof -
    have "ktc_pos c'' = (λk. go_move (move k) (n k))" using c''_eq by simp
    also have "… = n" using core by simp
    finally show ?thesis using c'_eq by simp
  qed
  have st: "ktc_state c'' = S''" using c''_eq by simp
  show ?thesis using tape pos core st by simp
qed

subsection ‹Source disambiguation for the remaining substeps›

text ‹Source disambiguation for the remaining three substeps,
  completing the ‹from_src› family alongside
  ‹ar_delta_compute_from_src› / ‹ar_delta_next_from_src›.›

lemma ar_delta_read_from_src:
  assumes "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
      and "fst (snd s) = AR_SimRead"
  shows "(s, a, s', a', d) ∈ ar_delta_read M"
  using assms unfolding alphabet_reduce_delta_def
  by (auto dest: ar_delta_compute_src ar_delta_write_src
                 ar_delta_advance_src ar_delta_next_src)

lemma ar_delta_write_from_src:
  assumes "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
      and "fst (snd s) = AR_SimWrite"
  shows "(s, a, s', a', d) ∈ ar_delta_write M"
  using assms unfolding alphabet_reduce_delta_def
  by (auto dest: ar_delta_read_src ar_delta_compute_src
                 ar_delta_advance_src ar_delta_next_src)

lemma ar_delta_advance_from_src:
  assumes "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
      and "fst (snd s) = AR_SimAdvance"
  shows "(s, a, s', a', d) ∈ ar_delta_advance M"
  using assms unfolding alphabet_reduce_delta_def
  by (auto dest: ar_delta_read_src ar_delta_compute_src
                 ar_delta_write_src ar_delta_next_src)

text ‹Every ‹alphabet_reduce_delta› tuple has its source at one
  of the five substep tags (the halt tags never appear as sources).›

lemma alphabet_reduce_delta_src_tag:
  assumes "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
  shows "fst (snd s) ∈ {AR_SimRead, AR_SimCompute, AR_SimWrite,
                          AR_SimAdvance, AR_SimNext}"
  using assms unfolding alphabet_reduce_delta_def
  by (auto dest: ar_delta_read_src ar_delta_compute_src ar_delta_write_src
                 ar_delta_advance_src ar_delta_next_src)

subsection ‹Where a step of each substep lands›

text ‹Lift the per-relation destination-tag lemmas
  (‹ar_delta_X_dest›) up through ‹ktm_step›: an
  ‹M'›-step out of a configuration whose source idx is
  ‹AR_SimX› lands at a configuration whose idx is in
  ‹X›'s dest set.  The five lemmas compose the substrate's
  ‹ktm_step_states› (the firing tuple's two states), the
  ‹from_src› union-disambiguation helpers, and
  ‹ar_delta_X_dest›.  Together they encode the cycle's
  substep transition graph at the level of whole ‹M'›-steps, which is
  what the induction along the path below uses: SimRead-loop-or-compute, compute-to-write,
  write-loop-or-advance, advance-loop-or-next,
  next-to-read-or-halt.›

lemma ar_step_from_SimRead_lands:
  assumes step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
      and src:  "fst (snd (ktc_state c)) = AR_SimRead"
  shows "fst (snd (ktc_state c')) = AR_SimRead
       ∨ fst (snd (ktc_state c')) = AR_SimCompute"
proof -
  from step obtain a a' d
    where "(ktc_state c, a, ktc_state c', a', d) ∈ alphabet_reduce_delta M"
    by (rule ktm_step_states)
  from ar_delta_read_from_src [OF this src] show ?thesis
    by (rule ar_delta_read_dest)
qed

text ‹The ‹compute› member of the five lemmas above is not used: the
  compute substep is the nondeterministic branch point, and the proof
  handles it by reading the ‹M›-transition off the step instead.  It is
  stated so that the substep transition graph is complete.›

lemma ar_step_from_SimCompute_lands:
  assumes step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
      and src:  "fst (snd (ktc_state c)) = AR_SimCompute"
  shows "fst (snd (ktc_state c')) = AR_SimWrite"
proof -
  from step obtain a a' d
    where "(ktc_state c, a, ktc_state c', a', d) ∈ alphabet_reduce_delta M"
    by (rule ktm_step_states)
  from ar_delta_compute_from_src [OF this src] show ?thesis
    by (rule ar_delta_compute_dest)
qed

lemma ar_step_from_SimWrite_lands:
  assumes step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
      and src:  "fst (snd (ktc_state c)) = AR_SimWrite"
  shows "fst (snd (ktc_state c')) = AR_SimWrite
       ∨ fst (snd (ktc_state c')) = AR_SimAdvance"
proof -
  from step obtain a a' d
    where "(ktc_state c, a, ktc_state c', a', d) ∈ alphabet_reduce_delta M"
    by (rule ktm_step_states)
  from ar_delta_write_from_src [OF this src] show ?thesis
    by (rule ar_delta_write_dest)
qed

lemma ar_step_from_SimAdvance_lands:
  assumes step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
      and src:  "fst (snd (ktc_state c)) = AR_SimAdvance"
  shows "fst (snd (ktc_state c')) = AR_SimAdvance
       ∨ fst (snd (ktc_state c')) = AR_SimNext"
proof -
  from step obtain a a' d
    where "(ktc_state c, a, ktc_state c', a', d) ∈ alphabet_reduce_delta M"
    by (rule ktm_step_states)
  from ar_delta_advance_from_src [OF this src] show ?thesis
    by (rule ar_delta_advance_dest)
qed

lemma ar_step_from_SimNext_lands:
  assumes step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
      and src:  "fst (snd (ktc_state c)) = AR_SimNext"
  shows "fst (snd (ktc_state c')) = AR_SimRead
       ∨ fst (snd (ktc_state c')) = AR_HaltAccept
       ∨ fst (snd (ktc_state c')) = AR_HaltReject"
proof -
  from step obtain a a' d
    where "(ktc_state c, a, ktc_state c', a', d) ∈ alphabet_reduce_delta M"
    by (rule ktm_step_states)
  from ar_delta_next_from_src [OF this src] show ?thesis
    by (rule ar_delta_next_dest)
qed

subsection ‹Invariants for each substep of the cycle›

text ‹The reverse direction walks along the ‹M'›-path one step at a time
  (hence the ∗‹walker› in the names below): an induction over the path
  that tracks where in the cycle we are by reading
  the substep idx off each visited configuration's state.  Six stage
  predicates carry the per-substep relationship between the cycle's
  source ‹M›-config ‹cM› and the current
  ‹M'›-configuration ‹c'›:

  ▪ ‹ar_walker_at_boundary M cM c'›: fresh cycle start —
    ‹c'› at ‹AR_SimRead› boundary, the three
    forward invariants hold for ‹cM›.
  ▪ ‹ar_walker_in_read M cM c'›: mid-read-phase —
    reachable from a boundary by ‹ar_delta_read›-only
    steps, still at ‹AR_SimRead›.
  ▪ ‹ar_walker_at_compute M cM c'›: read complete —
    reachable from a boundary by ‹ar_delta_read›-only
    steps, now at ‹AR_SimCompute›.  The next M'-step on
    the path extracts the M-tuple via
    ‹ar_compute_step_inv›.
  ▪ ‹ar_walker_in_write M cM c'›: M-tuple
    extracted, mid-write-phase — at ‹AR_SimWrite›.
  ▪ ‹ar_walker_in_advance M cM c'›: write done,
    mid-advance-phase — at ‹AR_SimAdvance›.
  ▪ ‹ar_walker_at_next M cM c'›: at
    ‹AR_SimNext›, about to dispatch to next boundary or
    halt via ‹ar_next_step_inv›.

  The witness-chain formulation (rather than concrete per-state
  conditions) makes preservation lemmas mechanical: at a config with
  substep tag T, an M'-step fires the unique substep relation with
  src tag T (by ‹ar_delta_T_src› + ‹from_src›);
  extending the witness chain by one step preserves the invariant.
  Chain shape (no cycle-wrap before completing this cycle) follows
  from the witness chain living in the ∗‹specific› substep relation
  ‹ktm_step (ar_delta_T M)›, which by
  ‹ar_delta_T_src› can only fire from sources at T —
  ruling out the wrap.›

definition ar_walker_at_boundary ::
  "('q, 'a) ktm
    ⇒ ('a, 'q) ktc_config
    ⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
  "ar_walker_at_boundary M cM c' ⟷
     ar_simulates M cM c'
   ∧ ar_posk_consistent M cM c'
   ∧ ar_at_read_boundary M c'"

definition ar_walker_in_read ::
  "('q, 'a) ktm
    ⇒ ('a, 'q) ktc_config
    ⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
  "ar_walker_in_read M cM c' ⟷
     fst (snd (ktc_state c')) = AR_SimRead
   ∧ (∃c_b m. ar_walker_at_boundary M cM c_b
                ∧ (c_b, c') ∈ (ktm_step (ar_delta_read M)) ^^ m)"

definition ar_walker_at_compute ::
  "('q, 'a) ktm
    ⇒ ('a, 'q) ktc_config
    ⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
  "ar_walker_at_compute M cM c' ⟷
     fst (snd (ktc_state c')) = AR_SimCompute
   ∧ (∃c_b m. ar_walker_at_boundary M cM c_b
                ∧ (c_b, c') ∈ (ktm_step (ar_delta_read M)) ^^ m)"

definition ar_walker_in_write ::
  "('q, 'a) ktm
    ⇒ ('a, 'q) ktc_config
    ⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
  "ar_walker_in_write M cM c' ⟷
     fst (snd (ktc_state c')) = AR_SimWrite
   ∧ (∃c_b c_w m_r m_w.
        ar_walker_at_boundary M cM c_b
        ∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
        ∧ fst (snd (ktc_state c_w)) = AR_SimCompute
        ∧ (∃c_w_post. (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
                       ∧ (c_w_post, c') ∈ (ktm_step (ar_delta_write M)) ^^ m_w))"

definition ar_walker_in_advance ::
  "('q, 'a) ktm
    ⇒ ('a, 'q) ktc_config
    ⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
  "ar_walker_in_advance M cM c' ⟷
     fst (snd (ktc_state c')) = AR_SimAdvance
   ∧ (∃c_b c_w c_a m_r m_w m_a.
        ar_walker_at_boundary M cM c_b
        ∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
        ∧ fst (snd (ktc_state c_w)) = AR_SimCompute
        ∧ fst (snd (ktc_state c_a)) = AR_SimAdvance
        ∧ (∃c_w_post. (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
                       ∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
                       ∧ (c_a, c') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a))"

definition ar_walker_at_next ::
  "('q, 'a) ktm
    ⇒ ('a, 'q) ktc_config
    ⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
  "ar_walker_at_next M cM c' ⟷
     fst (snd (ktc_state c')) = AR_SimNext
   ∧ (∃c_b c_w c_a c_n m_r m_w m_a.
        ar_walker_at_boundary M cM c_b
        ∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
        ∧ fst (snd (ktc_state c_w)) = AR_SimCompute
        ∧ fst (snd (ktc_state c_a)) = AR_SimAdvance
        ∧ (∃c_w_post. (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
                       ∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
                       ∧ (c_a, c_n) ∈ (ktm_step (ar_delta_advance M)) ^^ m_a
                       ∧ c_n = c'))"

subsection ‹A step from a given substep is a step of that substep's relation›

text ‹Four ‹ktm_step›-to-specific-substep lifts: an
  ‹M'›-step in ‹ktm_step (alphabet_reduce_delta M)›
  whose source carries substep tag T is in fact in the smaller
  ‹ktm_step (ar_delta_T M)›.  Each is the substrate's
  ‹ktm_step_restrict_src› applied to the matching
  ‹ar_delta_T_from_src› helper, which narrows the firing tuple by
  src-tag uniqueness.  The preservation lemmas below chain these lifts
  with the destination lemmas (‹ar_step_from_SimX_lands›) to extend
  the witness chain by one step.›

lemma ar_step_read_lift:
  fixes M :: "('q, 'a) ktm"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes src:  "fst (snd (ktc_state c')) = AR_SimRead"
      and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
  shows "(c', c'') ∈ ktm_step (ar_delta_read M)"
  by (rule ktm_step_restrict_src [OF step])
     (erule ar_delta_read_from_src, assumption, rule src)

lemma ar_step_compute_lift:
  fixes M :: "('q, 'a) ktm"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes src:  "fst (snd (ktc_state c')) = AR_SimCompute"
      and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
  shows "(c', c'') ∈ ktm_step (ar_delta_compute M)"
  by (rule ktm_step_restrict_src [OF step])
     (erule ar_delta_compute_from_src, assumption, rule src)

lemma ar_step_write_lift:
  fixes M :: "('q, 'a) ktm"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes src:  "fst (snd (ktc_state c')) = AR_SimWrite"
      and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
  shows "(c', c'') ∈ ktm_step (ar_delta_write M)"
  by (rule ktm_step_restrict_src [OF step])
     (erule ar_delta_write_from_src, assumption, rule src)

lemma ar_step_advance_lift:
  fixes M :: "('q, 'a) ktm"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes src:  "fst (snd (ktc_state c')) = AR_SimAdvance"
      and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
  shows "(c', c'') ∈ ktm_step (ar_delta_advance M)"
  by (rule ktm_step_restrict_src [OF step])
     (erule ar_delta_advance_from_src, assumption, rule src)

subsection ‹Runs of the read substep are determined›

text ‹Two structural facts about chains in the read sub-relation:
  the sub-relation is ∗‹functional› (‹ar_delta_read_functional›,
  lifted to steps by the substrate's ‹ktm_step_det_at›); and it
  cannot fire from a source whose substep tag is ‹AR_SimCompute›
  (by ‹ar_delta_read_src›).  The substrate's
  ‹relpow_halted_same_run› turns the two into the pinning: a chain
  ending at ‹AR_SimCompute› is unique in both its length and its
  endpoint, so if two chains in the sub-relation start at the same seed and both
  end at an ‹AR_SimCompute›-tagged config, they coincide.  This
  is what bridges the walker's by-construction ‹R_read› witness
  chain to the existence chain produced by ‹ar_read_phase›, whose
  steps lie in ‹ar_delta_read› as well as in the full relation: the
  witness chain inherits the latter's
  stated endpoint state shape, including the load-bearing
  ‹buf = λk. ktc_tape cM k (ktc_pos cM k)›.›

lemma ar_delta_read_no_step_from_SimCompute:
  fixes M :: "('q, 'a) ktm"
    and c c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes "fst (snd (ktc_state c)) = AR_SimCompute"
  shows "(c, c') ∉ ktm_step (ar_delta_read M)"
proof
  assume h: "(c, c') ∈ ktm_step (ar_delta_read M)"
  from h obtain S ts n S' aw move where
      ceq: "c = KConfig S ts n"
    and rel: "(S, (λk. ts k (n k)), S', aw, move) ∈ ar_delta_read M"
    by (auto elim: ktm_step.cases)
  have "fst (snd S) = AR_SimRead" using ar_delta_read_src[OF rel] .
  hence "fst (snd (ktc_state c)) = AR_SimRead" using ceq by simp
  with assms show False by simp
qed

lemma chain_ar_delta_read_to_SimCompute_uniq:
  fixes M :: "('q, 'a) ktm"
    and c c1 c2 :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes h1: "(c, c1) ∈ (ktm_step (ar_delta_read M)) ^^ m"
      and h2: "(c, c2) ∈ (ktm_step (ar_delta_read M)) ^^ n"
      and c1cpu: "fst (snd (ktc_state c1)) = AR_SimCompute"
      and c2cpu: "fst (snd (ktc_state c2)) = AR_SimCompute"
  shows "m = n ∧ c1 = c2"
proof -
  have fn: "y = z"
    if "x ∈ UNIV" "(x, y) ∈ ktm_step (ar_delta_read M)"
       "(x, z) ∈ ktm_step (ar_delta_read M)" for x y z
    by (rule ktm_step_det_at [OF _ that(2,3)])
       (blast dest: ar_delta_read_functional)
  have stuck: False
    if "u ∈ {C. fst (snd (ktc_state C)) = AR_SimCompute}"
       "(u, v) ∈ ktm_step (ar_delta_read M)" for u v
    using that ar_delta_read_no_step_from_SimCompute by blast
  show ?thesis
    by (rule relpow_halted_same_run
          [where R = UNIV and H = "{C. fst (snd (ktc_state C)) = AR_SimCompute}",
           OF _ fn stuck _ h1 _ h2])
       (simp_all add: c1cpu c2cpu)
qed


text ‹Two parallel chain-pinning suites for the write and advance
  sub-relations, mirroring the read suite verbatim with
  ‹ar_delta_write› / ‹ar_delta_advance› in place of
  ‹ar_delta_read› and ‹AR_SimAdvance› / ‹AR_SimNext›
  in place of ‹AR_SimCompute›.  Functionality
  (‹ar_delta_write_functional›, ‹ar_delta_advance_functional›) and src
  uniqueness (‹ar_delta_write_src›, ‹ar_delta_advance_src›)
  feed the same scaffold.  These suites are used by the cycle-close
  bridging lemma to pin walker write/advance chains against the
  forward ‹ar_write_phase› / ‹ar_advance_phase›
  constructions.›

lemma ar_delta_write_no_step_from_SimAdvance:
  fixes M :: "('q, 'a) ktm"
    and c c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes "fst (snd (ktc_state c)) = AR_SimAdvance"
  shows "(c, c') ∉ ktm_step (ar_delta_write M)"
proof
  assume h: "(c, c') ∈ ktm_step (ar_delta_write M)"
  from h obtain S ts n S' aw move where
      ceq: "c = KConfig S ts n"
    and rel: "(S, (λk. ts k (n k)), S', aw, move) ∈ ar_delta_write M"
    by (auto elim: ktm_step.cases)
  have "fst (snd S) = AR_SimWrite" using ar_delta_write_src[OF rel] .
  hence "fst (snd (ktc_state c)) = AR_SimWrite" using ceq by simp
  with assms show False by simp
qed

lemma chain_ar_delta_write_to_SimAdvance_uniq:
  fixes M :: "('q, 'a) ktm"
    and c c1 c2 :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes h1: "(c, c1) ∈ (ktm_step (ar_delta_write M)) ^^ m"
      and h2: "(c, c2) ∈ (ktm_step (ar_delta_write M)) ^^ n"
      and c1adv: "fst (snd (ktc_state c1)) = AR_SimAdvance"
      and c2adv: "fst (snd (ktc_state c2)) = AR_SimAdvance"
  shows "m = n ∧ c1 = c2"
proof -
  have fn: "y = z"
    if "x ∈ UNIV" "(x, y) ∈ ktm_step (ar_delta_write M)"
       "(x, z) ∈ ktm_step (ar_delta_write M)" for x y z
    by (rule ktm_step_det_at [OF _ that(2,3)])
       (blast dest: ar_delta_write_functional)
  have stuck: False
    if "u ∈ {C. fst (snd (ktc_state C)) = AR_SimAdvance}"
       "(u, v) ∈ ktm_step (ar_delta_write M)" for u v
    using that ar_delta_write_no_step_from_SimAdvance by blast
  show ?thesis
    by (rule relpow_halted_same_run
          [where R = UNIV and H = "{C. fst (snd (ktc_state C)) = AR_SimAdvance}",
           OF _ fn stuck _ h1 _ h2])
       (simp_all add: c1adv c2adv)
qed

lemma ar_delta_advance_no_step_from_SimNext:
  fixes M :: "('q, 'a) ktm"
    and c c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes "fst (snd (ktc_state c)) = AR_SimNext"
  shows "(c, c') ∉ ktm_step (ar_delta_advance M)"
proof
  assume h: "(c, c') ∈ ktm_step (ar_delta_advance M)"
  from h obtain S ts n S' aw move where
      ceq: "c = KConfig S ts n"
    and rel: "(S, (λk. ts k (n k)), S', aw, move) ∈ ar_delta_advance M"
    by (auto elim: ktm_step.cases)
  have "fst (snd S) = AR_SimAdvance" using ar_delta_advance_src[OF rel] .
  hence "fst (snd (ktc_state c)) = AR_SimAdvance" using ceq by simp
  with assms show False by simp
qed

lemma chain_ar_delta_advance_to_SimNext_uniq:
  fixes M :: "('q, 'a) ktm"
    and c c1 c2 :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes h1: "(c, c1) ∈ (ktm_step (ar_delta_advance M)) ^^ m"
      and h2: "(c, c2) ∈ (ktm_step (ar_delta_advance M)) ^^ n"
      and c1nxt: "fst (snd (ktc_state c1)) = AR_SimNext"
      and c2nxt: "fst (snd (ktc_state c2)) = AR_SimNext"
  shows "m = n ∧ c1 = c2"
proof -
  have fn: "y = z"
    if "x ∈ UNIV" "(x, y) ∈ ktm_step (ar_delta_advance M)"
       "(x, z) ∈ ktm_step (ar_delta_advance M)" for x y z
    by (rule ktm_step_det_at [OF _ that(2,3)])
       (blast dest: ar_delta_advance_functional)
  have stuck: False
    if "u ∈ {C. fst (snd (ktc_state C)) = AR_SimNext}"
       "(u, v) ∈ ktm_step (ar_delta_advance M)" for u v
    using that ar_delta_advance_no_step_from_SimNext by blast
  show ?thesis
    by (rule relpow_halted_same_run
          [where R = UNIV and H = "{C. fst (snd (ktc_state C)) = AR_SimNext}",
           OF _ fn stuck _ h1 _ h2])
       (simp_all add: c1nxt c2nxt)
qed

subsection ‹Each step preserves the substep invariants›

text ‹One preservation lemma per substep predicate: an
  ‹M'›-step out of a config satisfying the current invariant
  lands at a config satisfying the next invariant in the cycle (or
  splits the disjunction when the substep's relation has multiple
  destination arms).  Together with the chunked engine, these
  describe how the walker's invariant evolves step by step: the substep
  index carried in the ‹M'›-configuration decides which case applies at
  each step, so no argument about the shape of the whole chain is
  needed.›

lemma ar_walker_step_from_boundary:
  fixes M :: "('q, 'a) ktm"
    and cM :: "('a, 'q) ktc_config"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes inv: "ar_walker_at_boundary M cM c'"
      and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
  shows "ar_walker_in_read M cM c'' ∨ ar_walker_at_compute M cM c''"
proof -
  obtain qM' stg where st: "ktc_state c' = (qM', stg)"
    by (cases "ktc_state c'") auto
  obtain idx tk i buf dvec posk where
      sg: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
  ― ‹‹ar_at_read_boundary›'s condition is a
     non-trivial implication (‹idx = AR_SimRead ⟶ …›) — but
     the only way ‹ar_walker_at_boundary› can hold with
     ‹idx ≠ AR_SimRead› would require ‹ar_simulates›'s
     halt disjunct to fire, which the ‹ar_at_read_boundary›
     hypothesis combined with stage shape rules out at the boundary
     of a non-halting cycle.  Discharged via ‹ar_simulates›'s
     state-shape branches.›
  have src: "fst (snd (ktc_state c')) = AR_SimRead"
  proof -
    have sim: "ar_simulates M cM c'"
      using inv unfolding ar_walker_at_boundary_def by simp
    have sim_body:
        "((idx = AR_SimRead ∧ qM' ∉ {t_ktm M, r_ktm M})
            ∨ (qM' = t_ktm M
                 ∧ (idx, tk, i, buf, dvec, posk) = ar_accept_stage (bl_ktm M))
            ∨ (qM' = r_ktm M
                 ∧ (idx, tk, i, buf, dvec, posk) = ar_reject_stage (bl_ktm M)))
         ∧ ktc_state cM = qM'"
      using sim unfolding ar_simulates_def by (simp add: st sg Let_def)
    consider (R) "idx = AR_SimRead"
           | (A) "qM' = t_ktm M ∧ (idx, tk, i, buf, dvec, posk) = ar_accept_stage (bl_ktm M)"
           | (J) "qM' = r_ktm M ∧ (idx, tk, i, buf, dvec, posk) = ar_reject_stage (bl_ktm M)"
      using sim_body by blast
    thus ?thesis
    proof cases
      case R thus ?thesis using st sg by simp
    next
      case A
      ― ‹halt-accept stage has ‹idx = AR_HaltAccept›,
         which together with ‹ar_at_read_boundary›'s
         ‹idx = AR_SimRead ⟶ …› is consistent only
         if we are NOT at ‹AR_SimRead›.  But the step
         out of a halt-coerced config is impossible — ‹S›
         in ‹ktm_step.cases› with ‹fst (snd S) = AR_HaltAccept›
         cannot fire any of the five substep relations
         (constructor-distinctness from
         ‹alphabet_reduce_delta_src_tag›).›
      have idx_acc: "idx = AR_HaltAccept"
        using A by (simp add: ar_accept_stage_def)
      from step obtain S ts n S' aw move where
          c'_eq: "c' = KConfig S ts n"
        and rel: "(S, (λk. ts k (n k)), S', aw, move)
                    ∈ alphabet_reduce_delta M"
        by (auto elim: ktm_step.cases)
      have src_S: "fst (snd S) = AR_HaltAccept"
        using c'_eq st sg idx_acc by simp
      from alphabet_reduce_delta_src_tag[OF rel]
      have "fst (snd S) ∈ {AR_SimRead, AR_SimCompute, AR_SimWrite,
                            AR_SimAdvance, AR_SimNext}" .
      hence False using src_S by auto
      thus ?thesis ..
    next
      case J
      have idx_rej: "idx = AR_HaltReject"
        using J by (simp add: ar_reject_stage_def)
      from step obtain S ts n S' aw move where
          c'_eq: "c' = KConfig S ts n"
        and rel: "(S, (λk. ts k (n k)), S', aw, move)
                    ∈ alphabet_reduce_delta M"
        by (auto elim: ktm_step.cases)
      have src_S: "fst (snd S) = AR_HaltReject"
        using c'_eq st sg idx_rej by simp
      from alphabet_reduce_delta_src_tag[OF rel]
      have "fst (snd S) ∈ {AR_SimRead, AR_SimCompute, AR_SimWrite,
                            AR_SimAdvance, AR_SimNext}" .
      hence False using src_S by auto
      thus ?thesis ..
    qed
  qed
  ― ‹The M'-step fires ‹ar_delta_read› by src-tag
     uniqueness; the lift extends the witness chain by one step.›
  have step_read: "(c', c'') ∈ ktm_step (ar_delta_read M)"
    using ar_step_read_lift[OF src step] .
  hence step_read1: "(c', c'') ∈ (ktm_step (ar_delta_read M)) ^^ Suc 0"
    by simp
  ― ‹Dispatch on the dest tag›
  from ar_step_from_SimRead_lands[OF step src]
  have dest: "fst (snd (ktc_state c'')) = AR_SimRead
            ∨ fst (snd (ktc_state c'')) = AR_SimCompute" .
  thus ?thesis
  proof
    assume dr: "fst (snd (ktc_state c'')) = AR_SimRead"
    have "ar_walker_in_read M cM c''"
      unfolding ar_walker_in_read_def
      using dr inv step_read1 by blast
    thus ?thesis ..
  next
    assume dc: "fst (snd (ktc_state c'')) = AR_SimCompute"
    have "ar_walker_at_compute M cM c''"
      unfolding ar_walker_at_compute_def
      using dc inv step_read1 by blast
    thus ?thesis ..
  qed
qed

lemma ar_walker_step_from_in_read:
  fixes M :: "('q, 'a) ktm"
    and cM :: "('a, 'q) ktc_config"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes inv: "ar_walker_in_read M cM c'"
      and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
  shows "ar_walker_in_read M cM c'' ∨ ar_walker_at_compute M cM c''"
proof -
  have src: "fst (snd (ktc_state c')) = AR_SimRead"
    using inv unfolding ar_walker_in_read_def by simp
  obtain c_b m where
      wb: "ar_walker_at_boundary M cM c_b"
    and chain: "(c_b, c') ∈ (ktm_step (ar_delta_read M)) ^^ m"
    using inv unfolding ar_walker_in_read_def by blast
  have step_read: "(c', c'') ∈ ktm_step (ar_delta_read M)"
    using ar_step_read_lift[OF src step] .
  have chain_ext: "(c_b, c'') ∈ (ktm_step (ar_delta_read M)) ^^ Suc m"
    using chain step_read by (rule relpow_Suc_I)
  from ar_step_from_SimRead_lands[OF step src]
  have dest: "fst (snd (ktc_state c'')) = AR_SimRead
            ∨ fst (snd (ktc_state c'')) = AR_SimCompute" .
  thus ?thesis
  proof
    assume dr: "fst (snd (ktc_state c'')) = AR_SimRead"
    have "ar_walker_in_read M cM c''"
      unfolding ar_walker_in_read_def
      using dr wb chain_ext by blast
    thus ?thesis ..
  next
    assume dc: "fst (snd (ktc_state c'')) = AR_SimCompute"
    have "ar_walker_at_compute M cM c''"
      unfolding ar_walker_at_compute_def
      using dc wb chain_ext by blast
    thus ?thesis ..
  qed
qed

lemma ar_walker_step_from_at_compute:
  fixes M :: "('q, 'a) ktm"
    and cM :: "('a, 'q) ktc_config"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes inv: "ar_walker_at_compute M cM c'"
      and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
      and vM: "valid_ktm M"
      and qQ: "ktc_state cM ∈ Q_ktm M"
      and kge2: "2 ≤ block_width (Γ_ktm M)"
      and tapeG: "⋀k. ktc_tape cM k (ktc_pos cM k) ∈ Γ_ktm M"
  shows "ar_walker_in_write M cM c''"
proof -
  let ?k = "block_width (Γ_ktm M)"
  let ?aM = "λk. ktc_tape cM k (ktc_pos cM k)"
  have c'_compute: "fst (snd (ktc_state c')) = AR_SimCompute"
    using inv unfolding ar_walker_at_compute_def by simp
  obtain c_b m_w where
      wb: "ar_walker_at_boundary M cM c_b"
    and chain_w: "(c_b, c') ∈ (ktm_step (ar_delta_read M)) ^^ m_w"
    using inv unfolding ar_walker_at_compute_def by blast
  have sim: "ar_simulates M cM c_b"
    using wb unfolding ar_walker_at_boundary_def by simp
  have pcons: "ar_posk_consistent M cM c_b"
    using wb unfolding ar_walker_at_boundary_def by simp
  have rbnd: "ar_at_read_boundary M c_b"
    using wb unfolding ar_walker_at_boundary_def by simp
  ― ‹‹c_b›'s tag is ‹AR_SimRead›: from a chain step (when
     ‹m_w > 0›) by ‹ar_delta_read_src›, or by ruling out the
     halt branches of ‹ar_simulates› (when ‹m_w = 0›).›
  have cb_idx: "fst (snd (ktc_state c_b)) = AR_SimRead"
  proof (cases m_w)
    case 0
    have cb_eq: "c_b = c'" using chain_w 0 by simp
    have cb_compute: "fst (snd (ktc_state c_b)) = AR_SimCompute"
      using c'_compute cb_eq by simp
    obtain qM' stg where st_b: "ktc_state c_b = (qM', stg)"
      by (cases "ktc_state c_b") auto
    obtain idx tk i buf dvec posk where
        sg_b: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
    have idx_cpu: "idx = AR_SimCompute" using cb_compute st_b sg_b by simp
    have "(idx = AR_SimRead ∧ qM' ∉ {t_ktm M, r_ktm M})
            ∨ (qM' = t_ktm M ∧ stg = ar_accept_stage (bl_ktm M))
            ∨ (qM' = r_ktm M ∧ stg = ar_reject_stage (bl_ktm M))"
      using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
    hence False
      using idx_cpu sg_b
      by (auto simp: ar_accept_stage_def ar_reject_stage_def)
    thus ?thesis ..
  next
    case (Suc m')
    have hsuc: "(c_b, c') ∈ (ktm_step (ar_delta_read M)) ^^ Suc m'"
      using chain_w Suc by simp
    obtain c_1 where
        first: "(c_b, c_1) ∈ ktm_step (ar_delta_read M)"
      using relpow_Suc_D2[OF hsuc] by blast
    from first obtain S ts n S' aw move where
        ceq: "c_b = KConfig S ts n"
      and rel: "(S, (λk. ts k (n k)), S', aw, move) ∈ ar_delta_read M"
      by (auto elim: ktm_step.cases)
    have "fst (snd S) = AR_SimRead" using ar_delta_read_src[OF rel] .
    thus ?thesis using ceq by simp
  qed
  ― ‹Extract ‹c_b›'s full state shape and the boundary's
     correspondences.›
  obtain qM' stg where st_b: "ktc_state c_b = (qM', stg)"
    by (cases "ktc_state c_b") auto
  obtain idx tk i buf dvec posk where
      sg_b: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
  have idx_read: "idx = AR_SimRead" using cb_idx st_b sg_b by simp
  have qM'_eq: "qM' = ktc_state cM"
    using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
  have tcorr: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
                       (ktc_tape cM k) (ktc_tape c_b k)"
    using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
  have ppos: "⋀k. ktc_pos c_b k = sim_pos ?k (ktc_pos cM k)"
    using sim st_b sg_b idx_read
    unfolding ar_simulates_def by (auto split: prod.splits)
  have pkok: "⋀k. posk k = AR_AtLE ⟷ ktc_pos cM k = 0"
    using pcons st_b sg_b idx_read
    unfolding ar_posk_consistent_def by (auto split: prod.splits)
  have bnd_unfold: "idx = AR_SimRead
        ⟶ (tk = 0 ∧ i = 0
             ∧ (∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M})
             ∧ ar_stage_bounded (bl_ktm M) (k_ktm M)
                  (idx, tk, i, buf, dvec, posk))"
    using rbnd st_b sg_b
    unfolding ar_at_read_boundary_def by (auto split: prod.splits)
  have tk0: "tk = 0" and i0: "i = 0"
    and bufG: "⋀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
    using bnd_unfold idx_read by simp_all
  have stg0: "ktc_state c_b = (ktc_state cM, AR_SimRead, 0, 0, buf, dvec, posk)"
    using st_b sg_b qM'_eq idx_read tk0 i0 by simp
  ― ‹Boundary blank-tail and bounded-stage facts, now produced by the
     strengthened ‹ar_at_read_boundary›: ‹src0_b› from its
     bounded-stage conjunct (specialised by ‹idx = AR_SimRead›,
     ‹tk = 0›, ‹i = 0›); ‹pad0_b› from its config
     padding-blank conjunct.›
  have pad0_b: "∀j ≥ k_ktm M. ktc_tape c_b j (ktc_pos c_b j) = BLANK4"
    using rbnd unfolding ar_at_read_boundary_def by (auto split: prod.splits)
  have src0_b: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                  (AR_SimRead, 0, 0, buf, dvec, posk)"
    using bnd_unfold idx_read tk0 i0 by simp
  ― ‹Apply ‹ar_read_phase› at the boundary, keeping the read sub-relation.›
  obtain c_r m_phase where
      r_chain: "(c_b, c_r) ∈ (ktm_step (ar_delta_read M)) ^^ m_phase"
    and r_state: "ktc_state c_r = (ktc_state cM, AR_SimCompute, k_unidx 0, 0,
                    (λk. if k < k_ktm M then ?aM k else buf k), dvec,
                    (λk. if k < k_ktm M
                          then (if ktc_pos cM k = 0 then AR_AtLE
                                else if ktc_pos cM k = 1 then AR_AtFirstProper
                                else AR_AtFurtherProper)
                          else posk k))"
    using ar_read_phase[OF vM qQ kge2 stg0 tcorr ppos pkok tapeG bufG
                           pad0_b src0_b] ktm_run_mono [OF Int_lower2]
    by blast
  have r_cpu: "fst (snd (ktc_state c_r)) = AR_SimCompute"
    using r_state by simp
  ― ‹Pin the walker's witness chain against ‹ar_read_phase›'s.›
  have c'_eq_c_r: "c' = c_r"
    using chain_ar_delta_read_to_SimCompute_uniq[OF chain_w r_chain c'_compute r_cpu]
    by simp
  have c'_state: "ktc_state c' = (ktc_state cM, AR_SimCompute, k_unidx 0, 0,
                    (λk. if k < k_ktm M then ?aM k else buf k), dvec,
                    (λk. if k < k_ktm M
                          then (if ktc_pos cM k = 0 then AR_AtLE
                                else if ktc_pos cM k = 1 then AR_AtFirstProper
                                else AR_AtFurtherProper)
                          else posk k))"
    using c'_eq_c_r r_state by simp
  ― ‹Lift the compute step to the sub-relation and invert.›
  have step_compute: "(c', c'') ∈ ktm_step (ar_delta_compute M)"
    using ar_step_compute_lift[OF c'_compute step] .
  obtain q' m_a' m_d where
      mdelta: "(ktc_state cM, (λk. if k < k_ktm M then ?aM k else buf k),
                  q', m_a', m_d) ∈ delta_ktm M"
    and c''_state: "ktc_state c'' = (q', AR_SimWrite, 0, 0, m_a', m_d,
                      (λk. if k < k_ktm M
                            then (if ktc_pos cM k = 0 then AR_AtLE
                                  else if ktc_pos cM k = 1 then AR_AtFirstProper
                                  else AR_AtFurtherProper)
                            else posk k))"
    and c''_tape: "ktc_tape c'' = ktc_tape c'"
    and c''_pos: "ktc_pos c'' = ktc_pos c'"
    using ar_compute_step_inv[OF step c'_state] by blast
  ― ‹Bundle the witness chain into ‹ar_walker_in_write›.›
  have c''_write: "fst (snd (ktc_state c'')) = AR_SimWrite"
    using c''_state by simp
  have empty_w: "(c'', c'') ∈ (ktm_step (ar_delta_write M)) ^^ 0" by simp
  show "ar_walker_in_write M cM c''"
    unfolding ar_walker_in_write_def
  proof (intro conjI)
    show "fst (snd (ktc_state c'')) = AR_SimWrite" by (rule c''_write)
    show "∃c_b c_w m_r m_w.
            ar_walker_at_boundary M cM c_b
          ∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
          ∧ fst (snd (ktc_state c_w)) = AR_SimCompute
          ∧ (∃c_w_post. (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
                          ∧ (c_w_post, c'') ∈ (ktm_step (ar_delta_write M)) ^^ m_w)"
      by (intro exI[where x = c_b] exI[where x = c'] exI[where x = m_w]
                exI[where x = 0] conjI wb chain_w c'_compute
                exI[where x = c''] step_compute empty_w)
  qed
qed

lemma ar_walker_step_from_in_write:
  fixes M :: "('q, 'a) ktm"
    and cM :: "('a, 'q) ktc_config"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes inv: "ar_walker_in_write M cM c'"
      and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
  shows "ar_walker_in_write M cM c'' ∨ ar_walker_in_advance M cM c''"
proof -
  have src: "fst (snd (ktc_state c')) = AR_SimWrite"
    using inv unfolding ar_walker_in_write_def by simp
  obtain c_b c_w m_r m_w where
      wb:   "ar_walker_at_boundary M cM c_b"
    and chr:  "(c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r"
    and cwC:  "fst (snd (ktc_state c_w)) = AR_SimCompute"
    and rest: "∃c_w_post. (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
                          ∧ (c_w_post, c') ∈ (ktm_step (ar_delta_write M)) ^^ m_w"
    using inv unfolding ar_walker_in_write_def by blast
  obtain c_w_post where
      ccs: "(c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)"
    and chw: "(c_w_post, c') ∈ (ktm_step (ar_delta_write M)) ^^ m_w"
    using rest by blast
  have step_write: "(c', c'') ∈ ktm_step (ar_delta_write M)"
    using ar_step_write_lift[OF src step] .
  have chw_ext: "(c_w_post, c'') ∈ (ktm_step (ar_delta_write M)) ^^ Suc m_w"
    using chw step_write by (rule relpow_Suc_I)
  from ar_step_from_SimWrite_lands[OF step src]
  have dest: "fst (snd (ktc_state c'')) = AR_SimWrite
            ∨ fst (snd (ktc_state c'')) = AR_SimAdvance" .
  thus ?thesis
  proof
    assume dw: "fst (snd (ktc_state c'')) = AR_SimWrite"
    have "ar_walker_in_write M cM c''"
      unfolding ar_walker_in_write_def
    proof (intro conjI)
      show "fst (snd (ktc_state c'')) = AR_SimWrite" by (rule dw)
      show "∃c_b c_w m_r m_w.
              ar_walker_at_boundary M cM c_b
              ∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
              ∧ fst (snd (ktc_state c_w)) = AR_SimCompute
              ∧ (∃c_w_post.
                   (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
                 ∧ (c_w_post, c'') ∈ (ktm_step (ar_delta_write M)) ^^ m_w)"
        by (intro exI[where x = c_b] exI[where x = c_w] exI[where x = m_r]
                  exI[where x = "Suc m_w"] conjI wb chr cwC
                  exI[where x = c_w_post] ccs chw_ext)
    qed
    thus ?thesis ..
  next
    assume da: "fst (snd (ktc_state c'')) = AR_SimAdvance"
    ― ‹Cycle transition write to advance: ‹c''› opens the
        advance phase with zero advance-steps elapsed.›
    have empty_a: "(c'', c'') ∈ (ktm_step (ar_delta_advance M)) ^^ 0"
      by simp
    have "ar_walker_in_advance M cM c''"
      unfolding ar_walker_in_advance_def
    proof (intro conjI)
      show "fst (snd (ktc_state c'')) = AR_SimAdvance" by (rule da)
      show "∃c_b c_w c_a m_r m_w m_a.
              ar_walker_at_boundary M cM c_b
              ∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
              ∧ fst (snd (ktc_state c_w)) = AR_SimCompute
              ∧ fst (snd (ktc_state c_a)) = AR_SimAdvance
              ∧ (∃c_w_post.
                   (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
                 ∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
                 ∧ (c_a, c'') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a)"
        by (intro exI[where x = c_b] exI[where x = c_w] exI[where x = c'']
                  exI[where x = m_r] exI[where x = "Suc m_w"] exI[where x = 0]
                  conjI wb chr cwC da
                  exI[where x = c_w_post] ccs chw_ext empty_a)
    qed
    thus ?thesis ..
  qed
qed

lemma ar_walker_step_from_in_advance:
  fixes M :: "('q, 'a) ktm"
    and cM :: "('a, 'q) ktc_config"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes inv: "ar_walker_in_advance M cM c'"
      and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
  shows "ar_walker_in_advance M cM c'' ∨ ar_walker_at_next M cM c''"
proof -
  have src: "fst (snd (ktc_state c')) = AR_SimAdvance"
    using inv unfolding ar_walker_in_advance_def by simp
  obtain c_b c_w c_a m_r m_w m_a where
      wb:   "ar_walker_at_boundary M cM c_b"
    and chr:  "(c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r"
    and cwC:  "fst (snd (ktc_state c_w)) = AR_SimCompute"
    and caC:  "fst (snd (ktc_state c_a)) = AR_SimAdvance"
    and rest: "∃c_w_post.
                  (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
                ∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
                ∧ (c_a, c') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a"
    using inv unfolding ar_walker_in_advance_def by blast
  obtain c_w_post where
      ccs: "(c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)"
    and chw: "(c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w"
    and cha: "(c_a, c') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a"
    using rest by blast
  have step_advance: "(c', c'') ∈ ktm_step (ar_delta_advance M)"
    using ar_step_advance_lift[OF src step] .
  have cha_ext: "(c_a, c'') ∈ (ktm_step (ar_delta_advance M)) ^^ Suc m_a"
    using cha step_advance by (rule relpow_Suc_I)
  from ar_step_from_SimAdvance_lands[OF step src]
  have dest: "fst (snd (ktc_state c'')) = AR_SimAdvance
            ∨ fst (snd (ktc_state c'')) = AR_SimNext" .
  thus ?thesis
  proof
    assume da: "fst (snd (ktc_state c'')) = AR_SimAdvance"
    have "ar_walker_in_advance M cM c''"
      unfolding ar_walker_in_advance_def
    proof (intro conjI)
      show "fst (snd (ktc_state c'')) = AR_SimAdvance" by (rule da)
      show "∃c_b c_w c_a m_r m_w m_a.
              ar_walker_at_boundary M cM c_b
              ∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
              ∧ fst (snd (ktc_state c_w)) = AR_SimCompute
              ∧ fst (snd (ktc_state c_a)) = AR_SimAdvance
              ∧ (∃c_w_post.
                   (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
                 ∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
                 ∧ (c_a, c'') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a)"
        by (intro exI[where x = c_b] exI[where x = c_w] exI[where x = c_a]
                  exI[where x = m_r] exI[where x = m_w] exI[where x = "Suc m_a"]
                  conjI wb chr cwC caC
                  exI[where x = c_w_post] ccs chw cha_ext)
    qed
    thus ?thesis ..
  next
    assume dn: "fst (snd (ktc_state c'')) = AR_SimNext"
    ― ‹Cycle transition advance to next: extended advance chain
        lands at ‹c''›, the redundant ‹c_n = c'› conjunct
        instantiates with ‹c_n = c''›.›
    have "ar_walker_at_next M cM c''"
      unfolding ar_walker_at_next_def
    proof (intro conjI)
      show "fst (snd (ktc_state c'')) = AR_SimNext" by (rule dn)
      show "∃c_b c_w c_a c_n m_r m_w m_a.
              ar_walker_at_boundary M cM c_b
              ∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
              ∧ fst (snd (ktc_state c_w)) = AR_SimCompute
              ∧ fst (snd (ktc_state c_a)) = AR_SimAdvance
              ∧ (∃c_w_post.
                   (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
                 ∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
                 ∧ (c_a, c_n) ∈ (ktm_step (ar_delta_advance M)) ^^ m_a
                 ∧ c_n = c'')"
        by (intro exI[where x = c_b] exI[where x = c_w] exI[where x = c_a]
                  exI[where x = c''] exI[where x = m_r] exI[where x = m_w]
                  exI[where x = "Suc m_a"] conjI wb chr cwC caC
                  exI[where x = c_w_post] ccs chw cha_ext refl)
    qed
    thus ?thesis ..
  qed
qed

text ‹The sixth and last of the preservation lemmas: an ‹M'›-step out
  of ‹AR_SimNext› leads to ‹AR_SimRead› (closing the cycle),
  ‹AR_HaltAccept›, or ‹AR_HaltReject›, by
  ‹ar_step_from_SimNext_lands›.  It only sorts the cases.
  Establishing the invariant for the reconstructed ‹M›-successor when
  a cycle closes is done once per cycle, by ‹ar_walker_cycle_close›
  and the chunked reverse induction, and the proof goes through that
  lemma directly; this one is not used below, and is stated so that all
  six substeps have their one-step lemma.›

lemma ar_walker_step_from_at_next:
  fixes M :: "('q, 'a) ktm"
    and cM :: "('a, 'q) ktc_config"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes inv: "ar_walker_at_next M cM c'"
      and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
  shows "fst (snd (ktc_state c'')) = AR_SimRead
       ∨ fst (snd (ktc_state c'')) = AR_HaltAccept
       ∨ fst (snd (ktc_state c'')) = AR_HaltReject"
proof -
  have src: "fst (snd (ktc_state c')) = AR_SimNext"
    using inv unfolding ar_walker_at_next_def by simp
  show ?thesis using ar_step_from_SimNext_lands[OF step src] .
qed

subsection ‹Closing a simulation cycle›

text ‹An ‹AR_SimNext› step closes a simulation cycle: the walker is
  re-established at a boundary for the next ‹M›-configuration.  The
  successor is ∗‹reconstructed› from the pinned compute branch
  (the ‹∃cM'› in the conclusion): under nondeterministic
  ‹delta_ktm M› the source ‹cM› may have several successors, so the
  fired branch is recovered from the walker's own witness chain rather
  than assumed.  The forward phase lemmas run in the full relation and
  in the substep sub-relation at once, so the forward direction is read in the
  sub-relations and each walker
  witness chain is pinned by a ‹chain_ar_delta_X_to_Y_uniq› suite.

  The closing next step is inverted by ‹ar_next_step_inv›, which
  dispatches on the reconstructed ‹M›-state ‹q'› into three
  outcomes: continue (‹q' ∉ {t, r}›, landing at ‹AR_SimRead›),
  accept (‹q' = t_ktm M›) or reject (‹q' = r_ktm M›).  All three
  re-establish ‹ar_walker_at_boundary M cMn c''›: the boundary
  invariant carries the halt cases too — ‹ar_simulates›'s state
  disjunction has dedicated accept/reject arms, and both
  ‹ar_posk_consistent› and ‹ar_at_read_boundary› are
  ‹AR_SimRead›-guarded, hence vacuous off the read boundary.  The
  three predicates are discharged from the explicit endpoint by the shared
  semantic lemmas (‹ar_write_tape_correspondence›,
  ‹ar_advance_newsimpos›, ‹ar_newpos_atLE_iff›).  No union chain
  is pinned and ‹ar_simulates_forward_step› is not invoked.›

lemma ar_walker_cycle_close:
  fixes M :: "('q, 'a) ktm"
    and w :: "'a list"
    and cM :: "('a, 'q) ktc_config"
    and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes inv: "ar_walker_at_next M cM c'"
      and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
      and vM: "valid_ktm M"
      and qQ: "ktc_state cM ∈ Q_ktm M"
      and kge2: "2 ≤ block_width (Γ_ktm M)"
      and tapeG: "⋀k. ktc_tape cM k (ktc_pos cM k) ∈ Γ_ktm M"
      and w_sub: "set w ⊆ Sigma_ktm M"
      and reach_M: "(init_config_ktm M w, cM) ∈ (ktm_step (delta_ktm M))*"
      and lebl: "le_ktm M ≠ bl_ktm M"
  shows "∃cM'. (cM, cM') ∈ ktm_step (delta_ktm M)
               ∧ ar_walker_at_boundary M cM' c''"
proof -
  let ?k = "block_width (Γ_ktm M)"
  let ?aM = "λk. ktc_tape cM k (ktc_pos cM k)"
  have kpos_ktm: "0 < k_ktm M" using vM by (cases M) auto
  ― ‹Unpack the ‹ar_walker_at_next› witness.›
  obtain c_b c_w c_a c_n m_r m_w m_a c_w_post where
      wb: "ar_walker_at_boundary M cM c_b"
    and chain_r: "(c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r"
    and cw_cpu: "fst (snd (ktc_state c_w)) = AR_SimCompute"
    and ca_adv: "fst (snd (ktc_state c_a)) = AR_SimAdvance"
    and cstep: "(c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)"
    and wchain: "(c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w"
    and achain0: "(c_a, c_n) ∈ (ktm_step (ar_delta_advance M)) ^^ m_a"
    and cn_eq: "c_n = c'"
    using inv unfolding ar_walker_at_next_def by blast
  have achain: "(c_a, c') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a"
    using achain0 cn_eq by simp
  have c'_next: "fst (snd (ktc_state c')) = AR_SimNext"
    using inv unfolding ar_walker_at_next_def by simp
  have sim: "ar_simulates M cM c_b"
    using wb unfolding ar_walker_at_boundary_def by simp
  have pcons: "ar_posk_consistent M cM c_b"
    using wb unfolding ar_walker_at_boundary_def by simp
  have rbnd: "ar_at_read_boundary M c_b"
    using wb unfolding ar_walker_at_boundary_def by simp
  have cb_idx: "fst (snd (ktc_state c_b)) = AR_SimRead"
  proof (cases m_r)
    case 0
    have cb_eq: "c_b = c_w" using chain_r 0 by simp
    have cb_compute: "fst (snd (ktc_state c_b)) = AR_SimCompute"
      using cw_cpu cb_eq by simp
    obtain qM' stg where st_b: "ktc_state c_b = (qM', stg)"
      by (cases "ktc_state c_b") auto
    obtain idx tk i buf dvec posk where
        sg_b: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
    have idx_cpu: "idx = AR_SimCompute" using cb_compute st_b sg_b by simp
    have "(idx = AR_SimRead ∧ qM' ∉ {t_ktm M, r_ktm M})
            ∨ (qM' = t_ktm M ∧ stg = ar_accept_stage (bl_ktm M))
            ∨ (qM' = r_ktm M ∧ stg = ar_reject_stage (bl_ktm M))"
      using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
    hence False using idx_cpu sg_b
      by (auto simp: ar_accept_stage_def ar_reject_stage_def)
    thus ?thesis ..
  next
    case (Suc m')
    have hsuc: "(c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ Suc m'"
      using chain_r Suc by simp
    obtain c_1 where first: "(c_b, c_1) ∈ ktm_step (ar_delta_read M)"
      using relpow_Suc_D2[OF hsuc] by blast
    from first obtain S ts n S' aw move where
        ceq: "c_b = KConfig S ts n"
      and rel: "(S, (λk. ts k (n k)), S', aw, move) ∈ ar_delta_read M"
      by (auto elim: ktm_step.cases)
    have "fst (snd S) = AR_SimRead" using ar_delta_read_src[OF rel] .
    thus ?thesis using ceq by simp
  qed
  obtain qM' stg where st_b: "ktc_state c_b = (qM', stg)"
    by (cases "ktc_state c_b") auto
  obtain idx tk i buf dvec posk where
      sg_b: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
  have idx_read: "idx = AR_SimRead" using cb_idx st_b sg_b by simp
  have qM'_eq: "qM' = ktc_state cM"
    using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
  have tcorr: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
                       (ktc_tape cM k) (ktc_tape c_b k)"
    using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
  have ppos: "⋀k. ktc_pos c_b k = sim_pos ?k (ktc_pos cM k)"
    using sim st_b sg_b idx_read
    unfolding ar_simulates_def by (auto split: prod.splits)
  have pkok: "⋀k. posk k = AR_AtLE ⟷ ktc_pos cM k = 0"
    using pcons st_b sg_b idx_read
    unfolding ar_posk_consistent_def by (auto split: prod.splits)
  have bnd_unfold: "idx = AR_SimRead
        ⟶ (tk = 0 ∧ i = 0
             ∧ (∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M})
             ∧ ar_stage_bounded (bl_ktm M) (k_ktm M)
                  (idx, tk, i, buf, dvec, posk))"
    using rbnd st_b sg_b
    unfolding ar_at_read_boundary_def by (auto split: prod.splits)
  have tk0: "tk = 0" and i0: "i = 0"
    and bufG: "⋀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
    using bnd_unfold idx_read by simp_all
  have src_b: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                 (AR_SimRead, 0, 0, buf, dvec, posk)"
    using bnd_unfold idx_read tk0 i0 by simp
  have pad_b: "∀j ≥ k_ktm M. ktc_tape c_b j (ktc_pos c_b j) = BLANK4"
    using rbnd unfolding ar_at_read_boundary_def by (auto split: prod.splits)
  have stg0: "ktc_state c_b = (ktc_state cM, AR_SimRead, 0, 0, buf, dvec, posk)"
    using st_b sg_b qM'_eq idx_read tk0 i0 by simp
  have buf_tail: "∀j ≥ k_ktm M. buf j = bl_ktm M"
    using src_b by (simp add: ar_stage_bounded_def)
  have posk_tail: "∀j ≥ k_ktm M. posk j = AR_AtLE"
    using src_b by (simp add: ar_stage_bounded_def)
  have valcM: "valid_config_ktm M cM"
    using valid_reach_ktm[OF vM w_sub reach_M] .
  have aM_tail: "∀j ≥ k_ktm M. ktc_tape cM j (ktc_pos cM j) = bl_ktm M"
    using valid_config_ktm_blank_tail[OF valcM] by blast
  ― ‹Read-pin: reconstruct the canonical compute config (guarded read
     buffer / posk / position), pin the walker's read chain to it.›
  let ?rbuf = "λk. if k < k_ktm M then ?aM k else buf k"
  let ?rposk = "λk. if k < k_ktm M
                     then (if ktc_pos cM k = 0 then AR_AtLE
                           else if ktc_pos cM k = 1 then AR_AtFirstProper
                           else AR_AtFurtherProper)
                     else posk k"
  let ?rpos = "λk. if k < k_ktm M
                    then (if ktc_pos cM k = 0 then Suc 0
                          else sim_pos ?k (ktc_pos cM k) + ?k)
                    else ktc_pos c_b k"
  obtain c_r m_phase where
      r_chain: "(c_b, c_r) ∈ (ktm_step (ar_delta_read M)) ^^ m_phase"
    and r_state: "ktc_state c_r = (ktc_state cM, AR_SimCompute, k_unidx 0, 0,
                    ?rbuf, dvec, ?rposk)"
    and r_tape: "ktc_tape c_r = ktc_tape c_b"
    and r_pos: "ktc_pos c_r = ?rpos"
    using ar_read_phase[OF vM qQ kge2 stg0 tcorr ppos pkok tapeG bufG
                           pad_b src_b] ktm_run_mono [OF Int_lower2]
    by blast
  have r_cpu: "fst (snd (ktc_state c_r)) = AR_SimCompute" using r_state by simp
  have cw_eq_cr: "c_w = c_r"
    using chain_ar_delta_read_to_SimCompute_uniq[OF chain_r r_chain cw_cpu r_cpu]
    by simp
  have cw_state: "ktc_state c_w = (ktc_state cM, AR_SimCompute, k_unidx 0, 0,
                    ?rbuf, dvec, ?rposk)"
    using cw_eq_cr r_state by simp
  ― ‹Invert the compute step: the explicit post-state and the fired
     ‹delta_ktm M› branch (on the guarded read buffer).›
  obtain q' m_a' m_d where
      mdelta: "(ktc_state cM, ?rbuf, q', m_a', m_d) ∈ delta_ktm M"
    and cwpost_state: "ktc_state c_w_post = (q', AR_SimWrite, 0, 0, m_a', m_d, ?rposk)"
    and cwpost_tape: "ktc_tape c_w_post = ktc_tape c_w"
    and cwpost_pos: "ktc_pos c_w_post = ktc_pos c_w"
    using ar_compute_step_inv_sub[OF cstep cw_state] by blast
  obtain qM tsM nM where cM_eq: "cM = KConfig qM tsM nM" by (cases cM) auto
  have qM_eq: "qM = ktc_state cM" using cM_eq by simp
  have aM_eq: "(λk. tsM k (nM k)) = ?aM" using cM_eq by simp
  have rbuf_eq: "?rbuf = ?aM"
  proof (rule ext)
    fix k show "?rbuf k = ?aM k"
    proof (cases "k < k_ktm M")
      case True thus ?thesis by simp
    next
      case False
      have "?rbuf k = bl_ktm M" using buf_tail False by simp
      moreover have "?aM k = bl_ktm M" using aM_tail False by simp
      ultimately show ?thesis by simp
    qed
  qed
  have mdelta_aM: "(ktc_state cM, ?aM, q', m_a', m_d) ∈ delta_ktm M"
    using mdelta rbuf_eq by simp
  define cMn where cMn_def: "cMn = KConfig q' (λk. (tsM k)(nM k := m_a' k))
                                              (λk. go_move (m_d k) (nM k))"
  have mdelta': "(qM, (λk. tsM k (nM k)), q', m_a', m_d) ∈ delta_ktm M"
    using mdelta_aM qM_eq aM_eq by simp
  have m_step: "(cM, cMn) ∈ ktm_step (delta_ktm M)"
    using ktm_step.step[where ts = tsM and n = nM, OF mdelta'] cM_eq cMn_def by simp
  have q'Q: "q' ∈ Q_ktm M" using valid_ktm_delta(3)[OF vM mdelta_aM] .
  have a'G: "m_a' k ∈ Γ_ktm M" for k using valid_ktm_delta(4)[OF vM mdelta_aM] .
  have a'val: "∀k. m_a' k ∈ Γ_ktm M ∪ {bl_ktm M}" using a'G by blast
  have dsupp: "∀j ≥ k_ktm M. m_a' j = bl_ktm M ∧ m_d j = MoveN"
    using valid_ktm_delta_support[OF vM mdelta_aM] by blast
  ― ‹Write phase: post-write tape / position setup and pad / src for the
     compute-exit config, then pin the walker's write chain.›
  have pad_cwpost: "∀j ≥ k_ktm M. ktc_tape c_w_post j (ktc_pos c_w_post j) = BLANK4"
  proof (intro allI impI)
    fix j assume jk: "k_ktm M ≤ j"
    have "ktc_pos c_w_post j = ktc_pos c_b j"
      using cwpost_pos cw_eq_cr r_pos jk by simp
    moreover have "ktc_tape c_w_post j = ktc_tape c_b j"
      using cwpost_tape cw_eq_cr r_tape by simp
    ultimately show "ktc_tape c_w_post j (ktc_pos c_w_post j) = BLANK4"
      using pad_b jk by simp
  qed
  have src_cwpost: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                      (AR_SimWrite, 0, 0, m_a', m_d, ?rposk)"
    using kpos_ktm dsupp posk_tail by (simp add: ar_stage_bounded_def)
  have tcorr_w: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
                     (ktc_tape cM k) (ktc_tape c_w_post k)"
  proof (intro allI impI)
    fix k assume kN: "k < k_ktm M"
    have "ktc_tape c_w_post k = ktc_tape c_b k"
      using cwpost_tape cw_eq_cr r_tape by simp
    thus "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
            (ktc_tape cM k) (ktc_tape c_w_post k)"
      using tcorr kN by simp
  qed
  have ppos_w: "∀k < k_ktm M. ktc_pos c_w_post k = (if ktc_pos cM k = 0 then Suc 0
                   else sim_pos ?k (ktc_pos cM k) + ?k)"
    using cwpost_pos cw_eq_cr r_pos by simp
  have a'le0_w: "∀k < k_ktm M. ktc_pos cM k = 0 ⟶ m_a' k = le_ktm M"
  proof (intro allI impI)
    fix k assume kN: "k < k_ktm M" and p0: "ktc_pos cM k = 0"
    have tsk0: "tsM k 0 = le_ktm M" using valcM cM_eq kN by (cases M) auto
    have "(λj. tsM j (nM j)) k = le_ktm M" using tsk0 p0 cM_eq by simp
    thus "m_a' k = le_ktm M" using valid_ktm_deltaLE[OF vM mdelta'] by simp
  qed
  have poskle_w: "∀k < k_ktm M. ?rposk k = AR_AtLE ⟷ ktc_pos cM k = 0"
    by auto
  obtain c_write mw where
      w_chain: "(c_w_post, c_write) ∈ (ktm_step (ar_delta_write M)) ^^ mw"
    and w_state: "ktc_state c_write = (q', AR_SimAdvance, k_unidx 0, 0, m_a', m_d,
                    ?rposk)"
    and w_tape: "ktc_tape c_write = (λk. if k < k_ktm M
          then (if ktc_pos cM k = 0 then ktc_tape c_w_post k
                else (λpos. if sim_pos ?k (ktc_pos cM k) ≤ pos
                              ∧ pos < sim_pos ?k (ktc_pos cM k) + ?k
                           then write_bit (Γ_ktm M) (bl_ktm M) (m_a' k)
                                  (pos - sim_pos ?k (ktc_pos cM k))
                           else ktc_tape c_w_post k pos))
          else ktc_tape c_w_post k)"
    and w_pos: "ktc_pos c_write = ktc_pos c_w_post"
    using ar_write_phase[OF vM q'Q kge2 cwpost_state tcorr_w ppos_w
                            poskle_w a'val pad_cwpost src_cwpost]
          ktm_run_mono [OF Int_lower2]
    by blast
  have c_write_adv: "fst (snd (ktc_state c_write)) = AR_SimAdvance"
    using w_state by simp
  have ca_eq: "c_a = c_write"
    using chain_ar_delta_write_to_SimAdvance_uniq[OF wchain w_chain ca_adv
                                                     c_write_adv]
    by simp
  ― ‹Advance phase: bridge the tk-field, displacement facts (active
     tapes), pad / src for the write-exit config, then pin.›
  have w_state': "ktc_state c_write = (q', AR_SimAdvance, 0, 0, m_a', m_d, ?rposk)"
    using w_state by (simp add: k_unidx_zero)
  have pad_cwrite: "∀j ≥ k_ktm M. ktc_tape c_write j (ktc_pos c_write j) = BLANK4"
  proof (intro allI impI)
    fix j assume jk: "k_ktm M ≤ j"
    have "ktc_tape c_write j = ktc_tape c_w_post j" using w_tape jk by simp
    moreover have "ktc_pos c_write j = ktc_pos c_w_post j" using w_pos by simp
    ultimately show "ktc_tape c_write j (ktc_pos c_write j) = BLANK4"
      using pad_cwpost jk by simp
  qed
  have src_cwrite: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                      (AR_SimAdvance, 0, 0, m_a', m_d, ?rposk)"
    using kpos_ktm dsupp posk_tail by (simp add: ar_stage_bounded_def)
  have dge1: "∀k < k_ktm M. m_d k ≠ MoveR ⟶ 0 < ar_disp ?k (m_d k) (?rposk k)"
  proof (intro allI impI)
    fix k assume kN: "k < k_ktm M" and dkR: "m_d k ≠ MoveR"
    show "0 < ar_disp ?k (m_d k) (?rposk k)"
    proof (cases "ktc_pos cM k = 0")
      case True
      have nM0: "nM k = 0" using True cM_eq by simp
      have "tsM k 0 = le_ktm M" using valcM cM_eq kN by (cases M) auto
      hence "(λj. tsM j (nM j)) k = le_ktm M" using nM0 by simp
      hence "m_d k ∈ {MoveN, MoveR}" using valid_ktm_deltaLE[OF vM mdelta'] by simp
      hence "m_d k = MoveN" using dkR by auto
      moreover have "?rposk k = AR_AtLE" using True kN by simp
      ultimately show "0 < ar_disp ?k (m_d k) (?rposk k)" by simp
    next
      case False
      have dN_or_L: "m_d k = MoveN ∨ m_d k = MoveL"
        using dkR by (cases "m_d k") auto
      have rk: "?rposk k = AR_AtFirstProper ∨ ?rposk k = AR_AtFurtherProper"
        using False kN by auto
      from dN_or_L rk kge2 show "0 < ar_disp ?k (m_d k) (?rposk k)" by auto
    qed
  qed
  have notLE: "∀k < k_ktm M. ∀m. m < ar_disp ?k (m_d k) (?rposk k)
                 ⟶ ktc_tape c_write k (ktc_pos c_write k - m) ≠ LE4"
  proof (intro allI impI)
    fix k m assume kN: "k < k_ktm M"
      and mlt: "m < ar_disp ?k (m_d k) (?rposk k)"
    have tcorr_wk: "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
                      (ktc_tape cM k) (ktc_tape c_w_post k)"
      using tcorr_w kN by blast
    have wcpos: "ktc_pos c_write k = (if ktc_pos cM k = 0 then Suc 0
                    else sim_pos ?k (ktc_pos cM k) + ?k)"
      using w_pos ppos_w kN by simp
    have wtape_notLE: "ktc_tape c_write k pos ≠ LE4" if pos1: "1 ≤ pos" for pos
    proof (cases "ktc_pos cM k = 0")
      case True
      have "ktc_tape c_write k pos = ktc_tape c_w_post k pos"
        using w_tape True kN by simp
      thus ?thesis
        using ar_tape_correspondence_not_LE4[OF tcorr_wk pos1] by simp
    next
      case False
      have wexp: "ktc_tape c_write k pos
            = (if sim_pos ?k (ktc_pos cM k) ≤ pos
                  ∧ pos < sim_pos ?k (ktc_pos cM k) + ?k
               then write_bit (Γ_ktm M) (bl_ktm M) (m_a' k)
                      (pos - sim_pos ?k (ktc_pos cM k))
               else ktc_tape c_w_post k pos)"
        using w_tape False kN by simp
      show ?thesis
      proof (cases "sim_pos ?k (ktc_pos cM k) ≤ pos
                      ∧ pos < sim_pos ?k (ktc_pos cM k) + ?k")
        case True
        have b: "pos - sim_pos ?k (ktc_pos cM k) < ?k" using True by linarith
        have "ktc_tape c_write k pos
                = write_bit (Γ_ktm M) (bl_ktm M) (m_a' k)
                    (pos - sim_pos ?k (ktc_pos cM k))"
          using wexp True by simp
        thus ?thesis using write_bit_not_LE4[OF b] by simp
      next
        case False
        have nreg: "¬ (sim_pos ?k (ktc_pos cM k) ≤ pos
                        ∧ pos < sim_pos ?k (ktc_pos cM k) + ?k)"
          using False by simp
        have "ktc_tape c_write k pos = ktc_tape c_w_post k pos"
          using wexp by (simp add: if_not_P[OF nreg])
        thus ?thesis
          using ar_tape_correspondence_not_LE4[OF tcorr_wk pos1] by simp
      qed
    qed
    have rge: "ar_disp ?k (m_d k) (?rposk k) ≤ ktc_pos c_write k"
    proof (cases "ktc_pos cM k = 0")
      case True
      have "ar_disp ?k (m_d k) (?rposk k) ≤ Suc 0"
        using True kN by (cases "m_d k") auto
      thus ?thesis using wcpos True by simp
    next
      case nz: False
      show ?thesis
      proof (cases "ktc_pos cM k = 1")
        case True
        have "ar_disp ?k (m_d k) (?rposk k) ≤ Suc ?k"
          using True kN by (cases "m_d k") auto
        thus ?thesis using wcpos True by (simp add: sim_pos_def)
      next
        case False
        have p2: "2 ≤ ktc_pos cM k" using nz False by simp
        have d2: "ar_disp ?k (m_d k) (?rposk k) ≤ 2 * ?k"
          using nz False kN by (cases "m_d k") auto
        have cw_eq2: "ktc_pos c_write k = (ktc_pos cM k - 1) * ?k + 1 + ?k"
          using wcpos nz by (simp add: sim_pos_def)
        have "(1::nat) ≤ ktc_pos cM k - 1" using p2 by simp
        hence "1 * ?k ≤ (ktc_pos cM k - 1) * ?k" by (rule mult_le_mono1)
        hence kk: "?k ≤ (ktc_pos cM k - 1) * ?k" by (simp only: mult_1_left)
        have "2 * ?k ≤ ktc_pos c_write k" using kk cw_eq2 by linarith
        thus ?thesis using d2 by linarith
      qed
    qed
    have "m < ktc_pos c_write k" using mlt rge by simp
    hence "1 ≤ ktc_pos c_write k - m" by simp
    thus "ktc_tape c_write k (ktc_pos c_write k - m) ≠ LE4" by (rule wtape_notLE)
  qed
  let ?aposk = "λk. if k < k_ktm M then ar_newpos (m_d k) (?rposk k) else ?rposk k"
  let ?apos = "λk. if k < k_ktm M
                    then (if m_d k = MoveR then ktc_pos c_write k
                          else ktc_pos c_write k - ar_disp ?k (m_d k) (?rposk k))
                    else ktc_pos c_write k"
  obtain c_adv ma where
      a_chain: "(c_write, c_adv) ∈ (ktm_step (ar_delta_advance M)) ^^ ma"
    and a_state: "ktc_state c_adv = (q', AR_SimNext, k_unidx 0, 0, m_a', m_d, ?aposk)"
    and a_tape: "ktc_tape c_adv = ktc_tape c_write"
    and a_pos: "ktc_pos c_adv = ?apos"
    using ar_advance_phase[OF vM q'Q kge2 w_state' a'val dge1 notLE
                              pad_cwrite src_cwrite] ktm_run_mono [OF Int_lower2]
    by blast
  have c_adv_nxt: "fst (snd (ktc_state c_adv)) = AR_SimNext" using a_state by simp
  have achain': "(c_write, c') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a"
    using achain ca_eq by simp
  have c'_eq: "c' = c_adv"
    using chain_ar_delta_advance_to_SimNext_uniq[OF achain' a_chain c'_next
                                                    c_adv_nxt]
    by simp
  have c'_state: "ktc_state c' = (q', AR_SimNext, k_unidx 0, 0, m_a', m_d, ?aposk)"
    using c'_eq a_state by simp
  ― ‹Closing next step: invert it; dispatch on the reconstructed
     ‹M›-state ‹q'›.›
  have nxt: "ktc_tape c'' = ktc_tape c' ∧ ktc_pos c'' = ktc_pos c'
       ∧ ((q' ∉ {t_ktm M, r_ktm M}
             ∧ ktc_state c'' = (q', AR_SimRead, 0, 0, m_a', m_d, ?aposk))
          ∨ (q' = t_ktm M
             ∧ ktc_state c'' = (t_ktm M, ar_accept_stage (bl_ktm M)))
          ∨ (q' = r_ktm M
             ∧ ktc_state c'' = (r_ktm M, ar_reject_stage (bl_ktm M))))"
    using ar_next_step_inv[OF step c'_state] .
  have nxt_tape: "ktc_tape c'' = ktc_tape c'" using nxt by simp
  have nxt_pos: "ktc_pos c'' = ktc_pos c'" using nxt by simp
  have nxt_disj:
      "(q' ∉ {t_ktm M, r_ktm M}
          ∧ ktc_state c'' = (q', AR_SimRead, 0, 0, m_a', m_d, ?aposk))
       ∨ (q' = t_ktm M
          ∧ ktc_state c'' = (t_ktm M, ar_accept_stage (bl_ktm M)))
       ∨ (q' = r_ktm M
          ∧ ktc_state c'' = (r_ktm M, ar_reject_stage (bl_ktm M)))"
    using nxt by simp
  ― ‹Re-establish the boundary predicates for ‹cMn› at ‹c''›.›
  have st_cMn: "ktc_state cMn = q'" using cMn_def by simp
  have padpos0: "∀j ≥ k_ktm M. ktc_pos cM j = 0" using pkok posk_tail by blast
  have dposL: "m_d k ≠ MoveL" if p0: "ktc_pos cM k = 0" and kN: "k < k_ktm M" for k
  proof -
    have nM0: "nM k = 0" using p0 cM_eq by simp
    have "tsM k 0 = le_ktm M" using valcM cM_eq kN by (cases M) auto
    hence "(λj. tsM j (nM j)) k = le_ktm M" using nM0 by simp
    hence "m_d k ∈ {MoveN, MoveR}" using valid_ktm_deltaLE[OF vM mdelta'] by simp
    thus "m_d k ≠ MoveL" by auto
  qed
  have cwpost_b: "ktc_tape c_w_post = ktc_tape c_b"
    using cwpost_tape cw_eq_cr r_tape by simp
  have cM1tape: "ktc_tape cMn k = (ktc_tape cM k)(ktc_pos cM k := m_a' k)" for k
    using cMn_def cM_eq by simp
  have wt_def: "ktc_tape c'' k pos
        = (if ktc_pos cM k = 0 then ktc_tape c_b k pos
           else if sim_pos ?k (ktc_pos cM k) ≤ pos
                   ∧ pos < sim_pos ?k (ktc_pos cM k) + ?k
                then write_bit (Γ_ktm M) (bl_ktm M) (m_a' k)
                       (pos - sim_pos ?k (ktc_pos cM k))
                else ktc_tape c_b k pos)" for k pos
  proof (cases "k < k_ktm M")
    case True
    thus ?thesis using nxt_tape c'_eq a_tape w_tape cwpost_b by simp
  next
    case False
    hence kge: "k_ktm M ≤ k" by simp
    have p0: "ktc_pos cM k = 0" using padpos0 kge by blast
    have "ktc_tape c'' k = ktc_tape c_b k"
      using nxt_tape c'_eq a_tape w_tape cwpost_b kge by simp
    thus ?thesis using p0 by simp
  qed
  have tcorr_1: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
                   (ktc_tape cMn k) (ktc_tape c'' k)"
  proof (intro allI impI)
    fix k assume kN: "k < k_ktm M"
    show "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
            (ktc_tape cMn k) (ktc_tape c'' k)"
      by (rule ar_write_tape_correspondence
                [OF kge2 kN tcorr cM1tape a'le0_w wt_def])
  qed
  have apos_1: "ktc_pos c'' k = sim_pos ?k (ktc_pos cMn k)" for k
  proof (cases "k < k_ktm M")
    case kN: True
    have posM1: "ktc_pos cMn k = go_move (m_d k) (ktc_pos cM k)"
      using cMn_def cM_eq by simp
    have key: "(if m_d k = MoveR
                 then (if ktc_pos cM k = 0 then Suc 0
                       else sim_pos ?k (ktc_pos cM k) + ?k)
                 else (if ktc_pos cM k = 0 then Suc 0
                       else sim_pos ?k (ktc_pos cM k) + ?k)
                        - ar_disp ?k (m_d k)
                            (if ktc_pos cM k = 0 then AR_AtLE
                             else if ktc_pos cM k = 1 then AR_AtFirstProper
                             else AR_AtFurtherProper))
               = sim_pos ?k (go_move (m_d k) (ktc_pos cM k))"
    proof (rule ar_advance_newsimpos)
      show "2 ≤ ?k" by (rule kge2)
      show "ktc_pos cM k = 0 ⟹ m_d k ≠ MoveL" using dposL kN by blast
    qed
    have cadv_pos: "ktc_pos c'' k = (if m_d k = MoveR
                 then (if ktc_pos cM k = 0 then Suc 0
                       else sim_pos ?k (ktc_pos cM k) + ?k)
                 else (if ktc_pos cM k = 0 then Suc 0
                       else sim_pos ?k (ktc_pos cM k) + ?k)
                        - ar_disp ?k (m_d k)
                            (if ktc_pos cM k = 0 then AR_AtLE
                             else if ktc_pos cM k = 1 then AR_AtFirstProper
                             else AR_AtFurtherProper))"
      using nxt_pos c'_eq a_pos w_pos ppos_w kN by simp
    show ?thesis by (simp add: cadv_pos key posM1)
  next
    case False
    hence kge: "k_ktm M ≤ k" by simp
    have dN: "m_d k = MoveN" using dsupp kge by blast
    have posM1: "ktc_pos cMn k = go_move (m_d k) (ktc_pos cM k)"
      using cMn_def cM_eq by simp
    have "ktc_pos c'' k = ktc_pos c_b k"
      using nxt_pos c'_eq a_pos w_pos cwpost_pos cw_eq_cr r_pos kge by simp
    also have "… = sim_pos ?k (ktc_pos cM k)" using ppos by simp
    also have "… = sim_pos ?k (ktc_pos cMn k)" using posM1 dN by simp
    finally show ?thesis .
  qed
  have aposk_1: "?aposk k = AR_AtLE ⟷ ktc_pos cMn k = 0" for k
  proof (cases "k < k_ktm M")
    case kN: True
    have posM1: "ktc_pos cMn k = go_move (m_d k) (ktc_pos cM k)"
      using cMn_def cM_eq by simp
    have key: "(ar_newpos (m_d k)
                  (if ktc_pos cM k = 0 then AR_AtLE
                   else if ktc_pos cM k = 1 then AR_AtFirstProper
                   else AR_AtFurtherProper) = AR_AtLE)
                 ⟷ go_move (m_d k) (ktc_pos cM k) = 0"
    proof (rule ar_newpos_atLE_iff)
      show "ktc_pos cM k = 0 ⟹ m_d k ≠ MoveL" using dposL kN by blast
    qed
    have aposk_k: "?aposk k = ar_newpos (m_d k)
                     (if ktc_pos cM k = 0 then AR_AtLE
                      else if ktc_pos cM k = 1 then AR_AtFirstProper
                      else AR_AtFurtherProper)"
      using kN by simp
    show ?thesis by (simp add: aposk_k key posM1)
  next
    case False
    hence kge: "k_ktm M ≤ k" by simp
    have dN: "m_d k = MoveN" using dsupp kge by blast
    have p0: "ktc_pos cM k = 0" using padpos0 kge by blast
    have posM1: "ktc_pos cMn k = go_move (m_d k) (ktc_pos cM k)"
      using cMn_def cM_eq by simp
    have "ktc_pos cMn k = 0" using posM1 dN p0 by simp
    moreover have "posk k = AR_AtLE" using posk_tail kge by blast
    moreover have "?aposk k = posk k" using kge by simp
    ultimately show ?thesis by simp
  qed
  have pad_c'': "∀j ≥ k_ktm M. ktc_tape c'' j (ktc_pos c'' j) = BLANK4"
  proof (intro allI impI)
    fix j assume jk: "k_ktm M ≤ j"
    have "ktc_pos c'' j = ktc_pos c_write j"
      using nxt_pos c'_eq a_pos jk by simp
    moreover have "ktc_tape c'' j = ktc_tape c_write j"
      using nxt_tape c'_eq a_tape by simp
    ultimately show "ktc_tape c'' j (ktc_pos c'' j) = BLANK4"
      using pad_cwrite jk by simp
  qed
  have src_read'': "ar_stage_bounded (bl_ktm M) (k_ktm M)
                      (AR_SimRead, 0, 0, m_a', m_d, ?aposk)"
    using kpos_ktm dsupp posk_tail by (simp add: ar_stage_bounded_def)
  show ?thesis
  proof (intro exI[where x = cMn] conjI)
    show "(cM, cMn) ∈ ktm_step (delta_ktm M)" by (rule m_step)
    show "ar_walker_at_boundary M cMn c''"
    proof -
      consider
          (cont) "q' ∉ {t_ktm M, r_ktm M}"
                 "ktc_state c'' = (q', AR_SimRead, 0, 0, m_a', m_d, ?aposk)"
        | (acc)  "q' = t_ktm M"
                 "ktc_state c'' = (t_ktm M, ar_accept_stage (bl_ktm M))"
        | (rej)  "q' = r_ktm M"
                 "ktc_state c'' = (r_ktm M, ar_reject_stage (bl_ktm M))"
        using nxt_disj by blast
      thus ?thesis
      proof cases
        case cont
        have notT: "q' ≠ t_ktm M" using cont(1) by simp
        have notR: "q' ≠ r_ktm M" using cont(1) by simp
        show ?thesis
          unfolding ar_walker_at_boundary_def
        proof (intro conjI)
          show "ar_simulates M cMn c''"
            by (simp add: ar_simulates_def Let_def cont(2) st_cMn notT notR
                          tcorr_1 apos_1)
          show "ar_posk_consistent M cMn c''"
            by (simp add: ar_posk_consistent_def cont(2) aposk_1)
          show "ar_at_read_boundary M c''"
            by (simp add: ar_at_read_boundary_def cont(2) a'G pad_c'' src_read'')
        qed
      next
        case acc
        show ?thesis
          unfolding ar_walker_at_boundary_def
        proof (intro conjI)
          show "ar_simulates M cMn c''"
            by (simp add: ar_simulates_def Let_def acc(2) st_cMn acc(1)
                          tcorr_1 ar_accept_stage_def)
          show "ar_posk_consistent M cMn c''"
            by (simp add: ar_posk_consistent_def acc(2) ar_accept_stage_def)
          show "ar_at_read_boundary M c''"
            by (simp add: ar_at_read_boundary_def acc(2) ar_accept_stage_def
                          pad_c'')
        qed
      next
        case rej
        show ?thesis
          unfolding ar_walker_at_boundary_def
        proof (intro conjI)
          show "ar_simulates M cMn c''"
            by (simp add: ar_simulates_def Let_def rej(2) st_cMn rej(1)
                          tcorr_1 ar_reject_stage_def)
          show "ar_posk_consistent M cMn c''"
            by (simp add: ar_posk_consistent_def rej(2) ar_reject_stage_def)
          show "ar_at_read_boundary M c''"
            by (simp add: ar_at_read_boundary_def rej(2) ar_reject_stage_def
                          pad_c'')
        qed
      qed
    qed
  qed
qed

subsection ‹The reverse simulation, one cycle at a time›

text ‹The reverse-direction loop invariant: the substep-walker is in
  ∗‹some› stage of the cycle.  Six disjuncts, one per walker
  predicate.  This is the AR analogue of
  carrying ‹ae_simulates› across AE's reverse induction, but
  stage-granular: where AE peels a whole fixed-length cycle per
  ‹ae_backward_stage›, AR peels one ‹M'›-substep and dispatches on
  the current substep tag, because here the length of a cycle depends on
  the data.›

definition ar_walker ::
  "('q, 'a) ktm
    ⇒ ('a, 'q) ktc_config
    ⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
  "ar_walker M cM c' ⟷
     ar_walker_at_boundary M cM c'
   ∨ ar_walker_in_read M cM c'
   ∨ ar_walker_at_compute M cM c'
   ∨ ar_walker_in_write M cM c'
   ∨ ar_walker_in_advance M cM c'
   ∨ ar_walker_at_next M cM c'"

text ‹Chunked-induction engine for the reverse direction, the AR analogue of
  AE's ‹ae_simulation_phase_chunked_reverse›.  Given a finite
  ‹M'›-trace ‹(c', c_acc)› of length ‹m› ending in the canonical
  accept config ‹(t_ktm M, ar_accept_stage (bl_ktm M))› and the walker
  invariant at ‹c'› relative to a reachable ‹cM›, deliver an
  accepting ‹M›-path from ‹cM›.  Strong induction on ‹m›; at
  each level dispatch on the walker stage and peel one ‹M'›-step:

  ▪ the five active stages (‹in_read›, ‹at_compute›,
    ‹in_write›, ‹in_advance›, ‹at_next›, and an active read
    boundary) all have ‹c' ≠ c_acc›, so ‹m = Suc m'›; peel
    the step via the matching preservation lemma (‹at_compute› emits
    one ‹M›-step into the ‹in_write› witness; ‹at_next› emits
    one via ‹ar_walker_cycle_close› and advances ‹cM›), then
    recurse on ‹m'›;
  ▪ a boundary at the accept config closes the induction:
    ‹ar_simulates_accept_iff› forces ‹ktc_state cM = t_ktm M›;
  ▪ a boundary at the reject config is impossible — the trace runs to
    the accept config, but reject is terminal (‹ar_reject_terminal›)
    and the reject config is not the accept config.

  The conclusion is in ‹rtrancl› form for the downstream
  ‹Lang_ktm›-repacking in ‹alphabet_reduce_language›.›

lemma ar_simulation_phase_chunked_reverse:
  fixes M :: "('q, 'a) ktm"
    and w :: "'a list"
    and cM :: "('a, 'q) ktc_config"
    and c' c_acc :: "(sym4, 'q × 'a ar_stage) ktc_config"
    and m :: nat
  assumes vM:      "valid_ktm M"
      and w_sub:   "set w ⊆ Sigma_ktm M"
      and card_ge: "card (Γ_ktm M) ≥ 4"
      and lebl:    "le_ktm M ≠ bl_ktm M"
      and reach_M: "(init_config_ktm M w, cM) ∈ (ktm_step (delta_ktm M))*"
      and trace:   "(c', c_acc) ∈ (ktm_step (alphabet_reduce_delta M)) ^^ m"
      and accept:  "ktc_state c_acc = (t_ktm M, ar_accept_stage (bl_ktm M))"
      and walk:    "ar_walker M cM c'"
  shows "∃cM_final. (cM, cM_final) ∈ (ktm_step (delta_ktm M))*
                    ∧ ktc_state cM_final = t_ktm M"
  using reach_M trace walk
proof (induction m arbitrary: cM c' rule: less_induct)
  case (less m)
  let ?R = "ktm_step (alphabet_reduce_delta M)"
  ― ‹Encoding width ‹≥ 2› from ‹card Γ_M ≥ 4›, and the
     reachable-config invariants ‹cM› needs for the substep lemmas.›
  have kge2: "2 ≤ block_width (Γ_ktm M)"
  proof -
    have "(2::nat) ^ 2 ≤ 2 ^ block_width (Γ_ktm M)"
      using card_ge card_le_two_pow_block_width[of "Γ_ktm M"] by simp
    thus "2 ≤ block_width (Γ_ktm M)"
      using power_le_imp_le_exp[of "2::nat" 2 "block_width (Γ_ktm M)"] by simp
  qed
  have valcM: "valid_config_ktm M cM"
    by (rule valid_reach_ktm[OF vM w_sub less.prems(1)])
  have qQ: "ktc_state cM ∈ Q_ktm M" using valcM by (cases M; cases cM) auto
  have tapeG: "ktc_tape cM k (ktc_pos cM k) ∈ Γ_ktm M" for k
  proof -
    have "range (ktc_tape cM k) ⊆ Γ_ktm M"
      using valcM by (cases M; cases cM) auto
    thus ?thesis by blast
  qed
  have acc_idx: "fst (snd (ktc_state c_acc)) = AR_HaltAccept"
    using accept by (simp add: ar_accept_stage_def)
  ― ‹An active config (substep tag ‹≠ AR_HaltAccept›) cannot be
     ‹c_acc›, so the trace has a first step to peel.›
  have peel: "∃m' c'_1. m = Suc m'
                ∧ (c', c'_1) ∈ ?R ∧ (c'_1, c_acc) ∈ ?R ^^ m'"
    if notHA: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
  proof -
    have "m ≠ 0"
    proof
      assume "m = 0"
      hence "c' = c_acc" using less.prems(2) by simp
      thus False using notHA acc_idx by simp
    qed
    then obtain m' where mSuc: "m = Suc m'" using not0_implies_Suc by blast
    have "(c', c_acc) ∈ ?R ^^ Suc m'" using less.prems(2) mSuc by simp
    from relpow_Suc_D2[OF this] obtain c'_1 where
        "(c', c'_1) ∈ ?R" and "(c'_1, c_acc) ∈ ?R ^^ m'" by blast
    thus ?thesis using mSuc by blast
  qed
  from less.prems(3)
  consider (bnd) "ar_walker_at_boundary M cM c'"
         | (rd)  "ar_walker_in_read M cM c'"
         | (cmp) "ar_walker_at_compute M cM c'"
         | (wr)  "ar_walker_in_write M cM c'"
         | (adv) "ar_walker_in_advance M cM c'"
         | (nx)  "ar_walker_at_next M cM c'"
    unfolding ar_walker_def by blast
  then show ?case
  proof cases
    case bnd
    have sim: "ar_simulates M cM c'"
      using bnd unfolding ar_walker_at_boundary_def by simp
    obtain qM0 stg where st: "ktc_state c' = (qM0, stg)"
      by (cases "ktc_state c'") auto
    obtain idx tk i buf dvec posk where
        sg: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
    have state_disj:
        "(idx = AR_SimRead ∧ qM0 ∉ {t_ktm M, r_ktm M})
           ∨ (qM0 = t_ktm M ∧ stg = ar_accept_stage (bl_ktm M))
           ∨ (qM0 = r_ktm M ∧ stg = ar_reject_stage (bl_ktm M))"
      using sim st sg unfolding ar_simulates_def by (auto split: prod.splits)
    consider (active) "idx = AR_SimRead"
           | (acc)    "stg = ar_accept_stage (bl_ktm M)" "qM0 = t_ktm M"
           | (rej)    "stg = ar_reject_stage (bl_ktm M)" "qM0 = r_ktm M"
      using state_disj by blast
    thus ?thesis
    proof cases
      case active
      have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
        using st sg active by simp
      obtain m' c'_1 where mSuc: "m = Suc m'"
        and fst_step: "(c', c'_1) ∈ ?R"
        and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
        using peel[OF neq] by blast
      have m'_lt: "m' < m" using mSuc by simp
      have "ar_walker_in_read M cM c'_1 ∨ ar_walker_at_compute M cM c'_1"
        using ar_walker_step_from_boundary[OF bnd fst_step] .
      hence walk_1: "ar_walker M cM c'_1" unfolding ar_walker_def by blast
      show ?thesis using less.IH[OF m'_lt less.prems(1) rest walk_1] .
    next
      case acc
      have c'_acc: "ktc_state c' = (t_ktm M, ar_accept_stage (bl_ktm M))"
        using st sg acc by simp
      have cM_t: "ktc_state cM = t_ktm M"
        using ar_simulates_accept_iff[OF vM sim] c'_acc by simp
      have "(cM, cM) ∈ (ktm_step (delta_ktm M))*" by simp
      thus ?thesis using cM_t by blast
    next
      case rej
      have c'_rej: "ktc_state c' = (r_ktm M, ar_reject_stage (bl_ktm M))"
        using st sg rej by simp
      show ?thesis
      proof (cases m)
        case 0
        have ceq: "c' = c_acc" using less.prems(2) 0 by simp
        have "fst (snd (ktc_state c')) = AR_HaltReject"
          using c'_rej by (simp add: ar_reject_stage_def)
        moreover have "fst (snd (ktc_state c')) = AR_HaltAccept"
          using ceq accept by (simp add: ar_accept_stage_def)
        ultimately show ?thesis by simp
      next
        case (Suc m')
        have "(c', c_acc) ∈ ?R ^^ Suc m'" using less.prems(2) Suc by simp
        from relpow_Suc_D2[OF this] obtain c'_1 where
            fst_step: "(c', c'_1) ∈ ?R" by blast
        have "ktc_state c' ≠ (r_ktm M, ar_reject_stage (bl_ktm M))"
          by (rule ar_reject_terminal[OF vM card_ge fst_step])
        thus ?thesis using c'_rej by simp
      qed
    qed
  next
    case rd
    have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
      using rd unfolding ar_walker_in_read_def by simp
    obtain m' c'_1 where mSuc: "m = Suc m'"
      and fst_step: "(c', c'_1) ∈ ?R"
      and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
      using peel[OF neq] by blast
    have m'_lt: "m' < m" using mSuc by simp
    have "ar_walker_in_read M cM c'_1 ∨ ar_walker_at_compute M cM c'_1"
      using ar_walker_step_from_in_read[OF rd fst_step] .
    hence walk_1: "ar_walker M cM c'_1" unfolding ar_walker_def by blast
    show ?thesis using less.IH[OF m'_lt less.prems(1) rest walk_1] .
  next
    case cmp
    have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
      using cmp unfolding ar_walker_at_compute_def by simp
    obtain m' c'_1 where mSuc: "m = Suc m'"
      and fst_step: "(c', c'_1) ∈ ?R"
      and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
      using peel[OF neq] by blast
    have m'_lt: "m' < m" using mSuc by simp
    have w_1: "ar_walker_in_write M cM c'_1"
      using ar_walker_step_from_at_compute[OF cmp fst_step vM qQ kge2 tapeG] .
    have walk_1: "ar_walker M cM c'_1" using w_1 unfolding ar_walker_def by blast
    show ?thesis using less.IH[OF m'_lt less.prems(1) rest walk_1] .
  next
    case wr
    have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
      using wr unfolding ar_walker_in_write_def by simp
    obtain m' c'_1 where mSuc: "m = Suc m'"
      and fst_step: "(c', c'_1) ∈ ?R"
      and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
      using peel[OF neq] by blast
    have m'_lt: "m' < m" using mSuc by simp
    have "ar_walker_in_write M cM c'_1 ∨ ar_walker_in_advance M cM c'_1"
      using ar_walker_step_from_in_write[OF wr fst_step] .
    hence walk_1: "ar_walker M cM c'_1" unfolding ar_walker_def by blast
    show ?thesis using less.IH[OF m'_lt less.prems(1) rest walk_1] .
  next
    case adv
    have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
      using adv unfolding ar_walker_in_advance_def by simp
    obtain m' c'_1 where mSuc: "m = Suc m'"
      and fst_step: "(c', c'_1) ∈ ?R"
      and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
      using peel[OF neq] by blast
    have m'_lt: "m' < m" using mSuc by simp
    have "ar_walker_in_advance M cM c'_1 ∨ ar_walker_at_next M cM c'_1"
      using ar_walker_step_from_in_advance[OF adv fst_step] .
    hence walk_1: "ar_walker M cM c'_1" unfolding ar_walker_def by blast
    show ?thesis using less.IH[OF m'_lt less.prems(1) rest walk_1] .
  next
    case nx
    have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
      using nx unfolding ar_walker_at_next_def by simp
    obtain m' c'_1 where mSuc: "m = Suc m'"
      and fst_step: "(c', c'_1) ∈ ?R"
      and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
      using peel[OF neq] by blast
    have m'_lt: "m' < m" using mSuc by simp
    obtain cMn where step_cMn: "(cM, cMn) ∈ ktm_step (delta_ktm M)"
      and bnd_1: "ar_walker_at_boundary M cMn c'_1"
      using ar_walker_cycle_close[OF nx fst_step vM qQ kge2 tapeG
                                     w_sub less.prems(1) lebl]
      by blast
    have reach_Mn: "(init_config_ktm M w, cMn) ∈ (ktm_step (delta_ktm M))*"
      using less.prems(1) step_cMn by (rule rtrancl.rtrancl_into_rtrancl)
    have walk_1: "ar_walker M cMn c'_1"
      using bnd_1 unfolding ar_walker_def by blast
    obtain cM_final where
        run_final: "(cMn, cM_final) ∈ (ktm_step (delta_ktm M))*"
      and acc_final: "ktc_state cM_final = t_ktm M"
      using less.IH[OF m'_lt reach_Mn rest walk_1] by blast
    have "(cM, cM_final) ∈ (ktm_step (delta_ktm M))*"
      using step_cMn run_final by (meson r_into_rtrancl rtrancl_trans)
    thus ?thesis using acc_final by blast
  qed
qed

text ‹Classical language-equivalence (biconditional) for alphabet
  reduction: an ‹'a›-word ‹w› over the input alphabet is in
  ‹M›'s language iff its ‹sym4›-encoding is in the language
  of the reduced machine ‹M'›.  Pairs the forward inclusion
  ‹alphabet_reduce_language_forward› (in
  ‹AlphabetReduction_Theorems.thy›) with the reverse leg supplied by
  ‹ar_simulation_phase_chunked_reverse›.

  Unlike AE, the alphabet-reduction construction has no input
  validation prefix (the no-validation design point), so the reverse
  direction needs neither a validation-peel nor a determinism /
  chain-uniqueness argument: the encoded input's accepting ‹M'›-run
  is handed to the engine directly off the initial read-boundary
  correspondence (‹ar_walker_at_boundary›, the conjunction of the
  three ‹_init› invariants).  No ‹det_ktm› hypothesis is
  required.

  The ‹set w ⊆ Sigma_ktm M› guard is required (and matches
  AE's statement): ‹Lang_ktm› bakes in the input-alphabet
  restriction, so ‹w ∈ Lang_ktm M› supplies the guard for
  free in the forward direction, but membership of the encoded word
  in ‹Lang_ktm M'› says nothing about ‹w›'s alphabet.  For
  ‹w› outside the input alphabet the encoded word can still be
  accepted by ‹M'› while ‹w ∉ Lang_ktm M›.›

theorem alphabet_reduce_language:
  fixes M :: "('q, 'a) ktm"
  assumes vM:        "valid_ktm M"
      and s_neq_t:   "s_ktm M ≠ t_ktm M"
      and s_neq_r:   "s_ktm M ≠ r_ktm M"
      and le_neq_bl: "le_ktm M ≠ bl_ktm M"
      and card_ge:   "card (Γ_ktm M) ≥ 4"
  shows "∀w. set w ⊆ Sigma_ktm M
              ⟶ (encode_input_ar (Γ_ktm M) (bl_ktm M) w ∈ Lang_ktm
                      (alphabet_reduce M
                         :: ('q × 'a ar_stage, sym4) ktm))
                  = (w ∈ Lang_ktm M)"
proof -
  let ?M' = "alphabet_reduce M :: ('q × 'a ar_stage, sym4) ktm"
  have fwd: "∀w. set w ⊆ Sigma_ktm M
                  ⟶ w ∈ Lang_ktm M
                  ⟶ encode_input_ar (Γ_ktm M) (bl_ktm M) w ∈ Lang_ktm ?M'"
    by (rule alphabet_reduce_language_forward[OF vM s_neq_t s_neq_r le_neq_bl card_ge])
  show ?thesis
  proof (intro allI impI)
    fix w :: "'a list"
    assume w_sub: "set w ⊆ Sigma_ktm M"
    let ?enc = "encode_input_ar (Γ_ktm M) (bl_ktm M) w"
    let ?c'  = "init_config_ktm ?M' ?enc"
    show "(?enc ∈ Lang_ktm ?M') = (w ∈ Lang_ktm M)"
    proof
      assume w_in_M: "w ∈ Lang_ktm M"
      from fwd w_sub w_in_M show "?enc ∈ Lang_ktm ?M'" by blast
    next
      ― ‹Reverse direction: an accepting ‹M'›-run on the encoded
          input yields an accepting ‹M›-run on ‹w›.  No
          validation prefix to peel, so the accepting trace feeds the
          chunked-reverse engine directly off the initial read-boundary
          correspondence.›
      assume enc_in_M': "?enc ∈ Lang_ktm ?M'"
      ― ‹Step 1: unpack the ‹M'›-acceptance into a relpow trace.›
      from enc_in_M' obtain wM' nM' where
          acc_path_M':
            "(?c', KConfig (t_ktm ?M') wM' nM')
                ∈ (ktm_step (delta_ktm ?M'))*"
        unfolding Lang_ktm_def by blast
      have acc_path:
          "(?c', KConfig (t_ktm ?M') wM' nM')
              ∈ (ktm_step (alphabet_reduce_delta M))*"
        using acc_path_M' by simp
      obtain m where trace:
          "(?c', KConfig (t_ktm ?M') wM' nM')
              ∈ (ktm_step (alphabet_reduce_delta M)) ^^ m"
        using acc_path rtrancl_imp_relpow by metis
      ― ‹Step 2: the accept state in the engine's canonical form.›
      have accept:
          "ktc_state (KConfig (t_ktm ?M') wM' nM')
              = (t_ktm M, ar_accept_stage (bl_ktm M))"
        by simp
      ― ‹Step 3: the initial read-boundary correspondence is the
          walker's boundary disjunct.›
      have sim:  "ar_simulates M (init_config_ktm M w) ?c'"
        by (rule ar_simulates_init[OF vM w_sub s_neq_t s_neq_r])
      have posk: "ar_posk_consistent M (init_config_ktm M w) ?c'"
        by (rule ar_posk_consistent_init)
      have rbnd: "ar_at_read_boundary M ?c'"
        by (rule ar_at_read_boundary_init[OF vM])
      have walk: "ar_walker M (init_config_ktm M w) ?c'"
        unfolding ar_walker_def ar_walker_at_boundary_def
        using sim posk rbnd by blast
      ― ‹Step 4: seed with the reflexive reach and run the engine.›
      have reach_refl: "(init_config_ktm M w, init_config_ktm M w)
                          ∈ (ktm_step (delta_ktm M))*" by simp
      obtain cM_final where
          M_path: "(init_config_ktm M w, cM_final)
                      ∈ (ktm_step (delta_ktm M))*"
        and M_acc: "ktc_state cM_final = t_ktm M"
        using ar_simulation_phase_chunked_reverse
                [OF vM w_sub card_ge le_neq_bl reach_refl trace accept walk]
        by blast
      ― ‹Step 5: repack as ‹w ∈ Lang_ktm M›.›
      obtain wM_acc nM_acc where
          cM_final_eq: "cM_final = KConfig (t_ktm M) wM_acc nM_acc"
        using M_acc by (cases cM_final) simp
      show "w ∈ Lang_ktm M"
        unfolding Lang_ktm_def
        using w_sub M_path cM_final_eq by blast
    qed
  qed
qed

end