Theory Multitape_Alphabet_Enlargement.AlphabetEnlargement_Window
theory AlphabetEnlargement_Window
imports AlphabetEnlargement_BufferArith
begin
subsection ‹Window-invariant single-step preservation›
text ‹Steady-regime window-invariant preservation under one
buffered ‹M›-step. Takes the IH-side invariant
‹ae_window_invariant tM nM bp blocks p_start›, the buffered
head advance ‹bp_advance_le le (tM nM) bp d = Some bp'›, the
position bounds excluding ‹bp_advance›'s None cases
(‹bp_linear < 3c - 1› for R, ‹0 < bp_linear› for L), and
a no-LE-at-head fact (‹tM nM ≠ le›) excluding
‹bp_advance_le›'s LE-jump. Produces the new invariant for
the parallel tape fun-update and buffer ‹write_bp›.
In the steady regime (‹pos ≥ 2›) the no-LE precondition is
forced by the regime's no-LE window: the buffered head's
‹nM = p_start + bp_linear bp› lies inside the no-LE
window ‹[p_start, p_start + 3c - 1]›, so ‹tM nM ≠ le›.
Used by the Suc case of ‹ae_coupled_run_aux_general› to
discharge conjunct 2 in the ‹pos ≥ 2› regime.›
lemma ae_window_invariant_step:
fixes le a' :: 'a
and tM :: "nat ⇒ 'a"
and nM p_start :: nat
and bp bp' :: "bp"
and blocks :: "(nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
and d :: move
assumes wi: "ae_window_invariant m tM nM bp blocks p_start"
and adv: "bp_advance_le m le (tM nM) bp d = Some bp'"
and bp_lt: "bp_linear m bp < 3 * m - 1"
and bp_pos: "0 < bp_linear m bp"
and no_le: "tM nM ≠ le"
shows "ae_window_invariant m
(tM(nM := a')) (go_move d nM)
bp' (write_bp blocks bp a') p_start"
proof -
let ?c = "m"
from wi have p_start_ge: "p_start ≥ 1"
unfolding ae_window_invariant_def by simp
from wi have head_corr: "nM = p_start + bp_linear m bp"
unfolding ae_window_invariant_def by simp
from wi have win_eq:
"∀i. i < 3 * ?c ⟶ tM (p_start + i) = buf_lin_at m blocks i"
unfolding ae_window_invariant_def by simp
from wi have bp_m: "snd bp < m"
unfolding ae_window_invariant_def by simp
from wi have bext: "ae_blocks_ext m blocks"
unfolding ae_window_invariant_def by simp
have bext': "ae_blocks_ext m (write_bp blocks bp a')"
by (rule ae_blocks_ext_write_bp[OF bext bp_m])
have bp'_m: "snd bp' < m"
using bp_advance_le_offset_lt[OF _ bp_m adv] bp_m by simp
have adv_plain: "bp_advance m bp d = Some bp'"
proof -
from no_le have "¬ (tM nM = le ∧ fst bp = AE_Home ∧ d = MoveR)"
by simp
hence "bp_advance_le m le (tM nM) bp d = bp_advance m bp d"
unfolding bp_advance_le_def by auto
with adv show ?thesis by simp
qed
have head_new: "go_move d nM = p_start + bp_linear m bp'"
proof (cases d)
case MoveN
from adv_plain MoveN have "Some bp' = Some bp"
using bp_advance_N_some[of _ bp] by simp
hence bp'_eq: "bp' = bp" by simp
show ?thesis using MoveN bp'_eq head_corr by simp
next
case MoveR
from adv_plain MoveR have adv_R: "bp_advance m bp MoveR = Some bp'" by simp
have lin_R: "bp_linear m bp' = Suc (bp_linear m bp)"
by (rule bp_advance_R_linear[OF adv_R bp_m])
show ?thesis using MoveR lin_R head_corr by simp
next
case MoveL
from adv_plain MoveL have adv_L: "bp_advance m bp MoveL = Some bp'" by simp
have lin_L: "Suc (bp_linear m bp') = bp_linear m bp"
by (rule bp_advance_L_linear[OF adv_L bp_m])
have nM_form: "nM = Suc (p_start + bp_linear m bp')"
using head_corr lin_L by simp
show ?thesis using MoveL nM_form by simp
qed
have win_new:
"∀i. i < 3 * ?c ⟶
(tM(nM := a')) (p_start + i)
= buf_lin_at m (write_bp blocks bp a') i"
proof (intro allI impI)
fix i
assume i_lt: "i < 3 * ?c"
show "(tM(nM := a')) (p_start + i)
= buf_lin_at m (write_bp blocks bp a') i"
proof (cases "i = bp_linear m bp")
case True
have pos_eq: "p_start + i = nM" using True head_corr by simp
have "(tM(nM := a')) (p_start + i) = a'" using pos_eq by simp
moreover have "buf_lin_at m (write_bp blocks bp a') i = a'"
using True buf_lin_at_write_bp_match[OF bp_m, where blocks=blocks and x=a'] by simp
ultimately show ?thesis by simp
next
case False
hence pos_neq: "p_start + i ≠ nM" using head_corr by simp
have "(tM(nM := a')) (p_start + i) = tM (p_start + i)"
using pos_neq by simp
also have "... = buf_lin_at m blocks i" using win_eq i_lt by blast
also have "... = buf_lin_at m (write_bp blocks bp a') i"
by (rule buf_lin_at_write_bp_other[OF False i_lt, symmetric])
finally show ?thesis .
qed
qed
show ?thesis
unfolding ae_window_invariant_def
using p_start_ge head_new win_new bp'_m bext' by simp
qed
text ‹Structural-case equivalence for the ‹le1› regime: the
case-on-‹fst bp› head-position constraint in
‹ae_window_invariant_le1› is equivalent to the single algebraic
relation ‹Suc (bp_linear bp) = nM + c›.
Forward direction (‹⇒›): case-split on ‹fst bp›, compute
‹bp_linear› from the case, conclude the algebraic relation.
Backward direction (‹⇐›): given the algebraic relation,
case-split on ‹fst bp› and recover the original case-clause
from ‹bp_linear›'s known form per case (using
‹c_last_def› for the ‹AE_Left› sub-case where the
algebraic relation forces ‹snd bp = c_last›).
Used by ‹ae_window_invariant_le1_step› to reduce the
structural-case preservation goal to a single algebraic check,
avoiding a per-direction-per-block-boundary nested case analysis.›
lemma bp_linear_le1_struct_iff:
fixes bp :: "bp"
and nM :: nat
assumes bp_m: "snd bp < m"
shows "(case fst bp of
AE_Left ⇒ snd bp = c_last m ∧ nM = 0
| AE_Home ⇒ nM = Suc (snd bp)
| AE_Right ⇒ nM = Suc (m
+ snd bp))
⟷ Suc (bp_linear m bp) = nM + m"
proof -
let ?c = "m"
show ?thesis
proof (cases "fst bp")
case AE_Left
have lin_eq: "bp_linear m bp = snd bp"
using AE_Left by (cases bp) simp
show ?thesis
proof
assume "case fst bp of
AE_Left ⇒ snd bp = c_last m ∧ nM = 0
| AE_Home ⇒ nM = Suc (snd bp)
| AE_Right ⇒ nM = Suc (?c + snd bp)"
with AE_Left have snd_eq: "snd bp = c_last m" and nM_eq: "nM = 0" by auto
have "snd bp = ?c - 1" using snd_eq c_last_def by simp
thus "Suc (bp_linear m bp) = nM + ?c"
using lin_eq nM_eq bp_m by simp
next
assume "Suc (bp_linear m bp) = nM + ?c"
hence "Suc (snd bp) = nM + ?c" using lin_eq by simp
hence nM_zero: "nM = 0"
using bp_m by linarith
with ‹Suc (snd bp) = nM + ?c›
have idx_eq: "snd bp = ?c - 1" using bp_m by simp
have c_last_eq: "(c_last m :: nat) = ?c - 1"
by (simp add: c_last_def)
have idx_at: "snd bp = (c_last m :: nat)"
using idx_eq c_last_eq by simp
hence snd_eq: "snd bp = c_last m"
by simp
show "case fst bp of
AE_Left ⇒ snd bp = c_last m ∧ nM = 0
| AE_Home ⇒ nM = Suc (snd bp)
| AE_Right ⇒ nM = Suc (?c + snd bp)"
using AE_Left snd_eq nM_zero by simp
qed
next
case AE_Home
have lin_eq: "bp_linear m bp = ?c + snd bp"
using AE_Home by (cases bp) simp
show ?thesis
proof
assume "case fst bp of
AE_Left ⇒ snd bp = c_last m ∧ nM = 0
| AE_Home ⇒ nM = Suc (snd bp)
| AE_Right ⇒ nM = Suc (?c + snd bp)"
with AE_Home have nM_eq: "nM = Suc (snd bp)" by simp
thus "Suc (bp_linear m bp) = nM + ?c" using lin_eq by simp
next
assume "Suc (bp_linear m bp) = nM + ?c"
hence "Suc (?c + snd bp) = nM + ?c" using lin_eq by simp
hence "nM = Suc (snd bp)" by simp
thus "case fst bp of
AE_Left ⇒ snd bp = c_last m ∧ nM = 0
| AE_Home ⇒ nM = Suc (snd bp)
| AE_Right ⇒ nM = Suc (?c + snd bp)"
using AE_Home by simp
qed
next
case AE_Right
have lin_eq: "bp_linear m bp = 2 * ?c + snd bp"
using AE_Right by (cases bp) simp
show ?thesis
proof
assume "case fst bp of
AE_Left ⇒ snd bp = c_last m ∧ nM = 0
| AE_Home ⇒ nM = Suc (snd bp)
| AE_Right ⇒ nM = Suc (?c + snd bp)"
with AE_Right have nM_eq: "nM = Suc (?c + snd bp)" by simp
thus "Suc (bp_linear m bp) = nM + ?c" using lin_eq by simp
next
assume "Suc (bp_linear m bp) = nM + ?c"
hence "Suc (2 * ?c + snd bp) = nM + ?c" using lin_eq by simp
hence "nM = Suc (?c + snd bp)" by simp
thus "case fst bp of
AE_Left ⇒ snd bp = c_last m ∧ nM = 0
| AE_Home ⇒ nM = Suc (snd bp)
| AE_Right ⇒ nM = Suc (?c + snd bp)"
using AE_Right by simp
qed
qed
qed
text ‹‹le1›-regime window-invariant preservation under one
buffered ‹M›-step. Takes the IH-side invariant
‹ae_window_invariant_le1 tM nM bp blocks le›, the buffered
head advance, the position bounds, and the substrate-derived
facts on ‹a'› / ‹d›'s response to the read symbol's
LE-status: when reading ‹le›, M writes ‹le› and moves
N or R (from ‹valid_ktm_deltaLE›); when reading
non-‹le›, M doesn't write ‹le› (from
‹valid_ktm_deltaLE_no_write›'s contrapositive). Also takes
a no-LE-in-window precondition (from the IH-side
‹no_le› invariant restricted to the ‹le1› regime's
window cells ‹1..2c›) which forces the LE-jump in
‹bp_advance_le› to never fire.
Used by the Suc case of ‹ae_coupled_run_aux_general› to
discharge conjunct 2 in the ‹pos = 1› regime.›
lemma ae_window_invariant_le1_step:
fixes le a' :: 'a
and tM :: "nat ⇒ 'a"
and nM :: nat
and bp bp' :: "bp"
and blocks :: "(nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
and d :: move
assumes wi: "ae_window_invariant_le1 m tM nM bp blocks le"
and adv: "bp_advance_le m le (tM nM) bp d = Some bp'"
and bp_lt: "bp_linear m bp < 3 * m - 1"
and bp_pos: "0 < bp_linear m bp"
and a_le: "tM nM = le ⟹ a' = le ∧ d ∈ {MoveN, MoveR}"
and a_not_le: "tM nM ≠ le ⟹ a' ≠ le"
and no_le_win: "∀i. 0 < i ∧ i ≤ 2 * m
⟶ tM i ≠ le"
shows "ae_window_invariant_le1 m
(tM(nM := a')) (go_move d nM)
bp' (write_bp blocks bp a') le"
proof -
let ?c = "m"
from wi have l_LE: "fst blocks = LE_block m le"
unfolding ae_window_invariant_le1_def by simp
from wi have tM_0: "tM 0 = le"
unfolding ae_window_invariant_le1_def by simp
from wi have bp_m: "snd bp < m"
unfolding ae_window_invariant_le1_def by simp
from wi have bext: "ae_blocks_ext m blocks"
unfolding ae_window_invariant_le1_def by simp
have bext': "ae_blocks_ext m (write_bp blocks bp a')"
by (rule ae_blocks_ext_write_bp[OF bext bp_m])
have bp'_m: "snd bp' < m"
using bp_advance_le_offset_lt[OF _ bp_m adv] bp_m by simp
have struct_lin: "Suc (bp_linear m bp) = nM + ?c"
proof -
have "(case fst bp of
AE_Left ⇒ snd bp = c_last m ∧ nM = 0
| AE_Home ⇒ nM = Suc (snd bp)
| AE_Right ⇒ nM = Suc (?c + snd bp))"
using wi unfolding ae_window_invariant_le1_def by simp
thus ?thesis
using bp_linear_le1_struct_iff[OF bp_m, where nM = nM]
by blast
qed
from wi have align:
"∀i. i < 2 * ?c ⟶ tM (Suc i) = buf_lin_at m blocks (?c + i)"
unfolding ae_window_invariant_le1_def by simp
have not_le_jump: "¬ (tM nM = le ∧ fst bp = AE_Home ∧ d = MoveR)"
proof
assume "tM nM = le ∧ fst bp = AE_Home ∧ d = MoveR"
hence le_at: "tM nM = le" and fst_home: "fst bp = AE_Home" by auto
have lin: "bp_linear m bp = ?c + snd bp"
using fst_home by (cases bp) simp
from struct_lin lin have nM_eq: "nM = Suc (snd bp)" by simp
have nM_bd: "0 < nM ∧ nM ≤ ?c" using nM_eq bp_m by simp
hence "tM nM ≠ le" using no_le_win by simp
with le_at show False by simp
qed
have adv_plain: "bp_advance m bp d = Some bp'"
proof -
have "bp_advance_le m le (tM nM) bp d = bp_advance m bp d"
using not_le_jump unfolding bp_advance_le_def by auto
with adv show ?thesis by simp
qed
have struct_new: "Suc (bp_linear m bp') = go_move d nM + ?c"
proof (cases d)
case MoveN
from adv_plain MoveN have "Some bp' = Some bp"
using bp_advance_N_some[of _ bp] by simp
hence bp'_eq: "bp' = bp" by simp
show ?thesis using MoveN bp'_eq struct_lin by simp
next
case MoveR
from adv_plain MoveR have adv_R: "bp_advance m bp MoveR = Some bp'" by simp
have lin_R: "bp_linear m bp' = Suc (bp_linear m bp)"
by (rule bp_advance_R_linear[OF adv_R bp_m])
show ?thesis using MoveR lin_R struct_lin by simp
next
case MoveL
from adv_plain MoveL have adv_L: "bp_advance m bp MoveL = Some bp'" by simp
have lin_L: "Suc (bp_linear m bp') = bp_linear m bp"
by (rule bp_advance_L_linear[OF adv_L bp_m])
have nM_pos: "0 < nM"
proof (rule ccontr)
assume "¬ 0 < nM"
hence "nM = 0" by simp
hence "tM nM = le" using tM_0 by simp
with a_le have d_in: "d ∈ {MoveN, MoveR}" by blast
with MoveL show False by simp
qed
obtain p where m_eq: "nM = Suc p" using nM_pos by (cases nM) auto
have "Suc (Suc (bp_linear m bp')) = Suc (bp_linear m bp)"
using lin_L by simp
also have "... = nM + ?c" using struct_lin by simp
also have "... = Suc (p + ?c)" using m_eq by simp
finally have lhs_eq: "Suc (bp_linear m bp') = p + ?c" by simp
have rhs_eq: "go_move MoveL nM = p" using m_eq by simp
show ?thesis using MoveL lhs_eq rhs_eq by simp
qed
have struct_post:
"(case fst bp' of
AE_Left ⇒ snd bp' = c_last m ∧ go_move d nM = 0
| AE_Home ⇒ go_move d nM = Suc (snd bp')
| AE_Right ⇒ go_move d nM = Suc (?c + snd bp'))"
using struct_new
bp_linear_le1_struct_iff[OF bp'_m, where nM = "go_move d nM"]
by blast
have align_new:
"∀i. i < 2 * ?c ⟶
(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (?c + i)"
proof (intro allI impI)
fix i
assume i_lt: "i < 2 * ?c"
show "(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (?c + i)"
proof (cases "?c + i = bp_linear m bp")
case True
hence "Suc (?c + i) = Suc (bp_linear m bp)" by simp
hence "Suc i + ?c = nM + ?c" using struct_lin by simp
hence Suc_i_eq: "Suc i = nM" by simp
have lhs: "(tM(nM := a')) (Suc i) = a'" using Suc_i_eq by simp
have rhs: "buf_lin_at m (write_bp blocks bp a') (?c + i) = a'"
using True buf_lin_at_write_bp_match[OF bp_m, where blocks=blocks and x=a'] by simp
show ?thesis using lhs rhs by simp
next
case False
hence c_plus_i_neq: "?c + i ≠ bp_linear m bp" by simp
have Suc_i_neq: "Suc i ≠ nM"
proof
assume "Suc i = nM"
hence "Suc i + ?c = nM + ?c" by simp
hence "Suc (?c + i) = Suc (bp_linear m bp)" using struct_lin by simp
hence "?c + i = bp_linear m bp" by simp
with c_plus_i_neq show False ..
qed
have c_plus_i_lt: "?c + i < 3 * ?c" using i_lt by simp
have "(tM(nM := a')) (Suc i) = tM (Suc i)" using Suc_i_neq by simp
also have "... = buf_lin_at m blocks (?c + i)" using align i_lt by blast
also have "... = buf_lin_at m (write_bp blocks bp a') (?c + i)"
by (rule buf_lin_at_write_bp_other
[OF c_plus_i_neq c_plus_i_lt, symmetric])
finally show ?thesis .
qed
qed
have fst_new: "fst (write_bp blocks bp a') = LE_block m le"
proof (cases "fst bp")
case AE_Left
obtain b' off where bp_eq: "bp = (b', off)" by (cases bp)
have b'_eq: "b' = AE_Left" using AE_Left bp_eq by simp
have lin_eq: "bp_linear m bp = off" using bp_eq AE_Left by simp
have off_m: "off < m" using bp_m bp_eq by simp
from struct_lin lin_eq have suc_eq: "Suc off = nM + ?c" by simp
have nM_zero: "nM = 0" using suc_eq off_m by linarith
have idx_top: "off = ?c - 1" using suc_eq nM_zero by linarith
have c_last_eq: "(c_last m :: nat) = ?c - 1" by (simp add: c_last_def)
have idx_at: "off = (c_last m :: nat)"
using idx_top c_last_eq by simp
hence off_eq: "off = c_last m" by simp
have tM_nM_eq: "tM nM = le" using nM_zero tM_0 by simp
have a'_eq: "a' = le" using a_le tM_nM_eq by blast
obtain l h r where blocks_eq: "blocks = (l, h, r)"
by (cases blocks) auto
have l_eq: "l = LE_block m le" using l_LE blocks_eq by simp
have wb_eq: "write_bp blocks bp a' = (l(off := a'), h, r)"
using bp_eq b'_eq blocks_eq unfolding write_bp_def by simp
have "l(off := a') = LE_block m le"
proof -
have "l(off := a') = (LE_block m le)(c_last m := le)"
using l_eq off_eq a'_eq by simp
also have "... = LE_block m le" unfolding LE_block_def using off_m off_eq by auto
finally show ?thesis .
qed
thus ?thesis using wb_eq by simp
next
case AE_Home
obtain b' off where bp_eq: "bp = (b', off)" by (cases bp)
have b'_eq: "b' = AE_Home" using AE_Home bp_eq by simp
obtain l h r where blocks_eq: "blocks = (l, h, r)"
by (cases blocks) auto
have wb_eq: "write_bp blocks bp a' = (l, h(off := a'), r)"
using bp_eq b'_eq blocks_eq unfolding write_bp_def by simp
show ?thesis using wb_eq l_LE blocks_eq by simp
next
case AE_Right
obtain b' off where bp_eq: "bp = (b', off)" by (cases bp)
have b'_eq: "b' = AE_Right" using AE_Right bp_eq by simp
obtain l h r where blocks_eq: "blocks = (l, h, r)"
by (cases blocks) auto
have wb_eq: "write_bp blocks bp a' = (l, h, r(off := a'))"
using bp_eq b'_eq blocks_eq unfolding write_bp_def by simp
show ?thesis using wb_eq l_LE blocks_eq by simp
qed
have tM_0_new: "(tM(nM := a')) 0 = le"
proof (cases "nM = 0")
case True
have "tM nM = le" using True tM_0 by simp
hence "a' = le" using a_le by blast
thus ?thesis using True by simp
next
case False
have "(tM(nM := a')) 0 = tM 0" using False by simp
thus ?thesis using tM_0 by simp
qed
show ?thesis
unfolding ae_window_invariant_le1_def
using fst_new tM_0_new struct_post align_new bp'_m bext' by simp
qed
text ‹‹le0›-regime window-invariant preservation under one
buffered ‹M›-step. Differs from ‹le1› in that:
‹∙› the LE block lives in the home slot, not the left slot;
‹∙› ‹fst bp = AE_Left› is forbidden by the invariant;
‹∙› ‹fst bp = AE_Home› always reads ‹le› (the whole home
slot is ‹LE_block le›) so the LE-jump in
‹bp_advance_le› DOES fire on R from ‹AE_Home›;
‹∙› the alignment is only over right-slot cells
‹{1..c} ↔ {2c..3c-1}›.
Structurally the proof splits on ‹fst bp›: ‹AE_Left›
is closed by contradiction with the invariant; ‹AE_Home›
case-splits on ‹d ∈ {N, R}› (L forbidden by
‹valid_ktm_deltaLE›); ‹AE_Right› falls through to the
standard ‹bp_advance› with displacement ‹\<pm>1/0› and the
no-LE precondition rules out the LE-jump.›
lemma ae_window_invariant_le0_step:
fixes le a' :: 'a
and tM :: "nat ⇒ 'a"
and nM :: nat
and bp bp' :: "bp"
and blocks :: "(nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
and d :: move
assumes wi: "ae_window_invariant_le0 m tM nM bp blocks le"
and adv: "bp_advance_le m le (tM nM) bp d = Some bp'"
and bp_lt: "bp_linear m bp < 3 * m - 1"
and bp_pos: "0 < bp_linear m bp"
and a_le: "tM nM = le ⟹ a' = le ∧ d ∈ {MoveN, MoveR}"
and a_not_le: "tM nM ≠ le ⟹ a' ≠ le"
and no_le_win: "∀i. 0 < i ∧ i ≤ m
⟶ tM i ≠ le"
shows "ae_window_invariant_le0 m
(tM(nM := a')) (go_move d nM)
bp' (write_bp blocks bp a') le"
proof -
let ?c = "m"
from wi have h_LE: "fst (snd blocks) = LE_block m le"
unfolding ae_window_invariant_le0_def by simp
from wi have tM_0: "tM 0 = le"
unfolding ae_window_invariant_le0_def by simp
from wi have bp_m: "snd bp < m"
unfolding ae_window_invariant_le0_def by simp
from wi have bext: "ae_blocks_ext m blocks"
unfolding ae_window_invariant_le0_def by simp
have bext': "ae_blocks_ext m (write_bp blocks bp a')"
by (rule ae_blocks_ext_write_bp[OF bext bp_m])
have bp'_m: "snd bp' < m"
using bp_advance_le_offset_lt[OF _ bp_m adv] bp_m by simp
from wi have align:
"∀i. i < ?c ⟶ tM (Suc i) = buf_lin_at m blocks (2 * ?c + i)"
unfolding ae_window_invariant_le0_def by simp
from wi have struct_pre:
"(case fst bp of
AE_Home ⇒ nM = 0
| AE_Right ⇒ nM = Suc (snd bp)
| AE_Left ⇒ False)"
unfolding ae_window_invariant_le0_def by simp
have not_left: "fst bp ≠ AE_Left"
using struct_pre by (cases "fst bp") auto
obtain l h r where blocks_eq: "blocks = (l, h, r)"
by (cases blocks) auto
have h_eq: "h = LE_block m le" using h_LE blocks_eq by simp
obtain b off where bp_eq: "bp = (b, off)" by (cases bp)
show ?thesis
proof (cases b)
case AE_Left
with bp_eq not_left show ?thesis by simp
next
case AE_Home
have b_home: "b = AE_Home" using AE_Home .
from struct_pre bp_eq AE_Home have nM_zero: "nM = 0" by simp
have tM_nM_le: "tM nM = le" using nM_zero tM_0 by simp
from a_le tM_nM_le have a'_le: "a' = le"
and d_in: "d ∈ {MoveN, MoveR}" by auto
have wb_eq: "write_bp blocks bp a' = (l, h(off := a'), r)"
using bp_eq b_home blocks_eq unfolding write_bp_def by simp
have h_new: "h(off := a') = LE_block m le"
using h_eq a'_le bp_m bp_eq unfolding LE_block_def by auto
have new_blocks: "write_bp blocks bp a' = (l, LE_block m le, r)"
using wb_eq h_new by simp
have tM_new: "tM(nM := a') = tM"
using nM_zero tM_0 a'_le by auto
show ?thesis
proof (cases d)
case MoveN
from adv MoveN have "bp_advance_le m le (tM nM) bp MoveN = Some bp'" by simp
hence bp'_eq: "bp' = bp"
unfolding bp_advance_le_def using bp_advance_N_some[of _ bp] by auto
show ?thesis
unfolding ae_window_invariant_le0_def
proof (intro conjI)
show "snd bp' < m" by (rule bp'_m)
show "ae_blocks_ext m (write_bp blocks bp a')" by (rule bext')
show "fst (snd (write_bp blocks bp a')) = LE_block m le"
using new_blocks by simp
show "(tM(nM := a')) 0 = le" using tM_new tM_0 by simp
show "(case fst bp' of
AE_Home ⇒ go_move d nM = 0
| AE_Right ⇒ go_move d nM = Suc (snd bp')
| AE_Left ⇒ False)"
using bp'_eq bp_eq b_home MoveN nM_zero by simp
show "∀i. i < ?c ⟶
(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
proof (intro allI impI)
fix i
assume i_lt: "i < ?c"
have lhs: "(tM(nM := a')) (Suc i) = tM (Suc i)"
using tM_new by simp
also have "... = buf_lin_at m blocks (2 * ?c + i)"
using align i_lt by blast
also have "... = buf_lin_at m (l, LE_block m le, r) (2 * ?c + i)"
using h_eq blocks_eq
unfolding buf_lin_at_def by simp
also have "... = buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
using new_blocks by simp
finally show "(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)" .
qed
qed
next
case MoveR
from adv MoveR tM_nM_le b_home bp_eq
have bp'_eq: "bp' = (AE_Right, 0)"
unfolding bp_advance_le_def by simp
have nM'_eq: "go_move MoveR nM = 1" using nM_zero by simp
show ?thesis
unfolding ae_window_invariant_le0_def
proof (intro conjI)
show "snd bp' < m" by (rule bp'_m)
show "ae_blocks_ext m (write_bp blocks bp a')" by (rule bext')
show "fst (snd (write_bp blocks bp a')) = LE_block m le"
using new_blocks by simp
show "(tM(nM := a')) 0 = le" using tM_new tM_0 by simp
show "(case fst bp' of
AE_Home ⇒ go_move d nM = 0
| AE_Right ⇒ go_move d nM = Suc (snd bp')
| AE_Left ⇒ False)"
using bp'_eq MoveR nM'_eq by simp
show "∀i. i < ?c ⟶
(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
proof (intro allI impI)
fix i
assume i_lt: "i < ?c"
have "(tM(nM := a')) (Suc i) = tM (Suc i)" using tM_new by simp
also have "... = buf_lin_at m blocks (2 * ?c + i)"
using align i_lt by blast
also have "... = buf_lin_at m (l, LE_block m le, r) (2 * ?c + i)"
using h_eq blocks_eq unfolding buf_lin_at_def by simp
also have "... = buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
using new_blocks by simp
finally show "(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)" .
qed
qed
next
case MoveL
with d_in show ?thesis by simp
qed
next
case AE_Right
have b_right: "b = AE_Right" using AE_Right .
from struct_pre bp_eq AE_Right
have nM_form: "nM = Suc off" by simp
have idx_lt: "off < ?c" using bp_m bp_eq by simp
have nM_bd: "0 < nM ∧ nM ≤ ?c" using nM_form idx_lt by simp
have adv_plain: "bp_advance m bp d = Some bp'"
proof -
have "¬ (tM nM = le ∧ fst bp = AE_Home ∧ d = MoveR)"
using bp_eq b_right by simp
hence "bp_advance_le m le (tM nM) bp d = bp_advance m bp d"
unfolding bp_advance_le_def by auto
with adv show ?thesis by simp
qed
have wb_eq: "write_bp blocks bp a' = (l, h, r(off := a'))"
using bp_eq b_right blocks_eq unfolding write_bp_def by simp
have new_h: "fst (snd (write_bp blocks bp a')) = LE_block m le"
using wb_eq h_eq by simp
have tM_0_new: "(tM(nM := a')) 0 = le"
using nM_bd tM_0 by simp
have bp_lin: "bp_linear m bp = 2 * ?c + off"
using bp_eq b_right by simp
show ?thesis
proof (cases d)
case MoveN
from adv_plain MoveN have "Some bp' = Some bp"
using bp_advance_N_some[of _ bp] by simp
hence bp'_eq: "bp' = bp" by simp
show ?thesis
unfolding ae_window_invariant_le0_def
proof (intro conjI)
show "snd bp' < m" by (rule bp'_m)
show "ae_blocks_ext m (write_bp blocks bp a')" by (rule bext')
show "fst (snd (write_bp blocks bp a')) = LE_block m le"
by (rule new_h)
show "(tM(nM := a')) 0 = le" by (rule tM_0_new)
show "(case fst bp' of
AE_Home ⇒ go_move d nM = 0
| AE_Right ⇒ go_move d nM = Suc (snd bp')
| AE_Left ⇒ False)"
using bp'_eq bp_eq b_right MoveN nM_form by simp
show "∀i. i < ?c ⟶
(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
proof (intro allI impI)
fix i
assume i_lt: "i < ?c"
show "(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
proof (cases "i = off")
case True
have "Suc i = nM" using True nM_form by simp
hence lhs: "(tM(nM := a')) (Suc i) = a'" by simp
have idx_eq: "2 * ?c + i = bp_linear m bp"
using True bp_lin by simp
have rhs: "buf_lin_at m (write_bp blocks bp a') (2 * ?c + i) = a'"
using idx_eq buf_lin_at_write_bp_match[OF bp_m, where blocks=blocks and x=a'] by simp
show ?thesis using lhs rhs by simp
next
case False
have idx_neq: "2 * ?c + i ≠ bp_linear m bp"
using False bp_lin by simp
have idx_2c_lt: "2 * ?c + i < 3 * ?c" using i_lt by simp
have Suc_i_neq: "Suc i ≠ nM"
using False nM_form by simp
have "(tM(nM := a')) (Suc i) = tM (Suc i)"
using Suc_i_neq by simp
also have "... = buf_lin_at m blocks (2 * ?c + i)"
using align i_lt by blast
also have "... = buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
by (rule buf_lin_at_write_bp_other
[OF idx_neq idx_2c_lt, symmetric])
finally show ?thesis .
qed
qed
qed
next
case MoveR
from adv_plain MoveR have adv_R: "bp_advance m bp MoveR = Some bp'" by simp
obtain ofs' where c_succ_off: "c_succ m off = Some ofs'"
proof (cases "c_succ m off")
case None
have "bp_advance m bp MoveR = None"
using bp_eq b_right None unfolding bp_advance_def by simp
with adv_R show thesis by simp
next
case (Some ofs')
thus thesis using that by simp
qed
have bp'_eq: "bp' = (AE_Right, ofs')"
using bp_eq b_right c_succ_off adv_R
unfolding bp_advance_def by simp
have idx_succ: "ofs' = Suc off"
by (rule c_succ_Some[OF c_succ_off])
have nM_succ: "go_move MoveR nM = Suc ofs'"
using nM_form idx_succ by simp
show ?thesis
unfolding ae_window_invariant_le0_def
proof (intro conjI)
show "snd bp' < m" by (rule bp'_m)
show "ae_blocks_ext m (write_bp blocks bp a')" by (rule bext')
show "fst (snd (write_bp blocks bp a')) = LE_block m le"
by (rule new_h)
show "(tM(nM := a')) 0 = le" by (rule tM_0_new)
show "(case fst bp' of
AE_Home ⇒ go_move d nM = 0
| AE_Right ⇒ go_move d nM = Suc (snd bp')
| AE_Left ⇒ False)"
using bp'_eq MoveR nM_succ by simp
show "∀i. i < ?c ⟶
(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
proof (intro allI impI)
fix i
assume i_lt: "i < ?c"
show "(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
proof (cases "i = off")
case True
have "Suc i = nM" using True nM_form by simp
hence lhs: "(tM(nM := a')) (Suc i) = a'" by simp
have idx_eq: "2 * ?c + i = bp_linear m bp"
using True bp_lin by simp
have rhs: "buf_lin_at m (write_bp blocks bp a') (2 * ?c + i) = a'"
using idx_eq buf_lin_at_write_bp_match[OF bp_m, where blocks=blocks and x=a'] by simp
show ?thesis using lhs rhs by simp
next
case False
have idx_neq: "2 * ?c + i ≠ bp_linear m bp"
using False bp_lin by simp
have idx_2c_lt: "2 * ?c + i < 3 * ?c" using i_lt by simp
have Suc_i_neq: "Suc i ≠ nM"
using False nM_form by simp
have "(tM(nM := a')) (Suc i) = tM (Suc i)"
using Suc_i_neq by simp
also have "... = buf_lin_at m blocks (2 * ?c + i)"
using align i_lt by blast
also have "... = buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
by (rule buf_lin_at_write_bp_other
[OF idx_neq idx_2c_lt, symmetric])
finally show ?thesis .
qed
qed
qed
next
case MoveL
from adv_plain MoveL have adv_L: "bp_advance m bp MoveL = Some bp'" by simp
show ?thesis
proof (cases "c_pred off")
case (Some ofs')
have bp'_eq: "bp' = (AE_Right, ofs')"
using bp_eq b_right Some adv_L
unfolding bp_advance_def by simp
have idx_pred: "Suc ofs' = off"
by (rule c_pred_Some[OF Some])
obtain p where nM_eq: "nM = Suc p"
using nM_bd by (cases nM) auto
have m_eq: "p = off" using nM_form nM_eq by simp
have nM'_eq: "go_move MoveL nM = Suc ofs'"
using nM_eq m_eq idx_pred by simp
show ?thesis
unfolding ae_window_invariant_le0_def
proof (intro conjI)
show "snd bp' < m" by (rule bp'_m)
show "ae_blocks_ext m (write_bp blocks bp a')" by (rule bext')
show "fst (snd (write_bp blocks bp a')) = LE_block m le"
by (rule new_h)
show "(tM(nM := a')) 0 = le" by (rule tM_0_new)
show "(case fst bp' of
AE_Home ⇒ go_move d nM = 0
| AE_Right ⇒ go_move d nM = Suc (snd bp')
| AE_Left ⇒ False)"
using bp'_eq MoveL nM'_eq by simp
show "∀i. i < ?c ⟶
(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
proof (intro allI impI)
fix i
assume i_lt: "i < ?c"
show "(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
proof (cases "i = off")
case True
have "Suc i = nM" using True nM_form by simp
hence lhs: "(tM(nM := a')) (Suc i) = a'" by simp
have idx_eq: "2 * ?c + i = bp_linear m bp"
using True bp_lin by simp
have rhs: "buf_lin_at m (write_bp blocks bp a') (2 * ?c + i) = a'"
using idx_eq buf_lin_at_write_bp_match[OF bp_m, where blocks=blocks and x=a'] by simp
show ?thesis using lhs rhs by simp
next
case False
have idx_neq: "2 * ?c + i ≠ bp_linear m bp"
using False bp_lin by simp
have idx_2c_lt: "2 * ?c + i < 3 * ?c" using i_lt by simp
have Suc_i_neq: "Suc i ≠ nM"
using False nM_form by simp
have "(tM(nM := a')) (Suc i) = tM (Suc i)"
using Suc_i_neq by simp
also have "... = buf_lin_at m blocks (2 * ?c + i)"
using align i_lt by blast
also have "... = buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
by (rule buf_lin_at_write_bp_other
[OF idx_neq idx_2c_lt, symmetric])
finally show ?thesis .
qed
qed
qed
next
case None
have idx_zero: "off = 0"
using c_pred_None[OF None] by simp
have bp'_eq: "bp' = (AE_Home, c_last m)"
using bp_eq b_right None adv_L
unfolding bp_advance_def by simp
have nM_one: "nM = 1" using nM_form idx_zero by simp
have nM'_eq: "go_move MoveL nM = 0" using nM_one by simp
show ?thesis
unfolding ae_window_invariant_le0_def
proof (intro conjI)
show "snd bp' < m" by (rule bp'_m)
show "ae_blocks_ext m (write_bp blocks bp a')" by (rule bext')
show "fst (snd (write_bp blocks bp a')) = LE_block m le"
by (rule new_h)
show "(tM(nM := a')) 0 = le" by (rule tM_0_new)
show "(case fst bp' of
AE_Home ⇒ go_move d nM = 0
| AE_Right ⇒ go_move d nM = Suc (snd bp')
| AE_Left ⇒ False)"
using bp'_eq MoveL nM'_eq by simp
show "∀i. i < ?c ⟶
(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
proof (intro allI impI)
fix i
assume i_lt: "i < ?c"
show "(tM(nM := a')) (Suc i)
= buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
proof (cases "i = off")
case True
have "Suc i = nM" using True nM_form by simp
hence lhs: "(tM(nM := a')) (Suc i) = a'" by simp
have idx_eq: "2 * ?c + i = bp_linear m bp"
using True bp_lin by simp
have rhs: "buf_lin_at m (write_bp blocks bp a') (2 * ?c + i) = a'"
using idx_eq buf_lin_at_write_bp_match[OF bp_m, where blocks=blocks and x=a'] by simp
show ?thesis using lhs rhs by simp
next
case False
have idx_neq: "2 * ?c + i ≠ bp_linear m bp"
using False bp_lin by simp
have idx_2c_lt: "2 * ?c + i < 3 * ?c" using i_lt by simp
have Suc_i_neq: "Suc i ≠ nM"
using False nM_form by simp
have "(tM(nM := a')) (Suc i) = tM (Suc i)"
using Suc_i_neq by simp
also have "... = buf_lin_at m blocks (2 * ?c + i)"
using align i_lt by blast
also have "... = buf_lin_at m (write_bp blocks bp a') (2 * ?c + i)"
by (rule buf_lin_at_write_bp_other
[OF idx_neq idx_2c_lt, symmetric])
finally show ?thesis .
qed
qed
qed
qed
qed
qed
qed
end