Theory 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