Theory Multitape_Alphabet_Enlargement.AlphabetEnlargement_ValidationStep

theory AlphabetEnlargement_ValidationStep
  imports AlphabetEnlargement_Codec
begin

subsection ‹Validation step machinery and initial config›

subsubsection ‹Validation canonicity equivalence with encoder image›

text ‹If a block is in ‹gamma_block (Sigma_M ∪ {bl_M})›,
  then the decoder's per-block output stays in ‹Sigma_M›: the
  takeWhile-prefix strips off any ‹bl_M›-symbols, leaving only
  ‹Sigma_M› elements.  Per-block contribution to the
  set-containment side of the iff lemma's forward direction.›

lemma ae_decode_block_subset:
  fixes c :: "nat ⇒ 'a"
    and Sigma :: "'a set"
    and bl :: 'a
  assumes "c ∈ gamma_block m (Sigma ∪ {bl})"
  shows "set (ae_decode_block m bl c) ⊆ Sigma"
proof
  fix a assume a_in: "a ∈ set (ae_decode_block m bl c)"
  let ?xs = "map c [0..<m]"
  have a_in_tW: "a ∈ set (takeWhile (λa. a ≠ bl) ?xs)"
    using a_in by (simp add: ae_decode_block_def)
  have neq_bl: "⋀ys :: 'a list. ∀x ∈ set (takeWhile (λa. a ≠ bl) ys).
                                    x ≠ bl"
  proof -
    fix ys :: "'a list"
    show "∀x ∈ set (takeWhile (λa. a ≠ bl) ys). x ≠ bl"
      by (induct ys) (auto split: if_split_asm)
  qed
  have a_neq_bl: "a ≠ bl" using a_in_tW neq_bl by blast
  have a_in_xs: "a ∈ set ?xs" using a_in_tW set_takeWhileD by metis
  obtain x where a_eq: "a = c x" and x_lt: "x < m"
    using a_in_xs by auto
  have c_x_in: "c x ∈ Sigma ∪ {bl}"
    using assms x_lt unfolding gamma_block_def by auto
  show "a ∈ Sigma" using a_eq a_neq_bl c_x_in by blast
qed

text ‹Validation lemmas — structural induction over the input.
  These do not require simulation infrastructure.›

text ‹The following biconditional characterises the AE machine's
  set of well-formed inputs: a string is
  ‹ae_input_well_formed› if and only if it is the encoder
  image of some base-alphabet input.  The headline language
  theorems ‹alphabet_enlarge_language› and
  ‹alphabet_enlarge_language_forward› are quantified only
  over explicit encoder-image inputs (‹set w ⊆ Sigma_ktm M›,
  with the AE-side string given as
  ‹encode_input (bl_ktm M) w›), so they need only the
  forward direction, ‹encode_input_well_formed› of theory
  ‹AlphabetEnlargement_Codec›; they never appeal to this
  biconditional's reverse direction (every well-formed AE-input
  has a preimage under the encoder).  The biconditional is
  retained as a structural completeness result identifying
  exactly what the AE machine accepts as a legitimate input, and
  is potentially useful for the nondeterministic-reverse
  research thread, where extracting an encoder preimage from an
  AE-validation hypothesis is one of the load-bearing steps.›

lemma ae_validation_canonical_iff_encoder_image:
  fixes M :: "('q, 'a) ktm"
    and w :: "(nat ⇒ 'a) list"
  assumes vM: "valid_ktm M"
      and w_sub: "set w ⊆ gamma_block m (Sigma_ktm M ∪ {bl_ktm M})"
      and m_pos: "0 < m"
  shows "ae_input_well_formed m (bl_ktm M) w
         ⟷ (∃u. set u ⊆ Sigma_ktm M
                  ∧ w = encode_input m (bl_ktm M) u)"
proof
  assume wf: "ae_input_well_formed m (bl_ktm M) w"
  let ?u = "ae_decode_input m (bl_ktm M) w"
  have round_trip: "encode_input m (bl_ktm M) ?u = w"
    using encode_decode_round_trip[OF wf m_pos] w_sub
    unfolding gamma_block_def by blast
  have u_sub: "set ?u ⊆ Sigma_ktm M"
  proof
    fix a assume "a ∈ set ?u"
    hence "a ∈ set (concat (map (ae_decode_block m (bl_ktm M)) w))"
      by (simp add: ae_decode_input_def)
    then obtain c where c_in: "c ∈ set w"
                    and a_in_blk: "a ∈ set (ae_decode_block m (bl_ktm M) c)"
      by auto
    have c_in_gamma: "c ∈ gamma_block m (Sigma_ktm M ∪ {bl_ktm M})"
      using c_in w_sub by blast
    have "set (ae_decode_block m (bl_ktm M) c) ⊆ Sigma_ktm M"
      by (rule ae_decode_block_subset[OF c_in_gamma])
    thus "a ∈ Sigma_ktm M" using a_in_blk by blast
  qed
  show "∃u. set u ⊆ Sigma_ktm M
              ∧ w = encode_input m (bl_ktm M) u"
    using u_sub round_trip[symmetric] by blast
next
  assume "∃u. set u ⊆ Sigma_ktm M
              ∧ w = encode_input m (bl_ktm M) u"
  then obtain u where
    u_sub: "set u ⊆ Sigma_ktm M" and
    w_eq: "w = encode_input m (bl_ktm M) u" by blast
  have "ae_input_well_formed m (bl_ktm M)
            (encode_input m (bl_ktm M) u :: (nat ⇒ 'a) list)"
    using encode_input_well_formed[OF vM u_sub] .
  thus "ae_input_well_formed m (bl_ktm M) w" using w_eq by simp
qed

subsubsection ‹Validation step helpers›

text ‹Step-helper library for the validation phase.  Each
  helper packages one validation substep relation as an
  ‹ktm_step›-constructor: given source-state and
  read-tape constraints satisfying the relation's source pattern,
  produce a single ‹ktm_step (alphabet_enlarge_delta M)›.
  Used by the three remaining commit-B lemmas
  (‹ae_validation_steps_bound›,
  ‹ae_validation_post_state_canonical›,
  ‹ae_validation_post_state_noncanonical›) to assemble
  validation-phase chains by composition rather than re-deriving
  each step.›

lemma ae_step_make:
  fixes M :: "('q, 'a) ktm"
    and ts :: "nat ⇒ nat ⇒ (nat ⇒ 'a)"
    and n :: "nat ⇒ nat"
    and s s' :: "'q × 'a ae_stage"
    and a' :: "nat ⇒ (nat ⇒ 'a)"
    and d :: "nat ⇒ move"
  assumes rel: "(s, (λk. ts k (n k)), s', a', d)
                  ∈ alphabet_enlarge_delta m M"
  shows "(KConfig s ts n,
            KConfig s' (λk. (ts k)(n k := a' k))
              (λk. go_move (d k) (n k)))
           ∈ ktm_step (alphabet_enlarge_delta m M)"
proof (rule ktm_step.intros)
  show "(s, (λk. ts k (n k)), s', a', d)
          ∈ alphabet_enlarge_delta m M" by (rule rel)
qed

text ‹Reflexive frozen-tail for the initial stage.  The stage
  fields ‹init_offset› / ‹init_buffer le› / ‹init_dest› agree with
  themselves beyond any tape count ‹K›, so this discharges the
  ‹stage_tail› premise of every validation step-helper at the call
  sites, where the stage is literally ‹init_stage (le_ktm M)› (the
  validation phases never touch the buffer).›

lemma init_stage_tail:
  "0 < m ⟹
   (∀j≥K. init_offset j = init_offset j)
   ∧ (∀j≥K. init_buffer m le j = init_buffer m le j)
   ∧ (∀j≥K. init_dest j = init_dest j)
   ∧ (∀j. init_offset j < m)"
  by (simp add: init_offset_def)

text ‹VFwd advance: read ‹LE_block› or a pure block on
  tape 0; head moves R on tape 0, N elsewhere; phase stays VFwd;
  no write change.›

lemma ae_step_val_fwd_advance:
  fixes M :: "('q, 'a) ktm"
    and ts :: "nat ⇒ nat ⇒ (nat ⇒ 'a)"
    and n :: "nat ⇒ nat"
    and q :: 'q
    and ofs :: "nat ⇒ nat"
    and buf :: "nat ⇒ (nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
    and dest :: "nat ⇒ ae_dest"
  assumes q_in: "q ∈ Q_ktm M"
      and q_neq_t: "q ≠ t_ktm M"
      and q_neq_r: "q ≠ r_ktm M"
      and read: "ts (0 :: nat) (n 0) = LE_block m (le_ktm M)
                  ∨ is_pure_block m (bl_ktm M) (ts 0 (n 0))"
      and bt: "∀j≥k_ktm M. ∀i. ts j i = bl_block m (bl_ktm M)"
      and stage_tail: "(∀j≥k_ktm M. ofs j = init_offset j)
                        ∧ (∀j≥k_ktm M. buf j = init_buffer m (le_ktm M) j)
                        ∧ (∀j≥k_ktm M. dest j = init_dest j)
                        ∧ (∀j. ofs j < m)"
      and gamma: "∀k. ts k (n k) ∈ gamma_block m (Γ_ktm M)"
      and buf_gamma: "∀k. fst (buf k) ∈ gamma_block m (Γ_ktm M)
                            ∧ fst (snd (buf k)) ∈ gamma_block m (Γ_ktm M)
                            ∧ snd (snd (buf k)) ∈ gamma_block m (Γ_ktm M)"
  shows "(KConfig (q, ofs, buf, dest, VFwd) ts n,
            KConfig (q, ofs, buf, dest, VFwd) ts
              (λk. go_move (if k = 0 then MoveR else MoveN) (n k)))
           ∈ ktm_step (alphabet_enlarge_delta m M)"
proof -
  let ?d = "λk :: nat. if k = 0 then MoveR else MoveN"
  let ?a = "λk. ts k (n k)"
  have rel_in: "((q, ofs, buf, dest, VFwd), ?a,
                  (q, ofs, buf, dest, VFwd), ?a, ?d)
                  ∈ ae_delta_val_fwd_advance m M"
    unfolding ae_delta_val_fwd_advance_def
    using q_in q_neq_t q_neq_r read bt by auto
  have src_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, VFwd)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have aed_in: "((q, ofs, buf, dest, VFwd), ?a,
                  (q, ofs, buf, dest, VFwd), ?a, ?d)
                  ∈ alphabet_enlarge_delta m M"
    unfolding alphabet_enlarge_delta_def
    using rel_in gamma src_valid by auto
  have ts_unchanged: "(λk. (ts k)(n k := ?a k)) = ts"
    by (rule ext) auto
  have step: "(KConfig (q, ofs, buf, dest, VFwd) ts n,
                KConfig (q, ofs, buf, dest, VFwd)
                  (λk. (ts k)(n k := ?a k))
                  (λk. go_move (?d k) (n k)))
                ∈ ktm_step (alphabet_enlarge_delta m M)"
  proof (rule ae_step_make)
    show "((q, ofs, buf, dest, VFwd), ?a,
            (q, ofs, buf, dest, VFwd), ?a, ?d)
              ∈ alphabet_enlarge_delta m M" by (rule aed_in)
  qed
  show ?thesis using step ts_unchanged by simp
qed

text ‹VFwd ‹→› VFwdPad: read a padded block on
  tape 0; head moves R on tape 0, N elsewhere; phase becomes
  VFwdPad; no write change.›

lemma ae_step_val_fwd_to_padded:
  fixes M :: "('q, 'a) ktm"
    and ts :: "nat ⇒ nat ⇒ (nat ⇒ 'a)"
    and n :: "nat ⇒ nat"
    and q :: 'q
    and ofs :: "nat ⇒ nat"
    and buf :: "nat ⇒ (nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
    and dest :: "nat ⇒ ae_dest"
  assumes q_in: "q ∈ Q_ktm M"
      and q_neq_t: "q ≠ t_ktm M"
      and q_neq_r: "q ≠ r_ktm M"
      and read: "is_padded_block m (bl_ktm M) (ts (0 :: nat) (n 0))"
      and bt: "∀j≥k_ktm M. ∀i. ts j i = bl_block m (bl_ktm M)"
      and stage_tail: "(∀j≥k_ktm M. ofs j = init_offset j)
                        ∧ (∀j≥k_ktm M. buf j = init_buffer m (le_ktm M) j)
                        ∧ (∀j≥k_ktm M. dest j = init_dest j)
                        ∧ (∀j. ofs j < m)"
      and gamma: "∀k. ts k (n k) ∈ gamma_block m (Γ_ktm M)"
      and buf_gamma: "∀k. fst (buf k) ∈ gamma_block m (Γ_ktm M)
                            ∧ fst (snd (buf k)) ∈ gamma_block m (Γ_ktm M)
                            ∧ snd (snd (buf k)) ∈ gamma_block m (Γ_ktm M)"
  shows "(KConfig (q, ofs, buf, dest, VFwd) ts n,
            KConfig (q, ofs, buf, dest, VFwdPad) ts
              (λk. go_move (if k = 0 then MoveR else MoveN) (n k)))
           ∈ ktm_step (alphabet_enlarge_delta m M)"
proof -
  let ?d = "λk :: nat. if k = 0 then MoveR else MoveN"
  let ?a = "λk. ts k (n k)"
  have rel_in: "((q, ofs, buf, dest, VFwd), ?a,
                  (q, ofs, buf, dest, VFwdPad), ?a, ?d)
                  ∈ ae_delta_val_fwd_to_padded m M"
    unfolding ae_delta_val_fwd_to_padded_def
    using q_in q_neq_t q_neq_r read bt by auto
  have src_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, VFwd)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have dst_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, VFwdPad)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have aed_in: "((q, ofs, buf, dest, VFwd), ?a,
                  (q, ofs, buf, dest, VFwdPad), ?a, ?d)
                  ∈ alphabet_enlarge_delta m M"
    unfolding alphabet_enlarge_delta_def
    using rel_in gamma src_valid dst_valid by auto
  have ts_unchanged: "(λk. (ts k)(n k := ?a k)) = ts"
    by (rule ext) auto
  have step: "(KConfig (q, ofs, buf, dest, VFwd) ts n,
                KConfig (q, ofs, buf, dest, VFwdPad)
                  (λk. (ts k)(n k := ?a k))
                  (λk. go_move (?d k) (n k)))
                ∈ ktm_step (alphabet_enlarge_delta m M)"
  proof (rule ae_step_make)
    show "((q, ofs, buf, dest, VFwd), ?a,
            (q, ofs, buf, dest, VFwdPad), ?a, ?d)
              ∈ alphabet_enlarge_delta m M" by (rule aed_in)
  qed
  show ?thesis using step ts_unchanged by simp
qed

text ‹VFwd ‹→› VRet: read ‹bl_block bl_M› on tape 0
  (past the encoded input); N moves uniformly (head stays); phase
  becomes VRet.›

lemma ae_step_val_fwd_to_ret:
  fixes M :: "('q, 'a) ktm"
    and ts :: "nat ⇒ nat ⇒ (nat ⇒ 'a)"
    and n :: "nat ⇒ nat"
    and q :: 'q
    and ofs :: "nat ⇒ nat"
    and buf :: "nat ⇒ (nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
    and dest :: "nat ⇒ ae_dest"
  assumes q_in: "q ∈ Q_ktm M"
      and q_neq_t: "q ≠ t_ktm M"
      and q_neq_r: "q ≠ r_ktm M"
      and read: "ts (0 :: nat) (n 0) = bl_block m (bl_ktm M)"
      and bt: "∀j≥k_ktm M. ∀i. ts j i = bl_block m (bl_ktm M)"
      and stage_tail: "(∀j≥k_ktm M. ofs j = init_offset j)
                        ∧ (∀j≥k_ktm M. buf j = init_buffer m (le_ktm M) j)
                        ∧ (∀j≥k_ktm M. dest j = init_dest j)
                        ∧ (∀j. ofs j < m)"
      and gamma: "∀k. ts k (n k) ∈ gamma_block m (Γ_ktm M)"
      and buf_gamma: "∀k. fst (buf k) ∈ gamma_block m (Γ_ktm M)
                            ∧ fst (snd (buf k)) ∈ gamma_block m (Γ_ktm M)
                            ∧ snd (snd (buf k)) ∈ gamma_block m (Γ_ktm M)"
  shows "(KConfig (q, ofs, buf, dest, VFwd) ts n,
            KConfig (q, ofs, buf, dest, VRet) ts n)
           ∈ ktm_step (alphabet_enlarge_delta m M)"
proof -
  let ?d = "λ_ :: nat. MoveN"
  let ?a = "λk. ts k (n k)"
  have rel_in: "((q, ofs, buf, dest, VFwd), ?a,
                  (q, ofs, buf, dest, VRet), ?a, ?d)
                  ∈ ae_delta_val_fwd_to_ret m M"
    unfolding ae_delta_val_fwd_to_ret_def
    using q_in q_neq_t q_neq_r read bt by auto
  have src_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, VFwd)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have dst_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, VRet)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have aed_in: "((q, ofs, buf, dest, VFwd), ?a,
                  (q, ofs, buf, dest, VRet), ?a, ?d)
                  ∈ alphabet_enlarge_delta m M"
    unfolding alphabet_enlarge_delta_def
    using rel_in gamma src_valid dst_valid by auto
  have ts_unchanged: "(λk. (ts k)(n k := ?a k)) = ts"
    by (rule ext) auto
  have n_unchanged: "(λk :: nat. go_move (?d k) (n k)) = n"
    by (rule ext) simp
  have step: "(KConfig (q, ofs, buf, dest, VFwd) ts n,
                KConfig (q, ofs, buf, dest, VRet)
                  (λk. (ts k)(n k := ?a k))
                  (λk. go_move (?d k) (n k)))
                ∈ ktm_step (alphabet_enlarge_delta m M)"
  proof (rule ae_step_make)
    show "((q, ofs, buf, dest, VFwd), ?a,
            (q, ofs, buf, dest, VRet), ?a, ?d)
              ∈ alphabet_enlarge_delta m M" by (rule aed_in)
  qed
  show ?thesis using step ts_unchanged n_unchanged by simp
qed

text ‹VFwdPad ‹→› VRet: read ‹bl_block bl_M› on tape 0
  (past the trailing-padded block into the blanks); N moves;
  phase becomes VRet.›

lemma ae_step_val_pad_to_ret:
  fixes M :: "('q, 'a) ktm"
    and ts :: "nat ⇒ nat ⇒ (nat ⇒ 'a)"
    and n :: "nat ⇒ nat"
    and q :: 'q
    and ofs :: "nat ⇒ nat"
    and buf :: "nat ⇒ (nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
    and dest :: "nat ⇒ ae_dest"
  assumes q_in: "q ∈ Q_ktm M"
      and read: "ts (0 :: nat) (n 0) = bl_block m (bl_ktm M)"
      and bt: "∀j≥k_ktm M. ∀i. ts j i = bl_block m (bl_ktm M)"
      and stage_tail: "(∀j≥k_ktm M. ofs j = init_offset j)
                        ∧ (∀j≥k_ktm M. buf j = init_buffer m (le_ktm M) j)
                        ∧ (∀j≥k_ktm M. dest j = init_dest j)
                        ∧ (∀j. ofs j < m)"
      and gamma: "∀k. ts k (n k) ∈ gamma_block m (Γ_ktm M)"
      and buf_gamma: "∀k. fst (buf k) ∈ gamma_block m (Γ_ktm M)
                            ∧ fst (snd (buf k)) ∈ gamma_block m (Γ_ktm M)
                            ∧ snd (snd (buf k)) ∈ gamma_block m (Γ_ktm M)"
  shows "(KConfig (q, ofs, buf, dest, VFwdPad) ts n,
            KConfig (q, ofs, buf, dest, VRet) ts n)
           ∈ ktm_step (alphabet_enlarge_delta m M)"
proof -
  let ?d = "λ_ :: nat. MoveN"
  let ?a = "λk. ts k (n k)"
  have rel_in: "((q, ofs, buf, dest, VFwdPad), ?a,
                  (q, ofs, buf, dest, VRet), ?a, ?d)
                  ∈ ae_delta_val_pad_to_ret m M"
    unfolding ae_delta_val_pad_to_ret_def
    using q_in read bt by auto
  have src_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, VFwdPad)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have dst_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, VRet)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have aed_in: "((q, ofs, buf, dest, VFwdPad), ?a,
                  (q, ofs, buf, dest, VRet), ?a, ?d)
                  ∈ alphabet_enlarge_delta m M"
    unfolding alphabet_enlarge_delta_def
    using rel_in gamma src_valid dst_valid by auto
  have ts_unchanged: "(λk. (ts k)(n k := ?a k)) = ts"
    by (rule ext) auto
  have n_unchanged: "(λk :: nat. go_move (?d k) (n k)) = n"
    by (rule ext) simp
  have step: "(KConfig (q, ofs, buf, dest, VFwdPad) ts n,
                KConfig (q, ofs, buf, dest, VRet)
                  (λk. (ts k)(n k := ?a k))
                  (λk. go_move (?d k) (n k)))
                ∈ ktm_step (alphabet_enlarge_delta m M)"
  proof (rule ae_step_make)
    show "((q, ofs, buf, dest, VFwdPad), ?a,
            (q, ofs, buf, dest, VRet), ?a, ?d)
              ∈ alphabet_enlarge_delta m M" by (rule aed_in)
  qed
  show ?thesis using step ts_unchanged n_unchanged by simp
qed

text ‹VRet step: read a non-LE block on tape 0 (during the
  return scan); head moves L on tape 0, N elsewhere; phase stays
  VRet.›

lemma ae_step_val_ret_step:
  fixes M :: "('q, 'a) ktm"
    and ts :: "nat ⇒ nat ⇒ (nat ⇒ 'a)"
    and n :: "nat ⇒ nat"
    and q :: 'q
    and ofs :: "nat ⇒ nat"
    and buf :: "nat ⇒ (nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
    and dest :: "nat ⇒ ae_dest"
  assumes q_in: "q ∈ Q_ktm M"
      and read: "ts (0 :: nat) (n 0) ≠ LE_block m (le_ktm M)"
      and bt: "∀j≥k_ktm M. ∀i. ts j i = bl_block m (bl_ktm M)"
      and stage_tail: "(∀j≥k_ktm M. ofs j = init_offset j)
                        ∧ (∀j≥k_ktm M. buf j = init_buffer m (le_ktm M) j)
                        ∧ (∀j≥k_ktm M. dest j = init_dest j)
                        ∧ (∀j. ofs j < m)"
      and gamma: "∀k. ts k (n k) ∈ gamma_block m (Γ_ktm M)"
      and buf_gamma: "∀k. fst (buf k) ∈ gamma_block m (Γ_ktm M)
                            ∧ fst (snd (buf k)) ∈ gamma_block m (Γ_ktm M)
                            ∧ snd (snd (buf k)) ∈ gamma_block m (Γ_ktm M)"
  shows "(KConfig (q, ofs, buf, dest, VRet) ts n,
            KConfig (q, ofs, buf, dest, VRet) ts
              (λk. go_move (if k = 0 then MoveL else MoveN) (n k)))
           ∈ ktm_step (alphabet_enlarge_delta m M)"
proof -
  let ?d = "λk :: nat. if k = 0 then MoveL else MoveN"
  let ?a = "λk. ts k (n k)"
  have rel_in: "((q, ofs, buf, dest, VRet), ?a,
                  (q, ofs, buf, dest, VRet), ?a, ?d)
                  ∈ ae_delta_val_ret_step m M"
    unfolding ae_delta_val_ret_step_def
    using q_in read bt by auto
  have src_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, VRet)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have aed_in: "((q, ofs, buf, dest, VRet), ?a,
                  (q, ofs, buf, dest, VRet), ?a, ?d)
                  ∈ alphabet_enlarge_delta m M"
    unfolding alphabet_enlarge_delta_def
    using rel_in gamma src_valid by auto
  have ts_unchanged: "(λk. (ts k)(n k := ?a k)) = ts"
    by (rule ext) auto
  have step: "(KConfig (q, ofs, buf, dest, VRet) ts n,
                KConfig (q, ofs, buf, dest, VRet)
                  (λk. (ts k)(n k := ?a k))
                  (λk. go_move (?d k) (n k)))
                ∈ ktm_step (alphabet_enlarge_delta m M)"
  proof (rule ae_step_make)
    show "((q, ofs, buf, dest, VRet), ?a,
            (q, ofs, buf, dest, VRet), ?a, ?d)
              ∈ alphabet_enlarge_delta m M" by (rule aed_in)
  qed
  show ?thesis using step ts_unchanged by simp
qed

text ‹VRet ‹→› Sim: read ‹LE_block le_M› on tape 0
  (return scan reached position 0); N moves uniformly (head
  stays); phase becomes Sim with ‹substep_idx› = SS1.›

lemma ae_step_val_ret_to_sim:
  fixes M :: "('q, 'a) ktm"
    and ts :: "nat ⇒ nat ⇒ (nat ⇒ 'a)"
    and n :: "nat ⇒ nat"
    and q :: 'q
    and ofs :: "nat ⇒ nat"
    and buf :: "nat ⇒ (nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
    and dest :: "nat ⇒ ae_dest"
  assumes q_in: "q ∈ Q_ktm M"
      and read: "ts (0 :: nat) (n 0) = LE_block m (le_ktm M)"
      and bt: "∀j≥k_ktm M. ∀i. ts j i = bl_block m (bl_ktm M)"
      and stage_tail: "(∀j≥k_ktm M. ofs j = init_offset j)
                        ∧ (∀j≥k_ktm M. buf j = init_buffer m (le_ktm M) j)
                        ∧ (∀j≥k_ktm M. dest j = init_dest j)
                        ∧ (∀j. ofs j < m)"
      and gamma: "∀k. ts k (n k) ∈ gamma_block m (Γ_ktm M)"
      and buf_gamma: "∀k. fst (buf k) ∈ gamma_block m (Γ_ktm M)
                            ∧ fst (snd (buf k)) ∈ gamma_block m (Γ_ktm M)
                            ∧ snd (snd (buf k)) ∈ gamma_block m (Γ_ktm M)"
  shows "(KConfig (q, ofs, buf, dest, VRet) ts n,
            KConfig (q, ofs, buf, dest, SS1) ts n)
           ∈ ktm_step (alphabet_enlarge_delta m M)"
proof -
  let ?d = "λ_ :: nat. MoveN"
  let ?a = "λk. ts k (n k)"
  have rel_in: "((q, ofs, buf, dest, VRet), ?a,
                  (q, ofs, buf, dest, SS1), ?a, ?d)
                  ∈ ae_delta_val_ret_to_sim m M"
    unfolding ae_delta_val_ret_to_sim_def
    using q_in read bt by auto
  have src_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, VRet)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have dst_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, SS1)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have aed_in: "((q, ofs, buf, dest, VRet), ?a,
                  (q, ofs, buf, dest, SS1), ?a, ?d)
                  ∈ alphabet_enlarge_delta m M"
    unfolding alphabet_enlarge_delta_def
    using rel_in gamma src_valid dst_valid by auto
  have ts_unchanged: "(λk. (ts k)(n k := ?a k)) = ts"
    by (rule ext) auto
  have n_unchanged: "(λk :: nat. go_move (?d k) (n k)) = n"
    by (rule ext) simp
  have step: "(KConfig (q, ofs, buf, dest, VRet) ts n,
                KConfig (q, ofs, buf, dest, SS1)
                  (λk. (ts k)(n k := ?a k))
                  (λk. go_move (?d k) (n k)))
                ∈ ktm_step (alphabet_enlarge_delta m M)"
  proof (rule ae_step_make)
    show "((q, ofs, buf, dest, VRet), ?a,
            (q, ofs, buf, dest, SS1), ?a, ?d)
              ∈ alphabet_enlarge_delta m M" by (rule aed_in)
  qed
  show ?thesis using step ts_unchanged n_unchanged by simp
qed

text ‹VFwd reject: read a non-canonical block on tape 0
  (in ‹Σ'› but neither pure nor padded — blanks in
  non-trailing positions); N moves uniformly; transition to
  ‹(r_M, init_stage le_M)›.›

lemma ae_step_val_fwd_reject:
  fixes M :: "('q, 'a) ktm"
    and ts :: "nat ⇒ nat ⇒ (nat ⇒ 'a)"
    and n :: "nat ⇒ nat"
    and q :: 'q
    and ofs :: "nat ⇒ nat"
    and buf :: "nat ⇒ (nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
    and dest :: "nat ⇒ ae_dest"
  assumes vM: "valid_ktm M"
      and q_in: "q ∈ Q_ktm M"
      and q_neq_t: "q ≠ t_ktm M"
      and q_neq_r: "q ≠ r_ktm M"
      and read_nle: "ts (0 :: nat) (n 0) ≠ LE_block m (le_ktm M)"
      and read_nbl: "ts (0 :: nat) (n 0) ≠ bl_block m (bl_ktm M)"
      and read_ncan: "¬ is_canonical_block m (bl_ktm M) (ts (0 :: nat) (n 0))"
      and bt: "∀j≥k_ktm M. ∀i. ts j i = bl_block m (bl_ktm M)"
      and stage_tail: "(∀j≥k_ktm M. ofs j = init_offset j)
                        ∧ (∀j≥k_ktm M. buf j = init_buffer m (le_ktm M) j)
                        ∧ (∀j≥k_ktm M. dest j = init_dest j)
                        ∧ (∀j. ofs j < m)"
      and gamma: "∀k. ts k (n k) ∈ gamma_block m (Γ_ktm M)"
      and buf_gamma: "∀k. fst (buf k) ∈ gamma_block m (Γ_ktm M)
                            ∧ fst (snd (buf k)) ∈ gamma_block m (Γ_ktm M)
                            ∧ snd (snd (buf k)) ∈ gamma_block m (Γ_ktm M)"
  shows "(KConfig (q, ofs, buf, dest, VFwd) ts n,
            KConfig (r_ktm M, init_stage m (le_ktm M)) ts n)
           ∈ ktm_step (alphabet_enlarge_delta m M)"
proof -
  let ?d = "λ_ :: nat. MoveN"
  let ?a = "λk. ts k (n k)"
  have rel_in: "((q, ofs, buf, dest, VFwd), ?a,
                  (r_ktm M, init_stage m (le_ktm M)), ?a, ?d)
                  ∈ ae_delta_val_fwd_reject m M"
    unfolding ae_delta_val_fwd_reject_def
    using q_in q_neq_t q_neq_r read_nle read_nbl read_ncan bt by auto
  have src_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, VFwd)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have dst_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((r_ktm M, init_stage m (le_ktm M))
                              :: 'q × 'a ae_stage))"
    using ae_valid_stage_init[OF valid_ktm_LE_in_Gamma[OF vM]
        ae_valid_stage_width_pos[OF src_valid]] by simp
  have aed_in: "((q, ofs, buf, dest, VFwd), ?a,
                  (r_ktm M, init_stage m (le_ktm M)), ?a, ?d)
                  ∈ alphabet_enlarge_delta m M"
    unfolding alphabet_enlarge_delta_def
    using rel_in gamma src_valid dst_valid by auto
  have ts_unchanged: "(λk. (ts k)(n k := ?a k)) = ts"
    by (rule ext) auto
  have n_unchanged: "(λk :: nat. go_move (?d k) (n k)) = n"
    by (rule ext) simp
  have step: "(KConfig (q, ofs, buf, dest, VFwd) ts n,
                KConfig (r_ktm M, init_stage m (le_ktm M))
                  (λk. (ts k)(n k := ?a k))
                  (λk. go_move (?d k) (n k)))
                ∈ ktm_step (alphabet_enlarge_delta m M)"
  proof (rule ae_step_make)
    show "((q, ofs, buf, dest, VFwd), ?a,
            (r_ktm M, init_stage m (le_ktm M)), ?a, ?d)
              ∈ alphabet_enlarge_delta m M" by (rule aed_in)
  qed
  show ?thesis using step ts_unchanged n_unchanged by simp
qed

text ‹VFwdPad reject: read anything on tape 0 other than
  ‹bl_block bl_M› (a non-blank block after the
  trailing-padded one); N moves; transition to
  ‹(r_M, init_stage le_M)›.›

lemma ae_step_val_pad_reject:
  fixes M :: "('q, 'a) ktm"
    and ts :: "nat ⇒ nat ⇒ (nat ⇒ 'a)"
    and n :: "nat ⇒ nat"
    and q :: 'q
    and ofs :: "nat ⇒ nat"
    and buf :: "nat ⇒ (nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
    and dest :: "nat ⇒ ae_dest"
  assumes vM: "valid_ktm M"
      and q_in: "q ∈ Q_ktm M"
      and read: "ts (0 :: nat) (n 0) ≠ bl_block m (bl_ktm M)"
      and bt: "∀j≥k_ktm M. ∀i. ts j i = bl_block m (bl_ktm M)"
      and stage_tail: "(∀j≥k_ktm M. ofs j = init_offset j)
                        ∧ (∀j≥k_ktm M. buf j = init_buffer m (le_ktm M) j)
                        ∧ (∀j≥k_ktm M. dest j = init_dest j)
                        ∧ (∀j. ofs j < m)"
      and gamma: "∀k. ts k (n k) ∈ gamma_block m (Γ_ktm M)"
      and buf_gamma: "∀k. fst (buf k) ∈ gamma_block m (Γ_ktm M)
                            ∧ fst (snd (buf k)) ∈ gamma_block m (Γ_ktm M)
                            ∧ snd (snd (buf k)) ∈ gamma_block m (Γ_ktm M)"
  shows "(KConfig (q, ofs, buf, dest, VFwdPad) ts n,
            KConfig (r_ktm M, init_stage m (le_ktm M)) ts n)
           ∈ ktm_step (alphabet_enlarge_delta m M)"
proof -
  let ?d = "λ_ :: nat. MoveN"
  let ?a = "λk. ts k (n k)"
  have rel_in: "((q, ofs, buf, dest, VFwdPad), ?a,
                  (r_ktm M, init_stage m (le_ktm M)), ?a, ?d)
                  ∈ ae_delta_val_pad_reject m M"
    unfolding ae_delta_val_pad_reject_def
    using q_in read bt by auto
  have src_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((q, ofs, buf, dest, VFwdPad)
                              :: 'q × 'a ae_stage))"
    using buf_gamma stage_tail unfolding ae_valid_stage_def by simp
  have dst_valid: "ae_valid_stage m (Γ_ktm M) (le_ktm M) (k_ktm M)
                      (snd ((r_ktm M, init_stage m (le_ktm M))
                              :: 'q × 'a ae_stage))"
    using ae_valid_stage_init[OF valid_ktm_LE_in_Gamma[OF vM]
        ae_valid_stage_width_pos[OF src_valid]] by simp
  have aed_in: "((q, ofs, buf, dest, VFwdPad), ?a,
                  (r_ktm M, init_stage m (le_ktm M)), ?a, ?d)
                  ∈ alphabet_enlarge_delta m M"
    unfolding alphabet_enlarge_delta_def
    using rel_in gamma src_valid dst_valid by auto
  have ts_unchanged: "(λk. (ts k)(n k := ?a k)) = ts"
    by (rule ext) auto
  have n_unchanged: "(λk :: nat. go_move (?d k) (n k)) = n"
    by (rule ext) simp
  have step: "(KConfig (q, ofs, buf, dest, VFwdPad) ts n,
                KConfig (r_ktm M, init_stage m (le_ktm M))
                  (λk. (ts k)(n k := ?a k))
                  (λk. go_move (?d k) (n k)))
                ∈ ktm_step (alphabet_enlarge_delta m M)"
  proof (rule ae_step_make)
    show "((q, ofs, buf, dest, VFwdPad), ?a,
            (r_ktm M, init_stage m (le_ktm M)), ?a, ?d)
              ∈ alphabet_enlarge_delta m M" by (rule aed_in)
  qed
  show ?thesis using step ts_unchanged n_unchanged by simp
qed

subsubsection ‹The initial configuration›

text ‹Shape lookups for ‹ae_init_config›.  These give the tape
  contents at named positions — LE at position 0, input blocks
  at positions ‹1…length w›, blank-block elsewhere — and the
  uniform state / head shape.  Used pervasively by the validation
  chain proofs; trivial unfoldings of ‹ae_init_config_def›.›

lemma ae_init_config_state:
  "ktc_state (ae_init_config m M w) = (s_ktm M, init_stage m (le_ktm M))"
  unfolding ae_init_config_def by simp

lemma ae_init_config_pos:
  "ktc_pos (ae_init_config m M w) k = 0"
  unfolding ae_init_config_def by simp

lemma ae_init_config_tape_le:
  assumes "k < k_ktm M"
  shows "ktc_tape (ae_init_config m M w) k 0 = LE_block m (le_ktm M)"
  using assms unfolding ae_init_config_def by simp

lemma ae_init_config_tape_input:
  assumes "1 ≤ p" and "p ≤ length w" and "0 < k_ktm M"
  shows "ktc_tape (ae_init_config m M w) 0 p = w ! (p - 1)"
  using assms unfolding ae_init_config_def by simp

lemma ae_init_config_tape_blank_after_input:
  assumes "p > length w"
  shows "ktc_tape (ae_init_config m M w) 0 p = bl_block m (bl_ktm M)"
  using assms unfolding ae_init_config_def by simp

lemma ae_init_config_tape_other:
  assumes "k ≠ 0" and "p > 0"
  shows "ktc_tape (ae_init_config m M w) k p = bl_block m (bl_ktm M)"
  using assms unfolding ae_init_config_def by simp

text ‹Blank-tail of the initial configuration: every cell of every
  inactive tape (index ‹≥ k_ktm M›) holds the blank block.
  This is the value-level support condition the substrate's
  ‹init_config_ktm› imposes on ‹alphabet_enlarge M›; it discharges
  the ‹∀j≥k_ktm M. ts j (n j) = bl_block (bl_ktm M)› premise of every
  validation step-helper (the tape is never written during
  validation, so ‹ts = ktc_tape (ae_init_config M w)› throughout).›

lemma ae_init_config_tape_blank_tail:
  assumes "k_ktm M ≤ k"
  shows "ktc_tape (ae_init_config m M w) k p = bl_block m (bl_ktm M)"
  using assms unfolding ae_init_config_def by simp

text ‹Gamma-block membership of every tape cell of the initial
  configuration.  Uniformly discharges the
  ‹∀k. ts k (n k) ∈ gamma_block (Γ_ktm M)› premise of every
  validation step-helper, regardless of the head position ‹n›
  reached during the chain.›

lemma ae_init_config_in_gamma_block:
  fixes M :: "('q, 'a) ktm"
    and w :: "(nat ⇒ 'a) list"
  assumes vM: "valid_ktm M"
      and w_sub: "set w ⊆ gamma_block m (Sigma_ktm M ∪ {bl_ktm M})"
  shows "ktc_tape (ae_init_config m M w) k p ∈ gamma_block m (Γ_ktm M)"
proof -
  have bl_in: "bl_ktm M ∈ Γ_ktm M"
    by (rule valid_ktm_blank_in_Gamma[OF vM])
  have le_in: "le_ktm M ∈ Γ_ktm M"
    by (rule valid_ktm_LE_in_Gamma[OF vM])
  have Sigma_sub: "Sigma_ktm M ⊆ Γ_ktm M"
    by (rule valid_ktm_Sigma_sub_Gamma[OF vM])
  have sub: "Sigma_ktm M ∪ {bl_ktm M} ⊆ Γ_ktm M"
    using Sigma_sub bl_in by auto
  have w_sub_G: "set w ⊆ gamma_block m (Γ_ktm M)"
    using w_sub gamma_block_mono[OF sub] by blast
  have kpos: "0 < k_ktm M" by (rule valid_ktm_k_pos[OF vM])
  consider
      (zero_act) "p = 0" and "k < k_ktm M"
    | (zero_inact) "p = 0" and "¬ k < k_ktm M"
    | (input) "p ≠ 0" and "k = 0" and "p ≤ length w"
    | (blank) "p ≠ 0" and "¬ (k = 0 ∧ p ≤ length w)"
    by blast
  thus ?thesis
  proof cases
    case zero_act
    have "ktc_tape (ae_init_config m M w) k p = LE_block m (le_ktm M)"
      using zero_act ae_init_config_tape_le by simp
    thus ?thesis using LE_block_in_gamma_block[OF le_in] by simp
  next
    case zero_inact
    have "ktc_tape (ae_init_config m M w) k p = bl_block m (bl_ktm M)"
      using zero_inact unfolding ae_init_config_def by simp
    thus ?thesis using bl_block_in_gamma_block[OF bl_in] by simp
  next
    case input
    have "ktc_tape (ae_init_config m M w) k p = w ! (p - 1)"
      using input kpos ae_init_config_tape_input[of p w M] by simp
    moreover have "w ! (p - 1) ∈ set w"
      using input by auto
    ultimately show ?thesis using w_sub_G by auto
  next
    case blank
    have "ktc_tape (ae_init_config m M w) k p = bl_block m (bl_ktm M)"
      using blank unfolding ae_init_config_def by auto
    thus ?thesis using bl_block_in_gamma_block[OF bl_in] by simp
  qed
qed

end