Theory AlphabetReduction_Reverse
theory AlphabetReduction_Reverse
imports AlphabetReduction_Theorems
begin
section ‹Alphabet reduction: reverse language inclusion›
text ‹The reverse leg of ‹alphabet_reduce_language›:
‹encode_input_ar (Γ_ktm M) (bl_ktm M) w ∈ Lang_ktm (alphabet_reduce M)
⟹ w ∈ Lang_ktm M›, the converse of the proven
‹alphabet_reduce_language_forward›.
This holds for deterministic and nondeterministic ‹M› alike, and
the proof is direct, with no argument about the uniqueness of
validation chains as in AE's reverse direction, because AR's only
nondeterministic substep, ‹ar_delta_compute›, is a direct
single-step embedding of ‹delta_ktm M› (one substrate tuple per
‹M›-tuple, no AE-style ‹m_steps_buffered› slack), so every
accepting ‹M'›-path decodes branch-by-branch to a genuine
accepting ‹M›-path.
The proof inverts the simulation directly: a per-cycle
backward step lemma reads the ‹M›-transition straight off the
compute tuple on the given ‹M'›-path and reuses the forward
direction's invariants ‹ar_simulates›, ‹ar_posk_consistent›,
‹ar_at_read_boundary› read backward; a backward chunked engine
aggregates the per-cycle steps into an ‹M›-run.
Throughout, ‹b› abbreviates ‹block_width Γ› (the per-symbol cell width).›
subsection ‹Terminal accept configuration›
text ‹Base case of the backward engine: the accept state
‹t_ktm (alphabet_reduce M)› is terminal. A valid machine never
steps from its accept state (substrate ‹ktm_step_src_neq_t›),
and ‹alphabet_reduce M› is valid by ‹alphabet_reduce_wf›;
its accept state is ‹(t_ktm M, ar_accept_stage (bl_ktm M))› by
‹alphabet_reduce_accept›.
Not used below: the reverse induction needs only the reject case,
‹ar_reject_terminal›, to rule out a rejecting configuration in the
middle of a path; this lemma is its accepting counterpart.›
lemma ar_accept_terminal:
fixes M :: "('q, 'a) ktm"
and c c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes vM: "valid_ktm M"
and card_ge: "card (Γ_ktm M) ≥ 4"
and step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
shows "ktc_state c ≠ (t_ktm M, ar_accept_stage (bl_ktm M))"
proof -
let ?M' = "alphabet_reduce M :: ('q × 'a ar_stage, sym4) ktm"
have valM': "valid_ktm ?M'" by (rule alphabet_reduce_wf[OF vM card_ge])
have step': "(c, c') ∈ ktm_step (delta_ktm ?M')" using step by simp
have "ktc_state c ≠ t_ktm ?M'" by (rule ktm_step_src_neq_t[OF valM' step'])
thus ?thesis by simp
qed
text ‹Reject companion of ‹ar_accept_terminal›: the reject state
‹r_ktm (alphabet_reduce M) = (r_ktm M, ar_reject_stage (bl_ktm M))›
(by ‹alphabet_reduce_reject›) is terminal too (substrate
‹ktm_step_src_neq_r›). The backward engine uses it to kill a
reject boundary reached mid-trace: the trace runs to the accept
config, so a reject config can carry no outgoing step.›
lemma ar_reject_terminal:
fixes M :: "('q, 'a) ktm"
and c c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes vM: "valid_ktm M"
and card_ge: "card (Γ_ktm M) ≥ 4"
and step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
shows "ktc_state c ≠ (r_ktm M, ar_reject_stage (bl_ktm M))"
proof -
let ?M' = "alphabet_reduce M :: ('q × 'a ar_stage, sym4) ktm"
have valM': "valid_ktm ?M'" by (rule alphabet_reduce_wf[OF vM card_ge])
have step': "(c, c') ∈ ktm_step (delta_ktm ?M')" using step by simp
have "ktc_state c ≠ r_ktm ?M'" by (rule ktm_step_src_neq_r[OF valM' step'])
thus ?thesis by simp
qed
subsection ‹Source substep-tags partition the substep relations›
text ‹Each of the five substep relations carries a uniform source
substep-tag (‹fst (snd s)› for a source state ‹s = (q, stg)›),
and the five tags are pairwise distinct datatype constructors. This
is the structural fact every step-inversion lemma rests on: a step
whose source is at substep ‹X› can only come from the relation
whose sources carry tag ‹X›.›
lemma ar_delta_read_src:
"(s, a, s', a', d) ∈ ar_delta_read M ⟹ fst (snd s) = AR_SimRead"
by (auto simp: ar_delta_read_def)
lemma ar_delta_compute_src:
"(s, a, s', a', d) ∈ ar_delta_compute M ⟹ fst (snd s) = AR_SimCompute"
by (auto simp: ar_delta_compute_def)
lemma ar_delta_write_src:
"(s, a, s', a', d) ∈ ar_delta_write M ⟹ fst (snd s) = AR_SimWrite"
by (auto simp: ar_delta_write_def)
lemma ar_delta_advance_src:
"(s, a, s', a', d) ∈ ar_delta_advance M ⟹ fst (snd s) = AR_SimAdvance"
by (auto simp: ar_delta_advance_def)
lemma ar_delta_next_src:
"(s, a, s', a', d) ∈ ar_delta_next M ⟹ fst (snd s) = AR_SimNext"
by (auto simp: ar_delta_next_def)
subsection ‹Where each substep can lead›
text ‹Each substep relation's destination tag is confined to a
small set: read loops to itself or transitions to compute; compute
is the unique non-deterministic step and lands at write; write
loops or advances; advance loops or hands off to next; next closes
the cycle (back to read) or dispatches to a halt-coerced
configuration. These five facts encode the substep transition
graph, and the reverse direction's arguments about the shape of a
path rest on them.›
lemma ar_delta_read_dest:
"(s, a, s', a', d) ∈ ar_delta_read M ⟹
fst (snd s') = AR_SimRead ∨ fst (snd s') = AR_SimCompute"
by (auto simp: ar_delta_read_def)
lemma ar_delta_compute_dest:
"(s, a, s', a', d) ∈ ar_delta_compute M ⟹ fst (snd s') = AR_SimWrite"
by (auto simp: ar_delta_compute_def)
lemma ar_delta_write_dest:
"(s, a, s', a', d) ∈ ar_delta_write M ⟹
fst (snd s') = AR_SimWrite ∨ fst (snd s') = AR_SimAdvance"
by (auto simp: ar_delta_write_def)
lemma ar_delta_advance_dest:
"(s, a, s', a', d) ∈ ar_delta_advance M ⟹
fst (snd s') = AR_SimAdvance ∨ fst (snd s') = AR_SimNext"
by (auto simp: ar_delta_advance_def)
lemma ar_delta_next_dest:
"(s, a, s', a', d) ∈ ar_delta_next M ⟹
fst (snd s') = AR_SimRead ∨ fst (snd s') = AR_HaltAccept
∨ fst (snd s') = AR_HaltReject"
by (auto simp: ar_delta_next_def ar_accept_stage_def ar_reject_stage_def)
text ‹Union-disambiguation: a tuple in ‹alphabet_reduce_delta M›
whose source is at ‹AR_SimCompute› must lie in the compute
relation ‹ar_delta_compute M›. The intersection filters of
‹alphabet_reduce_delta› (‹δLE› and the valid-stage
guards) only shrink the union, so membership of the union is all we
need; the other four source-tag lemmas rule out the other disjuncts
by constructor-distinctness.›
lemma ar_delta_compute_from_src:
assumes mem: "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
and src: "fst (snd s) = AR_SimCompute"
shows "(s, a, s', a', d) ∈ ar_delta_compute M"
proof -
from mem
have u: "(s, a, s', a', d) ∈ ar_delta_read M ∪ ar_delta_compute M
∪ ar_delta_write M ∪ ar_delta_advance M ∪ ar_delta_next M"
unfolding alphabet_reduce_delta_def by blast
have nr: "(s, a, s', a', d) ∉ ar_delta_read M"
proof
assume "(s, a, s', a', d) ∈ ar_delta_read M"
from ar_delta_read_src[OF this] src show False by simp
qed
have nw: "(s, a, s', a', d) ∉ ar_delta_write M"
proof
assume "(s, a, s', a', d) ∈ ar_delta_write M"
from ar_delta_write_src[OF this] src show False by simp
qed
have nad: "(s, a, s', a', d) ∉ ar_delta_advance M"
proof
assume "(s, a, s', a', d) ∈ ar_delta_advance M"
from ar_delta_advance_src[OF this] src show False by simp
qed
have nx: "(s, a, s', a', d) ∉ ar_delta_next M"
proof
assume "(s, a, s', a', d) ∈ ar_delta_next M"
from ar_delta_next_src[OF this] src show False by simp
qed
from u nr nw nad nx show ?thesis by blast
qed
subsection ‹Compute-step inversion›
text ‹The central lemma of the reverse direction: a single ‹M'›-step out of
an ‹AR_SimCompute› configuration reads the simulated
‹M›-transition straight off the compute tuple. Because
‹ar_delta_compute› is a direct single-step embedding of
‹delta_ktm M›, the inversion yields a genuine
‹(q, buf, q', m_a', m_d) ∈ delta_ktm M› with no chain-uniqueness
or determinism assumption — this is where AR's ND-generality is
earned. Compute neither writes nor moves: the tape and head
positions are unchanged (read symbol equals write symbol, direction
‹N›).›
lemma ar_compute_step_inv_sub:
fixes M :: "('q, 'a) ktm"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes step: "(c', c'') ∈ ktm_step (ar_delta_compute M)"
and stg: "ktc_state c' = (q, AR_SimCompute, tk, i, buf, dvec, posk)"
obtains q' m_a' m_d where
"(q, buf, q', m_a', m_d) ∈ delta_ktm M"
and "ktc_state c'' = (q', AR_SimWrite, 0, 0, m_a', m_d, posk)"
and "ktc_tape c'' = ktc_tape c'"
and "ktc_pos c'' = ktc_pos c'"
proof -
from step obtain S ts n S'' aw move where
c'_eq: "c' = KConfig S ts n"
and c''_eq: "c'' = KConfig S'' (λk. (ts k)(n k := aw k))
(λk. go_move (move k) (n k))"
and rel: "(S, (λk. ts k (n k)), S'', aw, move)
∈ ar_delta_compute M"
by (auto elim: ktm_step.cases)
have S_eq: "S = (q, AR_SimCompute, tk, i, buf, dvec, posk)"
using stg c'_eq by simp
have crel: "((q, AR_SimCompute, tk, i, buf, dvec, posk),
(λk. ts k (n k)), S'', aw, move) ∈ ar_delta_compute M"
using rel S_eq by simp
from crel obtain q' m_a' m_d where
mdelta: "(q, buf, q', m_a', m_d) ∈ delta_ktm M"
and S''_eq: "S'' = (q', AR_SimWrite, 0, 0, m_a', m_d, posk)"
and aw_eq: "aw = (λk. ts k (n k))"
and dir_eq: "move = (λ_. MoveN)"
unfolding ar_delta_compute_def by auto
have state: "ktc_state c'' = (q', AR_SimWrite, 0, 0, m_a', m_d, posk)"
using c''_eq S''_eq by simp
have tape: "ktc_tape c'' = ktc_tape c'"
proof -
have "ktc_tape c'' = (λk. (ts k)(n k := aw k))" using c''_eq by simp
also have "… = ts" by (simp add: aw_eq fun_upd_triv)
finally show ?thesis using c'_eq by simp
qed
have pos: "ktc_pos c'' = ktc_pos c'"
proof -
have "ktc_pos c'' = (λk. go_move (move k) (n k))" using c''_eq by simp
also have "… = n" by (simp add: dir_eq)
finally show ?thesis using c'_eq by simp
qed
show ?thesis by (rule that[OF mdelta state tape pos])
qed
text ‹The union-step face of the inversion: lift the union step into
the compute sub-relation (‹ar_step_compute_lift›) and invert there.
Used by the preservation lemma ‹ar_walker_step_from_at_compute›
below; the lemma that closes a cycle inverts the compute step of the
sub-relation directly, via ‹ar_compute_step_inv_sub›.›
lemma ar_compute_step_inv:
fixes M :: "('q, 'a) ktm"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
and stg: "ktc_state c' = (q, AR_SimCompute, tk, i, buf, dvec, posk)"
obtains q' m_a' m_d where
"(q, buf, q', m_a', m_d) ∈ delta_ktm M"
and "ktc_state c'' = (q', AR_SimWrite, 0, 0, m_a', m_d, posk)"
and "ktc_tape c'' = ktc_tape c'"
and "ktc_pos c'' = ktc_pos c'"
proof -
from step obtain S ts n S'' aw move where
c'_eq: "c' = KConfig S ts n"
and c''_eq: "c'' = KConfig S'' (λk. (ts k)(n k := aw k))
(λk. go_move (move k) (n k))"
and rel: "(S, (λk. ts k (n k)), S'', aw, move)
∈ alphabet_reduce_delta M"
by (auto elim: ktm_step.cases)
have src: "fst (snd S) = AR_SimCompute" using stg c'_eq by simp
have crel: "(S, (λk. ts k (n k)), S'', aw, move) ∈ ar_delta_compute M"
by (rule ar_delta_compute_from_src[OF rel src])
have step_explicit:
"(KConfig S ts n, KConfig S'' (λk. (ts k)(n k := aw k))
(λk. go_move (move k) (n k))) ∈ ktm_step (ar_delta_compute M)"
using crel by (rule ktm_step.step)
have sub: "(c', c'') ∈ ktm_step (ar_delta_compute M)"
using step_explicit c'_eq c''_eq by simp
show thesis
proof (rule ar_compute_step_inv_sub[OF sub stg])
fix q' m_a' m_d
assume "(q, buf, q', m_a', m_d) ∈ delta_ktm M"
and "ktc_state c'' = (q', AR_SimWrite, 0, 0, m_a', m_d, posk)"
and "ktc_tape c'' = ktc_tape c'"
and "ktc_pos c'' = ktc_pos c'"
thus thesis by (rule that)
qed
qed
subsection ‹Inverting the closing substep: next cycle or halt›
text ‹Source disambiguation for ‹AR_SimNext›, mirroring
‹ar_delta_compute_from_src›.›
lemma ar_delta_next_from_src:
assumes mem: "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
and src: "fst (snd s) = AR_SimNext"
shows "(s, a, s', a', d) ∈ ar_delta_next M"
proof -
from mem
have u: "(s, a, s', a', d) ∈ ar_delta_read M ∪ ar_delta_compute M
∪ ar_delta_write M ∪ ar_delta_advance M ∪ ar_delta_next M"
unfolding alphabet_reduce_delta_def by blast
have nr: "(s, a, s', a', d) ∉ ar_delta_read M"
proof
assume "(s, a, s', a', d) ∈ ar_delta_read M"
from ar_delta_read_src[OF this] src show False by simp
qed
have nc: "(s, a, s', a', d) ∉ ar_delta_compute M"
proof
assume "(s, a, s', a', d) ∈ ar_delta_compute M"
from ar_delta_compute_src[OF this] src show False by simp
qed
have nw: "(s, a, s', a', d) ∉ ar_delta_write M"
proof
assume "(s, a, s', a', d) ∈ ar_delta_write M"
from ar_delta_write_src[OF this] src show False by simp
qed
have nad: "(s, a, s', a', d) ∉ ar_delta_advance M"
proof
assume "(s, a, s', a', d) ∈ ar_delta_advance M"
from ar_delta_advance_src[OF this] src show False by simp
qed
from u nr nc nw nad show ?thesis by blast
qed
text ‹A single ‹M'›-step out of an ‹AR_SimNext›
configuration neither writes nor moves, and dispatches on the
simulated ‹M›-state ‹q›: continue to the next
‹AR_SimRead› boundary when ‹q› is non-halting, or land
in the accept/reject halt stage when ‹q› is ‹M›'s
accept/reject state. The accept landing is exactly
‹t_ktm (alphabet_reduce M)›.›
lemma ar_next_step_inv:
fixes M :: "('q, 'a) ktm"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
and stg: "ktc_state c' = (q, AR_SimNext, tk, i, buf, dvec, posk)"
shows "ktc_tape c'' = ktc_tape c' ∧ ktc_pos c'' = ktc_pos c'
∧ ((q ∉ {t_ktm M, r_ktm M}
∧ ktc_state c'' = (q, AR_SimRead, 0, 0, buf, dvec, posk))
∨ (q = t_ktm M
∧ ktc_state c'' = (t_ktm M, ar_accept_stage (bl_ktm M)))
∨ (q = r_ktm M
∧ ktc_state c'' = (r_ktm M, ar_reject_stage (bl_ktm M))))"
proof -
from step obtain S ts n S'' aw move where
c'_eq: "c' = KConfig S ts n"
and c''_eq: "c'' = KConfig S'' (λk. (ts k)(n k := aw k))
(λk. go_move (move k) (n k))"
and rel: "(S, (λk. ts k (n k)), S'', aw, move)
∈ alphabet_reduce_delta M"
by (auto elim: ktm_step.cases)
have S_eq: "S = (q, AR_SimNext, tk, i, buf, dvec, posk)"
using stg c'_eq by simp
have src: "fst (snd S) = AR_SimNext" using S_eq by simp
have nrel: "((q, AR_SimNext, tk, i, buf, dvec, posk),
(λk. ts k (n k)), S'', aw, move) ∈ ar_delta_next M"
using ar_delta_next_from_src[OF rel src] S_eq by simp
have core: "aw = (λk. ts k (n k)) ∧ move = (λ_. MoveN)
∧ ((q ∉ {t_ktm M, r_ktm M}
∧ S'' = (q, AR_SimRead, 0, 0, buf, dvec, posk))
∨ (q = t_ktm M ∧ S'' = (t_ktm M, ar_accept_stage (bl_ktm M)))
∨ (q = r_ktm M ∧ S'' = (r_ktm M, ar_reject_stage (bl_ktm M))))"
using nrel
unfolding ar_delta_next_def ar_accept_stage_def ar_reject_stage_def
by auto
have tape: "ktc_tape c'' = ktc_tape c'"
proof -
have "ktc_tape c'' = (λk. (ts k)(n k := aw k))" using c''_eq by simp
also have "… = ts" using core by (simp add: fun_upd_triv)
finally show ?thesis using c'_eq by simp
qed
have pos: "ktc_pos c'' = ktc_pos c'"
proof -
have "ktc_pos c'' = (λk. go_move (move k) (n k))" using c''_eq by simp
also have "… = n" using core by simp
finally show ?thesis using c'_eq by simp
qed
have st: "ktc_state c'' = S''" using c''_eq by simp
show ?thesis using tape pos core st by simp
qed
subsection ‹Source disambiguation for the remaining substeps›
text ‹Source disambiguation for the remaining three substeps,
completing the ‹from_src› family alongside
‹ar_delta_compute_from_src› / ‹ar_delta_next_from_src›.›
lemma ar_delta_read_from_src:
assumes "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
and "fst (snd s) = AR_SimRead"
shows "(s, a, s', a', d) ∈ ar_delta_read M"
using assms unfolding alphabet_reduce_delta_def
by (auto dest: ar_delta_compute_src ar_delta_write_src
ar_delta_advance_src ar_delta_next_src)
lemma ar_delta_write_from_src:
assumes "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
and "fst (snd s) = AR_SimWrite"
shows "(s, a, s', a', d) ∈ ar_delta_write M"
using assms unfolding alphabet_reduce_delta_def
by (auto dest: ar_delta_read_src ar_delta_compute_src
ar_delta_advance_src ar_delta_next_src)
lemma ar_delta_advance_from_src:
assumes "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
and "fst (snd s) = AR_SimAdvance"
shows "(s, a, s', a', d) ∈ ar_delta_advance M"
using assms unfolding alphabet_reduce_delta_def
by (auto dest: ar_delta_read_src ar_delta_compute_src
ar_delta_write_src ar_delta_next_src)
text ‹Every ‹alphabet_reduce_delta› tuple has its source at one
of the five substep tags (the halt tags never appear as sources).›
lemma alphabet_reduce_delta_src_tag:
assumes "(s, a, s', a', d) ∈ alphabet_reduce_delta M"
shows "fst (snd s) ∈ {AR_SimRead, AR_SimCompute, AR_SimWrite,
AR_SimAdvance, AR_SimNext}"
using assms unfolding alphabet_reduce_delta_def
by (auto dest: ar_delta_read_src ar_delta_compute_src ar_delta_write_src
ar_delta_advance_src ar_delta_next_src)
subsection ‹Where a step of each substep lands›
text ‹Lift the per-relation destination-tag lemmas
(‹ar_delta_X_dest›) up through ‹ktm_step›: an
‹M'›-step out of a configuration whose source idx is
‹AR_SimX› lands at a configuration whose idx is in
‹X›'s dest set. The five lemmas compose the substrate's
‹ktm_step_states› (the firing tuple's two states), the
‹from_src› union-disambiguation helpers, and
‹ar_delta_X_dest›. Together they encode the cycle's
substep transition graph at the level of whole ‹M'›-steps, which is
what the induction along the path below uses: SimRead-loop-or-compute, compute-to-write,
write-loop-or-advance, advance-loop-or-next,
next-to-read-or-halt.›
lemma ar_step_from_SimRead_lands:
assumes step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
and src: "fst (snd (ktc_state c)) = AR_SimRead"
shows "fst (snd (ktc_state c')) = AR_SimRead
∨ fst (snd (ktc_state c')) = AR_SimCompute"
proof -
from step obtain a a' d
where "(ktc_state c, a, ktc_state c', a', d) ∈ alphabet_reduce_delta M"
by (rule ktm_step_states)
from ar_delta_read_from_src [OF this src] show ?thesis
by (rule ar_delta_read_dest)
qed
text ‹The ‹compute› member of the five lemmas above is not used: the
compute substep is the nondeterministic branch point, and the proof
handles it by reading the ‹M›-transition off the step instead. It is
stated so that the substep transition graph is complete.›
lemma ar_step_from_SimCompute_lands:
assumes step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
and src: "fst (snd (ktc_state c)) = AR_SimCompute"
shows "fst (snd (ktc_state c')) = AR_SimWrite"
proof -
from step obtain a a' d
where "(ktc_state c, a, ktc_state c', a', d) ∈ alphabet_reduce_delta M"
by (rule ktm_step_states)
from ar_delta_compute_from_src [OF this src] show ?thesis
by (rule ar_delta_compute_dest)
qed
lemma ar_step_from_SimWrite_lands:
assumes step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
and src: "fst (snd (ktc_state c)) = AR_SimWrite"
shows "fst (snd (ktc_state c')) = AR_SimWrite
∨ fst (snd (ktc_state c')) = AR_SimAdvance"
proof -
from step obtain a a' d
where "(ktc_state c, a, ktc_state c', a', d) ∈ alphabet_reduce_delta M"
by (rule ktm_step_states)
from ar_delta_write_from_src [OF this src] show ?thesis
by (rule ar_delta_write_dest)
qed
lemma ar_step_from_SimAdvance_lands:
assumes step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
and src: "fst (snd (ktc_state c)) = AR_SimAdvance"
shows "fst (snd (ktc_state c')) = AR_SimAdvance
∨ fst (snd (ktc_state c')) = AR_SimNext"
proof -
from step obtain a a' d
where "(ktc_state c, a, ktc_state c', a', d) ∈ alphabet_reduce_delta M"
by (rule ktm_step_states)
from ar_delta_advance_from_src [OF this src] show ?thesis
by (rule ar_delta_advance_dest)
qed
lemma ar_step_from_SimNext_lands:
assumes step: "(c, c') ∈ ktm_step (alphabet_reduce_delta M)"
and src: "fst (snd (ktc_state c)) = AR_SimNext"
shows "fst (snd (ktc_state c')) = AR_SimRead
∨ fst (snd (ktc_state c')) = AR_HaltAccept
∨ fst (snd (ktc_state c')) = AR_HaltReject"
proof -
from step obtain a a' d
where "(ktc_state c, a, ktc_state c', a', d) ∈ alphabet_reduce_delta M"
by (rule ktm_step_states)
from ar_delta_next_from_src [OF this src] show ?thesis
by (rule ar_delta_next_dest)
qed
subsection ‹Invariants for each substep of the cycle›
text ‹The reverse direction walks along the ‹M'›-path one step at a time
(hence the ∗‹walker› in the names below): an induction over the path
that tracks where in the cycle we are by reading
the substep idx off each visited configuration's state. Six stage
predicates carry the per-substep relationship between the cycle's
source ‹M›-config ‹cM› and the current
‹M'›-configuration ‹c'›:
▪ ‹ar_walker_at_boundary M cM c'›: fresh cycle start —
‹c'› at ‹AR_SimRead› boundary, the three
forward invariants hold for ‹cM›.
▪ ‹ar_walker_in_read M cM c'›: mid-read-phase —
reachable from a boundary by ‹ar_delta_read›-only
steps, still at ‹AR_SimRead›.
▪ ‹ar_walker_at_compute M cM c'›: read complete —
reachable from a boundary by ‹ar_delta_read›-only
steps, now at ‹AR_SimCompute›. The next M'-step on
the path extracts the M-tuple via
‹ar_compute_step_inv›.
▪ ‹ar_walker_in_write M cM c'›: M-tuple
extracted, mid-write-phase — at ‹AR_SimWrite›.
▪ ‹ar_walker_in_advance M cM c'›: write done,
mid-advance-phase — at ‹AR_SimAdvance›.
▪ ‹ar_walker_at_next M cM c'›: at
‹AR_SimNext›, about to dispatch to next boundary or
halt via ‹ar_next_step_inv›.
The witness-chain formulation (rather than concrete per-state
conditions) makes preservation lemmas mechanical: at a config with
substep tag T, an M'-step fires the unique substep relation with
src tag T (by ‹ar_delta_T_src› + ‹from_src›);
extending the witness chain by one step preserves the invariant.
Chain shape (no cycle-wrap before completing this cycle) follows
from the witness chain living in the ∗‹specific› substep relation
‹ktm_step (ar_delta_T M)›, which by
‹ar_delta_T_src› can only fire from sources at T —
ruling out the wrap.›
definition ar_walker_at_boundary ::
"('q, 'a) ktm
⇒ ('a, 'q) ktc_config
⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
"ar_walker_at_boundary M cM c' ⟷
ar_simulates M cM c'
∧ ar_posk_consistent M cM c'
∧ ar_at_read_boundary M c'"
definition ar_walker_in_read ::
"('q, 'a) ktm
⇒ ('a, 'q) ktc_config
⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
"ar_walker_in_read M cM c' ⟷
fst (snd (ktc_state c')) = AR_SimRead
∧ (∃c_b m. ar_walker_at_boundary M cM c_b
∧ (c_b, c') ∈ (ktm_step (ar_delta_read M)) ^^ m)"
definition ar_walker_at_compute ::
"('q, 'a) ktm
⇒ ('a, 'q) ktc_config
⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
"ar_walker_at_compute M cM c' ⟷
fst (snd (ktc_state c')) = AR_SimCompute
∧ (∃c_b m. ar_walker_at_boundary M cM c_b
∧ (c_b, c') ∈ (ktm_step (ar_delta_read M)) ^^ m)"
definition ar_walker_in_write ::
"('q, 'a) ktm
⇒ ('a, 'q) ktc_config
⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
"ar_walker_in_write M cM c' ⟷
fst (snd (ktc_state c')) = AR_SimWrite
∧ (∃c_b c_w m_r m_w.
ar_walker_at_boundary M cM c_b
∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
∧ fst (snd (ktc_state c_w)) = AR_SimCompute
∧ (∃c_w_post. (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
∧ (c_w_post, c') ∈ (ktm_step (ar_delta_write M)) ^^ m_w))"
definition ar_walker_in_advance ::
"('q, 'a) ktm
⇒ ('a, 'q) ktc_config
⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
"ar_walker_in_advance M cM c' ⟷
fst (snd (ktc_state c')) = AR_SimAdvance
∧ (∃c_b c_w c_a m_r m_w m_a.
ar_walker_at_boundary M cM c_b
∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
∧ fst (snd (ktc_state c_w)) = AR_SimCompute
∧ fst (snd (ktc_state c_a)) = AR_SimAdvance
∧ (∃c_w_post. (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
∧ (c_a, c') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a))"
definition ar_walker_at_next ::
"('q, 'a) ktm
⇒ ('a, 'q) ktc_config
⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
"ar_walker_at_next M cM c' ⟷
fst (snd (ktc_state c')) = AR_SimNext
∧ (∃c_b c_w c_a c_n m_r m_w m_a.
ar_walker_at_boundary M cM c_b
∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
∧ fst (snd (ktc_state c_w)) = AR_SimCompute
∧ fst (snd (ktc_state c_a)) = AR_SimAdvance
∧ (∃c_w_post. (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
∧ (c_a, c_n) ∈ (ktm_step (ar_delta_advance M)) ^^ m_a
∧ c_n = c'))"
subsection ‹A step from a given substep is a step of that substep's relation›
text ‹Four ‹ktm_step›-to-specific-substep lifts: an
‹M'›-step in ‹ktm_step (alphabet_reduce_delta M)›
whose source carries substep tag T is in fact in the smaller
‹ktm_step (ar_delta_T M)›. Each is the substrate's
‹ktm_step_restrict_src› applied to the matching
‹ar_delta_T_from_src› helper, which narrows the firing tuple by
src-tag uniqueness. The preservation lemmas below chain these lifts
with the destination lemmas (‹ar_step_from_SimX_lands›) to extend
the witness chain by one step.›
lemma ar_step_read_lift:
fixes M :: "('q, 'a) ktm"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes src: "fst (snd (ktc_state c')) = AR_SimRead"
and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
shows "(c', c'') ∈ ktm_step (ar_delta_read M)"
by (rule ktm_step_restrict_src [OF step])
(erule ar_delta_read_from_src, assumption, rule src)
lemma ar_step_compute_lift:
fixes M :: "('q, 'a) ktm"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes src: "fst (snd (ktc_state c')) = AR_SimCompute"
and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
shows "(c', c'') ∈ ktm_step (ar_delta_compute M)"
by (rule ktm_step_restrict_src [OF step])
(erule ar_delta_compute_from_src, assumption, rule src)
lemma ar_step_write_lift:
fixes M :: "('q, 'a) ktm"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes src: "fst (snd (ktc_state c')) = AR_SimWrite"
and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
shows "(c', c'') ∈ ktm_step (ar_delta_write M)"
by (rule ktm_step_restrict_src [OF step])
(erule ar_delta_write_from_src, assumption, rule src)
lemma ar_step_advance_lift:
fixes M :: "('q, 'a) ktm"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes src: "fst (snd (ktc_state c')) = AR_SimAdvance"
and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
shows "(c', c'') ∈ ktm_step (ar_delta_advance M)"
by (rule ktm_step_restrict_src [OF step])
(erule ar_delta_advance_from_src, assumption, rule src)
subsection ‹Runs of the read substep are determined›
text ‹Two structural facts about chains in the read sub-relation:
the sub-relation is ∗‹functional› (‹ar_delta_read_functional›,
lifted to steps by the substrate's ‹ktm_step_det_at›); and it
cannot fire from a source whose substep tag is ‹AR_SimCompute›
(by ‹ar_delta_read_src›). The substrate's
‹relpow_halted_same_run› turns the two into the pinning: a chain
ending at ‹AR_SimCompute› is unique in both its length and its
endpoint, so if two chains in the sub-relation start at the same seed and both
end at an ‹AR_SimCompute›-tagged config, they coincide. This
is what bridges the walker's by-construction ‹R_read› witness
chain to the existence chain produced by ‹ar_read_phase›, whose
steps lie in ‹ar_delta_read› as well as in the full relation: the
witness chain inherits the latter's
stated endpoint state shape, including the load-bearing
‹buf = λk. ktc_tape cM k (ktc_pos cM k)›.›
lemma ar_delta_read_no_step_from_SimCompute:
fixes M :: "('q, 'a) ktm"
and c c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes "fst (snd (ktc_state c)) = AR_SimCompute"
shows "(c, c') ∉ ktm_step (ar_delta_read M)"
proof
assume h: "(c, c') ∈ ktm_step (ar_delta_read M)"
from h obtain S ts n S' aw move where
ceq: "c = KConfig S ts n"
and rel: "(S, (λk. ts k (n k)), S', aw, move) ∈ ar_delta_read M"
by (auto elim: ktm_step.cases)
have "fst (snd S) = AR_SimRead" using ar_delta_read_src[OF rel] .
hence "fst (snd (ktc_state c)) = AR_SimRead" using ceq by simp
with assms show False by simp
qed
lemma chain_ar_delta_read_to_SimCompute_uniq:
fixes M :: "('q, 'a) ktm"
and c c⇩1 c⇩2 :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes h⇩1: "(c, c⇩1) ∈ (ktm_step (ar_delta_read M)) ^^ m"
and h⇩2: "(c, c⇩2) ∈ (ktm_step (ar_delta_read M)) ^^ n"
and c⇩1cpu: "fst (snd (ktc_state c⇩1)) = AR_SimCompute"
and c⇩2cpu: "fst (snd (ktc_state c⇩2)) = AR_SimCompute"
shows "m = n ∧ c⇩1 = c⇩2"
proof -
have fn: "y = z"
if "x ∈ UNIV" "(x, y) ∈ ktm_step (ar_delta_read M)"
"(x, z) ∈ ktm_step (ar_delta_read M)" for x y z
by (rule ktm_step_det_at [OF _ that(2,3)])
(blast dest: ar_delta_read_functional)
have stuck: False
if "u ∈ {C. fst (snd (ktc_state C)) = AR_SimCompute}"
"(u, v) ∈ ktm_step (ar_delta_read M)" for u v
using that ar_delta_read_no_step_from_SimCompute by blast
show ?thesis
by (rule relpow_halted_same_run
[where R = UNIV and H = "{C. fst (snd (ktc_state C)) = AR_SimCompute}",
OF _ fn stuck _ h⇩1 _ h⇩2])
(simp_all add: c⇩1cpu c⇩2cpu)
qed
text ‹Two parallel chain-pinning suites for the write and advance
sub-relations, mirroring the read suite verbatim with
‹ar_delta_write› / ‹ar_delta_advance› in place of
‹ar_delta_read› and ‹AR_SimAdvance› / ‹AR_SimNext›
in place of ‹AR_SimCompute›. Functionality
(‹ar_delta_write_functional›, ‹ar_delta_advance_functional›) and src
uniqueness (‹ar_delta_write_src›, ‹ar_delta_advance_src›)
feed the same scaffold. These suites are used by the cycle-close
bridging lemma to pin walker write/advance chains against the
forward ‹ar_write_phase› / ‹ar_advance_phase›
constructions.›
lemma ar_delta_write_no_step_from_SimAdvance:
fixes M :: "('q, 'a) ktm"
and c c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes "fst (snd (ktc_state c)) = AR_SimAdvance"
shows "(c, c') ∉ ktm_step (ar_delta_write M)"
proof
assume h: "(c, c') ∈ ktm_step (ar_delta_write M)"
from h obtain S ts n S' aw move where
ceq: "c = KConfig S ts n"
and rel: "(S, (λk. ts k (n k)), S', aw, move) ∈ ar_delta_write M"
by (auto elim: ktm_step.cases)
have "fst (snd S) = AR_SimWrite" using ar_delta_write_src[OF rel] .
hence "fst (snd (ktc_state c)) = AR_SimWrite" using ceq by simp
with assms show False by simp
qed
lemma chain_ar_delta_write_to_SimAdvance_uniq:
fixes M :: "('q, 'a) ktm"
and c c⇩1 c⇩2 :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes h⇩1: "(c, c⇩1) ∈ (ktm_step (ar_delta_write M)) ^^ m"
and h⇩2: "(c, c⇩2) ∈ (ktm_step (ar_delta_write M)) ^^ n"
and c⇩1adv: "fst (snd (ktc_state c⇩1)) = AR_SimAdvance"
and c⇩2adv: "fst (snd (ktc_state c⇩2)) = AR_SimAdvance"
shows "m = n ∧ c⇩1 = c⇩2"
proof -
have fn: "y = z"
if "x ∈ UNIV" "(x, y) ∈ ktm_step (ar_delta_write M)"
"(x, z) ∈ ktm_step (ar_delta_write M)" for x y z
by (rule ktm_step_det_at [OF _ that(2,3)])
(blast dest: ar_delta_write_functional)
have stuck: False
if "u ∈ {C. fst (snd (ktc_state C)) = AR_SimAdvance}"
"(u, v) ∈ ktm_step (ar_delta_write M)" for u v
using that ar_delta_write_no_step_from_SimAdvance by blast
show ?thesis
by (rule relpow_halted_same_run
[where R = UNIV and H = "{C. fst (snd (ktc_state C)) = AR_SimAdvance}",
OF _ fn stuck _ h⇩1 _ h⇩2])
(simp_all add: c⇩1adv c⇩2adv)
qed
lemma ar_delta_advance_no_step_from_SimNext:
fixes M :: "('q, 'a) ktm"
and c c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes "fst (snd (ktc_state c)) = AR_SimNext"
shows "(c, c') ∉ ktm_step (ar_delta_advance M)"
proof
assume h: "(c, c') ∈ ktm_step (ar_delta_advance M)"
from h obtain S ts n S' aw move where
ceq: "c = KConfig S ts n"
and rel: "(S, (λk. ts k (n k)), S', aw, move) ∈ ar_delta_advance M"
by (auto elim: ktm_step.cases)
have "fst (snd S) = AR_SimAdvance" using ar_delta_advance_src[OF rel] .
hence "fst (snd (ktc_state c)) = AR_SimAdvance" using ceq by simp
with assms show False by simp
qed
lemma chain_ar_delta_advance_to_SimNext_uniq:
fixes M :: "('q, 'a) ktm"
and c c⇩1 c⇩2 :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes h⇩1: "(c, c⇩1) ∈ (ktm_step (ar_delta_advance M)) ^^ m"
and h⇩2: "(c, c⇩2) ∈ (ktm_step (ar_delta_advance M)) ^^ n"
and c⇩1nxt: "fst (snd (ktc_state c⇩1)) = AR_SimNext"
and c⇩2nxt: "fst (snd (ktc_state c⇩2)) = AR_SimNext"
shows "m = n ∧ c⇩1 = c⇩2"
proof -
have fn: "y = z"
if "x ∈ UNIV" "(x, y) ∈ ktm_step (ar_delta_advance M)"
"(x, z) ∈ ktm_step (ar_delta_advance M)" for x y z
by (rule ktm_step_det_at [OF _ that(2,3)])
(blast dest: ar_delta_advance_functional)
have stuck: False
if "u ∈ {C. fst (snd (ktc_state C)) = AR_SimNext}"
"(u, v) ∈ ktm_step (ar_delta_advance M)" for u v
using that ar_delta_advance_no_step_from_SimNext by blast
show ?thesis
by (rule relpow_halted_same_run
[where R = UNIV and H = "{C. fst (snd (ktc_state C)) = AR_SimNext}",
OF _ fn stuck _ h⇩1 _ h⇩2])
(simp_all add: c⇩1nxt c⇩2nxt)
qed
subsection ‹Each step preserves the substep invariants›
text ‹One preservation lemma per substep predicate: an
‹M'›-step out of a config satisfying the current invariant
lands at a config satisfying the next invariant in the cycle (or
splits the disjunction when the substep's relation has multiple
destination arms). Together with the chunked engine, these
describe how the walker's invariant evolves step by step: the substep
index carried in the ‹M'›-configuration decides which case applies at
each step, so no argument about the shape of the whole chain is
needed.›
lemma ar_walker_step_from_boundary:
fixes M :: "('q, 'a) ktm"
and cM :: "('a, 'q) ktc_config"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes inv: "ar_walker_at_boundary M cM c'"
and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
shows "ar_walker_in_read M cM c'' ∨ ar_walker_at_compute M cM c''"
proof -
obtain qM' stg where st: "ktc_state c' = (qM', stg)"
by (cases "ktc_state c'") auto
obtain idx tk i buf dvec posk where
sg: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
have src: "fst (snd (ktc_state c')) = AR_SimRead"
proof -
have sim: "ar_simulates M cM c'"
using inv unfolding ar_walker_at_boundary_def by simp
have sim_body:
"((idx = AR_SimRead ∧ qM' ∉ {t_ktm M, r_ktm M})
∨ (qM' = t_ktm M
∧ (idx, tk, i, buf, dvec, posk) = ar_accept_stage (bl_ktm M))
∨ (qM' = r_ktm M
∧ (idx, tk, i, buf, dvec, posk) = ar_reject_stage (bl_ktm M)))
∧ ktc_state cM = qM'"
using sim unfolding ar_simulates_def by (simp add: st sg Let_def)
consider (R) "idx = AR_SimRead"
| (A) "qM' = t_ktm M ∧ (idx, tk, i, buf, dvec, posk) = ar_accept_stage (bl_ktm M)"
| (J) "qM' = r_ktm M ∧ (idx, tk, i, buf, dvec, posk) = ar_reject_stage (bl_ktm M)"
using sim_body by blast
thus ?thesis
proof cases
case R thus ?thesis using st sg by simp
next
case A
have idx_acc: "idx = AR_HaltAccept"
using A by (simp add: ar_accept_stage_def)
from step obtain S ts n S' aw move where
c'_eq: "c' = KConfig S ts n"
and rel: "(S, (λk. ts k (n k)), S', aw, move)
∈ alphabet_reduce_delta M"
by (auto elim: ktm_step.cases)
have src_S: "fst (snd S) = AR_HaltAccept"
using c'_eq st sg idx_acc by simp
from alphabet_reduce_delta_src_tag[OF rel]
have "fst (snd S) ∈ {AR_SimRead, AR_SimCompute, AR_SimWrite,
AR_SimAdvance, AR_SimNext}" .
hence False using src_S by auto
thus ?thesis ..
next
case J
have idx_rej: "idx = AR_HaltReject"
using J by (simp add: ar_reject_stage_def)
from step obtain S ts n S' aw move where
c'_eq: "c' = KConfig S ts n"
and rel: "(S, (λk. ts k (n k)), S', aw, move)
∈ alphabet_reduce_delta M"
by (auto elim: ktm_step.cases)
have src_S: "fst (snd S) = AR_HaltReject"
using c'_eq st sg idx_rej by simp
from alphabet_reduce_delta_src_tag[OF rel]
have "fst (snd S) ∈ {AR_SimRead, AR_SimCompute, AR_SimWrite,
AR_SimAdvance, AR_SimNext}" .
hence False using src_S by auto
thus ?thesis ..
qed
qed
have step_read: "(c', c'') ∈ ktm_step (ar_delta_read M)"
using ar_step_read_lift[OF src step] .
hence step_read1: "(c', c'') ∈ (ktm_step (ar_delta_read M)) ^^ Suc 0"
by simp
from ar_step_from_SimRead_lands[OF step src]
have dest: "fst (snd (ktc_state c'')) = AR_SimRead
∨ fst (snd (ktc_state c'')) = AR_SimCompute" .
thus ?thesis
proof
assume dr: "fst (snd (ktc_state c'')) = AR_SimRead"
have "ar_walker_in_read M cM c''"
unfolding ar_walker_in_read_def
using dr inv step_read1 by blast
thus ?thesis ..
next
assume dc: "fst (snd (ktc_state c'')) = AR_SimCompute"
have "ar_walker_at_compute M cM c''"
unfolding ar_walker_at_compute_def
using dc inv step_read1 by blast
thus ?thesis ..
qed
qed
lemma ar_walker_step_from_in_read:
fixes M :: "('q, 'a) ktm"
and cM :: "('a, 'q) ktc_config"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes inv: "ar_walker_in_read M cM c'"
and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
shows "ar_walker_in_read M cM c'' ∨ ar_walker_at_compute M cM c''"
proof -
have src: "fst (snd (ktc_state c')) = AR_SimRead"
using inv unfolding ar_walker_in_read_def by simp
obtain c_b m where
wb: "ar_walker_at_boundary M cM c_b"
and chain: "(c_b, c') ∈ (ktm_step (ar_delta_read M)) ^^ m"
using inv unfolding ar_walker_in_read_def by blast
have step_read: "(c', c'') ∈ ktm_step (ar_delta_read M)"
using ar_step_read_lift[OF src step] .
have chain_ext: "(c_b, c'') ∈ (ktm_step (ar_delta_read M)) ^^ Suc m"
using chain step_read by (rule relpow_Suc_I)
from ar_step_from_SimRead_lands[OF step src]
have dest: "fst (snd (ktc_state c'')) = AR_SimRead
∨ fst (snd (ktc_state c'')) = AR_SimCompute" .
thus ?thesis
proof
assume dr: "fst (snd (ktc_state c'')) = AR_SimRead"
have "ar_walker_in_read M cM c''"
unfolding ar_walker_in_read_def
using dr wb chain_ext by blast
thus ?thesis ..
next
assume dc: "fst (snd (ktc_state c'')) = AR_SimCompute"
have "ar_walker_at_compute M cM c''"
unfolding ar_walker_at_compute_def
using dc wb chain_ext by blast
thus ?thesis ..
qed
qed
lemma ar_walker_step_from_at_compute:
fixes M :: "('q, 'a) ktm"
and cM :: "('a, 'q) ktc_config"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes inv: "ar_walker_at_compute M cM c'"
and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
and vM: "valid_ktm M"
and qQ: "ktc_state cM ∈ Q_ktm M"
and kge2: "2 ≤ block_width (Γ_ktm M)"
and tapeG: "⋀k. ktc_tape cM k (ktc_pos cM k) ∈ Γ_ktm M"
shows "ar_walker_in_write M cM c''"
proof -
let ?k = "block_width (Γ_ktm M)"
let ?aM = "λk. ktc_tape cM k (ktc_pos cM k)"
have c'_compute: "fst (snd (ktc_state c')) = AR_SimCompute"
using inv unfolding ar_walker_at_compute_def by simp
obtain c_b m_w where
wb: "ar_walker_at_boundary M cM c_b"
and chain_w: "(c_b, c') ∈ (ktm_step (ar_delta_read M)) ^^ m_w"
using inv unfolding ar_walker_at_compute_def by blast
have sim: "ar_simulates M cM c_b"
using wb unfolding ar_walker_at_boundary_def by simp
have pcons: "ar_posk_consistent M cM c_b"
using wb unfolding ar_walker_at_boundary_def by simp
have rbnd: "ar_at_read_boundary M c_b"
using wb unfolding ar_walker_at_boundary_def by simp
have cb_idx: "fst (snd (ktc_state c_b)) = AR_SimRead"
proof (cases m_w)
case 0
have cb_eq: "c_b = c'" using chain_w 0 by simp
have cb_compute: "fst (snd (ktc_state c_b)) = AR_SimCompute"
using c'_compute cb_eq by simp
obtain qM' stg where st_b: "ktc_state c_b = (qM', stg)"
by (cases "ktc_state c_b") auto
obtain idx tk i buf dvec posk where
sg_b: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
have idx_cpu: "idx = AR_SimCompute" using cb_compute st_b sg_b by simp
have "(idx = AR_SimRead ∧ qM' ∉ {t_ktm M, r_ktm M})
∨ (qM' = t_ktm M ∧ stg = ar_accept_stage (bl_ktm M))
∨ (qM' = r_ktm M ∧ stg = ar_reject_stage (bl_ktm M))"
using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
hence False
using idx_cpu sg_b
by (auto simp: ar_accept_stage_def ar_reject_stage_def)
thus ?thesis ..
next
case (Suc m')
have hsuc: "(c_b, c') ∈ (ktm_step (ar_delta_read M)) ^^ Suc m'"
using chain_w Suc by simp
obtain c_1 where
first: "(c_b, c_1) ∈ ktm_step (ar_delta_read M)"
using relpow_Suc_D2[OF hsuc] by blast
from first obtain S ts n S' aw move where
ceq: "c_b = KConfig S ts n"
and rel: "(S, (λk. ts k (n k)), S', aw, move) ∈ ar_delta_read M"
by (auto elim: ktm_step.cases)
have "fst (snd S) = AR_SimRead" using ar_delta_read_src[OF rel] .
thus ?thesis using ceq by simp
qed
obtain qM' stg where st_b: "ktc_state c_b = (qM', stg)"
by (cases "ktc_state c_b") auto
obtain idx tk i buf dvec posk where
sg_b: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
have idx_read: "idx = AR_SimRead" using cb_idx st_b sg_b by simp
have qM'_eq: "qM' = ktc_state cM"
using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
have tcorr: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
(ktc_tape cM k) (ktc_tape c_b k)"
using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
have ppos: "⋀k. ktc_pos c_b k = sim_pos ?k (ktc_pos cM k)"
using sim st_b sg_b idx_read
unfolding ar_simulates_def by (auto split: prod.splits)
have pkok: "⋀k. posk k = AR_AtLE ⟷ ktc_pos cM k = 0"
using pcons st_b sg_b idx_read
unfolding ar_posk_consistent_def by (auto split: prod.splits)
have bnd_unfold: "idx = AR_SimRead
⟶ (tk = 0 ∧ i = 0
∧ (∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M})
∧ ar_stage_bounded (bl_ktm M) (k_ktm M)
(idx, tk, i, buf, dvec, posk))"
using rbnd st_b sg_b
unfolding ar_at_read_boundary_def by (auto split: prod.splits)
have tk0: "tk = 0" and i0: "i = 0"
and bufG: "⋀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
using bnd_unfold idx_read by simp_all
have stg0: "ktc_state c_b = (ktc_state cM, AR_SimRead, 0, 0, buf, dvec, posk)"
using st_b sg_b qM'_eq idx_read tk0 i0 by simp
have pad0_b: "∀j ≥ k_ktm M. ktc_tape c_b j (ktc_pos c_b j) = BLANK4"
using rbnd unfolding ar_at_read_boundary_def by (auto split: prod.splits)
have src0_b: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, 0, 0, buf, dvec, posk)"
using bnd_unfold idx_read tk0 i0 by simp
obtain c_r m_phase where
r_chain: "(c_b, c_r) ∈ (ktm_step (ar_delta_read M)) ^^ m_phase"
and r_state: "ktc_state c_r = (ktc_state cM, AR_SimCompute, k_unidx 0, 0,
(λk. if k < k_ktm M then ?aM k else buf k), dvec,
(λk. if k < k_ktm M
then (if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper)
else posk k))"
using ar_read_phase[OF vM qQ kge2 stg0 tcorr ppos pkok tapeG bufG
pad0_b src0_b] ktm_run_mono [OF Int_lower2]
by blast
have r_cpu: "fst (snd (ktc_state c_r)) = AR_SimCompute"
using r_state by simp
have c'_eq_c_r: "c' = c_r"
using chain_ar_delta_read_to_SimCompute_uniq[OF chain_w r_chain c'_compute r_cpu]
by simp
have c'_state: "ktc_state c' = (ktc_state cM, AR_SimCompute, k_unidx 0, 0,
(λk. if k < k_ktm M then ?aM k else buf k), dvec,
(λk. if k < k_ktm M
then (if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper)
else posk k))"
using c'_eq_c_r r_state by simp
have step_compute: "(c', c'') ∈ ktm_step (ar_delta_compute M)"
using ar_step_compute_lift[OF c'_compute step] .
obtain q' m_a' m_d where
mdelta: "(ktc_state cM, (λk. if k < k_ktm M then ?aM k else buf k),
q', m_a', m_d) ∈ delta_ktm M"
and c''_state: "ktc_state c'' = (q', AR_SimWrite, 0, 0, m_a', m_d,
(λk. if k < k_ktm M
then (if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper)
else posk k))"
and c''_tape: "ktc_tape c'' = ktc_tape c'"
and c''_pos: "ktc_pos c'' = ktc_pos c'"
using ar_compute_step_inv[OF step c'_state] by blast
have c''_write: "fst (snd (ktc_state c'')) = AR_SimWrite"
using c''_state by simp
have empty_w: "(c'', c'') ∈ (ktm_step (ar_delta_write M)) ^^ 0" by simp
show "ar_walker_in_write M cM c''"
unfolding ar_walker_in_write_def
proof (intro conjI)
show "fst (snd (ktc_state c'')) = AR_SimWrite" by (rule c''_write)
show "∃c_b c_w m_r m_w.
ar_walker_at_boundary M cM c_b
∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
∧ fst (snd (ktc_state c_w)) = AR_SimCompute
∧ (∃c_w_post. (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
∧ (c_w_post, c'') ∈ (ktm_step (ar_delta_write M)) ^^ m_w)"
by (intro exI[where x = c_b] exI[where x = c'] exI[where x = m_w]
exI[where x = 0] conjI wb chain_w c'_compute
exI[where x = c''] step_compute empty_w)
qed
qed
lemma ar_walker_step_from_in_write:
fixes M :: "('q, 'a) ktm"
and cM :: "('a, 'q) ktc_config"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes inv: "ar_walker_in_write M cM c'"
and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
shows "ar_walker_in_write M cM c'' ∨ ar_walker_in_advance M cM c''"
proof -
have src: "fst (snd (ktc_state c')) = AR_SimWrite"
using inv unfolding ar_walker_in_write_def by simp
obtain c_b c_w m_r m_w where
wb: "ar_walker_at_boundary M cM c_b"
and chr: "(c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r"
and cwC: "fst (snd (ktc_state c_w)) = AR_SimCompute"
and rest: "∃c_w_post. (c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
∧ (c_w_post, c') ∈ (ktm_step (ar_delta_write M)) ^^ m_w"
using inv unfolding ar_walker_in_write_def by blast
obtain c_w_post where
ccs: "(c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)"
and chw: "(c_w_post, c') ∈ (ktm_step (ar_delta_write M)) ^^ m_w"
using rest by blast
have step_write: "(c', c'') ∈ ktm_step (ar_delta_write M)"
using ar_step_write_lift[OF src step] .
have chw_ext: "(c_w_post, c'') ∈ (ktm_step (ar_delta_write M)) ^^ Suc m_w"
using chw step_write by (rule relpow_Suc_I)
from ar_step_from_SimWrite_lands[OF step src]
have dest: "fst (snd (ktc_state c'')) = AR_SimWrite
∨ fst (snd (ktc_state c'')) = AR_SimAdvance" .
thus ?thesis
proof
assume dw: "fst (snd (ktc_state c'')) = AR_SimWrite"
have "ar_walker_in_write M cM c''"
unfolding ar_walker_in_write_def
proof (intro conjI)
show "fst (snd (ktc_state c'')) = AR_SimWrite" by (rule dw)
show "∃c_b c_w m_r m_w.
ar_walker_at_boundary M cM c_b
∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
∧ fst (snd (ktc_state c_w)) = AR_SimCompute
∧ (∃c_w_post.
(c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
∧ (c_w_post, c'') ∈ (ktm_step (ar_delta_write M)) ^^ m_w)"
by (intro exI[where x = c_b] exI[where x = c_w] exI[where x = m_r]
exI[where x = "Suc m_w"] conjI wb chr cwC
exI[where x = c_w_post] ccs chw_ext)
qed
thus ?thesis ..
next
assume da: "fst (snd (ktc_state c'')) = AR_SimAdvance"
have empty_a: "(c'', c'') ∈ (ktm_step (ar_delta_advance M)) ^^ 0"
by simp
have "ar_walker_in_advance M cM c''"
unfolding ar_walker_in_advance_def
proof (intro conjI)
show "fst (snd (ktc_state c'')) = AR_SimAdvance" by (rule da)
show "∃c_b c_w c_a m_r m_w m_a.
ar_walker_at_boundary M cM c_b
∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
∧ fst (snd (ktc_state c_w)) = AR_SimCompute
∧ fst (snd (ktc_state c_a)) = AR_SimAdvance
∧ (∃c_w_post.
(c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
∧ (c_a, c'') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a)"
by (intro exI[where x = c_b] exI[where x = c_w] exI[where x = c'']
exI[where x = m_r] exI[where x = "Suc m_w"] exI[where x = 0]
conjI wb chr cwC da
exI[where x = c_w_post] ccs chw_ext empty_a)
qed
thus ?thesis ..
qed
qed
lemma ar_walker_step_from_in_advance:
fixes M :: "('q, 'a) ktm"
and cM :: "('a, 'q) ktc_config"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes inv: "ar_walker_in_advance M cM c'"
and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
shows "ar_walker_in_advance M cM c'' ∨ ar_walker_at_next M cM c''"
proof -
have src: "fst (snd (ktc_state c')) = AR_SimAdvance"
using inv unfolding ar_walker_in_advance_def by simp
obtain c_b c_w c_a m_r m_w m_a where
wb: "ar_walker_at_boundary M cM c_b"
and chr: "(c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r"
and cwC: "fst (snd (ktc_state c_w)) = AR_SimCompute"
and caC: "fst (snd (ktc_state c_a)) = AR_SimAdvance"
and rest: "∃c_w_post.
(c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
∧ (c_a, c') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a"
using inv unfolding ar_walker_in_advance_def by blast
obtain c_w_post where
ccs: "(c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)"
and chw: "(c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w"
and cha: "(c_a, c') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a"
using rest by blast
have step_advance: "(c', c'') ∈ ktm_step (ar_delta_advance M)"
using ar_step_advance_lift[OF src step] .
have cha_ext: "(c_a, c'') ∈ (ktm_step (ar_delta_advance M)) ^^ Suc m_a"
using cha step_advance by (rule relpow_Suc_I)
from ar_step_from_SimAdvance_lands[OF step src]
have dest: "fst (snd (ktc_state c'')) = AR_SimAdvance
∨ fst (snd (ktc_state c'')) = AR_SimNext" .
thus ?thesis
proof
assume da: "fst (snd (ktc_state c'')) = AR_SimAdvance"
have "ar_walker_in_advance M cM c''"
unfolding ar_walker_in_advance_def
proof (intro conjI)
show "fst (snd (ktc_state c'')) = AR_SimAdvance" by (rule da)
show "∃c_b c_w c_a m_r m_w m_a.
ar_walker_at_boundary M cM c_b
∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
∧ fst (snd (ktc_state c_w)) = AR_SimCompute
∧ fst (snd (ktc_state c_a)) = AR_SimAdvance
∧ (∃c_w_post.
(c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
∧ (c_a, c'') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a)"
by (intro exI[where x = c_b] exI[where x = c_w] exI[where x = c_a]
exI[where x = m_r] exI[where x = m_w] exI[where x = "Suc m_a"]
conjI wb chr cwC caC
exI[where x = c_w_post] ccs chw cha_ext)
qed
thus ?thesis ..
next
assume dn: "fst (snd (ktc_state c'')) = AR_SimNext"
have "ar_walker_at_next M cM c''"
unfolding ar_walker_at_next_def
proof (intro conjI)
show "fst (snd (ktc_state c'')) = AR_SimNext" by (rule dn)
show "∃c_b c_w c_a c_n m_r m_w m_a.
ar_walker_at_boundary M cM c_b
∧ (c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r
∧ fst (snd (ktc_state c_w)) = AR_SimCompute
∧ fst (snd (ktc_state c_a)) = AR_SimAdvance
∧ (∃c_w_post.
(c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)
∧ (c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w
∧ (c_a, c_n) ∈ (ktm_step (ar_delta_advance M)) ^^ m_a
∧ c_n = c'')"
by (intro exI[where x = c_b] exI[where x = c_w] exI[where x = c_a]
exI[where x = c''] exI[where x = m_r] exI[where x = m_w]
exI[where x = "Suc m_a"] conjI wb chr cwC caC
exI[where x = c_w_post] ccs chw cha_ext refl)
qed
thus ?thesis ..
qed
qed
text ‹The sixth and last of the preservation lemmas: an ‹M'›-step out
of ‹AR_SimNext› leads to ‹AR_SimRead› (closing the cycle),
‹AR_HaltAccept›, or ‹AR_HaltReject›, by
‹ar_step_from_SimNext_lands›. It only sorts the cases.
Establishing the invariant for the reconstructed ‹M›-successor when
a cycle closes is done once per cycle, by ‹ar_walker_cycle_close›
and the chunked reverse induction, and the proof goes through that
lemma directly; this one is not used below, and is stated so that all
six substeps have their one-step lemma.›
lemma ar_walker_step_from_at_next:
fixes M :: "('q, 'a) ktm"
and cM :: "('a, 'q) ktc_config"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes inv: "ar_walker_at_next M cM c'"
and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
shows "fst (snd (ktc_state c'')) = AR_SimRead
∨ fst (snd (ktc_state c'')) = AR_HaltAccept
∨ fst (snd (ktc_state c'')) = AR_HaltReject"
proof -
have src: "fst (snd (ktc_state c')) = AR_SimNext"
using inv unfolding ar_walker_at_next_def by simp
show ?thesis using ar_step_from_SimNext_lands[OF step src] .
qed
subsection ‹Closing a simulation cycle›
text ‹An ‹AR_SimNext› step closes a simulation cycle: the walker is
re-established at a boundary for the next ‹M›-configuration. The
successor is ∗‹reconstructed› from the pinned compute branch
(the ‹∃cM'› in the conclusion): under nondeterministic
‹delta_ktm M› the source ‹cM› may have several successors, so the
fired branch is recovered from the walker's own witness chain rather
than assumed. The forward phase lemmas run in the full relation and
in the substep sub-relation at once, so the forward direction is read in the
sub-relations and each walker
witness chain is pinned by a ‹chain_ar_delta_X_to_Y_uniq› suite.
The closing next step is inverted by ‹ar_next_step_inv›, which
dispatches on the reconstructed ‹M›-state ‹q'› into three
outcomes: continue (‹q' ∉ {t, r}›, landing at ‹AR_SimRead›),
accept (‹q' = t_ktm M›) or reject (‹q' = r_ktm M›). All three
re-establish ‹ar_walker_at_boundary M cMn c''›: the boundary
invariant carries the halt cases too — ‹ar_simulates›'s state
disjunction has dedicated accept/reject arms, and both
‹ar_posk_consistent› and ‹ar_at_read_boundary› are
‹AR_SimRead›-guarded, hence vacuous off the read boundary. The
three predicates are discharged from the explicit endpoint by the shared
semantic lemmas (‹ar_write_tape_correspondence›,
‹ar_advance_newsimpos›, ‹ar_newpos_atLE_iff›). No union chain
is pinned and ‹ar_simulates_forward_step› is not invoked.›
lemma ar_walker_cycle_close:
fixes M :: "('q, 'a) ktm"
and w :: "'a list"
and cM :: "('a, 'q) ktc_config"
and c' c'' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes inv: "ar_walker_at_next M cM c'"
and step: "(c', c'') ∈ ktm_step (alphabet_reduce_delta M)"
and vM: "valid_ktm M"
and qQ: "ktc_state cM ∈ Q_ktm M"
and kge2: "2 ≤ block_width (Γ_ktm M)"
and tapeG: "⋀k. ktc_tape cM k (ktc_pos cM k) ∈ Γ_ktm M"
and w_sub: "set w ⊆ Sigma_ktm M"
and reach_M: "(init_config_ktm M w, cM) ∈ (ktm_step (delta_ktm M))⇧*"
and lebl: "le_ktm M ≠ bl_ktm M"
shows "∃cM'. (cM, cM') ∈ ktm_step (delta_ktm M)
∧ ar_walker_at_boundary M cM' c''"
proof -
let ?k = "block_width (Γ_ktm M)"
let ?aM = "λk. ktc_tape cM k (ktc_pos cM k)"
have kpos_ktm: "0 < k_ktm M" using vM by (cases M) auto
obtain c_b c_w c_a c_n m_r m_w m_a c_w_post where
wb: "ar_walker_at_boundary M cM c_b"
and chain_r: "(c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ m_r"
and cw_cpu: "fst (snd (ktc_state c_w)) = AR_SimCompute"
and ca_adv: "fst (snd (ktc_state c_a)) = AR_SimAdvance"
and cstep: "(c_w, c_w_post) ∈ ktm_step (ar_delta_compute M)"
and wchain: "(c_w_post, c_a) ∈ (ktm_step (ar_delta_write M)) ^^ m_w"
and achain0: "(c_a, c_n) ∈ (ktm_step (ar_delta_advance M)) ^^ m_a"
and cn_eq: "c_n = c'"
using inv unfolding ar_walker_at_next_def by blast
have achain: "(c_a, c') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a"
using achain0 cn_eq by simp
have c'_next: "fst (snd (ktc_state c')) = AR_SimNext"
using inv unfolding ar_walker_at_next_def by simp
have sim: "ar_simulates M cM c_b"
using wb unfolding ar_walker_at_boundary_def by simp
have pcons: "ar_posk_consistent M cM c_b"
using wb unfolding ar_walker_at_boundary_def by simp
have rbnd: "ar_at_read_boundary M c_b"
using wb unfolding ar_walker_at_boundary_def by simp
have cb_idx: "fst (snd (ktc_state c_b)) = AR_SimRead"
proof (cases m_r)
case 0
have cb_eq: "c_b = c_w" using chain_r 0 by simp
have cb_compute: "fst (snd (ktc_state c_b)) = AR_SimCompute"
using cw_cpu cb_eq by simp
obtain qM' stg where st_b: "ktc_state c_b = (qM', stg)"
by (cases "ktc_state c_b") auto
obtain idx tk i buf dvec posk where
sg_b: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
have idx_cpu: "idx = AR_SimCompute" using cb_compute st_b sg_b by simp
have "(idx = AR_SimRead ∧ qM' ∉ {t_ktm M, r_ktm M})
∨ (qM' = t_ktm M ∧ stg = ar_accept_stage (bl_ktm M))
∨ (qM' = r_ktm M ∧ stg = ar_reject_stage (bl_ktm M))"
using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
hence False using idx_cpu sg_b
by (auto simp: ar_accept_stage_def ar_reject_stage_def)
thus ?thesis ..
next
case (Suc m')
have hsuc: "(c_b, c_w) ∈ (ktm_step (ar_delta_read M)) ^^ Suc m'"
using chain_r Suc by simp
obtain c_1 where first: "(c_b, c_1) ∈ ktm_step (ar_delta_read M)"
using relpow_Suc_D2[OF hsuc] by blast
from first obtain S ts n S' aw move where
ceq: "c_b = KConfig S ts n"
and rel: "(S, (λk. ts k (n k)), S', aw, move) ∈ ar_delta_read M"
by (auto elim: ktm_step.cases)
have "fst (snd S) = AR_SimRead" using ar_delta_read_src[OF rel] .
thus ?thesis using ceq by simp
qed
obtain qM' stg where st_b: "ktc_state c_b = (qM', stg)"
by (cases "ktc_state c_b") auto
obtain idx tk i buf dvec posk where
sg_b: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
have idx_read: "idx = AR_SimRead" using cb_idx st_b sg_b by simp
have qM'_eq: "qM' = ktc_state cM"
using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
have tcorr: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
(ktc_tape cM k) (ktc_tape c_b k)"
using sim st_b sg_b unfolding ar_simulates_def by (auto split: prod.splits)
have ppos: "⋀k. ktc_pos c_b k = sim_pos ?k (ktc_pos cM k)"
using sim st_b sg_b idx_read
unfolding ar_simulates_def by (auto split: prod.splits)
have pkok: "⋀k. posk k = AR_AtLE ⟷ ktc_pos cM k = 0"
using pcons st_b sg_b idx_read
unfolding ar_posk_consistent_def by (auto split: prod.splits)
have bnd_unfold: "idx = AR_SimRead
⟶ (tk = 0 ∧ i = 0
∧ (∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M})
∧ ar_stage_bounded (bl_ktm M) (k_ktm M)
(idx, tk, i, buf, dvec, posk))"
using rbnd st_b sg_b
unfolding ar_at_read_boundary_def by (auto split: prod.splits)
have tk0: "tk = 0" and i0: "i = 0"
and bufG: "⋀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
using bnd_unfold idx_read by simp_all
have src_b: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, 0, 0, buf, dvec, posk)"
using bnd_unfold idx_read tk0 i0 by simp
have pad_b: "∀j ≥ k_ktm M. ktc_tape c_b j (ktc_pos c_b j) = BLANK4"
using rbnd unfolding ar_at_read_boundary_def by (auto split: prod.splits)
have stg0: "ktc_state c_b = (ktc_state cM, AR_SimRead, 0, 0, buf, dvec, posk)"
using st_b sg_b qM'_eq idx_read tk0 i0 by simp
have buf_tail: "∀j ≥ k_ktm M. buf j = bl_ktm M"
using src_b by (simp add: ar_stage_bounded_def)
have posk_tail: "∀j ≥ k_ktm M. posk j = AR_AtLE"
using src_b by (simp add: ar_stage_bounded_def)
have valcM: "valid_config_ktm M cM"
using valid_reach_ktm[OF vM w_sub reach_M] .
have aM_tail: "∀j ≥ k_ktm M. ktc_tape cM j (ktc_pos cM j) = bl_ktm M"
using valid_config_ktm_blank_tail[OF valcM] by blast
let ?rbuf = "λk. if k < k_ktm M then ?aM k else buf k"
let ?rposk = "λk. if k < k_ktm M
then (if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper)
else posk k"
let ?rpos = "λk. if k < k_ktm M
then (if ktc_pos cM k = 0 then Suc 0
else sim_pos ?k (ktc_pos cM k) + ?k)
else ktc_pos c_b k"
obtain c_r m_phase where
r_chain: "(c_b, c_r) ∈ (ktm_step (ar_delta_read M)) ^^ m_phase"
and r_state: "ktc_state c_r = (ktc_state cM, AR_SimCompute, k_unidx 0, 0,
?rbuf, dvec, ?rposk)"
and r_tape: "ktc_tape c_r = ktc_tape c_b"
and r_pos: "ktc_pos c_r = ?rpos"
using ar_read_phase[OF vM qQ kge2 stg0 tcorr ppos pkok tapeG bufG
pad_b src_b] ktm_run_mono [OF Int_lower2]
by blast
have r_cpu: "fst (snd (ktc_state c_r)) = AR_SimCompute" using r_state by simp
have cw_eq_cr: "c_w = c_r"
using chain_ar_delta_read_to_SimCompute_uniq[OF chain_r r_chain cw_cpu r_cpu]
by simp
have cw_state: "ktc_state c_w = (ktc_state cM, AR_SimCompute, k_unidx 0, 0,
?rbuf, dvec, ?rposk)"
using cw_eq_cr r_state by simp
obtain q' m_a' m_d where
mdelta: "(ktc_state cM, ?rbuf, q', m_a', m_d) ∈ delta_ktm M"
and cwpost_state: "ktc_state c_w_post = (q', AR_SimWrite, 0, 0, m_a', m_d, ?rposk)"
and cwpost_tape: "ktc_tape c_w_post = ktc_tape c_w"
and cwpost_pos: "ktc_pos c_w_post = ktc_pos c_w"
using ar_compute_step_inv_sub[OF cstep cw_state] by blast
obtain qM tsM nM where cM_eq: "cM = KConfig qM tsM nM" by (cases cM) auto
have qM_eq: "qM = ktc_state cM" using cM_eq by simp
have aM_eq: "(λk. tsM k (nM k)) = ?aM" using cM_eq by simp
have rbuf_eq: "?rbuf = ?aM"
proof (rule ext)
fix k show "?rbuf k = ?aM k"
proof (cases "k < k_ktm M")
case True thus ?thesis by simp
next
case False
have "?rbuf k = bl_ktm M" using buf_tail False by simp
moreover have "?aM k = bl_ktm M" using aM_tail False by simp
ultimately show ?thesis by simp
qed
qed
have mdelta_aM: "(ktc_state cM, ?aM, q', m_a', m_d) ∈ delta_ktm M"
using mdelta rbuf_eq by simp
define cMn where cMn_def: "cMn = KConfig q' (λk. (tsM k)(nM k := m_a' k))
(λk. go_move (m_d k) (nM k))"
have mdelta': "(qM, (λk. tsM k (nM k)), q', m_a', m_d) ∈ delta_ktm M"
using mdelta_aM qM_eq aM_eq by simp
have m_step: "(cM, cMn) ∈ ktm_step (delta_ktm M)"
using ktm_step.step[where ts = tsM and n = nM, OF mdelta'] cM_eq cMn_def by simp
have q'Q: "q' ∈ Q_ktm M" using valid_ktm_delta(3)[OF vM mdelta_aM] .
have a'G: "m_a' k ∈ Γ_ktm M" for k using valid_ktm_delta(4)[OF vM mdelta_aM] .
have a'val: "∀k. m_a' k ∈ Γ_ktm M ∪ {bl_ktm M}" using a'G by blast
have dsupp: "∀j ≥ k_ktm M. m_a' j = bl_ktm M ∧ m_d j = MoveN"
using valid_ktm_delta_support[OF vM mdelta_aM] by blast
have pad_cwpost: "∀j ≥ k_ktm M. ktc_tape c_w_post j (ktc_pos c_w_post j) = BLANK4"
proof (intro allI impI)
fix j assume jk: "k_ktm M ≤ j"
have "ktc_pos c_w_post j = ktc_pos c_b j"
using cwpost_pos cw_eq_cr r_pos jk by simp
moreover have "ktc_tape c_w_post j = ktc_tape c_b j"
using cwpost_tape cw_eq_cr r_tape by simp
ultimately show "ktc_tape c_w_post j (ktc_pos c_w_post j) = BLANK4"
using pad_b jk by simp
qed
have src_cwpost: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimWrite, 0, 0, m_a', m_d, ?rposk)"
using kpos_ktm dsupp posk_tail by (simp add: ar_stage_bounded_def)
have tcorr_w: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
(ktc_tape cM k) (ktc_tape c_w_post k)"
proof (intro allI impI)
fix k assume kN: "k < k_ktm M"
have "ktc_tape c_w_post k = ktc_tape c_b k"
using cwpost_tape cw_eq_cr r_tape by simp
thus "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
(ktc_tape cM k) (ktc_tape c_w_post k)"
using tcorr kN by simp
qed
have ppos_w: "∀k < k_ktm M. ktc_pos c_w_post k = (if ktc_pos cM k = 0 then Suc 0
else sim_pos ?k (ktc_pos cM k) + ?k)"
using cwpost_pos cw_eq_cr r_pos by simp
have a'le0_w: "∀k < k_ktm M. ktc_pos cM k = 0 ⟶ m_a' k = le_ktm M"
proof (intro allI impI)
fix k assume kN: "k < k_ktm M" and p0: "ktc_pos cM k = 0"
have tsk0: "tsM k 0 = le_ktm M" using valcM cM_eq kN by (cases M) auto
have "(λj. tsM j (nM j)) k = le_ktm M" using tsk0 p0 cM_eq by simp
thus "m_a' k = le_ktm M" using valid_ktm_deltaLE[OF vM mdelta'] by simp
qed
have poskle_w: "∀k < k_ktm M. ?rposk k = AR_AtLE ⟷ ktc_pos cM k = 0"
by auto
obtain c_write mw where
w_chain: "(c_w_post, c_write) ∈ (ktm_step (ar_delta_write M)) ^^ mw"
and w_state: "ktc_state c_write = (q', AR_SimAdvance, k_unidx 0, 0, m_a', m_d,
?rposk)"
and w_tape: "ktc_tape c_write = (λk. if k < k_ktm M
then (if ktc_pos cM k = 0 then ktc_tape c_w_post k
else (λpos. if sim_pos ?k (ktc_pos cM k) ≤ pos
∧ pos < sim_pos ?k (ktc_pos cM k) + ?k
then write_bit (Γ_ktm M) (bl_ktm M) (m_a' k)
(pos - sim_pos ?k (ktc_pos cM k))
else ktc_tape c_w_post k pos))
else ktc_tape c_w_post k)"
and w_pos: "ktc_pos c_write = ktc_pos c_w_post"
using ar_write_phase[OF vM q'Q kge2 cwpost_state tcorr_w ppos_w
poskle_w a'val pad_cwpost src_cwpost]
ktm_run_mono [OF Int_lower2]
by blast
have c_write_adv: "fst (snd (ktc_state c_write)) = AR_SimAdvance"
using w_state by simp
have ca_eq: "c_a = c_write"
using chain_ar_delta_write_to_SimAdvance_uniq[OF wchain w_chain ca_adv
c_write_adv]
by simp
have w_state': "ktc_state c_write = (q', AR_SimAdvance, 0, 0, m_a', m_d, ?rposk)"
using w_state by (simp add: k_unidx_zero)
have pad_cwrite: "∀j ≥ k_ktm M. ktc_tape c_write j (ktc_pos c_write j) = BLANK4"
proof (intro allI impI)
fix j assume jk: "k_ktm M ≤ j"
have "ktc_tape c_write j = ktc_tape c_w_post j" using w_tape jk by simp
moreover have "ktc_pos c_write j = ktc_pos c_w_post j" using w_pos by simp
ultimately show "ktc_tape c_write j (ktc_pos c_write j) = BLANK4"
using pad_cwpost jk by simp
qed
have src_cwrite: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimAdvance, 0, 0, m_a', m_d, ?rposk)"
using kpos_ktm dsupp posk_tail by (simp add: ar_stage_bounded_def)
have dge1: "∀k < k_ktm M. m_d k ≠ MoveR ⟶ 0 < ar_disp ?k (m_d k) (?rposk k)"
proof (intro allI impI)
fix k assume kN: "k < k_ktm M" and dkR: "m_d k ≠ MoveR"
show "0 < ar_disp ?k (m_d k) (?rposk k)"
proof (cases "ktc_pos cM k = 0")
case True
have nM0: "nM k = 0" using True cM_eq by simp
have "tsM k 0 = le_ktm M" using valcM cM_eq kN by (cases M) auto
hence "(λj. tsM j (nM j)) k = le_ktm M" using nM0 by simp
hence "m_d k ∈ {MoveN, MoveR}" using valid_ktm_deltaLE[OF vM mdelta'] by simp
hence "m_d k = MoveN" using dkR by auto
moreover have "?rposk k = AR_AtLE" using True kN by simp
ultimately show "0 < ar_disp ?k (m_d k) (?rposk k)" by simp
next
case False
have dN_or_L: "m_d k = MoveN ∨ m_d k = MoveL"
using dkR by (cases "m_d k") auto
have rk: "?rposk k = AR_AtFirstProper ∨ ?rposk k = AR_AtFurtherProper"
using False kN by auto
from dN_or_L rk kge2 show "0 < ar_disp ?k (m_d k) (?rposk k)" by auto
qed
qed
have notLE: "∀k < k_ktm M. ∀m. m < ar_disp ?k (m_d k) (?rposk k)
⟶ ktc_tape c_write k (ktc_pos c_write k - m) ≠ LE4"
proof (intro allI impI)
fix k m assume kN: "k < k_ktm M"
and mlt: "m < ar_disp ?k (m_d k) (?rposk k)"
have tcorr_wk: "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
(ktc_tape cM k) (ktc_tape c_w_post k)"
using tcorr_w kN by blast
have wcpos: "ktc_pos c_write k = (if ktc_pos cM k = 0 then Suc 0
else sim_pos ?k (ktc_pos cM k) + ?k)"
using w_pos ppos_w kN by simp
have wtape_notLE: "ktc_tape c_write k pos ≠ LE4" if pos1: "1 ≤ pos" for pos
proof (cases "ktc_pos cM k = 0")
case True
have "ktc_tape c_write k pos = ktc_tape c_w_post k pos"
using w_tape True kN by simp
thus ?thesis
using ar_tape_correspondence_not_LE4[OF tcorr_wk pos1] by simp
next
case False
have wexp: "ktc_tape c_write k pos
= (if sim_pos ?k (ktc_pos cM k) ≤ pos
∧ pos < sim_pos ?k (ktc_pos cM k) + ?k
then write_bit (Γ_ktm M) (bl_ktm M) (m_a' k)
(pos - sim_pos ?k (ktc_pos cM k))
else ktc_tape c_w_post k pos)"
using w_tape False kN by simp
show ?thesis
proof (cases "sim_pos ?k (ktc_pos cM k) ≤ pos
∧ pos < sim_pos ?k (ktc_pos cM k) + ?k")
case True
have b: "pos - sim_pos ?k (ktc_pos cM k) < ?k" using True by linarith
have "ktc_tape c_write k pos
= write_bit (Γ_ktm M) (bl_ktm M) (m_a' k)
(pos - sim_pos ?k (ktc_pos cM k))"
using wexp True by simp
thus ?thesis using write_bit_not_LE4[OF b] by simp
next
case False
have nreg: "¬ (sim_pos ?k (ktc_pos cM k) ≤ pos
∧ pos < sim_pos ?k (ktc_pos cM k) + ?k)"
using False by simp
have "ktc_tape c_write k pos = ktc_tape c_w_post k pos"
using wexp by (simp add: if_not_P[OF nreg])
thus ?thesis
using ar_tape_correspondence_not_LE4[OF tcorr_wk pos1] by simp
qed
qed
have rge: "ar_disp ?k (m_d k) (?rposk k) ≤ ktc_pos c_write k"
proof (cases "ktc_pos cM k = 0")
case True
have "ar_disp ?k (m_d k) (?rposk k) ≤ Suc 0"
using True kN by (cases "m_d k") auto
thus ?thesis using wcpos True by simp
next
case nz: False
show ?thesis
proof (cases "ktc_pos cM k = 1")
case True
have "ar_disp ?k (m_d k) (?rposk k) ≤ Suc ?k"
using True kN by (cases "m_d k") auto
thus ?thesis using wcpos True by (simp add: sim_pos_def)
next
case False
have p2: "2 ≤ ktc_pos cM k" using nz False by simp
have d2: "ar_disp ?k (m_d k) (?rposk k) ≤ 2 * ?k"
using nz False kN by (cases "m_d k") auto
have cw_eq2: "ktc_pos c_write k = (ktc_pos cM k - 1) * ?k + 1 + ?k"
using wcpos nz by (simp add: sim_pos_def)
have "(1::nat) ≤ ktc_pos cM k - 1" using p2 by simp
hence "1 * ?k ≤ (ktc_pos cM k - 1) * ?k" by (rule mult_le_mono1)
hence kk: "?k ≤ (ktc_pos cM k - 1) * ?k" by (simp only: mult_1_left)
have "2 * ?k ≤ ktc_pos c_write k" using kk cw_eq2 by linarith
thus ?thesis using d2 by linarith
qed
qed
have "m < ktc_pos c_write k" using mlt rge by simp
hence "1 ≤ ktc_pos c_write k - m" by simp
thus "ktc_tape c_write k (ktc_pos c_write k - m) ≠ LE4" by (rule wtape_notLE)
qed
let ?aposk = "λk. if k < k_ktm M then ar_newpos (m_d k) (?rposk k) else ?rposk k"
let ?apos = "λk. if k < k_ktm M
then (if m_d k = MoveR then ktc_pos c_write k
else ktc_pos c_write k - ar_disp ?k (m_d k) (?rposk k))
else ktc_pos c_write k"
obtain c_adv ma where
a_chain: "(c_write, c_adv) ∈ (ktm_step (ar_delta_advance M)) ^^ ma"
and a_state: "ktc_state c_adv = (q', AR_SimNext, k_unidx 0, 0, m_a', m_d, ?aposk)"
and a_tape: "ktc_tape c_adv = ktc_tape c_write"
and a_pos: "ktc_pos c_adv = ?apos"
using ar_advance_phase[OF vM q'Q kge2 w_state' a'val dge1 notLE
pad_cwrite src_cwrite] ktm_run_mono [OF Int_lower2]
by blast
have c_adv_nxt: "fst (snd (ktc_state c_adv)) = AR_SimNext" using a_state by simp
have achain': "(c_write, c') ∈ (ktm_step (ar_delta_advance M)) ^^ m_a"
using achain ca_eq by simp
have c'_eq: "c' = c_adv"
using chain_ar_delta_advance_to_SimNext_uniq[OF achain' a_chain c'_next
c_adv_nxt]
by simp
have c'_state: "ktc_state c' = (q', AR_SimNext, k_unidx 0, 0, m_a', m_d, ?aposk)"
using c'_eq a_state by simp
have nxt: "ktc_tape c'' = ktc_tape c' ∧ ktc_pos c'' = ktc_pos c'
∧ ((q' ∉ {t_ktm M, r_ktm M}
∧ ktc_state c'' = (q', AR_SimRead, 0, 0, m_a', m_d, ?aposk))
∨ (q' = t_ktm M
∧ ktc_state c'' = (t_ktm M, ar_accept_stage (bl_ktm M)))
∨ (q' = r_ktm M
∧ ktc_state c'' = (r_ktm M, ar_reject_stage (bl_ktm M))))"
using ar_next_step_inv[OF step c'_state] .
have nxt_tape: "ktc_tape c'' = ktc_tape c'" using nxt by simp
have nxt_pos: "ktc_pos c'' = ktc_pos c'" using nxt by simp
have nxt_disj:
"(q' ∉ {t_ktm M, r_ktm M}
∧ ktc_state c'' = (q', AR_SimRead, 0, 0, m_a', m_d, ?aposk))
∨ (q' = t_ktm M
∧ ktc_state c'' = (t_ktm M, ar_accept_stage (bl_ktm M)))
∨ (q' = r_ktm M
∧ ktc_state c'' = (r_ktm M, ar_reject_stage (bl_ktm M)))"
using nxt by simp
have st_cMn: "ktc_state cMn = q'" using cMn_def by simp
have padpos0: "∀j ≥ k_ktm M. ktc_pos cM j = 0" using pkok posk_tail by blast
have dposL: "m_d k ≠ MoveL" if p0: "ktc_pos cM k = 0" and kN: "k < k_ktm M" for k
proof -
have nM0: "nM k = 0" using p0 cM_eq by simp
have "tsM k 0 = le_ktm M" using valcM cM_eq kN by (cases M) auto
hence "(λj. tsM j (nM j)) k = le_ktm M" using nM0 by simp
hence "m_d k ∈ {MoveN, MoveR}" using valid_ktm_deltaLE[OF vM mdelta'] by simp
thus "m_d k ≠ MoveL" by auto
qed
have cwpost_b: "ktc_tape c_w_post = ktc_tape c_b"
using cwpost_tape cw_eq_cr r_tape by simp
have cM1tape: "ktc_tape cMn k = (ktc_tape cM k)(ktc_pos cM k := m_a' k)" for k
using cMn_def cM_eq by simp
have wt_def: "ktc_tape c'' k pos
= (if ktc_pos cM k = 0 then ktc_tape c_b k pos
else if sim_pos ?k (ktc_pos cM k) ≤ pos
∧ pos < sim_pos ?k (ktc_pos cM k) + ?k
then write_bit (Γ_ktm M) (bl_ktm M) (m_a' k)
(pos - sim_pos ?k (ktc_pos cM k))
else ktc_tape c_b k pos)" for k pos
proof (cases "k < k_ktm M")
case True
thus ?thesis using nxt_tape c'_eq a_tape w_tape cwpost_b by simp
next
case False
hence kge: "k_ktm M ≤ k" by simp
have p0: "ktc_pos cM k = 0" using padpos0 kge by blast
have "ktc_tape c'' k = ktc_tape c_b k"
using nxt_tape c'_eq a_tape w_tape cwpost_b kge by simp
thus ?thesis using p0 by simp
qed
have tcorr_1: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
(ktc_tape cMn k) (ktc_tape c'' k)"
proof (intro allI impI)
fix k assume kN: "k < k_ktm M"
show "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
(ktc_tape cMn k) (ktc_tape c'' k)"
by (rule ar_write_tape_correspondence
[OF kge2 kN tcorr cM1tape a'le0_w wt_def])
qed
have apos_1: "ktc_pos c'' k = sim_pos ?k (ktc_pos cMn k)" for k
proof (cases "k < k_ktm M")
case kN: True
have posM1: "ktc_pos cMn k = go_move (m_d k) (ktc_pos cM k)"
using cMn_def cM_eq by simp
have key: "(if m_d k = MoveR
then (if ktc_pos cM k = 0 then Suc 0
else sim_pos ?k (ktc_pos cM k) + ?k)
else (if ktc_pos cM k = 0 then Suc 0
else sim_pos ?k (ktc_pos cM k) + ?k)
- ar_disp ?k (m_d k)
(if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper))
= sim_pos ?k (go_move (m_d k) (ktc_pos cM k))"
proof (rule ar_advance_newsimpos)
show "2 ≤ ?k" by (rule kge2)
show "ktc_pos cM k = 0 ⟹ m_d k ≠ MoveL" using dposL kN by blast
qed
have cadv_pos: "ktc_pos c'' k = (if m_d k = MoveR
then (if ktc_pos cM k = 0 then Suc 0
else sim_pos ?k (ktc_pos cM k) + ?k)
else (if ktc_pos cM k = 0 then Suc 0
else sim_pos ?k (ktc_pos cM k) + ?k)
- ar_disp ?k (m_d k)
(if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper))"
using nxt_pos c'_eq a_pos w_pos ppos_w kN by simp
show ?thesis by (simp add: cadv_pos key posM1)
next
case False
hence kge: "k_ktm M ≤ k" by simp
have dN: "m_d k = MoveN" using dsupp kge by blast
have posM1: "ktc_pos cMn k = go_move (m_d k) (ktc_pos cM k)"
using cMn_def cM_eq by simp
have "ktc_pos c'' k = ktc_pos c_b k"
using nxt_pos c'_eq a_pos w_pos cwpost_pos cw_eq_cr r_pos kge by simp
also have "… = sim_pos ?k (ktc_pos cM k)" using ppos by simp
also have "… = sim_pos ?k (ktc_pos cMn k)" using posM1 dN by simp
finally show ?thesis .
qed
have aposk_1: "?aposk k = AR_AtLE ⟷ ktc_pos cMn k = 0" for k
proof (cases "k < k_ktm M")
case kN: True
have posM1: "ktc_pos cMn k = go_move (m_d k) (ktc_pos cM k)"
using cMn_def cM_eq by simp
have key: "(ar_newpos (m_d k)
(if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper) = AR_AtLE)
⟷ go_move (m_d k) (ktc_pos cM k) = 0"
proof (rule ar_newpos_atLE_iff)
show "ktc_pos cM k = 0 ⟹ m_d k ≠ MoveL" using dposL kN by blast
qed
have aposk_k: "?aposk k = ar_newpos (m_d k)
(if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper)"
using kN by simp
show ?thesis by (simp add: aposk_k key posM1)
next
case False
hence kge: "k_ktm M ≤ k" by simp
have dN: "m_d k = MoveN" using dsupp kge by blast
have p0: "ktc_pos cM k = 0" using padpos0 kge by blast
have posM1: "ktc_pos cMn k = go_move (m_d k) (ktc_pos cM k)"
using cMn_def cM_eq by simp
have "ktc_pos cMn k = 0" using posM1 dN p0 by simp
moreover have "posk k = AR_AtLE" using posk_tail kge by blast
moreover have "?aposk k = posk k" using kge by simp
ultimately show ?thesis by simp
qed
have pad_c'': "∀j ≥ k_ktm M. ktc_tape c'' j (ktc_pos c'' j) = BLANK4"
proof (intro allI impI)
fix j assume jk: "k_ktm M ≤ j"
have "ktc_pos c'' j = ktc_pos c_write j"
using nxt_pos c'_eq a_pos jk by simp
moreover have "ktc_tape c'' j = ktc_tape c_write j"
using nxt_tape c'_eq a_tape by simp
ultimately show "ktc_tape c'' j (ktc_pos c'' j) = BLANK4"
using pad_cwrite jk by simp
qed
have src_read'': "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, 0, 0, m_a', m_d, ?aposk)"
using kpos_ktm dsupp posk_tail by (simp add: ar_stage_bounded_def)
show ?thesis
proof (intro exI[where x = cMn] conjI)
show "(cM, cMn) ∈ ktm_step (delta_ktm M)" by (rule m_step)
show "ar_walker_at_boundary M cMn c''"
proof -
consider
(cont) "q' ∉ {t_ktm M, r_ktm M}"
"ktc_state c'' = (q', AR_SimRead, 0, 0, m_a', m_d, ?aposk)"
| (acc) "q' = t_ktm M"
"ktc_state c'' = (t_ktm M, ar_accept_stage (bl_ktm M))"
| (rej) "q' = r_ktm M"
"ktc_state c'' = (r_ktm M, ar_reject_stage (bl_ktm M))"
using nxt_disj by blast
thus ?thesis
proof cases
case cont
have notT: "q' ≠ t_ktm M" using cont(1) by simp
have notR: "q' ≠ r_ktm M" using cont(1) by simp
show ?thesis
unfolding ar_walker_at_boundary_def
proof (intro conjI)
show "ar_simulates M cMn c''"
by (simp add: ar_simulates_def Let_def cont(2) st_cMn notT notR
tcorr_1 apos_1)
show "ar_posk_consistent M cMn c''"
by (simp add: ar_posk_consistent_def cont(2) aposk_1)
show "ar_at_read_boundary M c''"
by (simp add: ar_at_read_boundary_def cont(2) a'G pad_c'' src_read'')
qed
next
case acc
show ?thesis
unfolding ar_walker_at_boundary_def
proof (intro conjI)
show "ar_simulates M cMn c''"
by (simp add: ar_simulates_def Let_def acc(2) st_cMn acc(1)
tcorr_1 ar_accept_stage_def)
show "ar_posk_consistent M cMn c''"
by (simp add: ar_posk_consistent_def acc(2) ar_accept_stage_def)
show "ar_at_read_boundary M c''"
by (simp add: ar_at_read_boundary_def acc(2) ar_accept_stage_def
pad_c'')
qed
next
case rej
show ?thesis
unfolding ar_walker_at_boundary_def
proof (intro conjI)
show "ar_simulates M cMn c''"
by (simp add: ar_simulates_def Let_def rej(2) st_cMn rej(1)
tcorr_1 ar_reject_stage_def)
show "ar_posk_consistent M cMn c''"
by (simp add: ar_posk_consistent_def rej(2) ar_reject_stage_def)
show "ar_at_read_boundary M c''"
by (simp add: ar_at_read_boundary_def rej(2) ar_reject_stage_def
pad_c'')
qed
qed
qed
qed
qed
subsection ‹The reverse simulation, one cycle at a time›
text ‹The reverse-direction loop invariant: the substep-walker is in
∗‹some› stage of the cycle. Six disjuncts, one per walker
predicate. This is the AR analogue of
carrying ‹ae_simulates› across AE's reverse induction, but
stage-granular: where AE peels a whole fixed-length cycle per
‹ae_backward_stage›, AR peels one ‹M'›-substep and dispatches on
the current substep tag, because here the length of a cycle depends on
the data.›
definition ar_walker ::
"('q, 'a) ktm
⇒ ('a, 'q) ktc_config
⇒ (sym4, 'q × 'a ar_stage) ktc_config ⇒ bool" where
"ar_walker M cM c' ⟷
ar_walker_at_boundary M cM c'
∨ ar_walker_in_read M cM c'
∨ ar_walker_at_compute M cM c'
∨ ar_walker_in_write M cM c'
∨ ar_walker_in_advance M cM c'
∨ ar_walker_at_next M cM c'"
text ‹Chunked-induction engine for the reverse direction, the AR analogue of
AE's ‹ae_simulation_phase_chunked_reverse›. Given a finite
‹M'›-trace ‹(c', c_acc)› of length ‹m› ending in the canonical
accept config ‹(t_ktm M, ar_accept_stage (bl_ktm M))› and the walker
invariant at ‹c'› relative to a reachable ‹cM›, deliver an
accepting ‹M›-path from ‹cM›. Strong induction on ‹m›; at
each level dispatch on the walker stage and peel one ‹M'›-step:
▪ the five active stages (‹in_read›, ‹at_compute›,
‹in_write›, ‹in_advance›, ‹at_next›, and an active read
boundary) all have ‹c' ≠ c_acc›, so ‹m = Suc m'›; peel
the step via the matching preservation lemma (‹at_compute› emits
one ‹M›-step into the ‹in_write› witness; ‹at_next› emits
one via ‹ar_walker_cycle_close› and advances ‹cM›), then
recurse on ‹m'›;
▪ a boundary at the accept config closes the induction:
‹ar_simulates_accept_iff› forces ‹ktc_state cM = t_ktm M›;
▪ a boundary at the reject config is impossible — the trace runs to
the accept config, but reject is terminal (‹ar_reject_terminal›)
and the reject config is not the accept config.
The conclusion is in ‹rtrancl› form for the downstream
‹Lang_ktm›-repacking in ‹alphabet_reduce_language›.›
lemma ar_simulation_phase_chunked_reverse:
fixes M :: "('q, 'a) ktm"
and w :: "'a list"
and cM :: "('a, 'q) ktc_config"
and c' c_acc :: "(sym4, 'q × 'a ar_stage) ktc_config"
and m :: nat
assumes vM: "valid_ktm M"
and w_sub: "set w ⊆ Sigma_ktm M"
and card_ge: "card (Γ_ktm M) ≥ 4"
and lebl: "le_ktm M ≠ bl_ktm M"
and reach_M: "(init_config_ktm M w, cM) ∈ (ktm_step (delta_ktm M))⇧*"
and trace: "(c', c_acc) ∈ (ktm_step (alphabet_reduce_delta M)) ^^ m"
and accept: "ktc_state c_acc = (t_ktm M, ar_accept_stage (bl_ktm M))"
and walk: "ar_walker M cM c'"
shows "∃cM_final. (cM, cM_final) ∈ (ktm_step (delta_ktm M))⇧*
∧ ktc_state cM_final = t_ktm M"
using reach_M trace walk
proof (induction m arbitrary: cM c' rule: less_induct)
case (less m)
let ?R = "ktm_step (alphabet_reduce_delta M)"
have kge2: "2 ≤ block_width (Γ_ktm M)"
proof -
have "(2::nat) ^ 2 ≤ 2 ^ block_width (Γ_ktm M)"
using card_ge card_le_two_pow_block_width[of "Γ_ktm M"] by simp
thus "2 ≤ block_width (Γ_ktm M)"
using power_le_imp_le_exp[of "2::nat" 2 "block_width (Γ_ktm M)"] by simp
qed
have valcM: "valid_config_ktm M cM"
by (rule valid_reach_ktm[OF vM w_sub less.prems(1)])
have qQ: "ktc_state cM ∈ Q_ktm M" using valcM by (cases M; cases cM) auto
have tapeG: "ktc_tape cM k (ktc_pos cM k) ∈ Γ_ktm M" for k
proof -
have "range (ktc_tape cM k) ⊆ Γ_ktm M"
using valcM by (cases M; cases cM) auto
thus ?thesis by blast
qed
have acc_idx: "fst (snd (ktc_state c_acc)) = AR_HaltAccept"
using accept by (simp add: ar_accept_stage_def)
have peel: "∃m' c'_1. m = Suc m'
∧ (c', c'_1) ∈ ?R ∧ (c'_1, c_acc) ∈ ?R ^^ m'"
if notHA: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
proof -
have "m ≠ 0"
proof
assume "m = 0"
hence "c' = c_acc" using less.prems(2) by simp
thus False using notHA acc_idx by simp
qed
then obtain m' where mSuc: "m = Suc m'" using not0_implies_Suc by blast
have "(c', c_acc) ∈ ?R ^^ Suc m'" using less.prems(2) mSuc by simp
from relpow_Suc_D2[OF this] obtain c'_1 where
"(c', c'_1) ∈ ?R" and "(c'_1, c_acc) ∈ ?R ^^ m'" by blast
thus ?thesis using mSuc by blast
qed
from less.prems(3)
consider (bnd) "ar_walker_at_boundary M cM c'"
| (rd) "ar_walker_in_read M cM c'"
| (cmp) "ar_walker_at_compute M cM c'"
| (wr) "ar_walker_in_write M cM c'"
| (adv) "ar_walker_in_advance M cM c'"
| (nx) "ar_walker_at_next M cM c'"
unfolding ar_walker_def by blast
then show ?case
proof cases
case bnd
have sim: "ar_simulates M cM c'"
using bnd unfolding ar_walker_at_boundary_def by simp
obtain qM0 stg where st: "ktc_state c' = (qM0, stg)"
by (cases "ktc_state c'") auto
obtain idx tk i buf dvec posk where
sg: "stg = (idx, tk, i, buf, dvec, posk)" by (cases stg) auto
have state_disj:
"(idx = AR_SimRead ∧ qM0 ∉ {t_ktm M, r_ktm M})
∨ (qM0 = t_ktm M ∧ stg = ar_accept_stage (bl_ktm M))
∨ (qM0 = r_ktm M ∧ stg = ar_reject_stage (bl_ktm M))"
using sim st sg unfolding ar_simulates_def by (auto split: prod.splits)
consider (active) "idx = AR_SimRead"
| (acc) "stg = ar_accept_stage (bl_ktm M)" "qM0 = t_ktm M"
| (rej) "stg = ar_reject_stage (bl_ktm M)" "qM0 = r_ktm M"
using state_disj by blast
thus ?thesis
proof cases
case active
have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
using st sg active by simp
obtain m' c'_1 where mSuc: "m = Suc m'"
and fst_step: "(c', c'_1) ∈ ?R"
and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
using peel[OF neq] by blast
have m'_lt: "m' < m" using mSuc by simp
have "ar_walker_in_read M cM c'_1 ∨ ar_walker_at_compute M cM c'_1"
using ar_walker_step_from_boundary[OF bnd fst_step] .
hence walk_1: "ar_walker M cM c'_1" unfolding ar_walker_def by blast
show ?thesis using less.IH[OF m'_lt less.prems(1) rest walk_1] .
next
case acc
have c'_acc: "ktc_state c' = (t_ktm M, ar_accept_stage (bl_ktm M))"
using st sg acc by simp
have cM_t: "ktc_state cM = t_ktm M"
using ar_simulates_accept_iff[OF vM sim] c'_acc by simp
have "(cM, cM) ∈ (ktm_step (delta_ktm M))⇧*" by simp
thus ?thesis using cM_t by blast
next
case rej
have c'_rej: "ktc_state c' = (r_ktm M, ar_reject_stage (bl_ktm M))"
using st sg rej by simp
show ?thesis
proof (cases m)
case 0
have ceq: "c' = c_acc" using less.prems(2) 0 by simp
have "fst (snd (ktc_state c')) = AR_HaltReject"
using c'_rej by (simp add: ar_reject_stage_def)
moreover have "fst (snd (ktc_state c')) = AR_HaltAccept"
using ceq accept by (simp add: ar_accept_stage_def)
ultimately show ?thesis by simp
next
case (Suc m')
have "(c', c_acc) ∈ ?R ^^ Suc m'" using less.prems(2) Suc by simp
from relpow_Suc_D2[OF this] obtain c'_1 where
fst_step: "(c', c'_1) ∈ ?R" by blast
have "ktc_state c' ≠ (r_ktm M, ar_reject_stage (bl_ktm M))"
by (rule ar_reject_terminal[OF vM card_ge fst_step])
thus ?thesis using c'_rej by simp
qed
qed
next
case rd
have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
using rd unfolding ar_walker_in_read_def by simp
obtain m' c'_1 where mSuc: "m = Suc m'"
and fst_step: "(c', c'_1) ∈ ?R"
and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
using peel[OF neq] by blast
have m'_lt: "m' < m" using mSuc by simp
have "ar_walker_in_read M cM c'_1 ∨ ar_walker_at_compute M cM c'_1"
using ar_walker_step_from_in_read[OF rd fst_step] .
hence walk_1: "ar_walker M cM c'_1" unfolding ar_walker_def by blast
show ?thesis using less.IH[OF m'_lt less.prems(1) rest walk_1] .
next
case cmp
have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
using cmp unfolding ar_walker_at_compute_def by simp
obtain m' c'_1 where mSuc: "m = Suc m'"
and fst_step: "(c', c'_1) ∈ ?R"
and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
using peel[OF neq] by blast
have m'_lt: "m' < m" using mSuc by simp
have w_1: "ar_walker_in_write M cM c'_1"
using ar_walker_step_from_at_compute[OF cmp fst_step vM qQ kge2 tapeG] .
have walk_1: "ar_walker M cM c'_1" using w_1 unfolding ar_walker_def by blast
show ?thesis using less.IH[OF m'_lt less.prems(1) rest walk_1] .
next
case wr
have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
using wr unfolding ar_walker_in_write_def by simp
obtain m' c'_1 where mSuc: "m = Suc m'"
and fst_step: "(c', c'_1) ∈ ?R"
and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
using peel[OF neq] by blast
have m'_lt: "m' < m" using mSuc by simp
have "ar_walker_in_write M cM c'_1 ∨ ar_walker_in_advance M cM c'_1"
using ar_walker_step_from_in_write[OF wr fst_step] .
hence walk_1: "ar_walker M cM c'_1" unfolding ar_walker_def by blast
show ?thesis using less.IH[OF m'_lt less.prems(1) rest walk_1] .
next
case adv
have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
using adv unfolding ar_walker_in_advance_def by simp
obtain m' c'_1 where mSuc: "m = Suc m'"
and fst_step: "(c', c'_1) ∈ ?R"
and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
using peel[OF neq] by blast
have m'_lt: "m' < m" using mSuc by simp
have "ar_walker_in_advance M cM c'_1 ∨ ar_walker_at_next M cM c'_1"
using ar_walker_step_from_in_advance[OF adv fst_step] .
hence walk_1: "ar_walker M cM c'_1" unfolding ar_walker_def by blast
show ?thesis using less.IH[OF m'_lt less.prems(1) rest walk_1] .
next
case nx
have neq: "fst (snd (ktc_state c')) ≠ AR_HaltAccept"
using nx unfolding ar_walker_at_next_def by simp
obtain m' c'_1 where mSuc: "m = Suc m'"
and fst_step: "(c', c'_1) ∈ ?R"
and rest: "(c'_1, c_acc) ∈ ?R ^^ m'"
using peel[OF neq] by blast
have m'_lt: "m' < m" using mSuc by simp
obtain cMn where step_cMn: "(cM, cMn) ∈ ktm_step (delta_ktm M)"
and bnd_1: "ar_walker_at_boundary M cMn c'_1"
using ar_walker_cycle_close[OF nx fst_step vM qQ kge2 tapeG
w_sub less.prems(1) lebl]
by blast
have reach_Mn: "(init_config_ktm M w, cMn) ∈ (ktm_step (delta_ktm M))⇧*"
using less.prems(1) step_cMn by (rule rtrancl.rtrancl_into_rtrancl)
have walk_1: "ar_walker M cMn c'_1"
using bnd_1 unfolding ar_walker_def by blast
obtain cM_final where
run_final: "(cMn, cM_final) ∈ (ktm_step (delta_ktm M))⇧*"
and acc_final: "ktc_state cM_final = t_ktm M"
using less.IH[OF m'_lt reach_Mn rest walk_1] by blast
have "(cM, cM_final) ∈ (ktm_step (delta_ktm M))⇧*"
using step_cMn run_final by (meson r_into_rtrancl rtrancl_trans)
thus ?thesis using acc_final by blast
qed
qed
text ‹Classical language-equivalence (biconditional) for alphabet
reduction: an ‹'a›-word ‹w› over the input alphabet is in
‹M›'s language iff its ‹sym4›-encoding is in the language
of the reduced machine ‹M'›. Pairs the forward inclusion
‹alphabet_reduce_language_forward› (in
‹AlphabetReduction_Theorems.thy›) with the reverse leg supplied by
‹ar_simulation_phase_chunked_reverse›.
Unlike AE, the alphabet-reduction construction has no input
validation prefix (the no-validation design point), so the reverse
direction needs neither a validation-peel nor a determinism /
chain-uniqueness argument: the encoded input's accepting ‹M'›-run
is handed to the engine directly off the initial read-boundary
correspondence (‹ar_walker_at_boundary›, the conjunction of the
three ‹_init› invariants). No ‹det_ktm› hypothesis is
required.
The ‹set w ⊆ Sigma_ktm M› guard is required (and matches
AE's statement): ‹Lang_ktm› bakes in the input-alphabet
restriction, so ‹w ∈ Lang_ktm M› supplies the guard for
free in the forward direction, but membership of the encoded word
in ‹Lang_ktm M'› says nothing about ‹w›'s alphabet. For
‹w› outside the input alphabet the encoded word can still be
accepted by ‹M'› while ‹w ∉ Lang_ktm M›.›
theorem alphabet_reduce_language:
fixes M :: "('q, 'a) ktm"
assumes vM: "valid_ktm M"
and s_neq_t: "s_ktm M ≠ t_ktm M"
and s_neq_r: "s_ktm M ≠ r_ktm M"
and le_neq_bl: "le_ktm M ≠ bl_ktm M"
and card_ge: "card (Γ_ktm M) ≥ 4"
shows "∀w. set w ⊆ Sigma_ktm M
⟶ (encode_input_ar (Γ_ktm M) (bl_ktm M) w ∈ Lang_ktm
(alphabet_reduce M
:: ('q × 'a ar_stage, sym4) ktm))
= (w ∈ Lang_ktm M)"
proof -
let ?M' = "alphabet_reduce M :: ('q × 'a ar_stage, sym4) ktm"
have fwd: "∀w. set w ⊆ Sigma_ktm M
⟶ w ∈ Lang_ktm M
⟶ encode_input_ar (Γ_ktm M) (bl_ktm M) w ∈ Lang_ktm ?M'"
by (rule alphabet_reduce_language_forward[OF vM s_neq_t s_neq_r le_neq_bl card_ge])
show ?thesis
proof (intro allI impI)
fix w :: "'a list"
assume w_sub: "set w ⊆ Sigma_ktm M"
let ?enc = "encode_input_ar (Γ_ktm M) (bl_ktm M) w"
let ?c' = "init_config_ktm ?M' ?enc"
show "(?enc ∈ Lang_ktm ?M') = (w ∈ Lang_ktm M)"
proof
assume w_in_M: "w ∈ Lang_ktm M"
from fwd w_sub w_in_M show "?enc ∈ Lang_ktm ?M'" by blast
next
assume enc_in_M': "?enc ∈ Lang_ktm ?M'"
from enc_in_M' obtain wM' nM' where
acc_path_M':
"(?c', KConfig (t_ktm ?M') wM' nM')
∈ (ktm_step (delta_ktm ?M'))⇧*"
unfolding Lang_ktm_def by blast
have acc_path:
"(?c', KConfig (t_ktm ?M') wM' nM')
∈ (ktm_step (alphabet_reduce_delta M))⇧*"
using acc_path_M' by simp
obtain m where trace:
"(?c', KConfig (t_ktm ?M') wM' nM')
∈ (ktm_step (alphabet_reduce_delta M)) ^^ m"
using acc_path rtrancl_imp_relpow by metis
have accept:
"ktc_state (KConfig (t_ktm ?M') wM' nM')
= (t_ktm M, ar_accept_stage (bl_ktm M))"
by simp
have sim: "ar_simulates M (init_config_ktm M w) ?c'"
by (rule ar_simulates_init[OF vM w_sub s_neq_t s_neq_r])
have posk: "ar_posk_consistent M (init_config_ktm M w) ?c'"
by (rule ar_posk_consistent_init)
have rbnd: "ar_at_read_boundary M ?c'"
by (rule ar_at_read_boundary_init[OF vM])
have walk: "ar_walker M (init_config_ktm M w) ?c'"
unfolding ar_walker_def ar_walker_at_boundary_def
using sim posk rbnd by blast
have reach_refl: "(init_config_ktm M w, init_config_ktm M w)
∈ (ktm_step (delta_ktm M))⇧*" by simp
obtain cM_final where
M_path: "(init_config_ktm M w, cM_final)
∈ (ktm_step (delta_ktm M))⇧*"
and M_acc: "ktc_state cM_final = t_ktm M"
using ar_simulation_phase_chunked_reverse
[OF vM w_sub card_ge le_neq_bl reach_refl trace accept walk]
by blast
obtain wM_acc nM_acc where
cM_final_eq: "cM_final = KConfig (t_ktm M) wM_acc nM_acc"
using M_acc by (cases cM_final) simp
show "w ∈ Lang_ktm M"
unfolding Lang_ktm_def
using w_sub M_path cM_final_eq by blast
qed
qed
qed
end