Theory AlphabetEnlargement_BufferArith
theory AlphabetEnlargement_BufferArith
imports AlphabetEnlargement_Uniqueness
begin
text ‹Arithmetic lemmas on the 3-block buffer abstraction
used by the ‹alphabet_enlarge› simulation chain.
Definitions of ‹bp_advance›, ‹bp_linear›,
‹buf_lin_at›, ‹write_bp›, ‹read_bp›,
and the ‹ae_window_invariant› family live in
‹AlphabetEnlargement_Substeps›; this theory collects the
lemmas that relate them and forms a self-contained arithmetic
layer between the encoder/decoder and the forward simulation
proof.
Contents, in dependency order:
▪ Offset and ‹bp_linear› base arithmetic:
‹c_succ› / ‹c_pred› on offsets, ‹bp_linear›
at the three block-anchor patterns, and the universal
‹< 3c› bound.
▪ ‹bp_advance›'s commutation with
‹bp_linear›: each successful R-move increments
‹bp_linear›, each successful L-move
decrements it; failure cases correspond to buffer-edge
positions. Head-stays-in-buffer totality lemmas for
strict-interior R / L moves. LE-aware totality and
single-step linear-bound preservation for
‹bp_advance_le›.
▪ Read-from-window lemmas: bridge between buffer-read
at a buffered head position and the linearised buffer access
(steady / LE-edge / per-tape unified regimes).
▪ ‹buf_lin_at› effect of ‹write_bp›
at the matched buffered head's linear index and at all other
indices.
▪ Window-invariant single-step preservation under one
buffered ‹M›-step: steady regime,
‹le1› regime, ‹le0› regime, and the
per-tape unified companion dispatching on the regime
selector ‹pos›.
These lemmas are the standalone arithmetic underpinning piece
4 of the AE simulation correctness proof
(‹ae_m_steps_buffered_correct›): the buffered
compute's head displacement matches the actual head
displacement step-by-step, and the head stays in the buffer
for any prefix of ‹≤ c› moves starting from
the home block.›
subsection ‹Buffered head position arithmetic›
text ‹Lemmas relating ‹bp_linear› (linearised buffer index in
‹[0, 3c)›) to ‹bp_advance›'s case structure and to the
‹c_succ› / ‹c_pred› partial-step operations on offsets.
These are the standalone arithmetic underpinning piece 4
(‹ae_m_steps_buffered_correct›): the buffered compute's
head displacement matches the actual head displacement
step-by-step, and the head stays in the buffer for any
prefix of ‹≤ c› moves starting from the home block.›
subsubsection ‹Offset and ‹bp_linear› arithmetic›
text ‹‹c_succ› and ‹c_pred› step an offset by one, or
report that it would leave the block.›
lemma c_succ_Some:
fixes x y :: "nat"
assumes "c_succ m x = Some y"
shows "y = Suc x"
using assms by (auto simp: c_succ_def split: if_split_asm)
lemma c_succ_None:
fixes x :: "nat"
assumes "c_succ m x = None" and "x < m"
shows "Suc x = m"
using assms by (auto simp: c_succ_def split: if_split_asm)
lemma c_pred_Some:
fixes x y :: "nat"
assumes "c_pred x = Some y"
shows "Suc y = x"
using assms by (auto simp: c_pred_def split: if_split_asm)
lemma c_pred_None:
fixes x :: "nat"
assumes "c_pred x = None"
shows "x = 0"
using assms by (auto simp: c_pred_def split: if_split_asm)
text ‹‹bp_linear›'s value at the three home/left/right
block patterns, plus the universal ‹< 3c› bound.›
lemma bp_linear_AE_Left [simp]:
fixes off :: "nat"
shows "bp_linear m (AE_Left, off) = off"
by (simp add: bp_linear_def)
lemma bp_linear_AE_Home [simp]:
fixes off :: "nat"
shows "bp_linear m (AE_Home, off) = m + off"
by (simp add: bp_linear_def)
lemma bp_linear_AE_Right [simp]:
fixes off :: "nat"
shows "bp_linear m (AE_Right, off)
= 2 * m + off"
by (simp add: bp_linear_def)
lemma bp_linear_lt_3c:
fixes p :: "bp"
assumes "snd p < m"
shows "bp_linear m p < 3 * m"
proof -
have idx_lt: "snd p < m"
using assms .
show ?thesis using idx_lt
by (cases p; cases "fst p") auto
qed
subsubsection ‹‹bp_advance› commutation, totality, and bounds at the endmarker›
text ‹‹bp_advance›'s commutation with ‹bp_linear›: each
successful R-move increments ‹bp_linear› by 1, each
successful L-move decrements by 1, N is identity.›
lemma bp_advance_N_some:
"bp_advance m p MoveN = Some p"
unfolding bp_advance_def by (cases p) simp
lemma bp_advance_N_linear:
"bp_advance m p MoveN = Some p ∧ bp_linear m p = bp_linear m p"
using bp_advance_N_some by simp
lemma bp_advance_R_linear:
fixes p p' :: "bp"
assumes "bp_advance m p MoveR = Some p'"
and lt: "snd p < m"
shows "bp_linear m p' = Suc (bp_linear m p)"
proof (cases "c_succ m (snd p)")
case (Some off')
from Some assms have p'_eq: "p' = (fst p, off')"
unfolding bp_advance_def by (cases p) simp
have idx_eq: "off' = Suc (snd p)"
using c_succ_Some[OF Some] .
show ?thesis using p'_eq idx_eq
by (cases p; cases "fst p") auto
next
case None
from None have idx_at_last: "Suc (snd p) = m"
using c_succ_None[OF _ lt] by blast
show ?thesis
proof (cases "fst p")
case AE_Left
with None assms have p'_eq: "p' = (AE_Home, 0)"
unfolding bp_advance_def by (cases p) simp
show ?thesis using p'_eq AE_Left idx_at_last
by (cases p) auto
next
case AE_Home
with None assms have p'_eq: "p' = (AE_Right, 0)"
unfolding bp_advance_def by (cases p) simp
show ?thesis using p'_eq AE_Home idx_at_last
by (cases p) auto
next
case AE_Right
with None assms show ?thesis
unfolding bp_advance_def by (cases p) simp
qed
qed
lemma bp_advance_L_linear:
fixes p p' :: "bp"
assumes "bp_advance m p MoveL = Some p'"
and lt: "snd p < m"
shows "Suc (bp_linear m p') = bp_linear m p"
proof (cases "c_pred (snd p)")
case (Some off')
from Some assms have p'_eq: "p' = (fst p, off')"
unfolding bp_advance_def by (cases p) simp
have idx_eq: "Suc off' = snd p"
using c_pred_Some[OF Some] .
show ?thesis using p'_eq idx_eq
by (cases p; cases "fst p") auto
next
case None
from None have idx_zero: "snd p = 0"
using c_pred_None by blast
have c_pos: "0 < m"
using lt by linarith
show ?thesis
proof (cases "fst p")
case AE_Left
with None assms show ?thesis
unfolding bp_advance_def by (cases p) simp
next
case AE_Home
with None assms have p'_eq: "p' = (AE_Left, c_last m)"
unfolding bp_advance_def by (cases p) simp
have lin_p': "bp_linear m p' = m - 1"
using p'_eq c_last_def by simp
have lin_p: "bp_linear m p = m"
using AE_Home idx_zero by (cases p) auto
show ?thesis using lin_p' lin_p c_pos by linarith
next
case AE_Right
with None assms have p'_eq: "p' = (AE_Home, c_last m)"
unfolding bp_advance_def by (cases p) simp
have lin_p': "bp_linear m p' = m + (m - 1)"
using p'_eq c_last_def by simp
have lin_p: "bp_linear m p = 2 * m"
using AE_Right idx_zero by (cases p) auto
show ?thesis using lin_p' lin_p c_pos by linarith
qed
qed
text ‹Head-stays-in-buffer: any ‹R›-move from a strict-interior
position succeeds; any ‹L›-move from a strict-interior
position succeeds. These are the standalone arithmetic
underpinning the inductive proof of
‹ae_m_steps_buffered_correct›'s step case.›
lemma bp_advance_R_some:
fixes p :: "bp"
assumes "bp_linear m p < 3 * m - 1"
and lt: "snd p < m"
shows "∃p'. bp_advance m p MoveR = Some p'"
proof (cases "c_succ m (snd p)")
case (Some off')
thus ?thesis unfolding bp_advance_def by (cases p) simp
next
case None
hence idx_at_last: "Suc (snd p) = m"
using c_succ_None[OF _ lt] by blast
show ?thesis
proof (cases "fst p")
case AE_Left
with None show ?thesis
unfolding bp_advance_def by (cases p) simp
next
case AE_Home
with None show ?thesis
unfolding bp_advance_def by (cases p) simp
next
case AE_Right
have lin_eq: "bp_linear m p = 3 * m - 1"
using AE_Right idx_at_last
by (cases p) auto
with assms show ?thesis by linarith
qed
qed
lemma bp_advance_L_some:
fixes p :: "bp"
assumes "0 < bp_linear m p"
shows "∃p'. bp_advance m p MoveL = Some p'"
proof (cases "c_pred (snd p)")
case (Some off')
thus ?thesis unfolding bp_advance_def by (cases p) simp
next
case None
hence idx_zero: "snd p = 0"
using c_pred_None by blast
show ?thesis
proof (cases "fst p")
case AE_Left
have lin_eq: "bp_linear m p = 0"
using AE_Left idx_zero by (cases p) auto
with assms show ?thesis by linarith
next
case AE_Home
with None show ?thesis
unfolding bp_advance_def by (cases p) simp
next
case AE_Right
with None show ?thesis
unfolding bp_advance_def by (cases p) simp
qed
qed
text ‹LE-aware totality of ‹bp_advance_le›: given the same
position bounds that make ‹bp_advance› total
(‹bp_linear < 3c - 1› excludes the only None case for R,
‹0 < bp_linear› excludes the only None case for L), the
LE-aware wrapper is also total — the only "extra" behaviour
is the LE-jump, which always returns
‹Some (AE_Right, 0)›.
The two position bounds correspond to "head not at the
rightmost cell of the right block" and "head not at the
leftmost cell of the left block". In
‹ae_coupled_run_aux_general›'s inductive step these
bounds hold strictly at the precondition step ‹n'›
thanks to the fifth output conjunct (‹bp_linear bound›)
and the budget ‹n' ≤ c - 1›.›
lemma bp_advance_le_total:
fixes le a :: 'a
and p :: "bp"
and d :: move
assumes bp_lt_max: "bp_linear m p < 3 * m - 1"
and bp_gt_zero: "0 < bp_linear m p"
and lt: "snd p < m"
shows "∃p'. bp_advance_le m le a p d = Some p'"
proof (cases "a = le ∧ fst p = AE_Home ∧ d = MoveR")
case True
hence "bp_advance_le m le a p d = Some (AE_Right, 0)"
unfolding bp_advance_le_def by simp
thus ?thesis by auto
next
case False
hence skip: "bp_advance_le m le a p d = bp_advance m p d"
unfolding bp_advance_le_def by auto
show ?thesis
proof (cases d)
case MoveN
have "bp_advance_le m le a p d = Some p"
using skip MoveN bp_advance_N_some[of _ p] by simp
thus ?thesis by blast
next
case MoveR
thus ?thesis using skip bp_advance_R_some[OF bp_lt_max lt] by auto
next
case MoveL
thus ?thesis using skip bp_advance_L_some[OF bp_gt_zero] by auto
qed
qed
text ‹Single-step ‹bp_linear› preservation for
‹bp_advance_le›: the ‹c ≤ bp_linear + n›
/\ ‹bp_linear < 2c + n› invariant is preserved when
‹n› increases by one. Four cases by
‹bp_advance_le›'s outcome:
- LE-jump fires: ‹bp_linear p' = 2c›, both bounds hold
trivially.
- ‹bp_advance› N: ‹bp_linear p' = bp_linear p›;
bounds widen.
- ‹bp_advance› R: ‹bp_linear p' = Suc (bp_linear p)›
(‹bp_advance_R_linear›); upper bound +1, lower +0.
- ‹bp_advance› L: ‹Suc (bp_linear p') = bp_linear p›
(‹bp_advance_L_linear›); upper -1, lower +1 (needs
‹0 < bp_linear p› to avoid nat truncation).
Used in ‹ae_coupled_run_aux_general›'s inductive step
to discharge the fifth output conjunct at ‹cM_n›.›
lemma bp_advance_le_lin_bounded:
fixes le a :: 'a
and p p' :: "bp"
and d :: move and n :: nat
assumes adv: "bp_advance_le m le a p d = Some p'"
and p_pos: "0 < bp_linear m p"
and p_upper: "bp_linear m p < 2 * m + n"
and p_lower: "m ≤ bp_linear m p + n"
and lt: "snd p < m"
shows "m ≤ bp_linear m p' + Suc n
∧ bp_linear m p' < 2 * m + Suc n"
proof (cases "a = le ∧ fst p = AE_Home ∧ d = MoveR")
case True
hence p'_eq: "p' = (AE_Right, 0)"
using adv unfolding bp_advance_le_def by simp
hence lin_p': "bp_linear m p' = 2 * m"
by simp
show ?thesis using lin_p' by simp
next
case False
hence skip: "bp_advance_le m le a p d = bp_advance m p d"
unfolding bp_advance_le_def by auto
with adv have adv_bp: "bp_advance m p d = Some p'" by simp
show ?thesis
proof (cases d)
case MoveN
have "bp_advance m p MoveN = Some p" by (rule bp_advance_N_some)
with adv_bp MoveN have "p' = p" by simp
hence "bp_linear m p' = bp_linear m p" by simp
thus ?thesis using p_upper p_lower by linarith
next
case MoveR
with adv_bp have "bp_linear m p' = Suc (bp_linear m p)"
using bp_advance_R_linear[OF _ lt] by blast
thus ?thesis using p_upper p_lower by linarith
next
case MoveL
with adv_bp have "Suc (bp_linear m p') = bp_linear m p"
using bp_advance_L_linear[OF _ lt] by blast
thus ?thesis using p_upper p_lower p_pos by linarith
qed
qed
subsubsection ‹Read-from-window lemmas›
text ‹Bridge between buffer-read at a buffered head position
and the linearised buffer access. Together with the window
invariant this gives ‹read_bp blocks bp = tM nM›, the key
step that lets a buffered ‹δ›-tuple be matched against an
M-step's actual symbol read.›
lemma buf_lin_at_eq_read_bp:
fixes blocks :: "(nat ⇒ 'a)
× (nat ⇒ 'a) × (nat ⇒ 'a)"
and bp :: "bp"
assumes lt: "snd bp < m"
shows "buf_lin_at m blocks (bp_linear m bp) = read_bp blocks bp"
proof -
obtain l h r where blocks_eq: "blocks = (l, h, r)"
by (cases blocks) auto
obtain b off where bp_eq: "bp = (b, off)" by (cases bp)
let ?c = "m"
let ?xs = "[0..<m] :: nat list"
have off_lt: "off < m" using lt bp_eq by simp
have nth_off: "?xs ! off = off" using off_lt by simp
show ?thesis
proof (cases b)
case AE_Left
have "bp_linear m bp = off"
using bp_eq AE_Left by simp
moreover have "off < ?c" using off_lt .
ultimately show ?thesis
using bp_eq blocks_eq AE_Left nth_off
unfolding buf_lin_at_def read_bp_def by simp
next
case AE_Home
have lin_eq: "bp_linear m bp = ?c + off"
using bp_eq AE_Home by simp
have not_lt_c: "¬ ?c + off < ?c" by simp
have lt_2c: "?c + off < 2 * ?c" using off_lt by simp
have sub_eq: "?c + off - ?c = off" by simp
show ?thesis
using bp_eq blocks_eq AE_Home lin_eq not_lt_c lt_2c sub_eq nth_off
unfolding buf_lin_at_def read_bp_def by simp
next
case AE_Right
have lin_eq: "bp_linear m bp = 2 * ?c + off"
using bp_eq AE_Right by simp
have not_lt_c: "¬ 2 * ?c + off < ?c" by simp
have not_lt_2c: "¬ 2 * ?c + off < 2 * ?c" by simp
have sub_eq: "2 * ?c + off - 2 * ?c = off" by simp
show ?thesis
using bp_eq blocks_eq AE_Right lin_eq not_lt_c not_lt_2c sub_eq nth_off
unfolding buf_lin_at_def read_bp_def by simp
qed
qed
lemma read_bp_via_window:
fixes tM :: "nat ⇒ 'a"
and bp :: "bp"
and blocks :: "(nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
assumes "ae_window_invariant m tM nM bp blocks p_start"
shows "read_bp blocks bp = tM nM"
proof -
let ?c = "m"
from assms have nM_eq: "nM = p_start + bp_linear m bp"
unfolding ae_window_invariant_def by blast
from assms have win:
"∀i. i < 3 * ?c ⟶ tM (p_start + i) = buf_lin_at m blocks i"
unfolding ae_window_invariant_def by blast
from assms have lt: "snd bp < m"
unfolding ae_window_invariant_def by blast
have lin_lt: "bp_linear m bp < 3 * ?c" using lt by (rule bp_linear_lt_3c)
have e1: "tM nM = buf_lin_at m blocks (bp_linear m bp)"
using win lin_lt nM_eq by simp
have e2: "buf_lin_at m blocks (bp_linear m bp) = read_bp blocks bp"
using lt by (rule buf_lin_at_eq_read_bp)
from e1 e2 show ?thesis by simp
qed
text ‹LE-edge analogue of ‹read_bp_via_window› for the
‹le1› regime: the buffered read at the head equals the
M-tape read at the M-side head position, under
‹ae_window_invariant_le1›. Three sub-cases on
‹fst bp›:
- ‹AE_Left› (head at ‹(AE_Left, c_last)›):
‹nM = 0›; M reads ‹le›; buffer reads
‹l c_last = LE_block le c_last = le›. Match.
- ‹AE_Home› (head in home block, offset ‹off›):
‹nM = Suc off›; routes through the right slot
of the buf-linearisation ‹tM (Suc i)
= buf_lin_at blocks (c + i)› at ‹i = off›.
- ‹AE_Right› (head in right block, offset ‹off›):
‹nM = Suc (c + off)›; same buf-linearisation at
‹i = c + off›.›
lemma read_bp_via_window_le1:
fixes tM :: "nat ⇒ 'a"
and bp :: "bp"
and blocks :: "(nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
assumes wi: "ae_window_invariant_le1 m tM nM bp blocks le"
shows "read_bp blocks bp = tM nM"
proof -
let ?c = "m"
obtain b off where bp_eq: "bp = (b, off)" by (cases bp)
obtain l h r where blocks_eq: "blocks = (l, h, r)"
by (cases blocks) auto
from wi have tM_0: "tM 0 = le"
unfolding ae_window_invariant_le1_def by blast
from wi have l_eq: "fst blocks = LE_block m le"
unfolding ae_window_invariant_le1_def by blast
from wi have win:
"∀i. i < 2 * ?c
⟶ tM (Suc i) = buf_lin_at m blocks (?c + i)"
unfolding ae_window_invariant_le1_def by blast
show ?thesis
proof (cases b)
case AE_Left
have off_c_last: "off = c_last m"
using wi bp_eq AE_Left
unfolding ae_window_invariant_le1_def by auto
have nM_eq: "nM = 0"
using wi bp_eq AE_Left
unfolding ae_window_invariant_le1_def by auto
have rd_l: "read_bp blocks bp = l (c_last m)"
using bp_eq AE_Left off_c_last blocks_eq
unfolding read_bp_def by simp
have last_lt: "c_last m < m"
using wi bp_eq off_c_last unfolding ae_window_invariant_le1_def by auto
have l_const: "l (c_last m) = le"
using l_eq blocks_eq last_lt unfolding LE_block_def by simp
show ?thesis using rd_l l_const nM_eq tM_0 by simp
next
case AE_Home
have nM_eq: "nM = Suc off"
using wi bp_eq AE_Home
unfolding ae_window_invariant_le1_def by auto
have idx_lt: "off < ?c"
using wi bp_eq
unfolding ae_window_invariant_le1_def ae_window_invariant_le0_def
by auto
have idx_lt_2c: "off < 2 * ?c" using idx_lt by simp
have tM_eq:
"tM (Suc off) = buf_lin_at m blocks (?c + off)"
using win idx_lt_2c by simp
have lin_eq: "bp_linear m bp = ?c + off"
using bp_eq AE_Home unfolding bp_linear_def by simp
have bp_m: "snd bp < m" using bp_eq idx_lt by simp
have rd_e: "buf_lin_at m blocks (bp_linear m bp) = read_bp blocks bp"
by (rule buf_lin_at_eq_read_bp[OF bp_m])
show ?thesis using nM_eq tM_eq lin_eq rd_e by simp
next
case AE_Right
have nM_eq: "nM = Suc (?c + off)"
using wi bp_eq AE_Right
unfolding ae_window_invariant_le1_def by auto
have idx_lt: "off < ?c"
using wi bp_eq
unfolding ae_window_invariant_le1_def ae_window_invariant_le0_def
by auto
have lt_2c: "?c + off < 2 * ?c" using idx_lt by simp
have tM_eq:
"tM (Suc (?c + off))
= buf_lin_at m blocks (?c + (?c + off))"
using win lt_2c by simp
have lin_eq: "bp_linear m bp = 2 * ?c + off"
using bp_eq AE_Right unfolding bp_linear_def by simp
have eq2: "?c + (?c + off) = 2 * ?c + off"
by simp
have bp_m: "snd bp < m" using bp_eq idx_lt by simp
have rd_e: "buf_lin_at m blocks (bp_linear m bp) = read_bp blocks bp"
by (rule buf_lin_at_eq_read_bp[OF bp_m])
show ?thesis using nM_eq tM_eq lin_eq rd_e eq2 by simp
qed
qed
text ‹LE-edge analogue of ‹read_bp_via_window› for the
‹le0› regime. Buffered head can be:
- ‹AE_Home›: ‹nM = 0›; M reads ‹le›;
buffer reads ‹h off = LE_block le off = le›
(home slot is the ‹LE_block›). Match.
- ‹AE_Right›: ‹nM = Suc off›; routes through
the right slot's buf-linearisation ‹tM (Suc i)
= buf_lin_at blocks (2c + i)› at ‹i = off›.
- ‹AE_Left› excluded by the window invariant.›
lemma read_bp_via_window_le0:
fixes tM :: "nat ⇒ 'a"
and bp :: "bp"
and blocks :: "(nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
assumes wi: "ae_window_invariant_le0 m tM nM bp blocks le"
shows "read_bp blocks bp = tM nM"
proof -
let ?c = "m"
obtain b off where bp_eq: "bp = (b, off)" by (cases bp)
obtain l h r where blocks_eq: "blocks = (l, h, r)"
by (cases blocks) auto
from wi have tM_0: "tM 0 = le"
unfolding ae_window_invariant_le0_def by blast
from wi have h_eq: "fst (snd blocks) = LE_block m le"
unfolding ae_window_invariant_le0_def by blast
from wi have win:
"∀i. i < ?c
⟶ tM (Suc i) = buf_lin_at m blocks (2 * ?c + i)"
unfolding ae_window_invariant_le0_def by blast
show ?thesis
proof (cases b)
case AE_Left
from wi bp_eq AE_Left have False
unfolding ae_window_invariant_le0_def by auto
thus ?thesis ..
next
case AE_Home
have nM_eq: "nM = 0"
using wi bp_eq AE_Home
unfolding ae_window_invariant_le0_def by auto
have rd_h: "read_bp blocks bp = h off"
using bp_eq AE_Home blocks_eq
unfolding read_bp_def by simp
have off_lt: "off < m"
using wi bp_eq unfolding ae_window_invariant_le0_def by auto
have h_const: "h off = le"
using h_eq blocks_eq off_lt unfolding LE_block_def by simp
show ?thesis using rd_h h_const nM_eq tM_0 by simp
next
case AE_Right
have nM_eq: "nM = Suc off"
using wi bp_eq AE_Right
unfolding ae_window_invariant_le0_def by auto
have idx_lt: "off < ?c"
using wi bp_eq
unfolding ae_window_invariant_le1_def ae_window_invariant_le0_def
by auto
have tM_eq:
"tM (Suc off)
= buf_lin_at m blocks (2 * ?c + off)"
using win idx_lt by simp
have lin_eq: "bp_linear m bp = 2 * ?c + off"
using bp_eq AE_Right unfolding bp_linear_def by simp
have bp_m: "snd bp < m" using bp_eq idx_lt by simp
have rd_e: "buf_lin_at m blocks (bp_linear m bp) = read_bp blocks bp"
by (rule buf_lin_at_eq_read_bp[OF bp_m])
show ?thesis using nM_eq tM_eq lin_eq rd_e by simp
qed
qed
text ‹Per-tape unified read-from-window companion: dispatches on
the regime selector ‹pos› into the three sibling
read-match lemmas (‹read_bp_via_window_le0›,
‹read_bp_via_window_le1›, ‹read_bp_via_window›).
This is the load-bearing read-match lemma at the inductive step
of ‹ae_coupled_run_aux_general›: ‹read_bp› at
the buffered head equals ‹M›-side read.›
lemma read_bp_via_window_general:
fixes tM :: "nat ⇒ 'a"
and bp :: "bp"
and blocks :: "(nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a)"
assumes wi: "ae_window_invariant_general m tM nM bp blocks pos le"
shows "read_bp blocks bp = tM nM"
proof -
let ?c = "m"
consider (steady) "pos ≥ 2" | (le1) "pos = 1" | (le0) "pos = 0"
by linarith
then show ?thesis
proof cases
case steady
have wi_st: "ae_window_invariant m tM nM bp blocks
((pos - 2) * ?c + 1)"
using wi steady
unfolding ae_window_invariant_general_def by simp
show ?thesis by (rule read_bp_via_window[OF wi_st])
next
case le1
have wi_l1: "ae_window_invariant_le1 m tM nM bp blocks le"
using wi le1
unfolding ae_window_invariant_general_def by simp
show ?thesis by (rule read_bp_via_window_le1[OF wi_l1])
next
case le0
have wi_l0: "ae_window_invariant_le0 m tM nM bp blocks le"
using wi le0
unfolding ae_window_invariant_general_def by simp
show ?thesis by (rule read_bp_via_window_le0[OF wi_l0])
qed
qed
subsubsection ‹‹buf_lin_at› preservation under ‹write_bp››
text ‹Effect of ‹write_bp› on ‹buf_lin_at›: at the
buffered head's linearised position, the linearised access
reads back the freshly written symbol; at any other
in-window position, the linearised access is unchanged.
Used in the window-invariant preservation step of the
Suc case of ‹ae_coupled_run_aux›.›
lemma buf_lin_at_write_bp_match:
fixes blocks :: "(nat ⇒ 'a)
× (nat ⇒ 'a) × (nat ⇒ 'a)"
and bp :: "bp"
and x :: 'a
assumes lt: "snd bp < m"
shows "buf_lin_at m (write_bp blocks bp x) (bp_linear m bp) = x"
proof -
obtain l h r where blocks_eq: "blocks = (l, h, r)"
by (cases blocks) auto
obtain b off where bp_eq: "bp = (b, off)" by (cases bp)
let ?c = "m"
let ?xs = "[0..<m] :: nat list"
have off_lt: "off < m" using lt bp_eq by simp
have nth_off: "?xs ! off = off" using off_lt by simp
show ?thesis
proof (cases b)
case AE_Left
have lin_eq: "bp_linear m bp = off"
using bp_eq AE_Left by simp
have wb: "write_bp blocks bp x = (l(off := x), h, r)"
using bp_eq blocks_eq AE_Left unfolding write_bp_def by simp
show ?thesis
using lin_eq off_lt wb nth_off
unfolding buf_lin_at_def by simp
next
case AE_Home
have lin_eq: "bp_linear m bp = ?c + off"
using bp_eq AE_Home by simp
have not_lt_c: "¬ ?c + off < ?c" by simp
have lt_2c: "?c + off < 2 * ?c" using off_lt by simp
have sub_eq: "?c + off - ?c = off" by simp
have wb: "write_bp blocks bp x = (l, h(off := x), r)"
using bp_eq blocks_eq AE_Home unfolding write_bp_def by simp
show ?thesis
using lin_eq not_lt_c lt_2c sub_eq wb nth_off
unfolding buf_lin_at_def by simp
next
case AE_Right
have lin_eq: "bp_linear m bp = 2 * ?c + off"
using bp_eq AE_Right by simp
have not_lt_c: "¬ 2 * ?c + off < ?c" by simp
have not_lt_2c: "¬ 2 * ?c + off < 2 * ?c" by simp
have sub_eq: "2 * ?c + off - 2 * ?c = off" by simp
have wb: "write_bp blocks bp x = (l, h, r(off := x))"
using bp_eq blocks_eq AE_Right unfolding write_bp_def by simp
show ?thesis
using lin_eq not_lt_c not_lt_2c sub_eq wb nth_off
unfolding buf_lin_at_def by simp
qed
qed
lemma buf_lin_at_write_bp_other:
fixes blocks :: "(nat ⇒ 'a)
× (nat ⇒ 'a) × (nat ⇒ 'a)"
and bp :: "bp"
and x :: 'a
and i :: nat
assumes neq: "i ≠ bp_linear m bp"
and i_lt: "i < 3 * m"
shows "buf_lin_at m (write_bp blocks bp x) i = buf_lin_at m blocks i"
proof -
obtain l h r where blocks_eq: "blocks = (l, h, r)"
by (cases blocks) auto
obtain b off where bp_eq: "bp = (b, off)" by (cases bp)
let ?c = "m"
let ?xs = "[0..<m] :: nat list"
have len_eq: "length ?xs = ?c" by simp
have nth_upt_eq:
"⋀j. j < ?c ⟹ ((?xs :: nat list) ! j) = j"
proof -
fix j assume "j < ?c"
with len_eq have "j < length ?xs" by simp
thus "((?xs :: nat list) ! j) = j" by simp
qed
show ?thesis
proof (cases b)
case AE_Left
have lin_eq: "bp_linear m bp = off"
using bp_eq AE_Left by simp
have wb: "write_bp blocks bp x = (l(off := x), h, r)"
using bp_eq blocks_eq AE_Left unfolding write_bp_def by simp
show ?thesis
proof (cases "i < ?c")
case True
have idx_neq: "?xs ! i ≠ off"
proof
assume eq: "?xs ! i = off"
have "(?xs ! i) = i" using nth_upt_eq True by simp
with eq have "off = i" by simp
with neq lin_eq show False by simp
qed
show ?thesis using True wb idx_neq blocks_eq
unfolding buf_lin_at_def by simp
next
case False
show ?thesis using False wb blocks_eq
unfolding buf_lin_at_def by simp
qed
next
case AE_Home
have lin_eq: "bp_linear m bp = ?c + off"
using bp_eq AE_Home by simp
have wb: "write_bp blocks bp x = (l, h(off := x), r)"
using bp_eq blocks_eq AE_Home unfolding write_bp_def by simp
show ?thesis
proof (cases "i < ?c")
case True
show ?thesis using True wb blocks_eq
unfolding buf_lin_at_def by simp
next
case False
hence ge_c: "i ≥ ?c" by simp
show ?thesis
proof (cases "i < 2 * ?c")
case True
have sub_lt: "i - ?c < ?c" using True ge_c by simp
have idx_neq: "?xs ! (i - ?c) ≠ off"
proof
assume eq: "?xs ! (i - ?c) = off"
have "(?xs ! (i - ?c)) = i - ?c"
using nth_upt_eq sub_lt by simp
with eq have "off = i - ?c" by simp
with neq lin_eq ge_c show False by simp
qed
show ?thesis using True ge_c wb idx_neq blocks_eq
unfolding buf_lin_at_def by simp
next
case False
show ?thesis using False ge_c wb blocks_eq
unfolding buf_lin_at_def by simp
qed
qed
next
case AE_Right
have lin_eq: "bp_linear m bp = 2 * ?c + off"
using bp_eq AE_Right by simp
have wb: "write_bp blocks bp x = (l, h, r(off := x))"
using bp_eq blocks_eq AE_Right unfolding write_bp_def by simp
show ?thesis
proof (cases "i < 2 * ?c")
case True
show ?thesis using True wb blocks_eq
unfolding buf_lin_at_def Let_def by simp
next
case False
hence ge_2c: "i ≥ 2 * ?c" by simp
have sub_lt: "i - 2 * ?c < ?c" using ge_2c i_lt by simp
have idx_neq: "?xs ! (i - 2 * ?c) ≠ off"
proof
assume eq: "?xs ! (i - 2 * ?c) = off"
have "(?xs ! (i - 2 * ?c)) = i - 2 * ?c"
using nth_upt_eq sub_lt by simp
with eq have "off = i - 2 * ?c" by simp
with neq lin_eq ge_2c show False by simp
qed
show ?thesis using False ge_2c wb idx_neq blocks_eq
unfolding buf_lin_at_def Let_def by simp
qed
qed
qed
end