Theory Multitape_Alphabet_Reduction.AlphabetReduction_ForwardAdvance
theory AlphabetReduction_ForwardAdvance
imports AlphabetReduction_ForwardWrite
begin
subsection ‹Advance phase›
lemma ar_advance_walk_loop:
fixes M :: "('q, 'a) ktm"
and c0 :: "(sym4, 'q × 'a ar_stage) ktc_config"
assumes vM: "valid_ktm M"
and qQ: "q ∈ Q_ktm M"
and stg: "ktc_state c0 = (q, AR_SimAdvance, tk, 0, buf, dvec, posk)"
and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
and ndisp: "n < ar_disp (block_width (Γ_ktm M)) (dvec tk) (posk tk)"
and notLE: "⋀j. j < n ⟹ ktc_tape c0 tk (ktc_pos c0 tk - j) ≠ LE4"
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_SimAdvance, tk, 0, buf, dvec, posk)"
shows "∃c'. (c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)) ^^ n
∧ ktc_state c' = (q, AR_SimAdvance, tk, n, buf, dvec, posk)
∧ ktc_pos c' tk = ktc_pos c0 tk - n
∧ ktc_tape c' = ktc_tape c0
∧ (∀k'. k' ≠ tk ⟶ ktc_pos c' k' = ktc_pos c0 k')"
proof -
let ?k = "block_width (Γ_ktm M)"
let ?D = "ar_disp ?k (dvec tk) (posk tk)"
let ?start = "ktc_pos c0 tk"
have kpos: "0 < ?k" using block_width_pos[of "Γ_ktm M"] by simp
let ?P = "λj c.
ktc_state c = (q, AR_SimAdvance, tk, j, buf, dvec, posk)
∧ ktc_pos c tk = ?start - j
∧ ktc_tape c = ktc_tape c0
∧ (∀k'. k' ≠ tk ⟶ ktc_pos c k' = ktc_pos c0 k')"
have mybase: "?P 0 c0" using stg by simp
have mystep:
"⋀j cc. ⟦ j < n; ?P j cc ⟧
⟹ ∃c''. (cc, c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M))
∧ ?P (Suc j) c''"
proof -
fix j cc
assume jlt: "j < n" and Pj: "?P j cc"
from Pj have st_cc:
"ktc_state cc = (q, AR_SimAdvance, tk, j, buf, dvec, posk)"
and pos_cc: "ktc_pos cc tk = ?start - j"
and tape_cc: "ktc_tape cc = ktc_tape c0"
and other_cc: "∀k'. k' ≠ tk ⟶ ktc_pos cc k' = ktc_pos c0 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 c0 j' (ktc_pos c0 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_SimAdvance, tk, j, buf, dvec, posk)"
using src0 by (simp add: ar_stage_bounded_def)
have sucj_lt: "Suc j < ?D" using jlt ndisp by linarith
have j_lt2k: "j < 2 * ?k"
using sucj_lt ar_disp_le_2k[OF kpos, of "dvec tk" "posk tk"] by linarith
have vsrc_cc: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimAdvance, tk, j, buf, dvec, posk)"
using j_lt2k buf_valid by (simp add: ar_valid_stage_def)
have notLE_cc: "ktc_tape cc tk (ktc_pos cc tk) ≠ LE4"
using tape_cc pos_cc notLE[OF jlt] by simp
obtain c'' where
bstep: "(cc, c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M))"
and bst_state: "ktc_state c'' = (q, AR_SimAdvance, tk, Suc j, buf, dvec, posk)"
and bst_tape: "ktc_tape c'' = ktc_tape cc"
and bst_pos: "ktc_pos c'' = (ktc_pos cc)(tk := ktc_pos cc tk - 1)"
using ar_advance_walk_step[OF vM st_cc qQ notLE_cc sucj_lt vsrc_cc pad_cc src_cc] by blast
have pos_eq: "ktc_pos c'' tk = ?start - Suc j"
using bst_pos pos_cc by simp
have tape_eq: "ktc_tape c'' = ktc_tape c0" using bst_tape tape_cc by simp
have other_eq: "∀k'. k' ≠ tk ⟶ ktc_pos c'' k' = ktc_pos c0 k'"
using bst_pos other_cc by simp
show "∃c''. (cc, c'') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M))
∧ ?P (Suc j) c''"
using bstep bst_state pos_eq tape_eq other_eq by blast
qed
have loop:
"∃c'. (c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)) ^^ n
∧ ?P n c'"
by (rule relpow_invariant_chain
[where P = ?P and n = n, OF mystep mybase])
obtain c' where
chain: "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)) ^^ n"
and Pfin: "?P n c'"
using loop by blast
show ?thesis
proof (intro exI[where x = c'] conjI)
show "(c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)) ^^ n" by (rule chain)
show "ktc_state c' = (q, AR_SimAdvance, tk, n, buf, dvec, posk)"
using Pfin by simp
show "ktc_pos c' tk = ?start - n" using Pfin by simp
show "ktc_tape c' = ktc_tape c0" using Pfin by simp
show "∀k'. k' ≠ tk ⟶ ktc_pos c' k' = ktc_pos c0 k'" using Pfin by simp
qed
qed
lemma ar_advance_tape_step:
fixes M :: "('q, 'a) ktm"
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 notlast: "¬ is_last_k M tk"
and stg: "ktc_state c0 = (q, AR_SimAdvance, tk, 0, buf, dvec, posk)"
and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
and dge1: "dvec tk ≠ MoveR
⟹ 0 < ar_disp (block_width (Γ_ktm M)) (dvec tk) (posk tk)"
and notLE: "⋀m. m < ar_disp (block_width (Γ_ktm M)) (dvec tk) (posk tk)
⟹ ktc_tape c0 tk (ktc_pos c0 tk - m) ≠ LE4"
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_SimAdvance, tk, 0, buf, dvec, posk)"
shows "∃c'. (c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M))
^^ (if dvec tk = MoveR then 1
else ar_disp (block_width (Γ_ktm M)) (dvec tk) (posk tk))
∧ ktc_state c' = (q, AR_SimAdvance, k_succ tk, 0, buf, dvec,
posk(tk := ar_newpos (dvec tk) (posk tk)))
∧ ktc_tape c' = ktc_tape c0
∧ ktc_pos c' = (if dvec tk = MoveR then ktc_pos c0
else (ktc_pos c0)(tk := ktc_pos c0 tk
- ar_disp (block_width (Γ_ktm M)) (dvec tk) (posk tk)))"
proof -
let ?k = "block_width (Γ_ktm M)"
let ?R = "ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)"
let ?D = "ar_disp ?k (dvec tk) (posk tk)"
let ?start = "ktc_pos c0 tk"
have kpos: "0 < ?k" using kge2 by simp
show ?thesis
proof (cases "dvec tk = MoveR")
case True
have vsrc0: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimAdvance, tk, 0, buf, dvec, posk)"
using kpos buf_valid by (simp add: ar_valid_stage_def)
have fire: "(dvec tk = MoveR ∧ (0::nat) = 0)
∨ (dvec tk ≠ MoveR ∧ ktc_tape c0 tk (ktc_pos c0 tk) ≠ LE4
∧ Suc 0 = ?D)"
using True by simp
obtain c' where
step: "(c0, c') ∈ ?R"
and st: "ktc_state c' = (q, AR_SimAdvance, k_succ tk, 0, buf, dvec,
posk(tk := ar_newpos (dvec tk) (posk tk)))"
and tp: "ktc_tape c' = ktc_tape c0"
and ps: "ktc_pos c' = (if dvec tk = MoveR then ktc_pos c0
else (ktc_pos c0)(tk := ktc_pos c0 tk - 1))"
using ar_advance_boundary_step[OF vM stg qQ notlast fire vsrc0 pad0 src0] by blast
show ?thesis
proof (intro exI[where x = c'] conjI)
show "(c0, c') ∈ ?R ^^ (if dvec tk = MoveR then 1 else ?D)"
using step True by simp
show "ktc_state c' = (q, AR_SimAdvance, k_succ tk, 0, buf, dvec,
posk(tk := ar_newpos (dvec tk) (posk tk)))" by (rule st)
show "ktc_tape c' = ktc_tape c0" by (rule tp)
show "ktc_pos c' = (if dvec tk = MoveR then ktc_pos c0
else (ktc_pos c0)(tk := ktc_pos c0 tk - ?D))"
using ps True by simp
qed
next
case False
have Dpos: "0 < ?D" using dge1[OF False] by simp
obtain DD where DD: "?D = Suc DD" using Dpos by (cases ?D) auto
have ndisp: "DD < ?D" using DD by simp
have notLE_loop: "⋀j. j < DD ⟹ ktc_tape c0 tk (?start - j) ≠ LE4"
proof -
fix j assume "j < DD"
hence "j < ?D" using DD by simp
thus "ktc_tape c0 tk (?start - j) ≠ LE4" by (rule notLE)
qed
obtain cmid where
lstep: "(c0, cmid) ∈ ?R ^^ DD"
and lst: "ktc_state cmid = (q, AR_SimAdvance, tk, DD, buf, dvec, posk)"
and lpos: "ktc_pos cmid tk = ?start - DD"
and ltape: "ktc_tape cmid = ktc_tape c0"
and lother: "∀k'. k' ≠ tk ⟶ ktc_pos cmid k' = ktc_pos c0 k'"
using ar_advance_walk_loop[OF vM qQ stg buf_valid ndisp notLE_loop pad0 src0] by blast
have DD_lt2k: "DD < 2 * ?k"
using DD ar_disp_le_2k[OF kpos, of "dvec tk" "posk tk"] by linarith
have vsrcmid: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimAdvance, tk, DD, buf, dvec, posk)"
using DD_lt2k buf_valid by (simp add: ar_valid_stage_def)
have tk_lt: "tk < k_ktm M" using src0 by (simp add: ar_stage_bounded_def)
have pad_cmid: "∀j ≥ k_ktm M. ktc_tape cmid j (ktc_pos cmid 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 cmid j (ktc_pos cmid j) = ktc_tape c0 j (ktc_pos c0 j)"
using ltape lother jne by simp
thus "ktc_tape cmid j (ktc_pos cmid j) = BLANK4" using pad0 jge by simp
qed
have src_cmid: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimAdvance, tk, DD, buf, dvec, posk)"
using src0 by (simp add: ar_stage_bounded_def)
have notLE_b: "ktc_tape cmid tk (ktc_pos cmid tk) ≠ LE4"
using ltape lpos notLE[OF ndisp] by simp
have fire: "(dvec tk = MoveR ∧ DD = 0)
∨ (dvec tk ≠ MoveR
∧ ktc_tape cmid tk (ktc_pos cmid tk) ≠ LE4
∧ Suc DD = ?D)"
using False notLE_b DD by simp
obtain c' where
bstep: "(cmid, c') ∈ ?R"
and bst: "ktc_state c' = (q, AR_SimAdvance, k_succ tk, 0, buf, dvec,
posk(tk := ar_newpos (dvec tk) (posk tk)))"
and btp: "ktc_tape c' = ktc_tape cmid"
and bps: "ktc_pos c' = (if dvec tk = MoveR then ktc_pos cmid
else (ktc_pos cmid)(tk := ktc_pos cmid tk - 1))"
using ar_advance_boundary_step[OF vM lst qQ notlast fire vsrcmid pad_cmid src_cmid] by blast
have bps_ne: "ktc_pos c' = (ktc_pos cmid)(tk := ktc_pos cmid tk - 1)"
using bps False by simp
have chainD: "(c0, c') ∈ ?R ^^ ?D"
proof -
have "(c0, c') ∈ ?R ^^ Suc DD" by (rule relpow_Suc_I[OF lstep bstep])
thus ?thesis using DD by simp
qed
have ps_final: "ktc_pos c' = (ktc_pos c0)(tk := ?start - ?D)"
proof (rule ext)
fix k'
show "ktc_pos c' k' = ((ktc_pos c0)(tk := ?start - ?D)) k'"
proof (cases "k' = tk")
case True
have "ktc_pos c' tk = ktc_pos cmid tk - 1" using bps_ne by simp
also have "… = (?start - DD) - 1" using lpos by simp
also have "… = ?start - ?D" using DD by simp
finally show ?thesis using True by simp
next
case False
have "ktc_pos c' k' = ktc_pos cmid k'" using bps_ne False by simp
also have "… = ktc_pos c0 k'" using lother False by simp
finally show ?thesis using False by simp
qed
qed
have tp_final: "ktc_tape c' = ktc_tape c0" using btp ltape by simp
show ?thesis
proof (intro exI[where x = c'] conjI)
show "(c0, c') ∈ ?R ^^ (if dvec tk = MoveR then 1 else ?D)"
using chainD False by simp
show "ktc_state c' = (q, AR_SimAdvance, k_succ tk, 0, buf, dvec,
posk(tk := ar_newpos (dvec tk) (posk tk)))" by (rule bst)
show "ktc_tape c' = ktc_tape c0" by (rule tp_final)
show "ktc_pos c' = (if dvec tk = MoveR then ktc_pos c0
else (ktc_pos c0)(tk := ktc_pos c0 tk - ?D))"
using ps_final False by simp
qed
qed
qed
lemma ar_advance_tape_finish_step:
fixes M :: "('q, 'a) ktm"
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 last: "is_last_k M tk"
and stg: "ktc_state c0 = (q, AR_SimAdvance, tk, 0, buf, dvec, posk)"
and buf_valid: "∀k. buf k ∈ Γ_ktm M ∪ {bl_ktm M}"
and dge1: "dvec tk ≠ MoveR
⟹ 0 < ar_disp (block_width (Γ_ktm M)) (dvec tk) (posk tk)"
and notLE: "⋀m. m < ar_disp (block_width (Γ_ktm M)) (dvec tk) (posk tk)
⟹ ktc_tape c0 tk (ktc_pos c0 tk - m) ≠ LE4"
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_SimAdvance, tk, 0, buf, dvec, posk)"
shows "∃c'. (c0, c') ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M))
^^ (if dvec tk = MoveR then 1
else ar_disp (block_width (Γ_ktm M)) (dvec tk) (posk tk))
∧ ktc_state c' = (q, AR_SimNext, k_unidx 0, 0, buf, dvec,
posk(tk := ar_newpos (dvec tk) (posk tk)))
∧ ktc_tape c' = ktc_tape c0
∧ ktc_pos c' = (if dvec tk = MoveR then ktc_pos c0
else (ktc_pos c0)(tk := ktc_pos c0 tk
- ar_disp (block_width (Γ_ktm M)) (dvec tk) (posk tk)))"
proof -
let ?k = "block_width (Γ_ktm M)"
let ?R = "ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)"
let ?D = "ar_disp ?k (dvec tk) (posk tk)"
let ?start = "ktc_pos c0 tk"
have kpos: "0 < ?k" using kge2 by simp
show ?thesis
proof (cases "dvec tk = MoveR")
case True
have vsrc0: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimAdvance, tk, 0, buf, dvec, posk)"
using kpos buf_valid by (simp add: ar_valid_stage_def)
have fire: "(dvec tk = MoveR ∧ (0::nat) = 0)
∨ (dvec tk ≠ MoveR ∧ ktc_tape c0 tk (ktc_pos c0 tk) ≠ LE4
∧ Suc 0 = ?D)"
using True by simp
obtain c' where
step: "(c0, c') ∈ ?R"
and st: "ktc_state c' = (q, AR_SimNext, k_unidx 0, 0, buf, dvec,
posk(tk := ar_newpos (dvec tk) (posk tk)))"
and tp: "ktc_tape c' = ktc_tape c0"
and ps: "ktc_pos c' = (if dvec tk = MoveR then ktc_pos c0
else (ktc_pos c0)(tk := ktc_pos c0 tk - 1))"
using ar_advance_finish_step[OF vM stg qQ last fire vsrc0 pad0 src0] by blast
show ?thesis
proof (intro exI[where x = c'] conjI)
show "(c0, c') ∈ ?R ^^ (if dvec tk = MoveR then 1 else ?D)"
using step True by simp
show "ktc_state c' = (q, AR_SimNext, k_unidx 0, 0, buf, dvec,
posk(tk := ar_newpos (dvec tk) (posk tk)))" by (rule st)
show "ktc_tape c' = ktc_tape c0" by (rule tp)
show "ktc_pos c' = (if dvec tk = MoveR then ktc_pos c0
else (ktc_pos c0)(tk := ktc_pos c0 tk - ?D))"
using ps True by simp
qed
next
case False
have Dpos: "0 < ?D" using dge1[OF False] by simp
obtain DD where DD: "?D = Suc DD" using Dpos by (cases ?D) auto
have ndisp: "DD < ?D" using DD by simp
have notLE_loop: "⋀j. j < DD ⟹ ktc_tape c0 tk (?start - j) ≠ LE4"
proof -
fix j assume "j < DD"
hence "j < ?D" using DD by simp
thus "ktc_tape c0 tk (?start - j) ≠ LE4" by (rule notLE)
qed
obtain cmid where
lstep: "(c0, cmid) ∈ ?R ^^ DD"
and lst: "ktc_state cmid = (q, AR_SimAdvance, tk, DD, buf, dvec, posk)"
and lpos: "ktc_pos cmid tk = ?start - DD"
and ltape: "ktc_tape cmid = ktc_tape c0"
and lother: "∀k'. k' ≠ tk ⟶ ktc_pos cmid k' = ktc_pos c0 k'"
using ar_advance_walk_loop[OF vM qQ stg buf_valid ndisp notLE_loop pad0 src0] by blast
have DD_lt2k: "DD < 2 * ?k"
using DD ar_disp_le_2k[OF kpos, of "dvec tk" "posk tk"] by linarith
have vsrcmid: "ar_valid_stage (Γ_ktm M) (bl_ktm M)
(AR_SimAdvance, tk, DD, buf, dvec, posk)"
using DD_lt2k buf_valid by (simp add: ar_valid_stage_def)
have tk_lt: "tk < k_ktm M" using src0 by (simp add: ar_stage_bounded_def)
have pad_cmid: "∀j ≥ k_ktm M. ktc_tape cmid j (ktc_pos cmid 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 cmid j (ktc_pos cmid j) = ktc_tape c0 j (ktc_pos c0 j)"
using ltape lother jne by simp
thus "ktc_tape cmid j (ktc_pos cmid j) = BLANK4" using pad0 jge by simp
qed
have src_cmid: "ar_stage_bounded (bl_ktm M) (k_ktm M)
(AR_SimAdvance, tk, DD, buf, dvec, posk)"
using src0 by (simp add: ar_stage_bounded_def)
have notLE_b: "ktc_tape cmid tk (ktc_pos cmid tk) ≠ LE4"
using ltape lpos notLE[OF ndisp] by simp
have fire: "(dvec tk = MoveR ∧ DD = 0)
∨ (dvec tk ≠ MoveR
∧ ktc_tape cmid tk (ktc_pos cmid tk) ≠ LE4
∧ Suc DD = ?D)"
using False notLE_b DD by simp
obtain c' where
bstep: "(cmid, c') ∈ ?R"
and bst: "ktc_state c' = (q, AR_SimNext, k_unidx 0, 0, buf, dvec,
posk(tk := ar_newpos (dvec tk) (posk tk)))"
and btp: "ktc_tape c' = ktc_tape cmid"
and bps: "ktc_pos c' = (if dvec tk = MoveR then ktc_pos cmid
else (ktc_pos cmid)(tk := ktc_pos cmid tk - 1))"
using ar_advance_finish_step[OF vM lst qQ last fire vsrcmid pad_cmid src_cmid] by blast
have bps_ne: "ktc_pos c' = (ktc_pos cmid)(tk := ktc_pos cmid tk - 1)"
using bps False by simp
have chainD: "(c0, c') ∈ ?R ^^ ?D"
proof -
have "(c0, c') ∈ ?R ^^ Suc DD" by (rule relpow_Suc_I[OF lstep bstep])
thus ?thesis using DD by simp
qed
have ps_final: "ktc_pos c' = (ktc_pos c0)(tk := ?start - ?D)"
proof (rule ext)
fix k'
show "ktc_pos c' k' = ((ktc_pos c0)(tk := ?start - ?D)) k'"
proof (cases "k' = tk")
case True
have "ktc_pos c' tk = ktc_pos cmid tk - 1" using bps_ne by simp
also have "… = (?start - DD) - 1" using lpos by simp
also have "… = ?start - ?D" using DD by simp
finally show ?thesis using True by simp
next
case False
have "ktc_pos c' k' = ktc_pos cmid k'" using bps_ne False by simp
also have "… = ktc_pos c0 k'" using lother False by simp
finally show ?thesis using False by simp
qed
qed
have tp_final: "ktc_tape c' = ktc_tape c0" using btp ltape by simp
show ?thesis
proof (intro exI[where x = c'] conjI)
show "(c0, c') ∈ ?R ^^ (if dvec tk = MoveR then 1 else ?D)"
using chainD False by simp
show "ktc_state c' = (q, AR_SimNext, k_unidx 0, 0, buf, dvec,
posk(tk := ar_newpos (dvec tk) (posk tk)))" by (rule bst)
show "ktc_tape c' = ktc_tape c0" by (rule tp_final)
show "ktc_pos c' = (if dvec tk = MoveR then ktc_pos c0
else (ktc_pos c0)(tk := ktc_pos c0 tk - ?D))"
using ps_final False by simp
qed
qed
qed
lemma ar_advance_prefix:
fixes M :: "('q, 'a) ktm"
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_SimAdvance, 0, 0, buf0, dvec, posk0)"
and buf_valid: "∀k. buf0 k ∈ Γ_ktm M ∪ {bl_ktm M}"
and dge1: "∀k < k_ktm M. dvec k ≠ MoveR
⟶ 0 < ar_disp (block_width (Γ_ktm M)) (dvec k) (posk0 k)"
and notLE: "∀k < k_ktm M. ∀m. m < ar_disp (block_width (Γ_ktm M)) (dvec k) (posk0 k)
⟶ ktc_tape c0 k (ktc_pos c0 k - m) ≠ LE4"
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_SimAdvance, 0, 0, buf0, dvec, posk0)"
shows "j ≤ k_ktm M - 1 ⟹
(∃c m. (c0, c) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)) ^^ m
∧ m ≤ j * (2 * block_width (Γ_ktm M))
∧ ktc_state c = (q, AR_SimAdvance, k_unidx j, 0, buf0, dvec,
(λk. if k_idx k < j then ar_newpos (dvec k) (posk0 k)
else posk0 k))
∧ ktc_tape c = ktc_tape c0
∧ ktc_pos c = (λk. if k_idx k < j
then (if dvec k = MoveR then ktc_pos c0 k
else ktc_pos c0 k
- ar_disp (block_width (Γ_ktm M)) (dvec k) (posk0 k))
else ktc_pos c0 k))"
proof (induction j)
case 0
let ?pk0 = "λk. if k_idx k < (0::nat) then ar_newpos (dvec k) (posk0 k)
else posk0 k"
have "(c0, c0) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)) ^^ 0" by simp
moreover have "ktc_state c0 = (q, AR_SimAdvance, k_unidx 0, 0, buf0, dvec, ?pk0)"
using stg0 by (simp add: k_unidx_zero)
ultimately show ?case
by (intro exI[where x = c0] exI[where x = 0]) simp
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 ?R = "ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)"
let ?tk = "k_unidx j"
let ?pk = "λi. (λk. if k_idx k < i then ar_newpos (dvec k) (posk0 k)
else posk0 k)"
let ?ps = "λi. (λk. if k_idx k < i
then (if dvec k = MoveR then ktc_pos c0 k
else ktc_pos c0 k - ar_disp ?k (dvec k) (posk0 k))
else ktc_pos c0 k)"
have kpos: "0 < ?k" using kge2 by simp
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) ∈ ?R ^^ m"
and m_le: "m ≤ j * (2 * ?k)"
and c_st: "ktc_state c = (q, AR_SimAdvance, ?tk, 0, buf0, 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 pkj_tk: "?pk j ?tk = posk0 ?tk" using tkidx by simp
have psj_tk: "?ps j ?tk = ktc_pos c0 ?tk" using tkidx by simp
have c_pos_tk: "ktc_pos c ?tk = ktc_pos c0 ?tk" using c_ps psj_tk by simp
have tk_active: "?tk < k_ktm M" using jcard by (simp add: k_unidx_def)
have tk_dge1: "dvec ?tk ≠ MoveR ⟹ 0 < ar_disp ?k (dvec ?tk) (?pk j ?tk)"
using dge1[rule_format, OF tk_active] pkj_tk by simp
have tk_notLE: "⋀m. m < ar_disp ?k (dvec ?tk) (?pk j ?tk)
⟹ ktc_tape c ?tk (ktc_pos c ?tk - m) ≠ LE4"
proof -
fix m assume "m < ar_disp ?k (dvec ?tk) (?pk j ?tk)"
hence mlt: "m < ar_disp ?k (dvec ?tk) (posk0 ?tk)" using pkj_tk by simp
have "ktc_tape c ?tk (ktc_pos c ?tk - m) = ktc_tape c0 ?tk (ktc_pos c0 ?tk - m)"
using c_tp c_pos_tk by simp
thus "ktc_tape c ?tk (ktc_pos c ?tk - m) ≠ LE4"
using notLE[rule_format, OF tk_active mlt] by simp
qed
have tail_idx: "⋀j'. k_ktm M ≤ j' ⟹ ¬ k_idx j' < j"
using jcard unfolding k_idx_def by linarith
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 "ktc_tape c j' (ktc_pos c j') = ktc_tape c0 j' (ktc_pos c0 j')"
using c_tp c_ps tail_idx[OF jge] 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_SimAdvance, ?tk, 0, buf0, dvec, ?pk j)"
using src0 tk_active tail_idx by (auto simp: ar_stage_bounded_def)
obtain c' where
step: "(c, c') ∈ ?R ^^ (if dvec ?tk = MoveR then 1
else ar_disp ?k (dvec ?tk) (?pk j ?tk))"
and c'_st: "ktc_state c' = (q, AR_SimAdvance, k_succ ?tk, 0, buf0, dvec,
(?pk j)(?tk := ar_newpos (dvec ?tk) (?pk j ?tk)))"
and c'_tp: "ktc_tape c' = ktc_tape c"
and c'_ps: "ktc_pos c' = (if dvec ?tk = MoveR then ktc_pos c
else (ktc_pos c)(?tk := ktc_pos c ?tk
- ar_disp ?k (dvec ?tk) (?pk j ?tk)))"
using ar_advance_tape_step[OF vM qQ kge2 notlast c_st buf_valid tk_dge1 tk_notLE
pad_c src_c]
by blast
have pk_eq: "(?pk j)(?tk := ar_newpos (dvec ?tk) (?pk j ?tk)) = ?pk (Suc j)"
proof (rule ext)
fix k
show "((?pk j)(?tk := ar_newpos (dvec ?tk) (?pk j ?tk))) 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: "(if dvec ?tk = MoveR then ktc_pos c
else (ktc_pos c)(?tk := ktc_pos c ?tk
- ar_disp ?k (dvec ?tk) (?pk j ?tk))) = ?ps (Suc j)"
proof (rule ext)
fix k
show "(if dvec ?tk = MoveR then ktc_pos c
else (ktc_pos c)(?tk := ktc_pos c ?tk
- ar_disp ?k (dvec ?tk) (?pk j ?tk))) k = ?ps (Suc j) k"
proof (cases "k = ?tk")
case True thus ?thesis using c_ps tkidx by simp
next
case False
hence "k_idx k ≠ j" using kne by blast
thus ?thesis using False c_ps by (simp add: less_Suc_eq)
qed
qed
have chain: "(c0, c') ∈ ?R ^^ (m + (if dvec ?tk = MoveR then 1
else ar_disp ?k (dvec ?tk) (?pk j ?tk)))"
proof -
have "(c0, c') ∈ ?R ^^ m
O ?R ^^ (if dvec ?tk = MoveR then 1
else ar_disp ?k (dvec ?tk) (?pk j ?tk))"
using cm_rel step by (rule relcompI)
thus ?thesis by (simp add: relpow_add)
qed
have bound: "m + (if dvec ?tk = MoveR then 1
else ar_disp ?k (dvec ?tk) (?pk j ?tk)) ≤ Suc j * (2 * ?k)"
using m_le kpos ar_disp_le_2k[OF kpos, of "dvec ?tk" "?pk j ?tk"]
by (cases "dvec ?tk = MoveR") auto
show ?case
proof (intro exI[where x = c']
exI[where x = "m + (if dvec ?tk = MoveR then 1
else ar_disp ?k (dvec ?tk) (?pk j ?tk))"] conjI)
show "(c0, c') ∈ ?R ^^ (m + (if dvec ?tk = MoveR then 1
else ar_disp ?k (dvec ?tk) (?pk j ?tk)))" by (rule chain)
show "m + (if dvec ?tk = MoveR then 1
else ar_disp ?k (dvec ?tk) (?pk j ?tk)) ≤ Suc j * (2 * ?k)"
by (rule bound)
show "ktc_state c' = (q, AR_SimAdvance, k_unidx (Suc j), 0, buf0, dvec,
?pk (Suc j))"
using c'_st ksucc 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 ps_eq by simp
qed
qed
lemma ar_advance_phase:
fixes M :: "('q, 'a) ktm"
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_SimAdvance, 0, 0, buf0, dvec, posk0)"
and buf_valid: "∀k. buf0 k ∈ Γ_ktm M ∪ {bl_ktm M}"
and dge1: "∀k < k_ktm M. dvec k ≠ MoveR
⟶ 0 < ar_disp (block_width (Γ_ktm M)) (dvec k) (posk0 k)"
and notLE: "∀k < k_ktm M. ∀m. m < ar_disp (block_width (Γ_ktm M)) (dvec k) (posk0 k)
⟶ ktc_tape c0 k (ktc_pos c0 k - m) ≠ LE4"
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_SimAdvance, 0, 0, buf0, dvec, posk0)"
shows "∃c m. (c0, c) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)) ^^ m
∧ m ≤ k_ktm M * (2 * block_width (Γ_ktm M))
∧ ktc_state c = (q, AR_SimNext, k_unidx 0, 0, buf0, dvec,
(λk. if k < k_ktm M then ar_newpos (dvec k) (posk0 k)
else posk0 k))
∧ ktc_tape c = ktc_tape c0
∧ ktc_pos c = (λk. if k < k_ktm M
then (if dvec k = MoveR then ktc_pos c0 k
else ktc_pos c0 k - ar_disp (block_width (Γ_ktm M)) (dvec k) (posk0 k))
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"
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 kpos: "0 < ?k" using kge2 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 ?pk = "λk. if k_idx k < ?m1 then ar_newpos (dvec k) (posk0 k)
else posk0 k"
let ?ps = "λk. if k_idx k < ?m1
then (if dvec k = MoveR then ktc_pos c0 k
else ktc_pos c0 k - ar_disp ?k (dvec k) (posk0 k))
else ktc_pos c0 k"
have m1le: "?m1 ≤ k_ktm M - 1" by simp
obtain c1 m1 where
c1_rel: "(c0, c1) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)) ^^ m1"
and m1_le: "m1 ≤ ?m1 * (2 * ?k)"
and c1_st: "ktc_state c1 = (q, AR_SimAdvance, ?tl, 0, buf0, dvec, ?pk)"
and c1_tp: "ktc_tape c1 = ktc_tape c0"
and c1_ps: "ktc_pos c1 = ?ps"
using ar_advance_prefix[OF vM qQ kge2 stg0 buf_valid dge1 notLE pad0 src0 m1le]
by blast
have pk_tl: "?pk ?tl = posk0 ?tl" using tlidx by simp
have c1_pos_tl: "ktc_pos c1 ?tl = ktc_pos c0 ?tl" using c1_ps tlidx by simp
have tl_dge1: "dvec ?tl ≠ MoveR ⟹ 0 < ar_disp ?k (dvec ?tl) (?pk ?tl)"
using dge1[rule_format, OF tl_active] pk_tl by simp
have tl_notLE: "⋀m. m < ar_disp ?k (dvec ?tl) (?pk ?tl)
⟹ ktc_tape c1 ?tl (ktc_pos c1 ?tl - m) ≠ LE4"
proof -
fix m assume "m < ar_disp ?k (dvec ?tl) (?pk ?tl)"
hence mlt: "m < ar_disp ?k (dvec ?tl) (posk0 ?tl)" using pk_tl by simp
have "ktc_tape c1 ?tl (ktc_pos c1 ?tl - m) = ktc_tape c0 ?tl (ktc_pos c0 ?tl - m)"
using c1_tp c1_pos_tl by simp
thus "ktc_tape c1 ?tl (ktc_pos c1 ?tl - m) ≠ LE4"
using notLE[rule_format, OF tl_active mlt] by simp
qed
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_SimAdvance, ?tl, 0, buf0, 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_advance M)) ^^ (if dvec ?tl = MoveR then 1
else ar_disp ?k (dvec ?tl) (?pk ?tl))"
and c2_st: "ktc_state c2 = (q, AR_SimNext, k_unidx 0, 0, buf0, dvec,
?pk(?tl := ar_newpos (dvec ?tl) (?pk ?tl)))"
and c2_tp: "ktc_tape c2 = ktc_tape c1"
and c2_ps: "ktc_pos c2 = (if dvec ?tl = MoveR then ktc_pos c1
else (ktc_pos c1)(?tl := ktc_pos c1 ?tl
- ar_disp ?k (dvec ?tl) (?pk ?tl)))"
using ar_advance_tape_finish_step[OF vM qQ kge2 islast c1_st buf_valid
tl_dge1 tl_notLE pad_c1 src_c1]
by blast
have pk_full: "?pk(?tl := ar_newpos (dvec ?tl) (?pk ?tl))
= (λk. if k < k_ktm M then ar_newpos (dvec k) (posk0 k)
else posk0 k)"
proof (rule ext)
fix k
show "(?pk(?tl := ar_newpos (dvec ?tl) (?pk ?tl))) k
= (if k < k_ktm M then ar_newpos (dvec k) (posk0 k) else posk0 k)"
proof (cases "k = ?tl")
case True thus ?thesis using pk_tl tl_active 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: "(if dvec ?tl = MoveR then ktc_pos c1
else (ktc_pos c1)(?tl := ktc_pos c1 ?tl
- ar_disp ?k (dvec ?tl) (?pk ?tl)))
= (λk. if k < k_ktm M
then (if dvec k = MoveR then ktc_pos c0 k
else ktc_pos c0 k - ar_disp ?k (dvec k) (posk0 k))
else ktc_pos c0 k)"
proof (rule ext)
fix k
show "(if dvec ?tl = MoveR then ktc_pos c1
else (ktc_pos c1)(?tl := ktc_pos c1 ?tl
- ar_disp ?k (dvec ?tl) (?pk ?tl))) k
= (if k < k_ktm M
then (if dvec k = MoveR then ktc_pos c0 k
else ktc_pos c0 k - ar_disp ?k (dvec k) (posk0 k))
else ktc_pos c0 k)"
proof (cases "k = ?tl")
case True thus ?thesis using c1_pos_tl pk_tl tl_active 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_advance M)) ^^ (m1 + (if dvec ?tl = MoveR then 1
else ar_disp ?k (dvec ?tl) (?pk ?tl)))"
proof -
have "(c0, c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)) ^^ m1
O (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)) ^^ (if dvec ?tl = MoveR then 1
else ar_disp ?k (dvec ?tl) (?pk ?tl))"
using c1_rel step by (rule relcompI)
thus ?thesis by (simp add: relpow_add)
qed
have bound: "m1 + (if dvec ?tl = MoveR then 1
else ar_disp ?k (dvec ?tl) (?pk ?tl)) ≤ ?N * (2 * ?k)"
proof -
obtain Nm where Nm: "?N = Suc Nm" using card1 by (cases ?N) auto
have e1: "?N * (2 * ?k) = (2 * ?k) + Nm * (2 * ?k)" by (simp add: Nm)
have e2: "m1 ≤ Nm * (2 * ?k)" using m1_le Nm by simp
have e3: "(if dvec ?tl = MoveR then 1 else ar_disp ?k (dvec ?tl) (?pk ?tl))
≤ 2 * ?k"
using ar_disp_le_2k[OF kpos, of "dvec ?tl" "?pk ?tl"] kpos
by (cases "dvec ?tl = MoveR") auto
show ?thesis using e1 e2 e3 by linarith
qed
show ?thesis
proof (intro exI[where x = c2]
exI[where x = "m1 + (if dvec ?tl = MoveR then 1
else ar_disp ?k (dvec ?tl) (?pk ?tl))"] conjI)
show "(c0, c2) ∈ (ktm_step (alphabet_reduce_delta M ∩ ar_delta_advance M)) ^^ (m1 + (if dvec ?tl = MoveR then 1
else ar_disp ?k (dvec ?tl) (?pk ?tl)))" by (rule chain)
show "m1 + (if dvec ?tl = MoveR then 1
else ar_disp ?k (dvec ?tl) (?pk ?tl)) ≤ ?N * (2 * ?k)"
by (rule bound)
show "ktc_state c2 = (q, AR_SimNext, k_unidx 0, 0, buf0, dvec,
(λk. if k < k_ktm M then ar_newpos (dvec k) (posk0 k) else posk0 k))"
using c2_st 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 dvec k = MoveR then ktc_pos c0 k
else ktc_pos c0 k - ar_disp ?k (dvec k) (posk0 k))
else ktc_pos c0 k)"
using c2_ps ps_full by simp
qed
qed
end