Theory AlphabetReduction_ForwardRead
theory AlphabetReduction_ForwardRead
imports AlphabetReduction_ForwardSubsteps
begin
subsection ‹Read phase›
text ‹The accumulator fold stays inside ‹Γ ∪ {bl}›:
on a non-empty bit list the outermost ‹ar_acc› is a
‹gamma_unenum› image (always in range by ‹gamma_unenum_mem›);
on the empty list it is the seed. This is the read-loop's
‹ar_valid_stage› obligation discharged once for the running
‹buf› value, independent of how many bits have been folded so
far.
Throughout, ‹b› abbreviates ‹block_width Γ› (the per-symbol cell width).›
lemma foldl_ar_acc_mem:
assumes "finite Γ" and "a ∈ Γ ∪ {bl}"
shows "foldl (ar_acc Γ bl) a xs ∈ Γ ∪ {bl}"
proof (induct xs rule: rev_induct)
case Nil
show ?case using assms(2) by simp
next
case (snoc x ys)
have "foldl (ar_acc Γ bl) a (ys @ [x])
= ar_acc Γ bl (foldl (ar_acc Γ bl) a ys) x" by simp
also have "… ∈ Γ ∪ {bl}"
unfolding ar_acc_def by (rule gamma_unenum_mem[OF assms(1)])
finally show ?case .
qed
text ‹The inner read loop, single tape, proper cell: starting at
bit-counter ‹2› with the partial decode ‹buf0› and the
head at ‹base› (the first bit cell, ‹sim_pos p›), the
‹ar_read_bit_step› arm fires ‹b - 1› times, walking
‹R› across the first ‹b - 1› bit cells and folding each
into ‹buf tk› via ‹ar_acc›. After the loop the counter
is ‹Suc b› (ready for the boundary substep that reads the
‹b›-th, last bit), the head is at ‹base + (b - 1)›, the
tape is untouched, and every other tape's head is where it was.
Instantiates ‹relpow_invariant_chain›
with the loop-index-parameterised invariant whose ‹buf tk›
field is the ‹foldl (ar_acc) buf0_tk› of the cells read so
far — the same ‹foldl› the read-decode arithmetic
(‹foldl_ar_acc_encode_symbol›) is stated against, so the
per-step buf update is one ‹foldl_append› rewrite.›
lemma ar_read_bit_loop:
fixes M :: "('q, 'a) ktm"
and c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes vM: "valid_ktm M"
and qQ: "q ∈ Q_ktm M"
and kge2: "2 ≤ block_width (Γ_ktm M)"
and posk_proper: "posk tk ∈ {AR_AtFirstProper, AR_AtFurtherProper}"
and stg: "ktc_state c' = (q, AR_SimRead, tk, 2, buf0, dvec, posk)"
and buf0_valid: "∀k. buf0 k ∈ Γ_ktm M ∪ {bl_ktm M}"
and pos_base: "ktc_pos c' tk = base"
and pad0: "∀j ≥ k_ktm M. ktc_tape c' j (ktc_pos c' j) = BLANK4"
and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, tk, 2, buf0, dvec, posk)"
shows "∃c''. (c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (block_width (Γ_ktm M) - 1)
∧ ktc_state c'' = (q, AR_SimRead, tk, Suc (block_width (Γ_ktm M)),
buf0(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) (buf0 tk)
(map (λm. ktc_tape c' tk (base + m))
[0..<block_width (Γ_ktm M) - 1])),
dvec, posk)
∧ ktc_pos c'' tk = base + (block_width (Γ_ktm M) - 1)
∧ ktc_tape c'' = ktc_tape c'
∧ (∀k'. k' ≠ tk ⟶ ktc_pos c'' k' = ktc_pos c' k')"
proof -
have finG: "finite (Γ_ktm M)" by (rule valid_ktm_finite_Gamma[OF vM])
let ?fold = "λj. foldl (ar_acc (Γ_ktm M) (bl_ktm M)) (buf0 tk)
(map (λm. ktc_tape c' tk (base + m)) [0..<j])"
let ?P = "λj c.
ktc_state c = (q, AR_SimRead, tk, j + 2, buf0(tk := ?fold j), dvec, posk)
∧ ktc_pos c tk = base + j
∧ ktc_tape c = ktc_tape c'
∧ (∀k'. k' ≠ tk ⟶ ktc_pos c k' = ktc_pos c' k')"
have mybase: "?P 0 c'" using stg pos_base by simp
have mystep:
"⋀j cc. ⟦ j < block_width (Γ_ktm M) - 1; ?P j cc ⟧
⟹ ∃c''. (cc, c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))
∧ ?P (Suc j) c''"
proof -
fix j cc
assume jlt: "j < block_width (Γ_ktm M) - 1" and Pj: "?P j cc"
from Pj have st_cc:
"ktc_state cc = (q, AR_SimRead, tk, j + 2, buf0(tk := ?fold j), dvec, posk)"
and pos_cc: "ktc_pos cc tk = base + j"
and tape_cc: "ktc_tape cc = ktc_tape c'"
and other_cc: "∀k'. k' ≠ tk ⟶ ktc_pos cc k' = ktc_pos c' k'"
by simp_all
have tk_lt: "tk < k_ktm M" using src0 by (simp add: ar_stage_bounded_def)
have pad_cc: "∀j ≥ k_ktm M. ktc_tape cc j (ktc_pos cc j) = BLANK4"
proof (intro allI impI)
fix j' assume jge: "k_ktm M ≤ j'"
have jne: "j' ≠ tk" using jge tk_lt by simp
have "ktc_tape cc j' (ktc_pos cc j') = ktc_tape c' j' (ktc_pos c' j')"
using tape_cc other_cc jne by simp
thus "ktc_tape cc j' (ktc_pos cc j') = BLANK4" using pad0 jge by simp
qed
have src_cc: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, tk, j + 2, buf0(tk := ?fold j), dvec, posk)"
using src0 tk_lt by (auto simp: ar_stage_bounded_def)
have jhi: "j + 2 ≤ block_width (Γ_ktm M)" using jlt kge2 by linarith
have foldj_mem: "?fold j ∈ Γ_ktm M ∪ {bl_ktm M}"
using buf0_valid by (intro foldl_ar_acc_mem[OF finG]) simp
have bufj_valid: "∀k. (buf0(tk := ?fold j)) k ∈ Γ_ktm M ∪ {bl_ktm M}"
using buf0_valid foldj_mem by simp
have vsrc_cc:
"ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimRead, tk, j + 2, buf0(tk := ?fold j), dvec, posk)"
using jhi kge2 bufj_valid by (auto simp: ar_valid_stage_def)
obtain ccc where
bstep: "(cc, ccc) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))"
and bst_state: "ktc_state ccc = (q, AR_SimRead, tk, Suc (j + 2),
(buf0(tk := ?fold j))
(tk := gamma_unenum (Γ_ktm M) (bl_ktm M)
(2 * gamma_enum (Γ_ktm M) (bl_ktm M) ((buf0(tk := ?fold j)) tk)
+ bit_value (ktc_tape cc tk (ktc_pos cc tk)))),
dvec, posk)"
and bst_tape: "ktc_tape ccc = ktc_tape cc"
and bst_pos: "ktc_pos ccc = (ktc_pos cc)(tk := Suc (ktc_pos cc tk))"
using ar_read_bit_step[OF vM st_cc qQ posk_proper _ _ kge2 vsrc_cc pad_cc src_cc]
jhi by force
have read_cell: "ktc_tape cc tk (ktc_pos cc tk) = ktc_tape c' tk (base + j)"
using tape_cc pos_cc by simp
have fold_step:
"gamma_unenum (Γ_ktm M) (bl_ktm M)
(2 * gamma_enum (Γ_ktm M) (bl_ktm M) (?fold j)
+ bit_value (ktc_tape c' tk (base + j)))
= ?fold (Suc j)"
proof -
have "?fold (Suc j)
= foldl (ar_acc (Γ_ktm M) (bl_ktm M)) (buf0 tk)
(map (λm. ktc_tape c' tk (base + m)) [0..<j]
@ [ktc_tape c' tk (base + j)])"
by (simp add: upt_Suc_append)
also have "… = ar_acc (Γ_ktm M) (bl_ktm M) (?fold j)
(ktc_tape c' tk (base + j))"
by simp
finally show ?thesis by (simp add: ar_acc_def)
qed
have state_eq:
"ktc_state ccc = (q, AR_SimRead, tk, Suc j + 2,
buf0(tk := ?fold (Suc j)), dvec, posk)"
using bst_state by (simp add: read_cell fold_step)
have pos_eq: "ktc_pos ccc tk = base + Suc j"
using bst_pos pos_cc by simp
have other_eq: "∀k'. k' ≠ tk ⟶ ktc_pos ccc k' = ktc_pos c' k'"
using bst_pos other_cc by simp
have tape_eq: "ktc_tape ccc = ktc_tape c'" using bst_tape tape_cc by simp
show "∃c''. (cc, c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ∧ ?P (Suc j) c''"
using bstep state_eq pos_eq tape_eq other_eq by blast
qed
have loop:
"∃c''. (c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (block_width (Γ_ktm M) - 1)
∧ ?P (block_width (Γ_ktm M) - 1) c''"
by (rule relpow_invariant_chain
[where P = ?P and n = "block_width (Γ_ktm M) - 1", OF mystep mybase])
obtain c'' where
chain: "(c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (block_width (Γ_ktm M) - 1)"
and Pfin: "?P (block_width (Γ_ktm M) - 1) c''"
using loop by blast
have ctr: "(block_width (Γ_ktm M) - 1) + 2 = Suc (block_width (Γ_ktm M))"
using kge2 by simp
show ?thesis using chain Pfin ctr by (intro exI[where x = c'']) simp
qed
text ‹The proper-cell single-tape read, non-last tape. From an
‹AR_SimRead› stage at bit-counter ‹0› with the head over a
proper block ‹base = sim_pos p› (‹p ≥ 1›, so
‹0 < base›) whose current cell is not ‹LE4› and ‹posk
tk› proper, the read fires the two look-back steps, the inner
per-bit loop (‹ar_read_bit_loop›), and the bit boundary,
decoding the ‹b›-cell block at ‹base› into ‹buf
tk› and landing at the next tape's ‹AR_SimRead›
(‹k_succ tk›, counter ‹0›). The decoded ‹buf
tk› is the abstract fold ‹foldl (ar_acc Γ bl)
(gamma_unenum Γ bl 0)› over the block's ‹b› cells --
the form the caller collapses to the source symbol via
‹foldl_ar_acc_cell_repr› once tape-correspondence pins those
cells to ‹cell_repr›. The chain has length ‹b + 2›
(look-back 1, look-back 2, loop ‹b - 1›, boundary). The
refined ‹posk tk› records whether the look-back cell was
‹LE4› (the head sat at ‹sim_pos 1›).›
text ‹The snoc step of a left fold over a ‹map f [0..<b]›:
for ‹0 < b› the fold equals one ‹ar_acc› applied to the
fold over the first ‹b - 1› cells and the last cell
‹f (b - 1)›. This is the boundary/finish step's last-bit
accumulator collapse, shared by both proper-read consumers.›
lemma ar_acc_foldl_upt_last:
assumes "0 < k"
shows "foldl (ar_acc Γ bl) a (map f [0..<k])
= ar_acc Γ bl
(foldl (ar_acc Γ bl) a (map f [0..<k - 1])) (f (k - 1))"
proof -
obtain kk where "k = Suc kk" using assms by (cases k) auto
thus ?thesis by (simp add: upt_Suc_append)
qed
text ‹The proper-cell read prefix: the part of a proper-cell
single-tape read shared by the non-last (‹boundary›) and last
(‹finish›) variants. From an ‹AR_SimRead› stage at
bit-counter ‹0› with the head over a proper block
‹base = sim_pos p› (‹0 < base›) whose cell is not
‹LE4› and ‹posk tk› proper, it fires look-back 1, look-back
2, and the inner per-bit loop (‹ar_read_bit_loop›), reaching
bit-counter ‹Suc b› with the head at ‹base + (b - 1)› and
‹buf tk› the fold over the first ‹b - 1› cells. The
remaining last-bit step (boundary or finish) is added by the
consumer. Chain length ‹Suc b› (‹1 + 1 + (b - 1)›).›
lemma ar_read_proper_prefix:
fixes M :: "('q, 'a) ktm"
and c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes vM: "valid_ktm M"
and qQ: "q ∈ Q_ktm M"
and kge2: "2 ≤ block_width (Γ_ktm M)"
and posk_proper: "posk tk ∈ {AR_AtFirstProper, AR_AtFurtherProper}"
and stg: "ktc_state c' = (q, AR_SimRead, tk, 0, buf, dvec, posk)"
and notLE: "ktc_tape c' tk (ktc_pos c' tk) ≠ LE4"
and base_pos: "0 < base"
and pos_base: "ktc_pos c' tk = base"
and vsrc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimRead, tk, 0, buf, dvec, posk)"
and pad0: "∀j ≥ k_ktm M. ktc_tape c' j (ktc_pos c' j) = BLANK4"
and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, tk, 0, buf, dvec, posk)"
shows "∃c''. (c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ Suc (block_width (Γ_ktm M))
∧ ktc_state c'' = (q, AR_SimRead, tk, Suc (block_width (Γ_ktm M)),
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M))
(gamma_unenum (Γ_ktm M) (bl_ktm M) 0)
(map (λm. ktc_tape c' tk (base + m))
[0..<block_width (Γ_ktm M) - 1])),
dvec,
posk(tk := if ktc_tape c' tk (base - 1) = LE4
then AR_AtFirstProper else AR_AtFurtherProper))
∧ ktc_tape c'' = ktc_tape c'
∧ ktc_pos c'' = (ktc_pos c')(tk := base + (block_width (Γ_ktm M) - 1))"
proof -
let ?g0 = "gamma_unenum (Γ_ktm M) (bl_ktm M) 0"
let ?cells1 = "map (λm. ktc_tape c' tk (base + m)) [0..<block_width (Γ_ktm M) - 1]"
let ?posk' = "posk(tk := if ktc_tape c' tk (base - 1) = LE4
then AR_AtFirstProper else AR_AtFurtherProper)"
have finG: "finite (Γ_ktm M)" by (rule valid_ktm_finite_Gamma[OF vM])
have ksuc: "Suc (block_width (Γ_ktm M) - 1) = block_width (Γ_ktm M)"
using kge2 by (cases "block_width (Γ_ktm M)") auto
have bsuc: "Suc (base - 1) = base" using base_pos by (cases base) auto
have tk_lt: "tk < k_ktm M" using src0 by (simp add: ar_stage_bounded_def)
have buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
using vsrc by (simp add: ar_valid_stage_def)
have g0_mem: "?g0 ∈ Γ_ktm M ∪ {bl_ktm M}" by (rule gamma_unenum_mem[OF finG])
obtain c1 where
s1: "(c', c1) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))"
and st1: "ktc_state c1 = (q, AR_SimRead, tk, Suc 0, buf, dvec, posk)"
and tp1: "ktc_tape c1 = ktc_tape c'"
and pp1: "ktc_pos c1 = (ktc_pos c')(tk := ktc_pos c' tk - 1)"
using ar_read_lookback1_step[OF vM stg qQ posk_proper notLE vsrc pad0 src0]
by blast
have pos1_tk: "ktc_pos c1 tk = base - 1" using pp1 pos_base by simp
have pad_c1: "∀j ≥ k_ktm M. ktc_tape c1 j (ktc_pos c1 j) = BLANK4"
proof (intro allI impI)
fix j assume jge: "k_ktm M ≤ j"
have jne: "j ≠ tk" using jge tk_lt by simp
have "ktc_tape c1 j (ktc_pos c1 j) = ktc_tape c' j (ktc_pos c' j)"
using tp1 pp1 jne by simp
thus "ktc_tape c1 j (ktc_pos c1 j) = BLANK4" using pad0 jge by simp
qed
have src_c1: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, tk, Suc 0, buf, dvec, posk)"
using src0 by (simp add: ar_stage_bounded_def)
have i1lt: "Suc 0 < 2 * block_width (Γ_ktm M)" using kge2 by linarith
have vsrc1: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimRead, tk, Suc 0, buf, dvec, posk)"
using i1lt buf_valid by (simp add: ar_valid_stage_def)
obtain c2 where
s2: "(c1, c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))"
and st2: "ktc_state c2 = (q, AR_SimRead, tk, Suc (Suc 0),
buf(tk := ?g0), dvec,
posk(tk := if ktc_tape c1 tk (ktc_pos c1 tk) = LE4
then AR_AtFirstProper else AR_AtFurtherProper))"
and tp2: "ktc_tape c2 = ktc_tape c1"
and pp2: "ktc_pos c2 = (ktc_pos c1)(tk := Suc (ktc_pos c1 tk))"
using ar_read_lookback2_step[OF vM st1 qQ posk_proper kge2 vsrc1 pad_c1 src_c1]
by blast
have posk2_eq: "posk(tk := if ktc_tape c1 tk (ktc_pos c1 tk) = LE4
then AR_AtFirstProper else AR_AtFurtherProper) = ?posk'"
by (simp add: tp1 pos1_tk)
have st2': "ktc_state c2 = (q, AR_SimRead, tk, 2, buf(tk := ?g0), dvec, ?posk')"
using st2 posk2_eq by (simp add: numeral_2_eq_2)
have tp2': "ktc_tape c2 = ktc_tape c'" using tp2 tp1 by simp
have pos2_tk: "ktc_pos c2 tk = base" using pp2 pos1_tk bsuc by simp
have pad_c2: "∀j ≥ k_ktm M. ktc_tape c2 j (ktc_pos c2 j) = BLANK4"
proof (intro allI impI)
fix j assume jge: "k_ktm M ≤ j"
have jne: "j ≠ tk" using jge tk_lt by simp
have "ktc_tape c2 j (ktc_pos c2 j) = ktc_tape c1 j (ktc_pos c1 j)"
using tp2 pp2 jne by simp
thus "ktc_tape c2 j (ktc_pos c2 j) = BLANK4" using pad_c1 jge by simp
qed
have src_c2: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, tk, 2, buf(tk := ?g0), dvec, ?posk')"
using src0 tk_lt by (auto simp: ar_stage_bounded_def)
have posk'_proper: "?posk' tk ∈ {AR_AtFirstProper, AR_AtFurtherProper}" by simp
have buf0_valid: "∀k. (buf(tk := ?g0)) k ∈ Γ_ktm M ∪ {bl_ktm M}"
using buf_valid g0_mem by simp
obtain c3 where
s3: "(c2, c3) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (block_width (Γ_ktm M) - 1)"
and st3: "ktc_state c3 = (q, AR_SimRead, tk, Suc (block_width (Γ_ktm M)),
(buf(tk := ?g0))
(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ((buf(tk := ?g0)) tk)
(map (λm. ktc_tape c2 tk (base + m))
[0..<block_width (Γ_ktm M) - 1])),
dvec, ?posk')"
and pp3: "ktc_pos c3 tk = base + (block_width (Γ_ktm M) - 1)"
and tp3: "ktc_tape c3 = ktc_tape c2"
and pp3off: "∀k'. k' ≠ tk ⟶ ktc_pos c3 k' = ktc_pos c2 k'"
using ar_read_bit_loop[OF vM qQ kge2 posk'_proper st2' buf0_valid pos2_tk
pad_c2 src_c2]
by blast
have st3': "ktc_state c3 = (q, AR_SimRead, tk, Suc (block_width (Γ_ktm M)),
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1),
dvec, ?posk')"
using st3 by (simp add: tp2')
have tp3': "ktc_tape c3 = ktc_tape c'" using tp3 tp2' by simp
have pos3: "ktc_pos c3 = (ktc_pos c')(tk := base + (block_width (Γ_ktm M) - 1))"
proof (rule ext)
fix k'
show "ktc_pos c3 k' = ((ktc_pos c')(tk := base + (block_width (Γ_ktm M) - 1))) k'"
proof (cases "k' = tk")
case True thus ?thesis using pp3 by simp
next
case False
have "ktc_pos c3 k' = ktc_pos c2 k'" using pp3off False by simp
also have "… = ktc_pos c1 k'" using pp2 False by simp
also have "… = ktc_pos c' k'" using pp1 False by simp
finally show ?thesis using False by simp
qed
qed
have ch13: "(c1, c3) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ Suc (block_width (Γ_ktm M) - 1)"
by (rule relpow_Suc_I2[OF s2 s3])
have ch03: "(c', c3) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ Suc (Suc (block_width (Γ_ktm M) - 1))"
by (rule relpow_Suc_I2[OF s1 ch13])
have eqn: "Suc (Suc (block_width (Γ_ktm M) - 1)) = Suc (block_width (Γ_ktm M))"
using ksuc by simp
show ?thesis
proof (intro exI[where x = c3] conjI)
show "(c', c3) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ Suc (block_width (Γ_ktm M))"
using ch03 by (simp only: eqn[symmetric])
show "ktc_state c3 = (q, AR_SimRead, tk, Suc (block_width (Γ_ktm M)),
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1),
dvec, ?posk')"
by (rule st3')
show "ktc_tape c3 = ktc_tape c'" by (rule tp3')
show "ktc_pos c3 = (ktc_pos c')(tk := base + (block_width (Γ_ktm M) - 1))"
by (rule pos3)
qed
qed
text ‹The proper-cell single-tape read, non-last tape: the prefix
followed by the bit-boundary step (‹ar_read_bit_boundary_step›),
decoding the ‹b›-cell block at ‹base› into ‹buf tk›
(the abstract fold ‹foldl (ar_acc Γ bl) (gamma_unenum Γ
bl 0)›, collapsed to the source symbol by
‹foldl_ar_acc_cell_repr›) and landing at the next tape's
‹AR_SimRead› (‹k_succ tk›, counter ‹0›). Chain length
‹b + 2›.›
lemma ar_read_proper_step:
fixes M :: "('q, 'a) ktm"
and c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes vM: "valid_ktm M"
and qQ: "q ∈ Q_ktm M"
and kge2: "2 ≤ block_width (Γ_ktm M)"
and notlast: "¬ is_last_k M tk"
and posk_proper: "posk tk ∈ {AR_AtFirstProper, AR_AtFurtherProper}"
and stg: "ktc_state c' = (q, AR_SimRead, tk, 0, buf, dvec, posk)"
and notLE: "ktc_tape c' tk (ktc_pos c' tk) ≠ LE4"
and base_pos: "0 < base"
and pos_base: "ktc_pos c' tk = base"
and vsrc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimRead, tk, 0, buf, dvec, posk)"
and pad0: "∀j ≥ k_ktm M. ktc_tape c' j (ktc_pos c' j) = BLANK4"
and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, tk, 0, buf, dvec, posk)"
shows "∃c''. (c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (block_width (Γ_ktm M) + 2)
∧ ktc_state c'' = (q, AR_SimRead, k_succ tk, 0,
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M))
(gamma_unenum (Γ_ktm M) (bl_ktm M) 0)
(map (λm. ktc_tape c' tk (base + m))
[0..<block_width (Γ_ktm M)])),
dvec,
posk(tk := if ktc_tape c' tk (base - 1) = LE4
then AR_AtFirstProper else AR_AtFurtherProper))
∧ ktc_tape c'' = ktc_tape c'
∧ ktc_pos c'' = (ktc_pos c')(tk := base + block_width (Γ_ktm M))"
proof -
let ?g0 = "gamma_unenum (Γ_ktm M) (bl_ktm M) 0"
let ?cells1 = "map (λm. ktc_tape c' tk (base + m)) [0..<block_width (Γ_ktm M) - 1]"
let ?posk' = "posk(tk := if ktc_tape c' tk (base - 1) = LE4
then AR_AtFirstProper else AR_AtFurtherProper)"
have finG: "finite (Γ_ktm M)" by (rule valid_ktm_finite_Gamma[OF vM])
have kpos: "0 < block_width (Γ_ktm M)" using kge2 by simp
have ksuc: "Suc (block_width (Γ_ktm M) - 1) = block_width (Γ_ktm M)"
using kge2 by (cases "block_width (Γ_ktm M)") auto
have buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
using vsrc by (simp add: ar_valid_stage_def)
have g0_mem: "?g0 ∈ Γ_ktm M ∪ {bl_ktm M}" by (rule gamma_unenum_mem[OF finG])
obtain c3 where
pre_chain: "(c', c3) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ Suc (block_width (Γ_ktm M))"
and pre_st: "ktc_state c3 = (q, AR_SimRead, tk, Suc (block_width (Γ_ktm M)),
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1),
dvec, ?posk')"
and pre_tp: "ktc_tape c3 = ktc_tape c'"
and pre_pp: "ktc_pos c3 = (ktc_pos c')(tk := base + (block_width (Γ_ktm M) - 1))"
using ar_read_proper_prefix[OF vM qQ kge2 posk_proper stg notLE
base_pos pos_base vsrc pad0 src0] by blast
have posk'_proper: "?posk' tk ∈ {AR_AtFirstProper, AR_AtFurtherProper}" by simp
have fold3_mem:
"foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1 ∈ Γ_ktm M ∪ {bl_ktm M}"
using g0_mem by (rule foldl_ar_acc_mem[OF finG])
have buf3_valid:
"∀k. (buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1)) k
∈ Γ_ktm M ∪ {bl_ktm M}"
using buf_valid fold3_mem by simp
have ilt: "Suc (block_width (Γ_ktm M)) < 2 * block_width (Γ_ktm M)" using kge2 by linarith
have vsrc3: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimRead, tk, Suc (block_width (Γ_ktm M)),
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1),
dvec, ?posk')"
using ilt buf3_valid by (simp add: ar_valid_stage_def)
have pos3_tk: "ktc_pos c3 tk = base + (block_width (Γ_ktm M) - 1)" using pre_pp by simp
have tk_lt: "tk < k_ktm M" using src0 by (simp add: ar_stage_bounded_def)
have pad_c3: "∀j ≥ k_ktm M. ktc_tape c3 j (ktc_pos c3 j) = BLANK4"
proof (intro allI impI)
fix j assume jge: "k_ktm M ≤ j"
have jne: "j ≠ tk" using jge tk_lt by simp
have "ktc_tape c3 j (ktc_pos c3 j) = ktc_tape c' j (ktc_pos c' j)"
using pre_tp pre_pp jne by simp
thus "ktc_tape c3 j (ktc_pos c3 j) = BLANK4" using pad0 jge by simp
qed
have src_c3: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, tk, Suc (block_width (Γ_ktm M)),
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1),
dvec, ?posk')"
using src0 tk_lt by (auto simp: ar_stage_bounded_def)
obtain c4 where
s4: "(c3, c4) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))"
and st4: "ktc_state c4 = (q, AR_SimRead, k_succ tk, 0,
(buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1))
(tk := gamma_unenum (Γ_ktm M) (bl_ktm M)
(2 * gamma_enum (Γ_ktm M) (bl_ktm M)
((buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1)) tk)
+ bit_value (ktc_tape c3 tk (ktc_pos c3 tk)))),
dvec, ?posk')"
and tp4: "ktc_tape c4 = ktc_tape c3"
and pp4: "ktc_pos c4 = (ktc_pos c3)(tk := Suc (ktc_pos c3 tk))"
using ar_read_bit_boundary_step[OF vM pre_st qQ notlast posk'_proper
refl vsrc3 pad_c3 src_c3] by blast
have read_cell4: "ktc_tape c3 tk (ktc_pos c3 tk)
= ktc_tape c' tk (base + (block_width (Γ_ktm M) - 1))"
using pre_tp pos3_tk by simp
have st4': "ktc_state c4 = (q, AR_SimRead, k_succ tk, 0,
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0
(map (λm. ktc_tape c' tk (base + m))
[0..<block_width (Γ_ktm M)])),
dvec, ?posk')"
using st4 by (simp add: read_cell4 ar_acc_foldl_upt_last[OF kpos] ar_acc_def)
have tape4: "ktc_tape c4 = ktc_tape c'" using tp4 pre_tp by simp
have pos4: "ktc_pos c4 = (ktc_pos c')(tk := base + block_width (Γ_ktm M))"
proof (rule ext)
fix k'
show "ktc_pos c4 k' = ((ktc_pos c')(tk := base + block_width (Γ_ktm M))) k'"
proof (cases "k' = tk")
case True
have "ktc_pos c4 tk = Suc (ktc_pos c3 tk)" using pp4 by simp
also have "… = Suc (base + (block_width (Γ_ktm M) - 1))" using pos3_tk by simp
also have "… = base + block_width (Γ_ktm M)" using ksuc by simp
finally show ?thesis using True by simp
next
case False
have "ktc_pos c4 k' = ktc_pos c3 k'" using pp4 False by simp
also have "… = ktc_pos c' k'" using pre_pp False by simp
finally show ?thesis using False by simp
qed
qed
have ch04: "(c', c4) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ Suc (Suc (block_width (Γ_ktm M)))"
by (rule relpow_Suc_I[OF pre_chain s4])
have eqn: "Suc (Suc (block_width (Γ_ktm M))) = block_width (Γ_ktm M) + 2" by simp
show ?thesis
proof (intro exI[where x = c4] conjI)
show "(c', c4) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (block_width (Γ_ktm M) + 2)"
using ch04 by (simp only: eqn[symmetric])
show "ktc_state c4 = (q, AR_SimRead, k_succ tk, 0,
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0
(map (λm. ktc_tape c' tk (base + m))
[0..<block_width (Γ_ktm M)])),
dvec, ?posk')"
by (rule st4')
show "ktc_tape c4 = ktc_tape c'" by (rule tape4)
show "ktc_pos c4 = (ktc_pos c')(tk := base + block_width (Γ_ktm M))" by (rule pos4)
qed
qed
text ‹The proper-cell single-tape read, last tape: the prefix
followed by the bit-finish step (‹ar_read_bit_finish_step›),
decoding the ‹b›-cell block at ‹base› into ‹buf tk›
exactly as the non-last variant, but transitioning to
‹AR_SimCompute› with the current-tape field reset to
‹k_unidx 0› (all tapes decoded). Chain length ‹b + 2›.›
lemma ar_read_proper_finish_step:
fixes M :: "('q, 'a) ktm"
and c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes vM: "valid_ktm M"
and qQ: "q ∈ Q_ktm M"
and kge2: "2 ≤ block_width (Γ_ktm M)"
and last: "is_last_k M tk"
and posk_proper: "posk tk ∈ {AR_AtFirstProper, AR_AtFurtherProper}"
and stg: "ktc_state c' = (q, AR_SimRead, tk, 0, buf, dvec, posk)"
and notLE: "ktc_tape c' tk (ktc_pos c' tk) ≠ LE4"
and base_pos: "0 < base"
and pos_base: "ktc_pos c' tk = base"
and vsrc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimRead, tk, 0, buf, dvec, posk)"
and pad0: "∀j ≥ k_ktm M. ktc_tape c' j (ktc_pos c' j) = BLANK4"
and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, tk, 0, buf, dvec, posk)"
shows "∃c''. (c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (block_width (Γ_ktm M) + 2)
∧ ktc_state c'' = (q, AR_SimCompute, k_unidx 0, 0,
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M))
(gamma_unenum (Γ_ktm M) (bl_ktm M) 0)
(map (λm. ktc_tape c' tk (base + m))
[0..<block_width (Γ_ktm M)])),
dvec,
posk(tk := if ktc_tape c' tk (base - 1) = LE4
then AR_AtFirstProper else AR_AtFurtherProper))
∧ ktc_tape c'' = ktc_tape c'
∧ ktc_pos c'' = (ktc_pos c')(tk := base + block_width (Γ_ktm M))"
proof -
let ?g0 = "gamma_unenum (Γ_ktm M) (bl_ktm M) 0"
let ?cells1 = "map (λm. ktc_tape c' tk (base + m)) [0..<block_width (Γ_ktm M) - 1]"
let ?posk' = "posk(tk := if ktc_tape c' tk (base - 1) = LE4
then AR_AtFirstProper else AR_AtFurtherProper)"
have finG: "finite (Γ_ktm M)" by (rule valid_ktm_finite_Gamma[OF vM])
have kpos: "0 < block_width (Γ_ktm M)" using kge2 by simp
have ksuc: "Suc (block_width (Γ_ktm M) - 1) = block_width (Γ_ktm M)"
using kge2 by (cases "block_width (Γ_ktm M)") auto
have buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
using vsrc by (simp add: ar_valid_stage_def)
have g0_mem: "?g0 ∈ Γ_ktm M ∪ {bl_ktm M}" by (rule gamma_unenum_mem[OF finG])
obtain c3 where
pre_chain: "(c', c3) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ Suc (block_width (Γ_ktm M))"
and pre_st: "ktc_state c3 = (q, AR_SimRead, tk, Suc (block_width (Γ_ktm M)),
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1),
dvec, ?posk')"
and pre_tp: "ktc_tape c3 = ktc_tape c'"
and pre_pp: "ktc_pos c3 = (ktc_pos c')(tk := base + (block_width (Γ_ktm M) - 1))"
using ar_read_proper_prefix[OF vM qQ kge2 posk_proper stg notLE
base_pos pos_base vsrc pad0 src0] by blast
have posk'_proper: "?posk' tk ∈ {AR_AtFirstProper, AR_AtFurtherProper}" by simp
have fold3_mem:
"foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1 ∈ Γ_ktm M ∪ {bl_ktm M}"
using g0_mem by (rule foldl_ar_acc_mem[OF finG])
have buf3_valid:
"∀k. (buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1)) k
∈ Γ_ktm M ∪ {bl_ktm M}"
using buf_valid fold3_mem by simp
have ilt: "Suc (block_width (Γ_ktm M)) < 2 * block_width (Γ_ktm M)" using kge2 by linarith
have vsrc3: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimRead, tk, Suc (block_width (Γ_ktm M)),
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1),
dvec, ?posk')"
using ilt buf3_valid by (simp add: ar_valid_stage_def)
have pos3_tk: "ktc_pos c3 tk = base + (block_width (Γ_ktm M) - 1)" using pre_pp by simp
have tk_lt: "tk < k_ktm M" using src0 by (simp add: ar_stage_bounded_def)
have pad_c3: "∀j ≥ k_ktm M. ktc_tape c3 j (ktc_pos c3 j) = BLANK4"
proof (intro allI impI)
fix j assume jge: "k_ktm M ≤ j"
have jne: "j ≠ tk" using jge tk_lt by simp
have "ktc_tape c3 j (ktc_pos c3 j) = ktc_tape c' j (ktc_pos c' j)"
using pre_tp pre_pp jne by simp
thus "ktc_tape c3 j (ktc_pos c3 j) = BLANK4" using pad0 jge by simp
qed
have src_c3: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, tk, Suc (block_width (Γ_ktm M)),
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1),
dvec, ?posk')"
using src0 tk_lt by (auto simp: ar_stage_bounded_def)
obtain c4 where
s4: "(c3, c4) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))"
and st4: "ktc_state c4 = (q, AR_SimCompute, k_unidx 0, 0,
(buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1))
(tk := gamma_unenum (Γ_ktm M) (bl_ktm M)
(2 * gamma_enum (Γ_ktm M) (bl_ktm M)
((buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0 ?cells1)) tk)
+ bit_value (ktc_tape c3 tk (ktc_pos c3 tk)))),
dvec, ?posk')"
and tp4: "ktc_tape c4 = ktc_tape c3"
and pp4: "ktc_pos c4 = (ktc_pos c3)(tk := Suc (ktc_pos c3 tk))"
using ar_read_bit_finish_step[OF vM pre_st qQ last posk'_proper
refl vsrc3 pad_c3 src_c3] by blast
have read_cell4: "ktc_tape c3 tk (ktc_pos c3 tk)
= ktc_tape c' tk (base + (block_width (Γ_ktm M) - 1))"
using pre_tp pos3_tk by simp
have st4': "ktc_state c4 = (q, AR_SimCompute, k_unidx 0, 0,
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0
(map (λm. ktc_tape c' tk (base + m))
[0..<block_width (Γ_ktm M)])),
dvec, ?posk')"
using st4 by (simp add: read_cell4 ar_acc_foldl_upt_last[OF kpos] ar_acc_def)
have tape4: "ktc_tape c4 = ktc_tape c'" using tp4 pre_tp by simp
have pos4: "ktc_pos c4 = (ktc_pos c')(tk := base + block_width (Γ_ktm M))"
proof (rule ext)
fix k'
show "ktc_pos c4 k' = ((ktc_pos c')(tk := base + block_width (Γ_ktm M))) k'"
proof (cases "k' = tk")
case True
have "ktc_pos c4 tk = Suc (ktc_pos c3 tk)" using pp4 by simp
also have "… = Suc (base + (block_width (Γ_ktm M) - 1))" using pos3_tk by simp
also have "… = base + block_width (Γ_ktm M)" using ksuc by simp
finally show ?thesis using True by simp
next
case False
have "ktc_pos c4 k' = ktc_pos c3 k'" using pp4 False by simp
also have "… = ktc_pos c' k'" using pre_pp False by simp
finally show ?thesis using False by simp
qed
qed
have ch04: "(c', c4) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ Suc (Suc (block_width (Γ_ktm M)))"
by (rule relpow_Suc_I[OF pre_chain s4])
have eqn: "Suc (Suc (block_width (Γ_ktm M))) = block_width (Γ_ktm M) + 2" by simp
show ?thesis
proof (intro exI[where x = c4] conjI)
show "(c', c4) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (block_width (Γ_ktm M) + 2)"
using ch04 by (simp only: eqn[symmetric])
show "ktc_state c4 = (q, AR_SimCompute, k_unidx 0, 0,
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M)) ?g0
(map (λm. ktc_tape c' tk (base + m))
[0..<block_width (Γ_ktm M)])),
dvec, ?posk')"
by (rule st4')
show "ktc_tape c4 = ktc_tape c'" by (rule tape4)
show "ktc_pos c4 = (ktc_pos c')(tk := base + block_width (Γ_ktm M))" by (rule pos4)
qed
qed
text ‹Unified single-tape read, non-last tape: dispatches the per-tape
read on whether ‹M›'s head sits on the left-end marker
(‹p = 0›, the LE arm) or in the proper region (‹p ≥ 1›,
the proper arm) from the per-tape correspondence facts rather than the
raw cell pattern. Both arms land back at ‹AR_SimRead› on the
successor tape with ‹buf tk› holding the decoded ‹M›-symbol
‹tM p› (via ‹foldl_ar_acc_cell_repr›) and ‹posk tk›
re-synced exact to the head's position kind (‹AR_AtLE› at
‹0›, ‹AR_AtFirstProper› at ‹1›,
‹AR_AtFurtherProper› beyond — the marker test
‹tM' (base - 1) = LE4› coincides with ‹p = 1› by the
left-end discipline). Cost ‹1› (LE) or ‹b + 2› (proper).
This is the uniform per-tape step the read-phase tape walk iterates.›
lemma ar_read_tape_step:
fixes M :: "('q, 'a) ktm"
and c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
and tM :: "nat ⇒ 'a"
assumes vM: "valid_ktm M"
and qQ: "q ∈ Q_ktm M"
and kge2: "2 ≤ block_width (Γ_ktm M)"
and notlast: "¬ is_last_k M tk"
and stg: "ktc_state c' = (q, AR_SimRead, tk, 0, buf, dvec, posk)"
and tcorr: "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
tM (ktc_tape c' tk)"
and ppos: "ktc_pos c' tk = sim_pos (block_width (Γ_ktm M)) p"
and pkok: "posk tk = AR_AtLE ⟷ p = 0"
and proper_mem: "1 ≤ p ⟹ tM p ∈ Γ_ktm M"
and vsrc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimRead, tk, 0, buf, dvec, posk)"
and pad0: "∀j ≥ k_ktm M. ktc_tape c' j (ktc_pos c' j) = BLANK4"
and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, tk, 0, buf, dvec, posk)"
shows "∃c''. (c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (if p = 0 then 1 else block_width (Γ_ktm M) + 2)
∧ ktc_state c'' = (q, AR_SimRead, k_succ tk, 0,
buf(tk := tM p), dvec,
posk(tk := if p = 0 then AR_AtLE
else if p = 1 then AR_AtFirstProper
else AR_AtFurtherProper))
∧ ktc_tape c'' = ktc_tape c'
∧ ktc_pos c'' = (ktc_pos c')(tk :=
if p = 0 then Suc 0
else sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M))"
proof -
have kpos: "0 < block_width (Γ_ktm M)" using kge2 by simp
have finG: "finite (Γ_ktm M)" by (rule valid_ktm_finite_Gamma[OF vM])
have blG: "bl_ktm M ∈ Γ_ktm M" by (rule valid_ktm_blank_in_Gamma[OF vM])
have tape0: "ktc_tape c' tk 0 = LE4"
using tcorr by (simp add: ar_tape_correspondence_def)
have tM0: "tM 0 = le_ktm M"
using tcorr by (simp add: ar_tape_correspondence_def)
have cr_wb: "⋀x j. j < block_width (Γ_ktm M) ⟹
cell_repr (Γ_ktm M) (bl_ktm M) x ! j
= write_bit (Γ_ktm M) (bl_ktm M) x j"
proof -
fix x :: 'a and j
assume jk: "j < block_width (Γ_ktm M)"
show "cell_repr (Γ_ktm M) (bl_ktm M) x ! j
= write_bit (Γ_ktm M) (bl_ktm M) x j"
using jk by (cases "x = bl_ktm M")
(simp_all add: cell_repr_def write_bit_def length_encode_symbol)
qed
show ?thesis
proof (cases "p = 0")
case True
have posk_le: "posk tk = AR_AtLE" using pkok True by simp
have pos0: "ktc_pos c' tk = 0" using ppos True by (simp add: sim_pos_def)
have aLE: "ktc_tape c' tk (ktc_pos c' tk) = LE4" using tape0 pos0 by simp
obtain c'' where
step: "(c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))"
and st: "ktc_state c'' = (q, AR_SimRead, k_succ tk, 0,
buf(tk := le_ktm M), dvec, posk)"
and tp: "ktc_tape c'' = ktc_tape c'"
and ps: "ktc_pos c'' = (ktc_pos c')(tk := Suc (ktc_pos c' tk))"
using ar_read_le_step[OF vM stg qQ notlast posk_le aLE vsrc pad0 src0] by blast
have poskid: "posk(tk := AR_AtLE) = posk"
using posk_le by (simp add: fun_upd_idem)
show ?thesis
proof (intro exI[where x = c''] conjI)
show "(c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))
^^ (if p = 0 then 1 else block_width (Γ_ktm M) + 2)"
using step True by simp
show "ktc_state c'' = (q, AR_SimRead, k_succ tk, 0, buf(tk := tM p), dvec,
posk(tk := if p = 0 then AR_AtLE
else if p = 1 then AR_AtFirstProper
else AR_AtFurtherProper))"
using st tM0 True poskid by simp
show "ktc_tape c'' = ktc_tape c'" by (rule tp)
show "ktc_pos c'' = (ktc_pos c')(tk :=
if p = 0 then Suc 0
else sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M))"
using ps pos0 True by simp
qed
next
case False
hence pge1: "1 ≤ p" by simp
have bpos: "0 < sim_pos (block_width (Γ_ktm M)) p"
using pge1 by (simp add: sim_pos_def)
have posk_ne: "posk tk ≠ AR_AtLE" using pkok False by simp
have posk_proper: "posk tk ∈ {AR_AtFirstProper, AR_AtFurtherProper}"
using posk_ne by (cases "posk tk") auto
have corr: "∀j < block_width (Γ_ktm M).
ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p + j)
= cell_repr (Γ_ktm M) (bl_ktm M) (tM p) ! j"
using tcorr pge1 unfolding ar_tape_correspondence_def by blast
have cell0: "ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p)
= cell_repr (Γ_ktm M) (bl_ktm M) (tM p) ! 0"
using corr[rule_format, OF kpos] by simp
have notLE: "ktc_tape c' tk (ktc_pos c' tk) ≠ LE4"
proof -
have "ktc_tape c' tk (ktc_pos c' tk)
= write_bit (Γ_ktm M) (bl_ktm M) (tM p) 0"
using ppos cell0 cr_wb[OF kpos] by simp
thus ?thesis using write_bit_not_LE4[OF kpos] by simp
qed
obtain c'' where
step: "(c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (block_width (Γ_ktm M) + 2)"
and st: "ktc_state c'' = (q, AR_SimRead, k_succ tk, 0,
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M))
(gamma_unenum (Γ_ktm M) (bl_ktm M) 0)
(map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)])),
dvec,
posk(tk := if ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p - 1) = LE4
then AR_AtFirstProper else AR_AtFurtherProper))"
and tp: "ktc_tape c'' = ktc_tape c'"
and ps: "ktc_pos c'' = (ktc_pos c')(tk :=
sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M))"
using ar_read_proper_step[OF vM qQ kge2 notlast posk_proper stg
notLE bpos ppos vsrc pad0 src0] by blast
have len_cr: "length (cell_repr (Γ_ktm M) (bl_ktm M) (tM p))
= block_width (Γ_ktm M)"
by (simp add: cell_repr_def length_encode_symbol)
have cells_eq: "map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)]
= cell_repr (Γ_ktm M) (bl_ktm M) (tM p)"
proof (rule nth_equalityI)
show "length (map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)])
= length (cell_repr (Γ_ktm M) (bl_ktm M) (tM p))"
using len_cr by simp
next
fix j
assume "j < length (map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)])"
hence jk: "j < block_width (Γ_ktm M)" by simp
show "map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)] ! j
= cell_repr (Γ_ktm M) (bl_ktm M) (tM p) ! j"
using corr[rule_format, OF jk] jk by simp
qed
have decoded: "foldl (ar_acc (Γ_ktm M) (bl_ktm M))
(gamma_unenum (Γ_ktm M) (bl_ktm M) 0)
(map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)])
= tM p"
using cells_eq foldl_ar_acc_cell_repr[OF finG blG proper_mem[OF pge1]]
by simp
have resync: "(if ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p - 1) = LE4
then AR_AtFirstProper else AR_AtFurtherProper)
= (if p = 1 then AR_AtFirstProper else AR_AtFurtherProper)"
proof (cases "p = 1")
case True
have "ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p - 1) = LE4"
using True tape0 by (simp add: sim_pos_def)
thus ?thesis using True by simp
next
case False
with pge1 have pge2: "2 ≤ p" by simp
then obtain p2 where pp: "p = Suc (Suc p2)"
using Suc_le_D by (metis Suc_1 le_Suc_ex add_2_eq_Suc)
obtain k2 where kk: "block_width (Γ_ktm M) = Suc k2"
using kpos by (cases "block_width (Γ_ktm M)") auto
have idx_eq: "sim_pos (block_width (Γ_ktm M)) p - 1
= sim_pos (block_width (Γ_ktm M)) (p - 1) + (block_width (Γ_ktm M) - 1)"
by (simp add: sim_pos_def pp kk algebra_simps)
have pm1: "1 ≤ p - 1" using pge2 by simp
have corr2: "∀j < block_width (Γ_ktm M).
ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) (p - 1) + j)
= cell_repr (Γ_ktm M) (bl_ktm M) (tM (p - 1)) ! j"
using tcorr pm1 unfolding ar_tape_correspondence_def by blast
have km1: "block_width (Γ_ktm M) - 1 < block_width (Γ_ktm M)" using kpos by simp
have "ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p - 1)
= write_bit (Γ_ktm M) (bl_ktm M) (tM (p - 1))
(block_width (Γ_ktm M) - 1)"
using corr2[rule_format, OF km1] idx_eq cr_wb[OF km1] by simp
hence "ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p - 1) ≠ LE4"
using write_bit_not_LE4[OF km1] by simp
thus ?thesis using False by simp
qed
show ?thesis
proof (intro exI[where x = c''] conjI)
show "(c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))
^^ (if p = 0 then 1 else block_width (Γ_ktm M) + 2)"
using step False by simp
show "ktc_state c'' = (q, AR_SimRead, k_succ tk, 0, buf(tk := tM p), dvec,
posk(tk := if p = 0 then AR_AtLE
else if p = 1 then AR_AtFirstProper
else AR_AtFurtherProper))"
using st decoded resync False by simp
show "ktc_tape c'' = ktc_tape c'" by (rule tp)
show "ktc_pos c'' = (ktc_pos c')(tk :=
if p = 0 then Suc 0
else sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M))"
using ps False by simp
qed
qed
qed
text ‹Unified single-tape read, last tape: as ‹ar_read_tape_step›
but ‹tk› is the last tape, so both arms transition to
‹AR_SimCompute› with the current-tape field reset to
‹k_unidx 0› (all tapes decoded, the read phase complete). The
‹buf tk› decode and ‹posk tk› re-sync are identical to the
non-last variant; only the hand-off target differs.›
lemma ar_read_tape_finish_step:
fixes M :: "('q, 'a) ktm"
and c' :: "(sym4, 'q × 'a ar_stage) ktc_config"
and tM :: "nat ⇒ 'a"
assumes vM: "valid_ktm M"
and qQ: "q ∈ Q_ktm M"
and kge2: "2 ≤ block_width (Γ_ktm M)"
and last: "is_last_k M tk"
and stg: "ktc_state c' = (q, AR_SimRead, tk, 0, buf, dvec, posk)"
and tcorr: "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
tM (ktc_tape c' tk)"
and ppos: "ktc_pos c' tk = sim_pos (block_width (Γ_ktm M)) p"
and pkok: "posk tk = AR_AtLE ⟷ p = 0"
and proper_mem: "1 ≤ p ⟹ tM p ∈ Γ_ktm M"
and vsrc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimRead, tk, 0, buf, dvec, posk)"
and pad0: "∀j ≥ k_ktm M. ktc_tape c' j (ktc_pos c' j) = BLANK4"
and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, tk, 0, buf, dvec, posk)"
shows "∃c''. (c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (if p = 0 then 1 else block_width (Γ_ktm M) + 2)
∧ ktc_state c'' = (q, AR_SimCompute, k_unidx 0, 0,
buf(tk := tM p), dvec,
posk(tk := if p = 0 then AR_AtLE
else if p = 1 then AR_AtFirstProper
else AR_AtFurtherProper))
∧ ktc_tape c'' = ktc_tape c'
∧ ktc_pos c'' = (ktc_pos c')(tk :=
if p = 0 then Suc 0
else sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M))"
proof -
have kpos: "0 < block_width (Γ_ktm M)" using kge2 by simp
have finG: "finite (Γ_ktm M)" by (rule valid_ktm_finite_Gamma[OF vM])
have blG: "bl_ktm M ∈ Γ_ktm M" by (rule valid_ktm_blank_in_Gamma[OF vM])
have tape0: "ktc_tape c' tk 0 = LE4"
using tcorr by (simp add: ar_tape_correspondence_def)
have tM0: "tM 0 = le_ktm M"
using tcorr by (simp add: ar_tape_correspondence_def)
have cr_wb: "⋀x j. j < block_width (Γ_ktm M) ⟹
cell_repr (Γ_ktm M) (bl_ktm M) x ! j
= write_bit (Γ_ktm M) (bl_ktm M) x j"
proof -
fix x :: 'a and j
assume jk: "j < block_width (Γ_ktm M)"
show "cell_repr (Γ_ktm M) (bl_ktm M) x ! j
= write_bit (Γ_ktm M) (bl_ktm M) x j"
using jk by (cases "x = bl_ktm M")
(simp_all add: cell_repr_def write_bit_def length_encode_symbol)
qed
show ?thesis
proof (cases "p = 0")
case True
have posk_le: "posk tk = AR_AtLE" using pkok True by simp
have pos0: "ktc_pos c' tk = 0" using ppos True by (simp add: sim_pos_def)
have aLE: "ktc_tape c' tk (ktc_pos c' tk) = LE4" using tape0 pos0 by simp
obtain c'' where
step: "(c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))"
and st: "ktc_state c'' = (q, AR_SimCompute, k_unidx 0, 0,
buf(tk := le_ktm M), dvec, posk)"
and tp: "ktc_tape c'' = ktc_tape c'"
and ps: "ktc_pos c'' = (ktc_pos c')(tk := Suc (ktc_pos c' tk))"
using ar_read_le_finish_step[OF vM stg qQ last posk_le aLE vsrc pad0 src0]
by blast
have poskid: "posk(tk := AR_AtLE) = posk"
using posk_le by (simp add: fun_upd_idem)
show ?thesis
proof (intro exI[where x = c''] conjI)
show "(c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))
^^ (if p = 0 then 1 else block_width (Γ_ktm M) + 2)"
using step True by simp
show "ktc_state c'' = (q, AR_SimCompute, k_unidx 0, 0, buf(tk := tM p), dvec,
posk(tk := if p = 0 then AR_AtLE
else if p = 1 then AR_AtFirstProper
else AR_AtFurtherProper))"
using st tM0 True poskid by simp
show "ktc_tape c'' = ktc_tape c'" by (rule tp)
show "ktc_pos c'' = (ktc_pos c')(tk :=
if p = 0 then Suc 0
else sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M))"
using ps pos0 True by simp
qed
next
case False
hence pge1: "1 ≤ p" by simp
have bpos: "0 < sim_pos (block_width (Γ_ktm M)) p"
using pge1 by (simp add: sim_pos_def)
have posk_ne: "posk tk ≠ AR_AtLE" using pkok False by simp
have posk_proper: "posk tk ∈ {AR_AtFirstProper, AR_AtFurtherProper}"
using posk_ne by (cases "posk tk") auto
have corr: "∀j < block_width (Γ_ktm M).
ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p + j)
= cell_repr (Γ_ktm M) (bl_ktm M) (tM p) ! j"
using tcorr pge1 unfolding ar_tape_correspondence_def by blast
have cell0: "ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p)
= cell_repr (Γ_ktm M) (bl_ktm M) (tM p) ! 0"
using corr[rule_format, OF kpos] by simp
have notLE: "ktc_tape c' tk (ktc_pos c' tk) ≠ LE4"
proof -
have "ktc_tape c' tk (ktc_pos c' tk)
= write_bit (Γ_ktm M) (bl_ktm M) (tM p) 0"
using ppos cell0 cr_wb[OF kpos] by simp
thus ?thesis using write_bit_not_LE4[OF kpos] by simp
qed
obtain c'' where
step: "(c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (block_width (Γ_ktm M) + 2)"
and st: "ktc_state c'' = (q, AR_SimCompute, k_unidx 0, 0,
buf(tk := foldl (ar_acc (Γ_ktm M) (bl_ktm M))
(gamma_unenum (Γ_ktm M) (bl_ktm M) 0)
(map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)])),
dvec,
posk(tk := if ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p - 1) = LE4
then AR_AtFirstProper else AR_AtFurtherProper))"
and tp: "ktc_tape c'' = ktc_tape c'"
and ps: "ktc_pos c'' = (ktc_pos c')(tk :=
sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M))"
using ar_read_proper_finish_step[OF vM qQ kge2 last posk_proper stg
notLE bpos ppos vsrc pad0 src0] by blast
have len_cr: "length (cell_repr (Γ_ktm M) (bl_ktm M) (tM p))
= block_width (Γ_ktm M)"
by (simp add: cell_repr_def length_encode_symbol)
have cells_eq: "map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)]
= cell_repr (Γ_ktm M) (bl_ktm M) (tM p)"
proof (rule nth_equalityI)
show "length (map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)])
= length (cell_repr (Γ_ktm M) (bl_ktm M) (tM p))"
using len_cr by simp
next
fix j
assume "j < length (map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)])"
hence jk: "j < block_width (Γ_ktm M)" by simp
show "map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)] ! j
= cell_repr (Γ_ktm M) (bl_ktm M) (tM p) ! j"
using corr[rule_format, OF jk] jk by simp
qed
have decoded: "foldl (ar_acc (Γ_ktm M) (bl_ktm M))
(gamma_unenum (Γ_ktm M) (bl_ktm M) 0)
(map (λm. ktc_tape c' tk
(sim_pos (block_width (Γ_ktm M)) p + m))
[0..<block_width (Γ_ktm M)])
= tM p"
using cells_eq foldl_ar_acc_cell_repr[OF finG blG proper_mem[OF pge1]]
by simp
have resync: "(if ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p - 1) = LE4
then AR_AtFirstProper else AR_AtFurtherProper)
= (if p = 1 then AR_AtFirstProper else AR_AtFurtherProper)"
proof (cases "p = 1")
case True
have "ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p - 1) = LE4"
using True tape0 by (simp add: sim_pos_def)
thus ?thesis using True by simp
next
case False
with pge1 have pge2: "2 ≤ p" by simp
then obtain p2 where pp: "p = Suc (Suc p2)"
using Suc_le_D by (metis Suc_1 le_Suc_ex add_2_eq_Suc)
obtain k2 where kk: "block_width (Γ_ktm M) = Suc k2"
using kpos by (cases "block_width (Γ_ktm M)") auto
have idx_eq: "sim_pos (block_width (Γ_ktm M)) p - 1
= sim_pos (block_width (Γ_ktm M)) (p - 1) + (block_width (Γ_ktm M) - 1)"
by (simp add: sim_pos_def pp kk algebra_simps)
have pm1: "1 ≤ p - 1" using pge2 by simp
have corr2: "∀j < block_width (Γ_ktm M).
ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) (p - 1) + j)
= cell_repr (Γ_ktm M) (bl_ktm M) (tM (p - 1)) ! j"
using tcorr pm1 unfolding ar_tape_correspondence_def by blast
have km1: "block_width (Γ_ktm M) - 1 < block_width (Γ_ktm M)" using kpos by simp
have "ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p - 1)
= write_bit (Γ_ktm M) (bl_ktm M) (tM (p - 1))
(block_width (Γ_ktm M) - 1)"
using corr2[rule_format, OF km1] idx_eq cr_wb[OF km1] by simp
hence "ktc_tape c' tk (sim_pos (block_width (Γ_ktm M)) p - 1) ≠ LE4"
using write_bit_not_LE4[OF km1] by simp
thus ?thesis using False by simp
qed
show ?thesis
proof (intro exI[where x = c''] conjI)
show "(c', c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M))
^^ (if p = 0 then 1 else block_width (Γ_ktm M) + 2)"
using step False by simp
show "ktc_state c'' = (q, AR_SimCompute, k_unidx 0, 0, buf(tk := tM p), dvec,
posk(tk := if p = 0 then AR_AtLE
else if p = 1 then AR_AtFirstProper
else AR_AtFurtherProper))"
using st decoded resync False by simp
show "ktc_tape c'' = ktc_tape c'" by (rule tp)
show "ktc_pos c'' = (ktc_pos c')(tk :=
if p = 0 then Suc 0
else sim_pos (block_width (Γ_ktm M)) p + block_width (Γ_ktm M))"
using ps False by simp
qed
qed
qed
text ‹The read-phase prefix walk: starting from the read boundary
(current-tape field ‹k_unidx 0›, bit-counter
‹0›), iterate the unified non-last per-tape read
‹ar_read_tape_step› over the first ‹j› tapes of the
enumeration (‹j ≤ k_ktm M - 1›, so every tape touched is
non-last), landing back at ‹AR_SimRead› on tape
‹k_unidx j›. The walk descriptor splits on ‹k_idx k <
j›: tapes already visited carry the decoded ‹M›-symbol in
‹buf›, the exact re-synced ‹posk›, and the block-end
head position; the rest retain their boundary values. Variable
per-tape cost (‹1› or ‹b + 2›), aggregate bounded by
‹j ⋅ (b + 2)›. Custom induction on ‹j›; the
inductive step's function-update bookkeeping rests on ‹k_idx›
injectivity (‹k ≠ k_unidx j ⟹ k_idx k ≠
j›).›
lemma ar_read_prefix:
fixes M :: "('q, 'a) ktm"
and cM :: "('a, 'q) ktc_config"
and c0 :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes vM: "valid_ktm M"
and qQ: "q ∈ Q_ktm M"
and kge2: "2 ≤ block_width (Γ_ktm M)"
and stg0: "ktc_state c0 = (q, AR_SimRead, 0, 0, buf0, dvec, posk0)"
and tcorr: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
(ktc_tape cM k) (ktc_tape c0 k)"
and ppos: "⋀k. ktc_pos c0 k = sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k)"
and pkok: "⋀k. posk0 k = AR_AtLE ⟷ ktc_pos cM k = 0"
and tapeG: "⋀k. ktc_tape cM k (ktc_pos cM k) ∈ Γ_ktm M"
and bufG: "⋀k. buf0 k ∈ Γ_ktm M ∪ {bl_ktm M}"
and pad0: "∀j ≥ k_ktm M. ktc_tape c0 j (ktc_pos c0 j) = BLANK4"
and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, 0, 0, buf0, dvec, posk0)"
shows "j ≤ k_ktm M - 1 ⟹
(∃c m. (c0, c) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ m
∧ m ≤ j * (block_width (Γ_ktm M) + 2)
∧ ktc_state c = (q, AR_SimRead, k_unidx j, 0,
(λk. if k_idx k < j then ktc_tape cM k (ktc_pos cM k) else buf0 k),
dvec,
(λk. if k_idx k < j
then (if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper)
else posk0 k))
∧ ktc_tape c = ktc_tape c0
∧ ktc_pos c = (λk. if k_idx k < j
then (if ktc_pos cM k = 0 then Suc 0
else sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k)
+ block_width (Γ_ktm M))
else ktc_pos c0 k))"
proof (induction j)
case 0
have "(c0, c0) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ 0" by simp
moreover have "ktc_state c0 = (q, AR_SimRead, k_unidx 0, 0,
(λk. if k_idx k < 0 then ktc_tape cM k (ktc_pos cM k) else buf0 k), dvec,
(λk. if k_idx k < 0
then (if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper)
else posk0 k))"
using stg0 by (simp add: k_unidx_zero)
ultimately show ?case
by (intro exI[where x = c0] exI[where x = 0]) (simp add: ppos)
next
case (Suc j)
have sucle: "Suc j ≤ k_ktm M - 1" by (rule Suc.prems)
have jcard: "j < k_ktm M" using sucle by simp
have sjcard: "Suc j < k_ktm M" using sucle by simp
have jle: "j ≤ k_ktm M - 1" using sucle by simp
let ?k = "block_width (Γ_ktm M)"
let ?tk = "k_unidx j"
let ?p = "ktc_pos cM ?tk"
let ?aM = "λk. ktc_tape cM k (ktc_pos cM k)"
let ?bf = "λi. (λk. if k_idx k < i then ?aM k else buf0 k)"
let ?pk = "λi. (λk. if k_idx k < i
then (if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper)
else posk0 k)"
let ?ps = "λi. (λk. if k_idx k < i
then (if ktc_pos cM k = 0 then Suc 0
else sim_pos ?k (ktc_pos cM k) + ?k)
else ktc_pos c0 k)"
have tkidx: "k_idx ?tk = j" by (rule k_idx_unidx[OF jcard])
have notlast: "¬ is_last_k M ?tk"
using is_last_k_unidx[OF jcard] sjcard by simp
have ksucc: "k_succ ?tk = k_unidx (Suc j)" by (rule k_succ_unidx[OF sjcard])
have inj: "inj_on k_idx UNIV" by (rule k_idx_inj)
have kne: "⋀k. k_idx k = j ⟹ k = ?tk"
proof -
fix k assume "k_idx k = j"
hence "k_idx k = k_idx ?tk" using tkidx by simp
thus "k = ?tk" using inj_on_eq_iff[OF inj UNIV_I UNIV_I] by simp
qed
obtain c m where
cm_rel: "(c0, c) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ m"
and m_le: "m ≤ j * (?k + 2)"
and c_st: "ktc_state c = (q, AR_SimRead, ?tk, 0, ?bf j, dvec, ?pk j)"
and c_tp: "ktc_tape c = ktc_tape c0"
and c_ps: "ktc_pos c = ?ps j"
using Suc.IH[OF jle] by blast
have tk_active: "?tk < k_ktm M" using jcard by (simp add: k_unidx_def)
have tk_corr: "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
(ktc_tape cM ?tk) (ktc_tape c ?tk)"
using tcorr[rule_format, OF tk_active] c_tp by simp
have tk_pos: "ktc_pos c ?tk = sim_pos ?k ?p"
using c_ps ppos tkidx by simp
have tk_pkok: "?pk j ?tk = AR_AtLE ⟷ ?p = 0"
using pkok tkidx by simp
have bf_in: "⋀k. ?bf j k ∈ Γ_ktm M ∪ {bl_ktm M}"
using tapeG bufG by auto
have tk_vsrc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimRead, ?tk, 0, ?bf j, dvec, ?pk j)"
using kge2 bf_in by (auto simp: ar_valid_stage_def)
have pad_c: "∀j' ≥ k_ktm M. ktc_tape c j' (ktc_pos c j') = BLANK4"
proof (intro allI impI)
fix j' assume jge: "k_ktm M ≤ j'"
have jnj: "¬ k_idx j' < j" using jge jcard by (simp add: k_idx_def)
have "ktc_tape c j' (ktc_pos c j') = ktc_tape c0 j' (ktc_pos c0 j')"
using c_tp c_ps jnj by simp
thus "ktc_tape c j' (ktc_pos c j') = BLANK4" using pad0 jge by simp
qed
have src_c: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, ?tk, 0, ?bf j, dvec, ?pk j)"
using src0 tk_active jcard by (auto simp: ar_stage_bounded_def k_idx_def)
obtain c' where
step: "(c, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (if ?p = 0 then 1 else ?k + 2)"
and c'_st: "ktc_state c' = (q, AR_SimRead, k_succ ?tk, 0,
(?bf j)(?tk := ?aM ?tk), dvec,
(?pk j)(?tk := if ?p = 0 then AR_AtLE
else if ?p = 1 then AR_AtFirstProper
else AR_AtFurtherProper))"
and c'_tp: "ktc_tape c' = ktc_tape c"
and c'_ps: "ktc_pos c' = (ktc_pos c)(?tk :=
if ?p = 0 then Suc 0 else sim_pos ?k ?p + ?k)"
using ar_read_tape_step[OF vM qQ kge2 notlast c_st tk_corr tk_pos
tk_pkok _ tk_vsrc pad_c src_c] tapeG by blast
have bf_eq: "(?bf j)(?tk := ?aM ?tk) = ?bf (Suc j)"
proof (rule ext)
fix k
show "((?bf j)(?tk := ?aM ?tk)) k = ?bf (Suc j) k"
proof (cases "k = ?tk")
case True thus ?thesis using tkidx by simp
next
case False
hence "k_idx k ≠ j" using kne by blast
thus ?thesis using False by (simp add: less_Suc_eq)
qed
qed
have pk_eq: "(?pk j)(?tk := if ?p = 0 then AR_AtLE
else if ?p = 1 then AR_AtFirstProper
else AR_AtFurtherProper) = ?pk (Suc j)"
proof (rule ext)
fix k
show "((?pk j)(?tk := if ?p = 0 then AR_AtLE
else if ?p = 1 then AR_AtFirstProper
else AR_AtFurtherProper)) k = ?pk (Suc j) k"
proof (cases "k = ?tk")
case True thus ?thesis using tkidx by simp
next
case False
hence "k_idx k ≠ j" using kne by blast
thus ?thesis using False by (simp add: less_Suc_eq)
qed
qed
have ps_eq: "(?ps j)(?tk := if ?p = 0 then Suc 0 else sim_pos ?k ?p + ?k)
= ?ps (Suc j)"
proof (rule ext)
fix k
show "((?ps j)(?tk := if ?p = 0 then Suc 0
else sim_pos ?k ?p + ?k)) k = ?ps (Suc j) k"
proof (cases "k = ?tk")
case True thus ?thesis using tkidx by simp
next
case False
hence "k_idx k ≠ j" using kne by blast
thus ?thesis using False by (simp add: less_Suc_eq)
qed
qed
have chain: "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (m + (if ?p = 0 then 1 else ?k + 2))"
proof -
have "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ m
O (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (if ?p = 0 then 1 else ?k + 2)"
using cm_rel step by (rule relcompI)
thus ?thesis by (simp add: relpow_add)
qed
have bound: "m + (if ?p = 0 then 1 else ?k + 2) ≤ Suc j * (?k + 2)"
using m_le by (cases "?p = 0") auto
show ?case
proof (intro exI[where x = c'] exI[where x = "m + (if ?p = 0 then 1 else ?k + 2)"]
conjI)
show "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (m + (if ?p = 0 then 1 else ?k + 2))" by (rule chain)
show "m + (if ?p = 0 then 1 else ?k + 2) ≤ Suc j * (?k + 2)"
by (rule bound)
show "ktc_state c' = (q, AR_SimRead, k_unidx (Suc j), 0, ?bf (Suc j), dvec,
?pk (Suc j))"
using c'_st ksucc bf_eq pk_eq by simp
show "ktc_tape c' = ktc_tape c0" using c'_tp c_tp by simp
show "ktc_pos c' = ?ps (Suc j)" using c'_ps c_ps ps_eq by simp
qed
qed
text ‹The full read phase: the prefix walk over the first
‹k_ktm M - 1› tapes followed by the unified last-tape read
‹ar_read_tape_finish_step›, landing at ‹AR_SimCompute›
(current-tape field ‹k_unidx 0›) with every tape's
‹M›-read symbol decoded into ‹buf›, every ‹posk›
re-synced exact, and every head left at its block-end (or position
‹1› for an ‹LE› tape). Aggregate cost ‹≤ k_ktm M
⋅ (b + 2)›. The final ‹buf›/‹posk›/position
vectors collapse from the ‹k_idx k < j› split because, on the
last tape, every other tape has index ‹< k_ktm M - 1›
(‹k_idx› bijective into ‹{..< k_ktm M}›).›
lemma ar_read_phase:
fixes M :: "('q, 'a) ktm"
and cM :: "('a, 'q) ktc_config"
and c0 :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes vM: "valid_ktm M"
and qQ: "q ∈ Q_ktm M"
and kge2: "2 ≤ block_width (Γ_ktm M)"
and stg0: "ktc_state c0 = (q, AR_SimRead, 0, 0, buf0, dvec, posk0)"
and tcorr: "∀k < k_ktm M. ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
(ktc_tape cM k) (ktc_tape c0 k)"
and ppos: "⋀k. ktc_pos c0 k = sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k)"
and pkok: "⋀k. posk0 k = AR_AtLE ⟷ ktc_pos cM k = 0"
and tapeG: "⋀k. ktc_tape cM k (ktc_pos cM k) ∈ Γ_ktm M"
and bufG: "⋀k. buf0 k ∈ Γ_ktm M ∪ {bl_ktm M}"
and pad0: "∀j ≥ k_ktm M. ktc_tape c0 j (ktc_pos c0 j) = BLANK4"
and src0: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, 0, 0, buf0, dvec, posk0)"
shows "∃c m. (c0, c) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ m
∧ m ≤ k_ktm M * (block_width (Γ_ktm M) + 2)
∧ ktc_state c = (q, AR_SimCompute, k_unidx 0, 0,
(λk. if k < k_ktm M then ktc_tape cM k (ktc_pos cM k) else buf0 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 posk0 k))
∧ ktc_tape c = ktc_tape c0
∧ ktc_pos c = (λk. if k < k_ktm M
then (if ktc_pos cM k = 0 then Suc 0
else sim_pos (block_width (Γ_ktm M)) (ktc_pos cM k) + block_width (Γ_ktm M))
else ktc_pos c0 k)"
proof -
let ?k = "block_width (Γ_ktm M)"
let ?N = "k_ktm M"
let ?m1 = "?N - 1"
let ?tl = "k_unidx ?m1"
let ?p = "ktc_pos cM ?tl"
let ?aM = "λk. ktc_tape cM k (ktc_pos cM k)"
have card1: "0 < ?N" using vM by (cases M) auto
have m1suc: "?N = Suc ?m1" using card1 by simp
have m1card: "?m1 < ?N" using card1 by simp
have m1lt: "?m1 < k_ktm M" using card1 by simp
have tl_eq: "?tl = ?m1" by (simp add: k_unidx_def)
have tlidx: "k_idx ?tl = ?m1" by (rule k_idx_unidx[OF m1card])
have tl_active: "?tl < k_ktm M" using m1lt tl_eq by simp
have islast: "is_last_k M ?tl" using is_last_k_unidx[OF m1card] m1suc by simp
have cond: "(k < ?m1) = (k < k_ktm M)" if "k ≠ ?m1" for k
using that m1suc by (auto simp: less_Suc_eq)
let ?bf = "λk. if k_idx k < ?m1 then ?aM k else buf0 k"
let ?pk = "λk. if k_idx k < ?m1
then (if ktc_pos cM k = 0 then AR_AtLE
else if ktc_pos cM k = 1 then AR_AtFirstProper
else AR_AtFurtherProper)
else posk0 k"
let ?ps = "λk. if k_idx k < ?m1
then (if ktc_pos cM k = 0 then Suc 0
else sim_pos ?k (ktc_pos cM k) + ?k)
else ktc_pos c0 k"
obtain c1 m1 where
c1_rel: "(c0, c1) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ m1"
and m1_le: "m1 ≤ ?m1 * (?k + 2)"
and c1_st: "ktc_state c1 = (q, AR_SimRead, ?tl, 0, ?bf, dvec, ?pk)"
and c1_tp: "ktc_tape c1 = ktc_tape c0"
and c1_ps: "ktc_pos c1 = ?ps"
using ar_read_prefix[OF vM qQ kge2 stg0 tcorr ppos pkok tapeG bufG pad0 src0,
of ?m1]
by auto
have tl_corr: "ar_tape_correspondence (Γ_ktm M) (le_ktm M) (bl_ktm M)
(ktc_tape cM ?tl) (ktc_tape c1 ?tl)"
using tcorr[rule_format, OF tl_active] c1_tp by simp
have tl_pos: "ktc_pos c1 ?tl = sim_pos ?k ?p"
using c1_ps ppos tlidx by simp
have tl_pkok: "?pk ?tl = AR_AtLE ⟷ ?p = 0"
using pkok tlidx by simp
have bf_in: "⋀k. ?bf k ∈ Γ_ktm M ∪ {bl_ktm M}"
using tapeG bufG by auto
have tl_vsrc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimRead, ?tl, 0, ?bf, dvec, ?pk)"
using kge2 bf_in by (auto simp: ar_valid_stage_def)
have tail_idx: "⋀j. k_ktm M ≤ j ⟹ ¬ k_idx j < ?m1"
using m1suc unfolding k_idx_def by linarith
have pad_c1: "∀j ≥ k_ktm M. ktc_tape c1 j (ktc_pos c1 j) = BLANK4"
proof (intro allI impI)
fix j assume jge: "k_ktm M ≤ j"
have "ktc_tape c1 j (ktc_pos c1 j) = ktc_tape c0 j (ktc_pos c0 j)"
using c1_tp c1_ps tail_idx[OF jge] by simp
thus "ktc_tape c1 j (ktc_pos c1 j) = BLANK4" using pad0 jge by simp
qed
have src_c1: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimRead, ?tl, 0, ?bf, dvec, ?pk)"
using src0 tl_active tail_idx by (auto simp: ar_stage_bounded_def)
obtain c2 where
step: "(c1, c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (if ?p = 0 then 1 else ?k + 2)"
and c2_st: "ktc_state c2 = (q, AR_SimCompute, k_unidx 0, 0,
?bf(?tl := ?aM ?tl), dvec,
?pk(?tl := if ?p = 0 then AR_AtLE
else if ?p = 1 then AR_AtFirstProper
else AR_AtFurtherProper))"
and c2_tp: "ktc_tape c2 = ktc_tape c1"
and c2_ps: "ktc_pos c2 = (ktc_pos c1)(?tl :=
if ?p = 0 then Suc 0 else sim_pos ?k ?p + ?k)"
using ar_read_tape_finish_step[OF vM qQ kge2 islast c1_st tl_corr
tl_pos tl_pkok _ tl_vsrc pad_c1 src_c1] tapeG
by blast
have bf_full: "?bf(?tl := ?aM ?tl)
= (λk. if k < k_ktm M then ?aM k else buf0 k)"
proof (rule ext)
fix k
show "(?bf(?tl := ?aM ?tl)) k = (if k < k_ktm M then ?aM k else buf0 k)"
proof (cases "k = ?tl")
case True thus ?thesis using tl_eq m1lt by simp
next
case False
hence kne: "k ≠ ?m1" using tl_eq by simp
show ?thesis using False kne cond[OF kne] by (simp add: k_idx_def)
qed
qed
have pk_full: "?pk(?tl := if ?p = 0 then AR_AtLE
else if ?p = 1 then AR_AtFirstProper
else AR_AtFurtherProper)
= (λ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 posk0 k)"
proof (rule ext)
fix k
show "(?pk(?tl := if ?p = 0 then AR_AtLE
else if ?p = 1 then AR_AtFirstProper
else AR_AtFurtherProper)) 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 posk0 k)"
proof (cases "k = ?tl")
case True thus ?thesis using tl_eq m1lt by simp
next
case False
hence kne: "k ≠ ?m1" using tl_eq by simp
show ?thesis using False kne cond[OF kne] by (simp add: k_idx_def)
qed
qed
have ps_full: "(ktc_pos c1)(?tl := if ?p = 0 then Suc 0
else sim_pos ?k ?p + ?k)
= (λ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 c0 k)"
proof (rule ext)
fix k
show "((ktc_pos c1)(?tl := if ?p = 0 then Suc 0
else sim_pos ?k ?p + ?k)) 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 c0 k)"
proof (cases "k = ?tl")
case True thus ?thesis using tl_eq m1lt by simp
next
case False
hence kne: "k ≠ ?m1" using tl_eq by simp
show ?thesis
using False kne cond[OF kne] c1_ps by (simp add: k_idx_def)
qed
qed
have chain: "(c0, c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (m1 + (if ?p = 0 then 1 else ?k + 2))"
proof -
have "(c0, c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ m1
O (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (if ?p = 0 then 1 else ?k + 2)"
using c1_rel step by (rule relcompI)
thus ?thesis by (simp add: relpow_add)
qed
have bound: "m1 + (if ?p = 0 then 1 else ?k + 2) ≤ ?N * (?k + 2)"
proof -
obtain Nm where Nm: "?N = Suc Nm" using card1 by (cases ?N) auto
have e1: "?N * (?k + 2) = (?k + 2) + Nm * (?k + 2)" by (simp add: Nm)
have e2: "m1 ≤ Nm * (?k + 2)" using m1_le Nm by simp
have e3: "(if ?p = 0 then 1 else ?k + 2) ≤ ?k + 2" by simp
show ?thesis using e1 e2 e3 by linarith
qed
show ?thesis
proof (intro exI[where x = c2]
exI[where x = "m1 + (if ?p = 0 then 1 else ?k + 2)"] conjI)
show "(c0, c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_read M)) ^^ (m1 + (if ?p = 0 then 1 else ?k + 2))" by (rule chain)
show "m1 + (if ?p = 0 then 1 else ?k + 2) ≤ ?N * (?k + 2)" by (rule bound)
show "ktc_state c2 = (q, AR_SimCompute, k_unidx 0, 0,
(λk. if k < k_ktm M then ?aM k else buf0 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 posk0 k))"
using c2_st bf_full pk_full by simp
show "ktc_tape c2 = ktc_tape c0" using c2_tp c1_tp by simp
show "ktc_pos c2 = (λ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 c0 k)"
using c2_ps ps_full by simp
qed
qed
end