Theory AlphabetReduction_ForwardWrite

theory AlphabetReduction_ForwardWrite
  imports AlphabetReduction_ForwardRead
begin

subsection ‹Write phase composition›

lemma ar_write_back_loop:
  fixes M :: "('q, 'a) ktm"
    and c0 :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes vM: "valid_ktm M"
      and qQ: "q ∈ Q_ktm M"
      and kge2: "2 ≤ block_width (Γ_ktm M)"
      and poskproper: "posk tk ≠ AR_AtLE"
      and stg: "ktc_state c0 = (q, AR_SimWrite, tk, 0, buf, dvec, posk)"
      and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
      and pos_base: "ktc_pos c0 tk = base + block_width (Γ_ktm M)"
      and notLE: "⋀m. ⟦ 1 ≤ m; m ≤ block_width (Γ_ktm M) ⟧
                   ⟹ ktc_tape c0 tk (base + m) ≠ LE4"
      and pad0: "∀j ≥ k_ktm M. ktc_tape c0 j (ktc_pos c0 j) = BLANK4"
      and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                   (AR_SimWrite, tk, 0, buf, dvec, posk)"
  shows "∃c'. (c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ block_width (Γ_ktm M)
              ∧ ktc_state c' = (q, AR_SimWrite, tk, block_width (Γ_ktm M),
                                  buf, dvec, posk)
              ∧ ktc_pos c' tk = base
              ∧ ktc_tape c' = ktc_tape c0
              ∧ (∀k'. k' ≠ tk ⟶ ktc_pos c' k' = ktc_pos c0 k')"
proof -
  let ?k = "block_width (Γ_ktm M)"
  let ?P = "λj c.
       ktc_state c = (q, AR_SimWrite, tk, j, buf, dvec, posk)
     ∧ ktc_pos c tk = base + (?k - j)
     ∧ ktc_tape c = ktc_tape c0
     ∧ (∀k'. k' ≠ tk ⟶ ktc_pos c k' = ktc_pos c0 k')"
  have mybase: "?P 0 c0" using stg pos_base by simp
  have mystep:
      "⋀j cc. ⟦ j < ?k; ?P j cc ⟧
              ⟹ ∃c''. (cc, c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M))
                          ∧ ?P (Suc j) c''"
  proof -
    fix j cc
    assume jlt: "j < ?k" and Pj: "?P j cc"
    from Pj have st_cc:
        "ktc_state cc = (q, AR_SimWrite, tk, j, buf, dvec, posk)"
      and pos_cc: "ktc_pos cc tk = base + (?k - j)"
      and tape_cc: "ktc_tape cc = ktc_tape c0"
      and other_cc: "∀k'. k' ≠ tk ⟶ ktc_pos cc k' = ktc_pos c0 k'"
      by simp_all
    have tk_lt: "tk < k_ktm M" using src0 by (simp add: ar_stage_bounded_def)
    have pad_cc: "∀j' ≥ k_ktm M. ktc_tape cc j' (ktc_pos cc j') = BLANK4"
    proof (intro allI impI)
      fix j' assume jge: "k_ktm M ≤ j'"
      have jne: "j' ≠ tk" using jge tk_lt by simp
      have "ktc_tape cc j' (ktc_pos cc j') = ktc_tape c0 j' (ktc_pos c0 j')"
        using tape_cc other_cc jne by simp
      thus "ktc_tape cc j' (ktc_pos cc j') = BLANK4" using pad0 jge by simp
    qed
    have src_cc: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                    (AR_SimWrite, tk, j, buf, dvec, posk)"
      using src0 by (simp add: ar_stage_bounded_def)
    have mge1: "1 ≤ ?k - j" using jlt by simp
    have mlek: "?k - j ≤ ?k" by simp
    have suc_le: "Suc j ≤ ?k" using jlt by simp
    have jlt2: "j < 2 * ?k" using jlt by simp
    have ksub: "?k - j = Suc (?k - Suc j)" using jlt by simp
    have vsrc_cc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
                     (AR_SimWrite, tk, j, buf, dvec, posk)"
      using jlt2 buf_valid by (simp add: ar_valid_stage_def)
    have notLE_cc: "ktc_tape cc tk (ktc_pos cc tk) ≠ LE4"
      using tape_cc pos_cc notLE[OF mge1 mlek] by simp
    obtain c'' where
        bstep: "(cc, c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M))"
      and bst_state: "ktc_state c'' = (q, AR_SimWrite, tk, Suc j, buf, dvec, posk)"
      and bst_tape: "ktc_tape c'' = ktc_tape cc"
      and bst_pos: "ktc_pos c'' = (ktc_pos cc)(tk := ktc_pos cc tk - 1)"
      using ar_write_walk_step
              [OF vM st_cc qQ poskproper notLE_cc suc_le vsrc_cc pad_cc src_cc]
      by blast
    have pos_eq: "ktc_pos c'' tk = base + (?k - Suc j)"
      using bst_pos pos_cc ksub by simp
    have tape_eq: "ktc_tape c'' = ktc_tape c0" using bst_tape tape_cc by simp
    have other_eq: "∀k'. k' ≠ tk ⟶ ktc_pos c'' k' = ktc_pos c0 k'"
      using bst_pos other_cc by simp
    show "∃c''. (cc, c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M))
                ∧ ?P (Suc j) c''"
      using bstep bst_state pos_eq tape_eq other_eq by blast
  qed
  have loop:
      "∃c'. (c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ ?k
            ∧ ?P ?k c'"
    by (rule relpow_invariant_chain
          [where P = ?P and n = ?k, OF mystep mybase])
  obtain c' where
      chain: "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ ?k"
    and Pfin: "?P ?k c'"
    using loop by blast
  show ?thesis
  proof (intro exI[where x = c'] conjI)
    show "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ ?k" by (rule chain)
    show "ktc_state c' = (q, AR_SimWrite, tk, ?k, buf, dvec, posk)"
      using Pfin by simp
    show "ktc_pos c' tk = base" using Pfin by simp
    show "ktc_tape c' = ktc_tape c0" using Pfin by simp
    show "∀k'. k' ≠ tk ⟶ ktc_pos c' k' = ktc_pos c0 k'" using Pfin by simp
  qed
qed

text ‹The write forward bit-write loop, proper tape.  From an
  ‹AR_SimWrite› stage at bit-counter ‹b› with the head back
  at ‹base› (where ‹ar_write_back_loop› left it), the head
  walks ‹R› across the block writing each cell, reaching
  bit-counter ‹b + (b - 1)› with the head at ‹base + (b -
  1)›.  Unlike the read loops this loop ∗‹mutates› the
  tape: its invariant carries a partially-overwritten tape (cells
  ‹base … base + j - 1› already hold the new
  ‹write_bit› image, the rest hold old content), and each
  ‹ar_write_bit_step›'s ‹≠ LE4› guard reads the
  ∗‹not-yet-written› current cell ‹base + j›, which
  still holds old content (supplied ‹≠ LE4› by
  ‹notLE›).  Writes the first ‹b - 1› cells; the last is
  the boundary step's job.  Chain length ‹b - 1›.›

lemma ar_write_fwd_loop:
  fixes M :: "('q, 'a) ktm"
    and c0 :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes vM: "valid_ktm M"
      and qQ: "q ∈ Q_ktm M"
      and kge2: "2 ≤ block_width (Γ_ktm M)"
      and poskproper: "posk tk ≠ AR_AtLE"
      and stg: "ktc_state c0 = (q, AR_SimWrite, tk, block_width (Γ_ktm M),
                                 buf, dvec, posk)"
      and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
      and pos_base: "ktc_pos c0 tk = base"
      and notLE: "⋀m. m < block_width (Γ_ktm M)
                   ⟹ ktc_tape c0 tk (base + m) ≠ LE4"
      and pad0: "∀j ≥ k_ktm M. ktc_tape c0 j (ktc_pos c0 j) = BLANK4"
      and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                   (AR_SimWrite, tk, block_width (Γ_ktm M), buf, dvec, posk)"
  shows "∃c'. (c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (block_width (Γ_ktm M) - 1)
              ∧ ktc_state c' = (q, AR_SimWrite, tk,
                    block_width (Γ_ktm M) + (block_width (Γ_ktm M) - 1),
                    buf, dvec, posk)
              ∧ ktc_pos c' tk = base + (block_width (Γ_ktm M) - 1)
              ∧ ktc_tape c' tk = (λpos.
                    if base ≤ pos ∧ pos < base + (block_width (Γ_ktm M) - 1)
                    then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
                    else ktc_tape c0 tk pos)
              ∧ (∀k'. k' ≠ tk ⟶ ktc_tape c' k' = ktc_tape c0 k')
              ∧ (∀k'. k' ≠ tk ⟶ ktc_pos c' k' = ktc_pos c0 k')"
proof -
  let ?k = "block_width (Γ_ktm M)"
  let ?G = "Γ_ktm M" and ?bl = "bl_ktm M"
  let ?wb = "λm. write_bit ?G ?bl (buf tk) m"
  let ?tape = "λj pos. if base ≤ pos ∧ pos < base + j
                        then ?wb (pos - base) else ktc_tape c0 tk pos"
  let ?P = "λj c.
       ktc_state c = (q, AR_SimWrite, tk, ?k + j, buf, dvec, posk)
     ∧ ktc_pos c tk = base + j
     ∧ ktc_tape c tk = ?tape j
     ∧ (∀k'. k' ≠ tk ⟶ ktc_tape c k' = ktc_tape c0 k')
     ∧ (∀k'. k' ≠ tk ⟶ ktc_pos c k' = ktc_pos c0 k')"
  have mybase: "?P 0 c0"
  proof -
    have "?tape 0 = ktc_tape c0 tk" by (rule ext) auto
    thus ?thesis using stg pos_base by simp
  qed
  have mystep:
      "⋀j cc. ⟦ j < ?k - 1; ?P j cc ⟧
              ⟹ ∃c''. (cc, c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M))
                          ∧ ?P (Suc j) c''"
  proof -
    fix j cc
    assume jlt: "j < ?k - 1" and Pj: "?P j cc"
    from Pj have st_cc:
        "ktc_state cc = (q, AR_SimWrite, tk, ?k + j, buf, dvec, posk)"
      and pos_cc: "ktc_pos cc tk = base + j"
      and tape_cc: "ktc_tape cc tk = ?tape j"
      and otape_cc: "∀k'. k' ≠ tk ⟶ ktc_tape cc k' = ktc_tape c0 k'"
      and opos_cc: "∀k'. k' ≠ tk ⟶ ktc_pos cc k' = ktc_pos c0 k'"
      by simp_all
    have tk_lt: "tk < k_ktm M" using src0 by (simp add: ar_stage_bounded_def)
    have pad_cc: "∀j' ≥ k_ktm M. ktc_tape cc j' (ktc_pos cc j') = BLANK4"
    proof (intro allI impI)
      fix j' assume jge: "k_ktm M ≤ j'"
      have jne: "j' ≠ tk" using jge tk_lt by simp
      have "ktc_tape cc j' (ktc_pos cc j') = ktc_tape c0 j' (ktc_pos c0 j')"
        using otape_cc opos_cc jne by simp
      thus "ktc_tape cc j' (ktc_pos cc j') = BLANK4" using pad0 jge by simp
    qed
    have src_cc: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                    (AR_SimWrite, tk, ?k + j, buf, dvec, posk)"
      using src0 by (simp add: ar_stage_bounded_def)
    have jltk: "j < ?k" using jlt by simp
    have ilo: "?k ≤ ?k + j" by simp
    have ihi: "Suc (?k + j) < 2 * ?k" using jlt by simp
    have idx: "?k + j - ?k = j" by simp
    have vsrc_cc: "ar_valid_stage ?G ?bl
                     (AR_SimWrite, tk, ?k + j, buf, dvec, posk)"
      using ihi buf_valid by (simp add: ar_valid_stage_def)
    have cell_cur: "ktc_tape cc tk (ktc_pos cc tk) = ktc_tape c0 tk (base + j)"
      using tape_cc pos_cc by simp
    have notLE_cc: "ktc_tape cc tk (ktc_pos cc tk) ≠ LE4"
      using cell_cur notLE[OF jltk] by simp
    obtain c'' where
        bstep: "(cc, c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M))"
      and bst_state: "ktc_state c'' = (q, AR_SimWrite, tk, Suc (?k + j),
                                        buf, dvec, posk)"
      and bst_tape: "ktc_tape c'' = (ktc_tape cc)(tk :=
            (ktc_tape cc tk)(ktc_pos cc tk := ?wb (?k + j - ?k)))"
      and bst_pos: "ktc_pos c'' = (ktc_pos cc)(tk := Suc (ktc_pos cc tk))"
      using ar_write_bit_step
              [OF vM st_cc qQ poskproper notLE_cc ilo ihi vsrc_cc pad_cc src_cc]
      by blast
    have state_eq: "ktc_state c'' = (q, AR_SimWrite, tk, ?k + Suc j, buf, dvec, posk)"
      using bst_state by simp
    have pos_eq: "ktc_pos c'' tk = base + Suc j"
      using bst_pos pos_cc by simp
    have lhs: "ktc_tape c'' tk = (?tape j)(base + j := ?wb j)"
      using bst_tape tape_cc pos_cc idx by simp
    have tape_eq: "ktc_tape c'' tk = ?tape (Suc j)"
    proof (rule ext)
      fix pos
      show "ktc_tape c'' tk pos = ?tape (Suc j) pos"
      proof (cases "pos = base + j")
        case True
        thus ?thesis using lhs by simp
      next
        case False
        have "ktc_tape c'' tk pos = ?tape j pos" using lhs False by simp
        thus ?thesis using False by (auto simp: less_Suc_eq)
      qed
    qed
    have otape_eq: "∀k'. k' ≠ tk ⟶ ktc_tape c'' k' = ktc_tape c0 k'"
      using bst_tape otape_cc by simp
    have opos_eq: "∀k'. k' ≠ tk ⟶ ktc_pos c'' k' = ktc_pos c0 k'"
      using bst_pos opos_cc by simp
    show "∃c''. (cc, c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M))
                ∧ ?P (Suc j) c''"
      using bstep state_eq pos_eq tape_eq otape_eq opos_eq by blast
  qed
  have loop:
      "∃c'. (c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (?k - 1)
            ∧ ?P (?k - 1) c'"
    by (rule relpow_invariant_chain
          [where P = ?P and n = "?k - 1", OF mystep mybase])
  obtain c' where
      chain: "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (?k - 1)"
    and Pfin: "?P (?k - 1) c'"
    using loop by blast
  show ?thesis
  proof (intro exI[where x = c'] conjI)
    show "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (?k - 1)"
      by (rule chain)
    show "ktc_state c' = (q, AR_SimWrite, tk, ?k + (?k - 1), buf, dvec, posk)"
      using Pfin by simp
    show "ktc_pos c' tk = base + (?k - 1)" using Pfin by simp
    show "ktc_tape c' tk = (λpos.
            if base ≤ pos ∧ pos < base + (?k - 1)
            then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
            else ktc_tape c0 tk pos)"
      using Pfin by simp
    show "∀k'. k' ≠ tk ⟶ ktc_tape c' k' = ktc_tape c0 k'" using Pfin by simp
    show "∀k'. k' ≠ tk ⟶ ktc_pos c' k' = ktc_pos c0 k'" using Pfin by simp
  qed
qed

text ‹The proper-cell single-tape write prefix: the part of a
  proper-cell single-tape write shared by the non-last
  (‹boundary›) and last (‹finish›) variants.  From an
  ‹AR_SimWrite› stage at bit-counter ‹0› with the head at
  the block end ‹base + b› and ‹buf tk› a proper symbol,
  it fires the back-walk loop (‹ar_write_back_loop›, head to
  ‹base›) and the forward bit-write loop
  (‹ar_write_fwd_loop›, writing the first ‹b - 1›
  cells), reaching bit-counter ‹b + (b - 1)› with the head at
  ‹base + (b - 1)›.  The remaining last-cell step (boundary or
  finish) is added by the consumer.  The two segment costs compose by
  ‹relpow_add› on ‹relcompI› (chain length ‹b + (b
  - 1)›).  The ‹notLE› hypothesis (every block cell and the
  next-block lead cell ‹≠ LE4›) feeds both loops.›

lemma ar_write_proper_prefix:
  fixes M :: "('q, 'a) ktm"
    and c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes vM: "valid_ktm M"
      and qQ: "q ∈ Q_ktm M"
      and kge2: "2 ≤ block_width (Γ_ktm M)"
      and poskproper: "posk tk ≠ AR_AtLE"
      and stg: "ktc_state c' = (q, AR_SimWrite, tk, 0, buf, dvec, posk)"
      and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
      and pos_base: "ktc_pos c' tk = base + block_width (Γ_ktm M)"
      and notLE: "⋀m. m ≤ block_width (Γ_ktm M)
                   ⟹ ktc_tape c' tk (base + m) ≠ LE4"
      and pad0: "∀j ≥ k_ktm M. ktc_tape c' j (ktc_pos c' j) = BLANK4"
      and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                   (AR_SimWrite, tk, 0, buf, dvec, posk)"
  shows "∃c2. (c', c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (block_width (Γ_ktm M) + (block_width (Γ_ktm M) - 1))
              ∧ ktc_state c2 = (q, AR_SimWrite, tk,
                    block_width (Γ_ktm M) + (block_width (Γ_ktm M) - 1),
                    buf, dvec, posk)
              ∧ ktc_tape c2 = (ktc_tape c')(tk := (λpos.
                    if base ≤ pos ∧ pos < base + (block_width (Γ_ktm M) - 1)
                    then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
                    else ktc_tape c' tk pos))
              ∧ ktc_pos c2 = (ktc_pos c')(tk := base + (block_width (Γ_ktm M) - 1))"
proof -
  let ?k = "block_width (Γ_ktm M)"
  let ?R = "ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)"
  have notLE_back: "⋀m. ⟦ 1 ≤ m; m ≤ ?k ⟧
                      ⟹ ktc_tape c' tk (base + m) ≠ LE4"
    using notLE by blast
  obtain c1 where
      ch1: "(c', c1) ∈ ?R ^^ ?k"
    and st1: "ktc_state c1 = (q, AR_SimWrite, tk, ?k, buf, dvec, posk)"
    and pos1: "ktc_pos c1 tk = base"
    and tape1: "ktc_tape c1 = ktc_tape c'"
    and opos1: "∀k'. k' ≠ tk ⟶ ktc_pos c1 k' = ktc_pos c' k'"
    using ar_write_back_loop[OF vM qQ kge2 poskproper stg buf_valid pos_base notLE_back
                       pad0 src0]
    by blast
  have notLE_fwd: "⋀m. m < ?k ⟹ ktc_tape c1 tk (base + m) ≠ LE4"
  proof -
    fix m :: nat assume mlt: "m < ?k"
    have mle: "m ≤ ?k" using mlt by simp
    show "ktc_tape c1 tk (base + m) ≠ LE4"
      using notLE[OF mle] tape1 by simp
  qed
  have tk_lt: "tk < k_ktm M" using src0 by (simp add: ar_stage_bounded_def)
  have pad_c1: "∀j ≥ k_ktm M. ktc_tape c1 j (ktc_pos c1 j) = BLANK4"
  proof (intro allI impI)
    fix j assume jge: "k_ktm M ≤ j"
    have jne: "j ≠ tk" using jge tk_lt by simp
    have "ktc_tape c1 j (ktc_pos c1 j) = ktc_tape c' j (ktc_pos c' j)"
      using tape1 opos1 jne by simp
    thus "ktc_tape c1 j (ktc_pos c1 j) = BLANK4" using pad0 jge by simp
  qed
  have src_c1: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                  (AR_SimWrite, tk, block_width (Γ_ktm M), buf, dvec, posk)"
    using src0 by (simp add: ar_stage_bounded_def)
  obtain c2 where
      ch2: "(c1, c2) ∈ ?R ^^ (?k - 1)"
    and st2: "ktc_state c2 = (q, AR_SimWrite, tk, ?k + (?k - 1), buf, dvec, posk)"
    and pos2: "ktc_pos c2 tk = base + (?k - 1)"
    and tape2: "ktc_tape c2 tk = (λpos.
          if base ≤ pos ∧ pos < base + (?k - 1)
          then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
          else ktc_tape c1 tk pos)"
    and otape2: "∀k'. k' ≠ tk ⟶ ktc_tape c2 k' = ktc_tape c1 k'"
    and opos2: "∀k'. k' ≠ tk ⟶ ktc_pos c2 k' = ktc_pos c1 k'"
    using ar_write_fwd_loop[OF vM qQ kge2 poskproper st1 buf_valid pos1 notLE_fwd
                      pad_c1 src_c1]
    by blast
  have ch12: "(c', c2) ∈ ?R ^^ (?k + (?k - 1))"
  proof -
    have "(c', c2) ∈ ?R ^^ ?k O ?R ^^ (?k - 1)" using ch1 ch2 by (rule relcompI)
    thus ?thesis by (simp add: relpow_add)
  qed
  have tape_final: "ktc_tape c2 = (ktc_tape c')(tk := (λpos.
          if base ≤ pos ∧ pos < base + (?k - 1)
          then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
          else ktc_tape c' tk pos))"
  proof (rule ext)
    fix k'
    show "ktc_tape c2 k' = ((ktc_tape c')(tk := (λpos.
            if base ≤ pos ∧ pos < base + (?k - 1)
            then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
            else ktc_tape c' tk pos))) k'"
    proof (cases "k' = tk")
      case True
      have "ktc_tape c2 tk = (λpos.
              if base ≤ pos ∧ pos < base + (?k - 1)
              then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
              else ktc_tape c' tk pos)"
      proof (rule ext)
        fix pos
        show "ktc_tape c2 tk pos = (if base ≤ pos ∧ pos < base + (?k - 1)
                then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
                else ktc_tape c' tk pos)"
          using tape2 tape1 by simp
      qed
      thus ?thesis using True by simp
    next
      case False
      have "ktc_tape c2 k' = ktc_tape c1 k'" using otape2 False by simp
      also have "… = ktc_tape c' k'" using tape1 by simp
      finally show ?thesis using False by simp
    qed
  qed
  have pos_final: "ktc_pos c2 = (ktc_pos c')(tk := base + (?k - 1))"
  proof (rule ext)
    fix k'
    show "ktc_pos c2 k' = ((ktc_pos c')(tk := base + (?k - 1))) k'"
    proof (cases "k' = tk")
      case True thus ?thesis using pos2 by simp
    next
      case False
      have "ktc_pos c2 k' = ktc_pos c1 k'" using opos2 False by simp
      also have "… = ktc_pos c' k'" using opos1 False by simp
      finally show ?thesis using False by simp
    qed
  qed
  show ?thesis
  proof (intro exI[where x = c2] conjI)
    show "(c', c2) ∈ ?R ^^ (?k + (?k - 1))" by (rule ch12)
    show "ktc_state c2 = (q, AR_SimWrite, tk, ?k + (?k - 1), buf, dvec, posk)"
      by (rule st2)
    show "ktc_tape c2 = (ktc_tape c')(tk := (λpos.
            if base ≤ pos ∧ pos < base + (?k - 1)
            then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
            else ktc_tape c' tk pos))"
      by (rule tape_final)
    show "ktc_pos c2 = (ktc_pos c')(tk := base + (?k - 1))" by (rule pos_final)
  qed
qed

text ‹Extend a written block prefix by its last cell.  Both
  proper-write finishers reach a tape whose first ‹b - 1› block
  cells already hold the new ‹write_bit› image; the boundary /
  finish step writes the last cell ‹base + (b - 1)›.  This
  ‹fun_upd› closes the gap: updating the ‹b - 1›-prefix
  function at ‹base + (b - 1)› with ‹f (b - 1)› yields
  the full ‹b›-cell write.  Pure list/function arithmetic, shared
  by ‹ar_write_proper_step› and
  ‹ar_write_proper_finish_step›.›

lemma write_block_extend:
  fixes k base :: nat and f g :: "nat ⇒ sym4"
  assumes "0 < k"
  shows "((λpos. if base ≤ pos ∧ pos < base + (k - 1)
                  then f (pos - base) else g pos)
            (base + (k - 1) := f (k - 1)))
         = (λpos. if base ≤ pos ∧ pos < base + k
                  then f (pos - base) else g pos)"
proof -
  obtain kk where k: "k = Suc kk" using assms by (cases k) auto
  show ?thesis
  proof (rule ext)
    fix pos
    show "((λpos. if base ≤ pos ∧ pos < base + (k - 1)
                   then f (pos - base) else g pos)
             (base + (k - 1) := f (k - 1))) pos
          = (if base ≤ pos ∧ pos < base + k then f (pos - base) else g pos)"
    proof (cases "pos = base + (k - 1)")
      case True
      thus ?thesis using k by simp
    next
      case False
      thus ?thesis using k by (auto simp: less_Suc_eq)
    qed
  qed
qed

text ‹The proper-cell single-tape write, non-last tape: the prefix
  followed by the bit-boundary step (‹ar_write_bit_boundary_step›),
  writing the last block cell ‹base + (b - 1)› and landing at the
  next tape's ‹AR_SimWrite› (‹k_succ tk›, counter
  ‹0›).  After the ‹2b›-step walk the ‹b›-cell
  block at ‹base› spells out ‹write_bit (buf tk)› (the
  encoded new symbol), every other cell unchanged, and the head returns
  to the block end ‹base + b›.  Chain length ‹2b›.›

lemma ar_write_proper_step:
  fixes M :: "('q, 'a) ktm"
    and c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes vM: "valid_ktm M"
      and qQ: "q ∈ Q_ktm M"
      and kge2: "2 ≤ block_width (Γ_ktm M)"
      and notlast: "¬ is_last_k M tk"
      and poskproper: "posk tk ≠ AR_AtLE"
      and stg: "ktc_state c' = (q, AR_SimWrite, tk, 0, buf, dvec, posk)"
      and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
      and pos_base: "ktc_pos c' tk = base + block_width (Γ_ktm M)"
      and notLE: "⋀m. m ≤ block_width (Γ_ktm M)
                   ⟹ ktc_tape c' tk (base + m) ≠ LE4"
      and pad0: "∀j ≥ k_ktm M. ktc_tape c' j (ktc_pos c' j) = BLANK4"
      and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                   (AR_SimWrite, tk, 0, buf, dvec, posk)"
  shows "∃c''. (c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (2 * block_width (Γ_ktm M))
              ∧ ktc_state c'' = (q, AR_SimWrite, k_succ tk, 0, buf, dvec, posk)
              ∧ ktc_tape c'' = (ktc_tape c')(tk := (λpos.
                    if base ≤ pos ∧ pos < base + block_width (Γ_ktm M)
                    then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
                    else ktc_tape c' tk pos))
              ∧ ktc_pos c'' = (ktc_pos c')(tk := base + block_width (Γ_ktm M))"
proof -
  let ?k = "block_width (Γ_ktm M)"
  let ?R = "ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)"
  let ?wb = "λm. write_bit (Γ_ktm M) (bl_ktm M) (buf tk) m"
  let ?part = "λpos. if base ≤ pos ∧ pos < base + (?k - 1)
                       then ?wb (pos - base) else ktc_tape c' tk pos"
  let ?full = "λpos. if base ≤ pos ∧ pos < base + ?k
                       then ?wb (pos - base) else ktc_tape c' tk pos"
  have kpos: "0 < ?k" using kge2 by simp
  obtain kk where kdef: "?k = Suc kk" using kge2 by (cases ?k) auto
  obtain c2 where
      ch_pre: "(c', c2) ∈ ?R ^^ (?k + (?k - 1))"
    and st2: "ktc_state c2 = (q, AR_SimWrite, tk, ?k + (?k - 1), buf, dvec, posk)"
    and tape2: "ktc_tape c2 = (ktc_tape c')(tk := ?part)"
    and pos2: "ktc_pos c2 = (ktc_pos c')(tk := base + (?k - 1))"
    using ar_write_proper_prefix[OF vM qQ kge2 poskproper stg buf_valid pos_base notLE
                         pad0 src0]
    by blast
  have c2tk: "ktc_tape c2 tk = ?part" using tape2 by simp
  have pos2_tk: "ktc_pos c2 tk = base + (?k - 1)" using pos2 by simp
  have ihi: "Suc (?k + (?k - 1)) = 2 * ?k" using kdef by simp
  have lt2: "?k + (?k - 1) < 2 * ?k" using kdef by simp
  have vsrc2: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
                 (AR_SimWrite, tk, ?k + (?k - 1), buf, dvec, posk)"
    using lt2 buf_valid by (simp add: ar_valid_stage_def)
  have cell_cur: "ktc_tape c2 tk (ktc_pos c2 tk) = ktc_tape c' tk (base + (?k - 1))"
  proof -
    have "ktc_tape c2 tk (base + (?k - 1)) = ktc_tape c' tk (base + (?k - 1))"
      using c2tk by simp
    thus ?thesis using pos2_tk by simp
  qed
  have km1le: "?k - 1 ≤ ?k" by simp
  have notLE2: "ktc_tape c2 tk (ktc_pos c2 tk) ≠ LE4"
    using cell_cur notLE[OF km1le] by simp
  have tk_lt: "tk < k_ktm M" using src0 by (simp add: ar_stage_bounded_def)
  have pad_c2: "∀j ≥ k_ktm M. ktc_tape c2 j (ktc_pos c2 j) = BLANK4"
  proof (intro allI impI)
    fix j assume jge: "k_ktm M ≤ j"
    have jne: "j ≠ tk" using jge tk_lt by simp
    have "ktc_tape c2 j (ktc_pos c2 j) = ktc_tape c' j (ktc_pos c' j)"
      using tape2 pos2 jne by simp
    thus "ktc_tape c2 j (ktc_pos c2 j) = BLANK4" using pad0 jge by simp
  qed
  have src_c2: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                  (AR_SimWrite, tk, block_width (Γ_ktm M) + (block_width (Γ_ktm M) - 1),
                   buf, dvec, posk)"
    using src0 by (simp add: ar_stage_bounded_def)
  obtain c3 where
      s3: "(c2, c3) ∈ ?R"
    and st3: "ktc_state c3 = (q, AR_SimWrite, k_succ tk, 0, buf, dvec, posk)"
    and tape3: "ktc_tape c3 = (ktc_tape c2)(tk :=
          (ktc_tape c2 tk)(ktc_pos c2 tk := ?wb (?k + (?k - 1) - ?k)))"
    and pos3: "ktc_pos c3 = (ktc_pos c2)(tk := Suc (ktc_pos c2 tk))"
    using ar_write_bit_boundary_step[OF vM st2 qQ poskproper notLE2 notlast ihi vsrc2
                           pad_c2 src_c2]
    by blast
  ― ‹chain: prefix ‹b + (b - 1)› then one boundary step = ‹2b››
  have ch_full: "(c', c3) ∈ ?R ^^ (2 * ?k)"
  proof -
    have h: "(c', c3) ∈ ?R ^^ Suc (?k + (?k - 1))"
      by (rule relpow_Suc_I[OF ch_pre s3])
    from h show ?thesis by (simp only: ihi)
  qed
  ― ‹tape: the last block cell ‹base + (b - 1)› completes the write›
  have tape3_tk: "ktc_tape c3 tk = (?part(base + (?k - 1) := ?wb (?k - 1)))"
    using tape3 pos2_tk c2tk by simp
  have tape3_tk_full: "ktc_tape c3 tk = ?full"
    using tape3_tk write_block_extend[OF kpos, of base ?wb "ktc_tape c' tk"] by simp
  have tape_final: "ktc_tape c3 = (ktc_tape c')(tk := ?full)"
  proof (rule ext)
    fix k'
    show "ktc_tape c3 k' = ((ktc_tape c')(tk := ?full)) k'"
    proof (cases "k' = tk")
      case True thus ?thesis using tape3_tk_full by simp
    next
      case False
      have "ktc_tape c3 k' = ktc_tape c2 k'" using tape3 False by simp
      also have "… = ktc_tape c' k'" using tape2 False by simp
      finally show ?thesis using False by simp
    qed
  qed
  have pos_final: "ktc_pos c3 = (ktc_pos c')(tk := base + ?k)"
  proof -
    have "ktc_pos c3 = (ktc_pos c2)(tk := Suc (ktc_pos c2 tk))" by (rule pos3)
    also have "… = (ktc_pos c2)(tk := base + ?k)" using pos2_tk kdef by simp
    also have "… = (ktc_pos c')(tk := base + ?k)" using pos2 by simp
    finally show ?thesis .
  qed
  show ?thesis
  proof (intro exI[where x = c3] conjI)
    show "(c', c3) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (2 * ?k)"
      by (rule ch_full)
    show "ktc_state c3 = (q, AR_SimWrite, k_succ tk, 0, buf, dvec, posk)"
      by (rule st3)
    show "ktc_tape c3 = (ktc_tape c')(tk := (λpos.
            if base ≤ pos ∧ pos < base + ?k
            then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
            else ktc_tape c' tk pos))"
      by (rule tape_final)
    show "ktc_pos c3 = (ktc_pos c')(tk := base + ?k)" by (rule pos_final)
  qed
qed

text ‹The proper-cell single-tape write, last tape: as
  ‹ar_write_proper_step› but ‹tk› is the last tape, so after
  the last-cell write (‹ar_write_bit_finish_step›) the phase
  transitions to ‹AR_SimAdvance› with the current-tape field reset
  to ‹k_unidx 0› (all tapes written).  Same ‹b›-cell block
  write and head return to ‹base + b›.  Chain length ‹2b›.›

lemma ar_write_proper_finish_step:
  fixes M :: "('q, 'a) ktm"
    and c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes vM: "valid_ktm M"
      and qQ: "q ∈ Q_ktm M"
      and kge2: "2 ≤ block_width (Γ_ktm M)"
      and last: "is_last_k M tk"
      and poskproper: "posk tk ≠ AR_AtLE"
      and stg: "ktc_state c' = (q, AR_SimWrite, tk, 0, buf, dvec, posk)"
      and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
      and pos_base: "ktc_pos c' tk = base + block_width (Γ_ktm M)"
      and notLE: "⋀m. m ≤ block_width (Γ_ktm M)
                   ⟹ ktc_tape c' tk (base + m) ≠ LE4"
      and pad0: "∀j ≥ k_ktm M. ktc_tape c' j (ktc_pos c' j) = BLANK4"
      and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                   (AR_SimWrite, tk, 0, buf, dvec, posk)"
  shows "∃c''. (c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (2 * block_width (Γ_ktm M))
              ∧ ktc_state c'' = (q, AR_SimAdvance, k_unidx 0, 0, buf, dvec, posk)
              ∧ ktc_tape c'' = (ktc_tape c')(tk := (λpos.
                    if base ≤ pos ∧ pos < base + block_width (Γ_ktm M)
                    then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
                    else ktc_tape c' tk pos))
              ∧ ktc_pos c'' = (ktc_pos c')(tk := base + block_width (Γ_ktm M))"
proof -
  let ?k = "block_width (Γ_ktm M)"
  let ?R = "ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)"
  let ?wb = "λm. write_bit (Γ_ktm M) (bl_ktm M) (buf tk) m"
  let ?part = "λpos. if base ≤ pos ∧ pos < base + (?k - 1)
                       then ?wb (pos - base) else ktc_tape c' tk pos"
  let ?full = "λpos. if base ≤ pos ∧ pos < base + ?k
                       then ?wb (pos - base) else ktc_tape c' tk pos"
  have kpos: "0 < ?k" using kge2 by simp
  obtain kk where kdef: "?k = Suc kk" using kge2 by (cases ?k) auto
  obtain c2 where
      ch_pre: "(c', c2) ∈ ?R ^^ (?k + (?k - 1))"
    and st2: "ktc_state c2 = (q, AR_SimWrite, tk, ?k + (?k - 1), buf, dvec, posk)"
    and tape2: "ktc_tape c2 = (ktc_tape c')(tk := ?part)"
    and pos2: "ktc_pos c2 = (ktc_pos c')(tk := base + (?k - 1))"
    using ar_write_proper_prefix[OF vM qQ kge2 poskproper stg buf_valid pos_base notLE
                         pad0 src0]
    by blast
  have c2tk: "ktc_tape c2 tk = ?part" using tape2 by simp
  have pos2_tk: "ktc_pos c2 tk = base + (?k - 1)" using pos2 by simp
  have ihi: "Suc (?k + (?k - 1)) = 2 * ?k" using kdef by simp
  have lt2: "?k + (?k - 1) < 2 * ?k" using kdef by simp
  have vsrc2: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
                 (AR_SimWrite, tk, ?k + (?k - 1), buf, dvec, posk)"
    using lt2 buf_valid by (simp add: ar_valid_stage_def)
  have cell_cur: "ktc_tape c2 tk (ktc_pos c2 tk) = ktc_tape c' tk (base + (?k - 1))"
  proof -
    have "ktc_tape c2 tk (base + (?k - 1)) = ktc_tape c' tk (base + (?k - 1))"
      using c2tk by simp
    thus ?thesis using pos2_tk by simp
  qed
  have km1le: "?k - 1 ≤ ?k" by simp
  have notLE2: "ktc_tape c2 tk (ktc_pos c2 tk) ≠ LE4"
    using cell_cur notLE[OF km1le] by simp
  have tk_lt: "tk < k_ktm M" using src0 by (simp add: ar_stage_bounded_def)
  have pad_c2: "∀j ≥ k_ktm M. ktc_tape c2 j (ktc_pos c2 j) = BLANK4"
  proof (intro allI impI)
    fix j assume jge: "k_ktm M ≤ j"
    have jne: "j ≠ tk" using jge tk_lt by simp
    have "ktc_tape c2 j (ktc_pos c2 j) = ktc_tape c' j (ktc_pos c' j)"
      using tape2 pos2 jne by simp
    thus "ktc_tape c2 j (ktc_pos c2 j) = BLANK4" using pad0 jge by simp
  qed
  have src_c2: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                  (AR_SimWrite, tk, block_width (Γ_ktm M) + (block_width (Γ_ktm M) - 1),
                   buf, dvec, posk)"
    using src0 by (simp add: ar_stage_bounded_def)
  obtain c3 where
      s3: "(c2, c3) ∈ ?R"
    and st3: "ktc_state c3 = (q, AR_SimAdvance, k_unidx 0, 0, buf, dvec, posk)"
    and tape3: "ktc_tape c3 = (ktc_tape c2)(tk :=
          (ktc_tape c2 tk)(ktc_pos c2 tk := ?wb (?k + (?k - 1) - ?k)))"
    and pos3: "ktc_pos c3 = (ktc_pos c2)(tk := Suc (ktc_pos c2 tk))"
    using ar_write_bit_finish_step[OF vM st2 qQ poskproper notLE2 last ihi vsrc2
                         pad_c2 src_c2]
    by blast
  have ch_full: "(c', c3) ∈ ?R ^^ (2 * ?k)"
  proof -
    have h: "(c', c3) ∈ ?R ^^ Suc (?k + (?k - 1))"
      by (rule relpow_Suc_I[OF ch_pre s3])
    from h show ?thesis by (simp only: ihi)
  qed
  have tape3_tk: "ktc_tape c3 tk = (?part(base + (?k - 1) := ?wb (?k - 1)))"
    using tape3 pos2_tk c2tk by simp
  have tape3_tk_full: "ktc_tape c3 tk = ?full"
    using tape3_tk write_block_extend[OF kpos, of base ?wb "ktc_tape c' tk"] by simp
  have tape_final: "ktc_tape c3 = (ktc_tape c')(tk := ?full)"
  proof (rule ext)
    fix k'
    show "ktc_tape c3 k' = ((ktc_tape c')(tk := ?full)) k'"
    proof (cases "k' = tk")
      case True thus ?thesis using tape3_tk_full by simp
    next
      case False
      have "ktc_tape c3 k' = ktc_tape c2 k'" using tape3 False by simp
      also have "… = ktc_tape c' k'" using tape2 False by simp
      finally show ?thesis using False by simp
    qed
  qed
  have pos_final: "ktc_pos c3 = (ktc_pos c')(tk := base + ?k)"
  proof -
    have "ktc_pos c3 = (ktc_pos c2)(tk := Suc (ktc_pos c2 tk))" by (rule pos3)
    also have "… = (ktc_pos c2)(tk := base + ?k)" using pos2_tk kdef by simp
    also have "… = (ktc_pos c')(tk := base + ?k)" using pos2 by simp
    finally show ?thesis .
  qed
  show ?thesis
  proof (intro exI[where x = c3] conjI)
    show "(c', c3) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (2 * ?k)"
      by (rule ch_full)
    show "ktc_state c3 = (q, AR_SimAdvance, k_unidx 0, 0, buf, dvec, posk)"
      by (rule st3)
    show "ktc_tape c3 = (ktc_tape c')(tk := (λpos.
            if base ≤ pos ∧ pos < base + ?k
            then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - base)
            else ktc_tape c' tk pos))"
      by (rule tape_final)
    show "ktc_pos c3 = (ktc_pos c')(tk := base + ?k)" by (rule pos_final)
  qed
qed

text ‹The unified single-tape write, non-last tape: the LE/proper
  dispatch, the AR analogue of ‹ar_read_tape_step›.  From an
  ‹AR_SimWrite› stage at bit-counter ‹0›, dispatch on
  ‹posk tk = AR_AtLE› (which the caller pins to ‹p = 0›,
  ‹M›'s head on the marker): the LE arm
  (‹ar_write_le_step›, ‹1› step) leaves the tape and head
  untouched and hands off; the proper arm (‹ar_write_proper_step›,
  ‹2b› steps) overwrites the ‹b›-cell block at ‹sim_pos
  p› with ‹write_bit (buf tk)›.  In ∗‹both›
  arms every head is unchanged (the LE arm is all-‹N›; the proper
  arm back-walks then returns to the block end), so the conclusion is
  ‹ktc_pos c'' = ktc_pos c'› uniformly.  The proper-arm
  ‹≠ LE4› facts come from the input correspondence
  ‹tcorr› (block-‹p› cells and the block-‹(p+1)›
  lead cell, all ‹cell_repr› cells via
  ‹cell_repr_nth_not_LE4›).›

lemma ar_write_tape_step:
  fixes M :: "('q, 'a) ktm"
    and c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
    and tM :: "nat ⇒ 'a"
  assumes vM: "valid_ktm M"
      and qQ: "q ∈ Q_ktm M"
      and kge2: "2 ≤ block_width (Γ_ktm M)"
      and notlast: "¬ is_last_k M tk"
      and stg: "ktc_state c' = (q, AR_SimWrite, tk, 0, buf, dvec, posk)"
      and tcorr: "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
                    tM (ktc_tape c' tk)"
      and ppos: "ktc_pos c' tk = (if p = 0 then Suc 0
                    else sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M))"
      and poskle: "posk tk = AR_AtLE ⟷ p = 0"
      and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
      and vsrc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
                   (AR_SimWrite, tk, 0, buf, dvec, posk)"
      and pad0: "∀j ≥ k_ktm M. ktc_tape c' j (ktc_pos c' j) = BLANK4"
      and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                   (AR_SimWrite, tk, 0, buf, dvec, posk)"
  shows "∃c''. (c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (if p = 0 then 1 else 2 * block_width (Γ_ktm M))
              ∧ ktc_state c'' = (q, AR_SimWrite, k_succ tk, 0, buf, dvec, posk)
              ∧ ktc_tape c'' = (if p = 0 then ktc_tape c'
                    else (ktc_tape c')(tk := (λpos.
                      if sim_pos (block_width (Γ_ktm M)) p ≤ pos
                         ∧ pos < sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M)
                      then write_bit (Γ_ktm M) (bl_ktm M) (buf tk)
                             (pos - sim_pos (block_width (Γ_ktm M)) p)
                      else ktc_tape c' tk pos)))
              ∧ ktc_pos c'' = ktc_pos c'"
proof -
  let ?k = "block_width (Γ_ktm M)"
  let ?R = "ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)"
  have kpos: "0 < ?k" using kge2 by simp
  show ?thesis
  proof (cases "p = 0")
    case True
    have poskLE: "posk tk = AR_AtLE" using poskle True by simp
    obtain c'' where
        step: "(c', c'') ∈ ?R"
      and st: "ktc_state c'' = (q, AR_SimWrite, k_succ tk, 0, buf, dvec, posk)"
      and tp: "ktc_tape c'' = ktc_tape c'"
      and ps: "ktc_pos c'' = ktc_pos c'"
      using ar_write_le_step[OF vM stg qQ poskLE notlast vsrc pad0 src0] by blast
    show ?thesis
    proof (intro exI[where x = c''] conjI)
      show "(c', c'') ∈ ?R ^^ (if p = 0 then 1 else 2 * ?k)"
        using step True by simp
      show "ktc_state c'' = (q, AR_SimWrite, k_succ tk, 0, buf, dvec, posk)"
        by (rule st)
      show "ktc_tape c'' = (if p = 0 then ktc_tape c'
              else (ktc_tape c')(tk := (λpos.
                if sim_pos ?k p ≤ pos ∧ pos < sim_pos ?k p + ?k
                then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - sim_pos ?k p)
                else ktc_tape c' tk pos)))"
        using tp True by simp
      show "ktc_pos c'' = ktc_pos c'" by (rule ps)
    qed
  next
    case False
    hence pge1: "1 ≤ p" by simp
    have poskproper: "posk tk ≠ AR_AtLE" using poskle False by simp
    let ?base = "sim_pos ?k p"
    have pos_base: "ktc_pos c' tk = ?base + ?k" using ppos False by simp
    have notLE: "⋀m. m ≤ ?k ⟹ ktc_tape c' tk (?base + m) ≠ LE4"
    proof -
      fix m assume mle: "m ≤ ?k"
      show "ktc_tape c' tk (?base + m) ≠ LE4"
      proof (cases "m < ?k")
        case True
        have "ktc_tape c' tk (?base + m)
                = cell_repr (Γ_ktm M) (bl_ktm M) (tM p) ! m"
          using tcorr pge1 True unfolding ar_tape_correspondence_def by blast
        thus ?thesis using cell_repr_nth_not_LE4[OF True] by simp
      next
        case False
        hence meq: "m = ?k" using mle by simp
        obtain pp where pp: "p = Suc pp" using pge1 by (cases p) auto
        have psuc1: "1 ≤ Suc p" by simp
        have base_succ: "?base + ?k = sim_pos ?k (Suc p)"
          using pp by (simp add: sim_pos_def)
        have corr_succ: "∀j < ?k. ktc_tape c' tk (sim_pos ?k (Suc p) + j)
                            = cell_repr (Γ_ktm M) (bl_ktm M) (tM (Suc p)) ! j"
          using tcorr psuc1 unfolding ar_tape_correspondence_def by blast
        have "ktc_tape c' tk (?base + m)
                = cell_repr (Γ_ktm M) (bl_ktm M) (tM (Suc p)) ! 0"
          using meq base_succ corr_succ[rule_format, OF kpos] by simp
        thus ?thesis using cell_repr_nth_not_LE4[OF kpos] by simp
      qed
    qed
    obtain c'' where
        step: "(c', c'') ∈ ?R ^^ (2 * ?k)"
      and st: "ktc_state c'' = (q, AR_SimWrite, k_succ tk, 0, buf, dvec, posk)"
      and tp: "ktc_tape c'' = (ktc_tape c')(tk := (λpos.
            if ?base ≤ pos ∧ pos < ?base + ?k
            then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - ?base)
            else ktc_tape c' tk pos))"
      and ps: "ktc_pos c'' = (ktc_pos c')(tk := ?base + ?k)"
      using ar_write_proper_step[OF vM qQ kge2 notlast poskproper stg buf_valid
                                    pos_base notLE pad0 src0]
      by blast
    have ps': "ktc_pos c'' = ktc_pos c'"
    proof -
      have "(ktc_pos c')(tk := ?base + ?k) = ktc_pos c'"
        using pos_base by (rule fun_upd_idem)
      thus ?thesis using ps by simp
    qed
    show ?thesis
    proof (intro exI[where x = c''] conjI)
      show "(c', c'') ∈ ?R ^^ (if p = 0 then 1 else 2 * ?k)"
        using step False by simp
      show "ktc_state c'' = (q, AR_SimWrite, k_succ tk, 0, buf, dvec, posk)"
        by (rule st)
      show "ktc_tape c'' = (if p = 0 then ktc_tape c'
              else (ktc_tape c')(tk := (λpos.
                if sim_pos ?k p ≤ pos ∧ pos < sim_pos ?k p + ?k
                then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - sim_pos ?k p)
                else ktc_tape c' tk pos)))"
        using tp False by simp
      show "ktc_pos c'' = ktc_pos c'" by (rule ps')
    qed
  qed
qed

text ‹The unified single-tape write, last tape: as
  ‹ar_write_tape_step› but ‹tk› is the last tape, so both
  arms transition to ‹AR_SimAdvance› (current-tape field reset to
  ‹k_unidx 0›, all tapes written): the LE arm via
  ‹ar_write_le_finish_step›, the proper arm via
  ‹ar_write_proper_finish_step›.  Same tape edit and head
  invariance.›

lemma ar_write_tape_finish_step:
  fixes M :: "('q, 'a) ktm"
    and c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
    and tM :: "nat ⇒ 'a"
  assumes vM: "valid_ktm M"
      and qQ: "q ∈ Q_ktm M"
      and kge2: "2 ≤ block_width (Γ_ktm M)"
      and last: "is_last_k M tk"
      and stg: "ktc_state c' = (q, AR_SimWrite, tk, 0, buf, dvec, posk)"
      and tcorr: "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
                    tM (ktc_tape c' tk)"
      and ppos: "ktc_pos c' tk = (if p = 0 then Suc 0
                    else sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M))"
      and poskle: "posk tk = AR_AtLE ⟷ p = 0"
      and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
      and vsrc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
                   (AR_SimWrite, tk, 0, buf, dvec, posk)"
      and pad0: "∀j ≥ k_ktm M. ktc_tape c' j (ktc_pos c' j) = BLANK4"
      and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                   (AR_SimWrite, tk, 0, buf, dvec, posk)"
  shows "∃c''. (c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (if p = 0 then 1 else 2 * block_width (Γ_ktm M))
              ∧ ktc_state c'' = (q, AR_SimAdvance, k_unidx 0, 0, buf, dvec, posk)
              ∧ ktc_tape c'' = (if p = 0 then ktc_tape c'
                    else (ktc_tape c')(tk := (λpos.
                      if sim_pos (block_width (Γ_ktm M)) p ≤ pos
                         ∧ pos < sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M)
                      then write_bit (Γ_ktm M) (bl_ktm M) (buf tk)
                             (pos - sim_pos (block_width (Γ_ktm M)) p)
                      else ktc_tape c' tk pos)))
              ∧ ktc_pos c'' = ktc_pos c'"
proof -
  let ?k = "block_width (Γ_ktm M)"
  let ?R = "ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)"
  have kpos: "0 < ?k" using kge2 by simp
  show ?thesis
  proof (cases "p = 0")
    case True
    have poskLE: "posk tk = AR_AtLE" using poskle True by simp
    obtain c'' where
        step: "(c', c'') ∈ ?R"
      and st: "ktc_state c'' = (q, AR_SimAdvance, k_unidx 0, 0, buf, dvec, posk)"
      and tp: "ktc_tape c'' = ktc_tape c'"
      and ps: "ktc_pos c'' = ktc_pos c'"
      using ar_write_le_finish_step[OF vM stg qQ poskLE last vsrc pad0 src0] by blast
    show ?thesis
    proof (intro exI[where x = c''] conjI)
      show "(c', c'') ∈ ?R ^^ (if p = 0 then 1 else 2 * ?k)"
        using step True by simp
      show "ktc_state c'' = (q, AR_SimAdvance, k_unidx 0, 0, buf, dvec, posk)"
        by (rule st)
      show "ktc_tape c'' = (if p = 0 then ktc_tape c'
              else (ktc_tape c')(tk := (λpos.
                if sim_pos ?k p ≤ pos ∧ pos < sim_pos ?k p + ?k
                then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - sim_pos ?k p)
                else ktc_tape c' tk pos)))"
        using tp True by simp
      show "ktc_pos c'' = ktc_pos c'" by (rule ps)
    qed
  next
    case False
    hence pge1: "1 ≤ p" by simp
    have poskproper: "posk tk ≠ AR_AtLE" using poskle False by simp
    let ?base = "sim_pos ?k p"
    have pos_base: "ktc_pos c' tk = ?base + ?k" using ppos False by simp
    have notLE: "⋀m. m ≤ ?k ⟹ ktc_tape c' tk (?base + m) ≠ LE4"
    proof -
      fix m assume mle: "m ≤ ?k"
      show "ktc_tape c' tk (?base + m) ≠ LE4"
      proof (cases "m < ?k")
        case True
        have "ktc_tape c' tk (?base + m)
                = cell_repr (Γ_ktm M) (bl_ktm M) (tM p) ! m"
          using tcorr pge1 True unfolding ar_tape_correspondence_def by blast
        thus ?thesis using cell_repr_nth_not_LE4[OF True] by simp
      next
        case False
        hence meq: "m = ?k" using mle by simp
        obtain pp where pp: "p = Suc pp" using pge1 by (cases p) auto
        have psuc1: "1 ≤ Suc p" by simp
        have base_succ: "?base + ?k = sim_pos ?k (Suc p)"
          using pp by (simp add: sim_pos_def)
        have corr_succ: "∀j < ?k. ktc_tape c' tk (sim_pos ?k (Suc p) + j)
                            = cell_repr (Γ_ktm M) (bl_ktm M) (tM (Suc p)) ! j"
          using tcorr psuc1 unfolding ar_tape_correspondence_def by blast
        have "ktc_tape c' tk (?base + m)
                = cell_repr (Γ_ktm M) (bl_ktm M) (tM (Suc p)) ! 0"
          using meq base_succ corr_succ[rule_format, OF kpos] by simp
        thus ?thesis using cell_repr_nth_not_LE4[OF kpos] by simp
      qed
    qed
    obtain c'' where
        step: "(c', c'') ∈ ?R ^^ (2 * ?k)"
      and st: "ktc_state c'' = (q, AR_SimAdvance, k_unidx 0, 0, buf, dvec, posk)"
      and tp: "ktc_tape c'' = (ktc_tape c')(tk := (λpos.
            if ?base ≤ pos ∧ pos < ?base + ?k
            then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - ?base)
            else ktc_tape c' tk pos))"
      and ps: "ktc_pos c'' = (ktc_pos c')(tk := ?base + ?k)"
      using ar_write_proper_finish_step[OF vM qQ kge2 last poskproper stg buf_valid
                                           pos_base notLE pad0 src0]
      by blast
    have ps': "ktc_pos c'' = ktc_pos c'"
    proof -
      have "(ktc_pos c')(tk := ?base + ?k) = ktc_pos c'"
        using pos_base by (rule fun_upd_idem)
      thus ?thesis using ps by simp
    qed
    show ?thesis
    proof (intro exI[where x = c''] conjI)
      show "(c', c'') ∈ ?R ^^ (if p = 0 then 1 else 2 * ?k)"
        using step False by simp
      show "ktc_state c'' = (q, AR_SimAdvance, k_unidx 0, 0, buf, dvec, posk)"
        by (rule st)
      show "ktc_tape c'' = (if p = 0 then ktc_tape c'
              else (ktc_tape c')(tk := (λpos.
                if sim_pos ?k p ≤ pos ∧ pos < sim_pos ?k p + ?k
                then write_bit (Γ_ktm M) (bl_ktm M) (buf tk) (pos - sim_pos ?k p)
                else ktc_tape c' tk pos)))"
        using tp False by simp
      show "ktc_pos c'' = ktc_pos c'" by (rule ps')
    qed
  qed
qed

text ‹The write-phase prefix walk: from the write boundary
  (current-tape field ‹k_unidx 0›, bit-counter
  ‹0›, the head positions the read phase left), iterate the
  unified non-last per-tape write ‹ar_write_tape_step› over the
  first ‹j› tapes (‹j ≤ k_ktm M - 1›, all non-last),
  landing back at ‹AR_SimWrite› on tape ‹k_unidx j›.
  Dual to ‹ar_read_prefix›: the read kept the tape constant and
  varied ‹buf›/‹posk›; the write keeps
  ‹buf›/‹posk›/positions constant and varies the
  ∗‹tape›.  The descriptor splits on ‹k_idx k <
  j›: visited tapes carry their overwritten block
  (‹?out›, the ‹write_bit› image for proper tapes, or
  the unchanged tape for ‹LE› tapes); the rest are unchanged.
  Each per-tape step's ‹tcorr› / position entry facts hold
  because the current tape is not yet visited
  (‹ktc_tape c k_unidx j = ktc_tape c0 (k_unidx j)›).  Variable
  per-tape cost (‹1› or ‹2b›), aggregate bounded by
  ‹j ⋅ 2b›.›

lemma ar_write_prefix:
  fixes M :: "('q, 'a) ktm"
    and cM :: "('a, 'q) ktc_config"
    and c0 :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes vM: "valid_ktm M"
      and qQ: "q ∈ Q_ktm M"
      and kge2: "2 ≤ block_width (Γ_ktm M)"
      and stg0: "ktc_state c0 = (q, AR_SimWrite, 0, 0, buf, dvec, posk)"
      and tcorr: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
                       (ktc_tape cM k) (ktc_tape c0 k)"
      and ppos: "∀k < k_ktm M. ktc_pos c0 k = (if ktc_pos cM k = 0 then Suc 0
                       else sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k)
                              + block_width (Γ_ktm M))"
      and poskle: "∀k < k_ktm M. posk k = AR_AtLE ⟷ ktc_pos cM k = 0"
      and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
      and pad0: "∀j ≥ k_ktm M. ktc_tape c0 j (ktc_pos c0 j) = BLANK4"
      and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                   (AR_SimWrite, 0, 0, buf, dvec, posk)"
  shows "j ≤ k_ktm M - 1 ⟹
    (∃c m. (c0, c) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ m
         ∧ m ≤ j * (2 * block_width (Γ_ktm M))
         ∧ ktc_state c = (q, AR_SimWrite, k_unidx j, 0, buf, dvec, posk)
         ∧ ktc_tape c = (λk. if k_idx k < j
              then (if ktc_pos cM k = 0 then ktc_tape c0 k
                    else (λpos. if sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k) ≤ pos
                                  ∧ pos < sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k)
                                            + block_width (Γ_ktm M)
                               then write_bit (Γ_ktm M) (bl_ktm M) (buf k)
                                      (pos - sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k))
                               else ktc_tape c0 k pos))
              else ktc_tape c0 k)
         ∧ ktc_pos c = ktc_pos c0)"
proof (induction j)
  case 0
  let ?k = "block_width (Γ_ktm M)"
  have "(c0, c0) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ 0" by simp
  moreover have "ktc_tape c0 = (λk. if k_idx k < 0
              then (if ktc_pos cM k = 0 then ktc_tape c0 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) (buf k)
                                      (pos - sim_pos ?k (ktc_pos cM k))
                               else ktc_tape c0 k pos))
              else ktc_tape c0 k)"
    by simp
  ultimately show ?case
    using stg0 by (intro exI[where x = c0] exI[where x = 0]) (simp add: k_unidx_zero)
next
  case (Suc j)
  have sucle: "Suc j ≤ k_ktm M - 1" by (rule Suc.prems)
  have jcard: "j < k_ktm M" using sucle by simp
  have sjcard: "Suc j < k_ktm M" using sucle by simp
  have jle: "j ≤ k_ktm M - 1" using sucle by simp
  let ?k = "block_width (Γ_ktm M)"
  let ?tk = "k_unidx j"
  let ?p = "ktc_pos cM ?tk"
  let ?out = "λk. if ktc_pos cM k = 0 then ktc_tape c0 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) (buf k)
                                     (pos - sim_pos ?k (ktc_pos cM k))
                              else ktc_tape c0 k pos)"
  let ?tape = "λi. (λk. if k_idx k < i then ?out k else ktc_tape c0 k)"
  have tkidx: "k_idx ?tk = j" by (rule k_idx_unidx[OF jcard])
  have notlast: "¬ is_last_k M ?tk"
    using is_last_k_unidx[OF jcard] sjcard by simp
  have ksucc: "k_succ ?tk = k_unidx (Suc j)" by (rule k_succ_unidx[OF sjcard])
  have inj: "inj_on k_idx UNIV" by (rule k_idx_inj)
  have kne: "⋀k. k_idx k = j ⟹ k = ?tk"
  proof -
    fix k assume "k_idx k = j"
    hence "k_idx k = k_idx ?tk" using tkidx by simp
    thus "k = ?tk" using inj_on_eq_iff[OF inj UNIV_I UNIV_I] by simp
  qed
  obtain c m where
      cm_rel: "(c0, c) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ m"
    and m_le: "m ≤ j * (2 * ?k)"
    and c_st: "ktc_state c = (q, AR_SimWrite, ?tk, 0, buf, dvec, posk)"
    and c_tp: "ktc_tape c = ?tape j"
    and c_ps: "ktc_pos c = ktc_pos c0"
    using Suc.IH[OF jle] by blast
  ― ‹tape ‹?tk› is not yet visited, so still matches ‹c0››
  have tc_tk: "ktc_tape c ?tk = ktc_tape c0 ?tk" using c_tp tkidx by simp
  have tk_active: "?tk < k_ktm M" using jcard by (simp add: k_unidx_def)
  have tk_corr: "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
                   (ktc_tape cM ?tk) (ktc_tape c ?tk)"
    using tcorr[rule_format, OF tk_active] tc_tk by simp
  have tk_ppos: "ktc_pos c ?tk
                   = (if ?p = 0 then Suc 0 else sim_pos ?k ?p + ?k)"
    using c_ps ppos[rule_format, OF tk_active] by simp
  have tk_poskle: "posk ?tk = AR_AtLE ⟷ ?p = 0"
    by (rule poskle[rule_format, OF tk_active])
  have tk_vsrc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
                   (AR_SimWrite, ?tk, 0, buf, dvec, posk)"
    using kge2 buf_valid by (auto simp: ar_valid_stage_def)
  have tail_idx: "⋀j'. k_ktm M ≤ j' ⟹ ¬ k_idx j' < j"
    using jcard unfolding k_idx_def by linarith
  have pad_c: "∀j' ≥ k_ktm M. ktc_tape c j' (ktc_pos c j') = BLANK4"
  proof (intro allI impI)
    fix j' assume jge: "k_ktm M ≤ j'"
    have "ktc_tape c j' (ktc_pos c j') = ktc_tape c0 j' (ktc_pos c0 j')"
      using c_tp c_ps tail_idx[OF jge] by simp
    thus "ktc_tape c j' (ktc_pos c j') = BLANK4" using pad0 jge by simp
  qed
  have src_c: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                 (AR_SimWrite, ?tk, 0, buf, dvec, posk)"
    using src0 tk_active by (auto simp: ar_stage_bounded_def)
  obtain c' where
      step: "(c, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (if ?p = 0 then 1 else 2 * ?k)"
    and c'_st: "ktc_state c' = (q, AR_SimWrite, k_succ ?tk, 0, buf, dvec, posk)"
    and c'_tp: "ktc_tape c' = (if ?p = 0 then ktc_tape c
                  else (ktc_tape c)(?tk := (λpos.
                    if sim_pos ?k ?p ≤ pos ∧ pos < sim_pos ?k ?p + ?k
                    then write_bit (Γ_ktm M) (bl_ktm M) (buf ?tk)
                           (pos - sim_pos ?k ?p)
                    else ktc_tape c ?tk pos)))"
    and c'_ps: "ktc_pos c' = ktc_pos c"
    using ar_write_tape_step[OF vM qQ kge2 notlast c_st tk_corr tk_ppos tk_poskle
                                buf_valid tk_vsrc pad_c src_c]
    by blast
  ― ‹the post-state tape descriptor coincides with the ‹Suc j› one›
  have tape_eq: "ktc_tape c' = ?tape (Suc j)"
  proof (rule ext)
    fix k
    show "ktc_tape c' k = ?tape (Suc j) k"
    proof (cases "k = ?tk")
      case True
      show ?thesis
      proof (cases "?p = 0")
        case True
        have "ktc_tape c' k = ktc_tape c0 ?tk"
          using c'_tp ‹k = ?tk› ‹?p = 0› tc_tk by simp
        moreover have "?tape (Suc j) k = ktc_tape c0 ?tk"
          using ‹k = ?tk› tkidx ‹?p = 0› by simp
        ultimately show ?thesis by simp
      next
        case False
        show ?thesis
        proof (rule ext)
          fix pos
          have lhs: "ktc_tape c' k pos
                  = (if sim_pos ?k ?p ≤ pos ∧ pos < sim_pos ?k ?p + ?k
                     then write_bit (Γ_ktm M) (bl_ktm M) (buf ?tk) (pos - sim_pos ?k ?p)
                     else ktc_tape c ?tk pos)"
            using c'_tp ‹k = ?tk› ‹?p ≠ 0› by simp
          have rhs: "?tape (Suc j) k pos
                  = (if sim_pos ?k ?p ≤ pos ∧ pos < sim_pos ?k ?p + ?k
                     then write_bit (Γ_ktm M) (bl_ktm M) (buf ?tk) (pos - sim_pos ?k ?p)
                     else ktc_tape c0 ?tk pos)"
            using ‹k = ?tk› tkidx ‹?p ≠ 0› by simp
          show "ktc_tape c' k pos = ?tape (Suc j) k pos"
            using lhs rhs tc_tk by simp
        qed
      qed
    next
      case False
      hence kidx_ne: "k_idx k ≠ j" using kne by blast
      have "ktc_tape c' k = ktc_tape c k"
        using c'_tp False by (cases "?p = 0") simp_all
      also have "… = ?tape j k" using c_tp by simp
      also have "… = ?tape (Suc j) k" using kidx_ne by (simp add: less_Suc_eq)
      finally show ?thesis .
    qed
  qed
  have chain: "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (m + (if ?p = 0 then 1 else 2 * ?k))"
  proof -
    have "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ m
                       O (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (if ?p = 0 then 1 else 2 * ?k)"
      using cm_rel step by (rule relcompI)
    thus ?thesis by (simp add: relpow_add)
  qed
  have bound: "m + (if ?p = 0 then 1 else 2 * ?k) ≤ Suc j * (2 * ?k)"
    using m_le kge2 by (cases "?p = 0") auto
  show ?case
  proof (intro exI[where x = c']
           exI[where x = "m + (if ?p = 0 then 1 else 2 * ?k)"] conjI)
    show "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (m + (if ?p = 0 then 1 else 2 * ?k))" by (rule chain)
    show "m + (if ?p = 0 then 1 else 2 * ?k) ≤ Suc j * (2 * ?k)"
      by (rule bound)
    show "ktc_state c' = (q, AR_SimWrite, k_unidx (Suc j), 0, buf, dvec, posk)"
      using c'_st ksucc by simp
    show "ktc_tape c' = (λk. if k_idx k < Suc j
              then (if ktc_pos cM k = 0 then ktc_tape c0 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) (buf k)
                                      (pos - sim_pos ?k (ktc_pos cM k))
                               else ktc_tape c0 k pos))
              else ktc_tape c0 k)"
      using tape_eq by simp
    show "ktc_pos c' = ktc_pos c0" using c'_ps c_ps by simp
  qed
qed

text ‹The full write phase: the prefix walk over the first
  ‹k_ktm M - 1› tapes followed by the unified last-tape write
  ‹ar_write_tape_finish_step›, landing at ‹AR_SimAdvance›
  (current-tape field ‹k_unidx 0›) with every proper tape's
  ‹b›-cell block overwritten by ‹write_bit (buf k)› (the
  encoded ‹M›-write symbol) and every ‹LE› tape and head
  position unchanged.  Aggregate cost ‹≤ k_ktm M ⋅ 2b›.
  The split tape descriptor collapses to the full per-tape overwrite on
  the last tape (every other tape has index ‹< k_ktm M - 1›).›

lemma ar_write_phase:
  fixes M :: "('q, 'a) ktm"
    and cM :: "('a, 'q) ktc_config"
    and c0 :: "(sym4, 'q × 'a ar_stage) ktc_config"
  assumes vM: "valid_ktm M"
      and qQ: "q ∈ Q_ktm M"
      and kge2: "2 ≤ block_width (Γ_ktm M)"
      and stg0: "ktc_state c0 = (q, AR_SimWrite, 0, 0, buf, dvec, posk)"
      and tcorr: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
                       (ktc_tape cM k) (ktc_tape c0 k)"
      and ppos: "∀k < k_ktm M. ktc_pos c0 k = (if ktc_pos cM k = 0 then Suc 0
                       else sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k)
                              + block_width (Γ_ktm M))"
      and poskle: "∀k < k_ktm M. posk k = AR_AtLE ⟷ ktc_pos cM k = 0"
      and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
      and pad0: "∀j ≥ k_ktm M. ktc_tape c0 j (ktc_pos c0 j) = BLANK4"
      and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                   (AR_SimWrite, 0, 0, buf, dvec, posk)"
  shows "∃c m. (c0, c) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ m
         ∧ m ≤ k_ktm M * (2 * block_width (Γ_ktm M))
         ∧ ktc_state c = (q, AR_SimAdvance, k_unidx 0, 0, buf, dvec, posk)
         ∧ ktc_tape c = (λk. if k < k_ktm M
              then (if ktc_pos cM k = 0 then ktc_tape c0 k
                    else (λpos. if sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k) ≤ pos
                                  ∧ pos < sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k)
                                            + block_width (Γ_ktm M)
                               then write_bit (Γ_ktm M) (bl_ktm M) (buf k)
                                      (pos - sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k))
                               else ktc_tape c0 k pos))
              else ktc_tape c0 k)
         ∧ ktc_pos c = ktc_pos c0"
proof -
  let ?k = "block_width (Γ_ktm M)"
  let ?N = "k_ktm M"
  let ?m1 = "?N - 1"
  let ?tl = "k_unidx ?m1"
  let ?p = "ktc_pos cM ?tl"
  let ?out = "λk. if ktc_pos cM k = 0 then ktc_tape c0 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) (buf k)
                                     (pos - sim_pos ?k (ktc_pos cM k))
                              else ktc_tape c0 k pos)"
  let ?tape = "λi. (λk. if k_idx k < i then ?out k else ktc_tape c0 k)"
  have card1: "0 < ?N" using vM by (cases M) auto
  have m1suc: "?N = Suc ?m1" using card1 by simp
  have m1card: "?m1 < ?N" using card1 by simp
  have m1lt: "?m1 < k_ktm M" using card1 by simp
  have tl_eq: "?tl = ?m1" by (simp add: k_unidx_def)
  have tlidx: "k_idx ?tl = ?m1" by (rule k_idx_unidx[OF m1card])
  have tl_active: "?tl < k_ktm M" using m1lt tl_eq by simp
  have islast: "is_last_k M ?tl" using is_last_k_unidx[OF m1card] m1suc by simp
  have cond: "(k < ?m1) = (k < k_ktm M)" if "k ≠ ?m1" for k
    using that m1suc by (auto simp: less_Suc_eq)
  obtain c1 m1 where
      c1_rel: "(c0, c1) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ m1"
    and m1_le: "m1 ≤ ?m1 * (2 * ?k)"
    and c1_st: "ktc_state c1 = (q, AR_SimWrite, ?tl, 0, buf, dvec, posk)"
    and c1_tp: "ktc_tape c1 = ?tape ?m1"
    and c1_ps: "ktc_pos c1 = ktc_pos c0"
    using ar_write_prefix[OF vM qQ kge2 stg0 tcorr ppos poskle buf_valid pad0 src0,
                          of ?m1]
    by auto
  have tc_tl: "ktc_tape c1 ?tl = ktc_tape c0 ?tl" using c1_tp tlidx by simp
  have tl_corr: "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
                   (ktc_tape cM ?tl) (ktc_tape c1 ?tl)"
    using tcorr[rule_format, OF tl_active] tc_tl by simp
  have tl_ppos: "ktc_pos c1 ?tl
                   = (if ?p = 0 then Suc 0 else sim_pos ?k ?p + ?k)"
    using c1_ps ppos[rule_format, OF tl_active] by simp
  have tl_poskle: "posk ?tl = AR_AtLE ⟷ ?p = 0"
    by (rule poskle[rule_format, OF tl_active])
  have tl_vsrc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
                   (AR_SimWrite, ?tl, 0, buf, dvec, posk)"
    using kge2 buf_valid by (auto simp: ar_valid_stage_def)
  have tail_idx: "⋀j. k_ktm M ≤ j ⟹ ¬ k_idx j < ?m1"
    using m1suc unfolding k_idx_def by linarith
  have pad_c1: "∀j ≥ k_ktm M. ktc_tape c1 j (ktc_pos c1 j) = BLANK4"
  proof (intro allI impI)
    fix j assume jge: "k_ktm M ≤ j"
    have "ktc_tape c1 j (ktc_pos c1 j) = ktc_tape c0 j (ktc_pos c0 j)"
      using c1_tp c1_ps tail_idx[OF jge] by simp
    thus "ktc_tape c1 j (ktc_pos c1 j) = BLANK4" using pad0 jge by simp
  qed
  have src_c1: "ar_stage_bounded (bl_ktm M) (k_ktm M)
                  (AR_SimWrite, ?tl, 0, buf, dvec, posk)"
    using src0 tl_active by (auto simp: ar_stage_bounded_def)
  obtain c2 where
      step: "(c1, c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (if ?p = 0 then 1 else 2 * ?k)"
    and c2_st: "ktc_state c2 = (q, AR_SimAdvance, k_unidx 0, 0, buf, dvec, posk)"
    and c2_tp: "ktc_tape c2 = (if ?p = 0 then ktc_tape c1
                  else (ktc_tape c1)(?tl := (λpos.
                    if sim_pos ?k ?p ≤ pos ∧ pos < sim_pos ?k ?p + ?k
                    then write_bit (Γ_ktm M) (bl_ktm M) (buf ?tl)
                           (pos - sim_pos ?k ?p)
                    else ktc_tape c1 ?tl pos)))"
    and c2_ps: "ktc_pos c2 = ktc_pos c1"
    using ar_write_tape_finish_step[OF vM qQ kge2 islast c1_st tl_corr tl_ppos
                                       tl_poskle buf_valid tl_vsrc pad_c1 src_c1]
    by blast
  ― ‹The last-tape ‹fun_upd› collapses to the active-guarded
     per-tape overwrite: active tapes get ‹?out›, padding tapes
     stay at ‹c0›'s tape (the walk never visits them).›
  have tape_full: "ktc_tape c2 = (λk. if k < k_ktm M then ?out k else ktc_tape c0 k)"
  proof (rule ext)
    fix k
    show "ktc_tape c2 k = (if k < k_ktm M then ?out k else ktc_tape c0 k)"
    proof (cases "k = ?tl")
      case True
      have out_tl: "ktc_tape c2 k = ?out k"
      proof (cases "?p = 0")
        case True
        have "ktc_tape c2 k = ktc_tape c0 ?tl"
          using c2_tp ‹k = ?tl› ‹?p = 0› tc_tl by simp
        moreover have "?out k = ktc_tape c0 ?tl"
          using ‹k = ?tl› ‹?p = 0› by simp
        ultimately show ?thesis by simp
      next
        case False
        show ?thesis
        proof (rule ext)
          fix pos
          have lhs: "ktc_tape c2 k pos
                  = (if sim_pos ?k ?p ≤ pos ∧ pos < sim_pos ?k ?p + ?k
                     then write_bit (Γ_ktm M) (bl_ktm M) (buf ?tl) (pos - sim_pos ?k ?p)
                     else ktc_tape c1 ?tl pos)"
            using c2_tp ‹k = ?tl› ‹?p ≠ 0› by simp
          have rhs: "?out k pos
                  = (if sim_pos ?k ?p ≤ pos ∧ pos < sim_pos ?k ?p + ?k
                     then write_bit (Γ_ktm M) (bl_ktm M) (buf ?tl) (pos - sim_pos ?k ?p)
                     else ktc_tape c0 ?tl pos)"
            using ‹k = ?tl› ‹?p ≠ 0› by simp
          show "ktc_tape c2 k pos = ?out k pos"
            using lhs rhs tc_tl by simp
        qed
      qed
      show ?thesis using out_tl ‹k = ?tl› tl_eq m1lt by simp
    next
      case False
      hence kne: "k ≠ ?m1" using tl_eq by simp
      show ?thesis
      proof (cases "k < ?m1")
        case True
        have klt: "k < k_ktm M" using True m1lt by simp
        have "ktc_tape c2 k = ktc_tape c1 k"
          using c2_tp ‹k ≠ ?tl› by (cases "?p = 0") simp_all
        also have "… = ?out k" using c1_tp True by (simp add: k_idx_def)
        finally show ?thesis using klt by simp
      next
        case False
        have kge: "¬ k < k_ktm M" using False kne cond[OF kne] by simp
        have "ktc_tape c2 k = ktc_tape c1 k"
          using c2_tp ‹k ≠ ?tl› by (cases "?p = 0") simp_all
        also have "… = ktc_tape c0 k" using c1_tp False by (simp add: k_idx_def)
        finally show ?thesis using kge by simp
      qed
    qed
  qed
  have chain: "(c0, c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (m1 + (if ?p = 0 then 1 else 2 * ?k))"
  proof -
    have "(c0, c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ m1
                       O (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (if ?p = 0 then 1 else 2 * ?k)"
      using c1_rel step by (rule relcompI)
    thus ?thesis by (simp add: relpow_add)
  qed
  have bound: "m1 + (if ?p = 0 then 1 else 2 * ?k) ≤ ?N * (2 * ?k)"
  proof -
    obtain Nm where Nm: "?N = Suc Nm" using card1 by (cases ?N) auto
    have e1: "?N * (2 * ?k) = (2 * ?k) + Nm * (2 * ?k)" by (simp add: Nm)
    have e2: "m1 ≤ Nm * (2 * ?k)" using m1_le Nm by simp
    have e3: "(if ?p = 0 then 1 else 2 * ?k) ≤ 2 * ?k" using kge2 by simp
    show ?thesis using e1 e2 e3 by linarith
  qed
  show ?thesis
  proof (intro exI[where x = c2]
           exI[where x = "m1 + (if ?p = 0 then 1 else 2 * ?k)"] conjI)
    show "(c0, c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_write M)) ^^ (m1 + (if ?p = 0 then 1 else 2 * ?k))" by (rule chain)
    show "m1 + (if ?p = 0 then 1 else 2 * ?k) ≤ ?N * (2 * ?k)" by (rule bound)
    show "ktc_state c2 = (q, AR_SimAdvance, k_unidx 0, 0, buf, dvec, posk)"
      by (rule c2_st)
    show "ktc_tape c2 = (λk. if k < k_ktm M
              then (if ktc_pos cM k = 0 then ktc_tape c0 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) (buf k)
                                      (pos - sim_pos ?k (ktc_pos cM k))
                               else ktc_tape c0 k pos))
              else ktc_tape c0 k)"
      using tape_full by simp
    show "ktc_pos c2 = ktc_pos c0" using c2_ps c1_ps by simp
  qed
qed

end