Theory Multitape_Endmarker_Normal
theory Multitape_Endmarker_Normal
imports Multitape_Run_Facts
begin
section ‹Restoring the endmarker discipline›
text ‹@{const le_unique} asks that a transition write the left endmarker on a
tape only where it reads one. It is a hypothesis of the tape reduction
and hence of everything built on it, but it is not part of what a machine
∗‹is›: a valid machine may write the endmarker anywhere, and validity
only pins what happens when one is read --- it is rewritten, and the head
does not move left. So an endmarker written away from cell 0 is inert
except as a symbol that sends the head right.
‹endmarker_normal M› separates the two roles. Its alphabet is ‹'a option›, with
\<^term>‹None› a second endmarker: every endmarker ‹M› writes where it does
not read the real one becomes \<^term>‹None›, and each transition of ‹M›
is replicated for every way of reading its endmarkers as the real one or
as \<^term>‹None›. The copy is valid, satisfies @{const le_unique}, and runs
step for step with ‹M› on the words ‹map Some w›: decoding \<^term>‹None›
to the endmarker maps its runs to ‹M›'s, and encoding ‹M›'s tapes maps
‹M›'s runs to its own, because cell 0 of every tape holds the real
endmarker throughout (‹ktm_relpow_LE_pos0_preserve›).
The same renaming separates a blank that ∗‹is› the endmarker. Validity
allows it, and such a machine treats every blank cell as an endmarker; the
copy's blank is then \<^term>‹None›, which is what those cells are anyway. So
the copy also satisfies the substrate's other endmarker condition,
blank and endmarker distinct, for every valid machine.›
subsection ‹The combinator›
definition endmarker_reads :: "'a ⇒ (nat ⇒ 'a) ⇒ (nat ⇒ 'a option) set" where
"endmarker_reads le a = {b. ∀j. b j = Some (a j) ∨ (a j = le ∧ b j = None)}"
definition endmarker_write :: "'a ⇒ (nat ⇒ 'a option) ⇒ (nat ⇒ 'a) ⇒ nat ⇒ 'a option"
where
"endmarker_write le b a' j = (if a' j = le ∧ b j ≠ Some le then None else Some (a' j))"
text ‹The copy's blank: the original one, unless it is the endmarker.›
definition endmarker_blank :: "'a ⇒ 'a ⇒ 'a option" where
"endmarker_blank le bl = (if bl = le then None else Some bl)"
text ‹Above the tape count validity pins every read to the blank, so there the
copy reads its own blank and nothing else.›
definition endmarker_normal_delta ::
"'a ⇒ 'a option ⇒ nat
⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set
⇒ ('q × (nat ⇒ 'a option) × 'q × (nat ⇒ 'a option) × (nat ⇒ move)) set"
where
"endmarker_normal_delta le nb k D =
{(q, b, q', endmarker_write le b a', d) | q a q' a' d b.
(q, a, q', a', d) ∈ D ∧ b ∈ endmarker_reads le a ∧ (∀j≥k. b j = nb)}"
definition endmarker_normal :: "('q, 'a) ktm ⇒ ('q, 'a option) ktm" where
"endmarker_normal M =
KTM
(Q_ktm M)
(Some ` Sigma_ktm M)
(insert None (Some ` Γ_ktm M))
(endmarker_blank (le_ktm M) (bl_ktm M))
(Some (le_ktm M))
(endmarker_normal_delta (le_ktm M) (endmarker_blank (le_ktm M) (bl_ktm M)) (k_ktm M) (delta_ktm M))
(s_ktm M)
(t_ktm M)
(r_ktm M)
(k_ktm M)"
lemma endmarker_normal_fields [simp]:
"Q_ktm (endmarker_normal M) = Q_ktm M"
"Sigma_ktm (endmarker_normal M) = Some ` Sigma_ktm M"
"Γ_ktm (endmarker_normal M) = insert None (Some ` Γ_ktm M)"
"bl_ktm (endmarker_normal M) = endmarker_blank (le_ktm M) (bl_ktm M)"
"le_ktm (endmarker_normal M) = Some (le_ktm M)"
"delta_ktm (endmarker_normal M) = endmarker_normal_delta (le_ktm M) (endmarker_blank (le_ktm M) (bl_ktm M)) (k_ktm M) (delta_ktm M)"
"s_ktm (endmarker_normal M) = s_ktm M"
"t_ktm (endmarker_normal M) = t_ktm M"
"r_ktm (endmarker_normal M) = r_ktm M"
"k_ktm (endmarker_normal M) = k_ktm M"
by (simp_all add: endmarker_normal_def)
lemma endmarker_normal_delta_I:
"(q, a, q', a', d) ∈ D ⟹ b ∈ endmarker_reads le a ⟹ (⋀j. k ≤ j ⟹ b j = nb)
⟹ (q, b, q', endmarker_write le b a', d) ∈ endmarker_normal_delta le nb k D"
unfolding endmarker_normal_delta_def by blast
lemma endmarker_normal_delta_E:
assumes "(q, b, q', b', d) ∈ endmarker_normal_delta le nb k D"
obtains a a' where "(q, a, q', a', d) ∈ D" and "b ∈ endmarker_reads le a"
and "⋀j. k ≤ j ⟹ b j = nb" and "b' = endmarker_write le b a'"
using assms unfolding endmarker_normal_delta_def by blast
lemma endmarker_blank_simps [simp]:
"bl = le ⟹ endmarker_blank le bl = None"
"bl ≠ le ⟹ endmarker_blank le bl = Some bl"
"endmarker_blank le bl ≠ Some le"
by (simp_all add: endmarker_blank_def)
subsection ‹Validity and the discipline›
lemma endmarker_normal_valid:
assumes vM: "valid_ktm M"
shows "valid_ktm (endmarker_normal M)"
proof (cases M)
case M_eq: (KTM Q Sg Gm bl le D s t r k)
have V0: "valid_ktm (KTM Q Sg Gm bl le D s t r k)" using vM by (simp only: M_eq)
note V = V0 [unfolded valid_ktm.simps]
have v: "finite Q" "finite Gm" "Sg ⊆ Gm" "s ∈ Q" "t ∈ Q" "r ∈ Q"
"bl ∈ Gm" "bl ∉ Sg" "le ∈ Gm" "le ∉ Sg" "t ≠ r" "0 < k"
using V by simp_all
have Dsub: "D ⊆ (Q - {t, r}) × (UNIV → Gm) × Q × (UNIV → Gm) × (UNIV → UNIV)"
using V by (simp only:)
have Dle: "a' j = le ∧ d j ∈ {MoveN, MoveR}"
if "(q, a, q', a', d) ∈ D" and "a j = le" for q a q' a' d j
using V that by blast
have Dk: "a j = bl ∧ a' j = bl ∧ d j = MoveN"
if "(q, a, q', a', d) ∈ D" and "k ≤ j" for q a q' a' d j
using V that by blast
define nb where "nb = endmarker_blank le bl"
have F: "endmarker_normal M = KTM Q (Some ` Sg) (insert None (Some ` Gm)) nb (Some le)
(endmarker_normal_delta le nb k D) s t r k"
using M_eq by (simp add: endmarker_normal_def nb_def)
have nbG: "nb ∈ insert None (Some ` Gm)" using v(7) by (simp add: nb_def endmarker_blank_def)
have nbS: "nb ∉ Some ` Sg" using v(8) by (auto simp: nb_def endmarker_blank_def)
have sub: "endmarker_normal_delta le nb k D
⊆ (Q - {t, r}) × (UNIV → insert None (Some ` Gm)) × Q
× (UNIV → insert None (Some ` Gm)) × (UNIV → UNIV)"
proof
fix x assume "x ∈ endmarker_normal_delta le nb k D"
then obtain q b q' a a' d where x: "x = (q, b, q', endmarker_write le b a', d)"
and tr: "(q, a, q', a', d) ∈ D" and b: "b ∈ endmarker_reads le a"
unfolding endmarker_normal_delta_def by blast
from tr Dsub have "q ∈ Q - {t, r}" "q' ∈ Q" "⋀j. a j ∈ Gm" "⋀j. a' j ∈ Gm"
by (auto simp: Pi_def)
moreover have "b j ∈ insert None (Some ` Gm)" for j
proof -
have "b j = Some (a j) ∨ (a j = le ∧ b j = None)"
using b unfolding endmarker_reads_def by blast
then show ?thesis using ‹⋀j. a j ∈ Gm› by auto
qed
moreover have "endmarker_write le b a' j ∈ insert None (Some ` Gm)" for j
using ‹⋀j. a' j ∈ Gm› unfolding endmarker_write_def by auto
ultimately show "x ∈ (Q - {t, r}) × (UNIV → insert None (Some ` Gm)) × Q
× (UNIV → insert None (Some ` Gm)) × (UNIV → UNIV)"
unfolding x by auto
qed
have lecond: "b' j = Some le ∧ d j ∈ {MoveN, MoveR}"
if "(q, b, q', b', d) ∈ endmarker_normal_delta le nb k D" and "b j = Some le" for q b q' b' d j
proof -
from that(1) obtain a a' where tr: "(q, a, q', a', d) ∈ D"
and b: "b ∈ endmarker_reads le a" and "⋀j. k ≤ j ⟹ b j = nb"
and b': "b' = endmarker_write le b a'"
by (rule endmarker_normal_delta_E) blast
have "b j = Some (a j) ∨ (a j = le ∧ b j = None)"
using b unfolding endmarker_reads_def by blast
then have "a j = le" using that(2) by auto
then have "a' j = le ∧ d j ∈ {MoveN, MoveR}" using Dle [OF tr] by blast
then show ?thesis using b' that(2) unfolding endmarker_write_def by simp
qed
have kcond: "b j = nb ∧ b' j = nb ∧ d j = MoveN"
if "(q, b, q', b', d) ∈ endmarker_normal_delta le nb k D" and "k ≤ j" for q b q' b' d j
proof -
from that(1) obtain a a' where tr: "(q, a, q', a', d) ∈ D"
and "b ∈ endmarker_reads le a" and kb: "⋀j. k ≤ j ⟹ b j = nb"
and b': "b' = endmarker_write le b a'"
by (rule endmarker_normal_delta_E) blast
have a: "a' j = bl ∧ d j = MoveN" using Dk [OF tr that(2)] by blast
have bj: "b j = nb" by (rule kb [OF that(2)])
have "b' j = nb"
unfolding b' endmarker_write_def using a bj by (simp add: nb_def endmarker_blank_def)
then show ?thesis using a bj by blast
qed
show ?thesis
unfolding F valid_ktm.simps
apply (intro conjI allI impI)
using v nbG nbS sub lecond kcond by (blast | auto)+
qed
lemma endmarker_normal_le_unique: "le_unique (endmarker_normal M)"
unfolding le_unique_def
proof (intro allI impI)
fix q b q' b' d j
assume tr: "(q, b, q', b', d) ∈ delta_ktm (endmarker_normal M)"
and w: "b' j = le_ktm (endmarker_normal M)"
from tr obtain a a' where "b' = endmarker_write (le_ktm M) b a'"
by (auto elim: endmarker_normal_delta_E)
with w show "b j = le_ktm (endmarker_normal M)"
unfolding endmarker_write_def by (auto split: if_splits)
qed
lemma endmarker_normal_bl_le: "bl_ktm (endmarker_normal M) ≠ le_ktm (endmarker_normal M)"
by simp
subsection ‹Decoding: every run of the copy is a run of the machine›
definition endmarker_dec :: "'a ⇒ 'a option ⇒ 'a" where
"endmarker_dec le x = (case x of None ⇒ le | Some a ⇒ a)"
lemma endmarker_dec_simps [simp]:
"endmarker_dec le (Some a) = a"
"endmarker_dec le None = le"
by (simp_all add: endmarker_dec_def)
definition endmarker_dec_config :: "'a ⇒ ('a option, 'q) ktc_config ⇒ ('a, 'q) ktc_config"
where
"endmarker_dec_config le c = KConfig (ktc_state c) (λj p. endmarker_dec le (ktc_tape c j p)) (ktc_pos c)"
lemma endmarker_dec_config_simps [simp]:
"ktc_state (endmarker_dec_config le c) = ktc_state c"
"ktc_pos (endmarker_dec_config le c) = ktc_pos c"
by (simp_all add: endmarker_dec_config_def)
lemma endmarker_dec_blank [simp]: "endmarker_dec le (endmarker_blank le bl) = bl"
by (simp add: endmarker_blank_def)
lemma endmarker_dec_reads:
assumes "b ∈ endmarker_reads le a"
shows "(λj. endmarker_dec le (b j)) = a"
proof
fix j
have "b j = Some (a j) ∨ (a j = le ∧ b j = None)"
using assms unfolding endmarker_reads_def by blast
then show "endmarker_dec le (b j) = a j" by auto
qed
lemma endmarker_dec_write: "endmarker_dec le (endmarker_write le b a' j) = a' j"
unfolding endmarker_write_def by simp
lemma endmarker_normal_step_rev:
assumes "(c, c') ∈ ktm_step (delta_ktm (endmarker_normal M))"
shows "(endmarker_dec_config (le_ktm M) c, endmarker_dec_config (le_ktm M) c') ∈ ktm_step (delta_ktm M)"
using assms
proof (cases rule: ktm_step.cases)
case (step q ts n q' b' move)
from step(3) obtain a a' where tr: "(q, a, q', a', move) ∈ delta_ktm M"
and rd: "(λj. ts j (n j)) ∈ endmarker_reads (le_ktm M) a"
and wr: "b' = endmarker_write (le_ktm M) (λj. ts j (n j)) a'"
by (auto elim!: endmarker_normal_delta_E)
have a_eq: "(λj. endmarker_dec (le_ktm M) (ts j (n j))) = a" by (rule endmarker_dec_reads [OF rd])
have "(KConfig q (λj p. endmarker_dec (le_ktm M) (ts j p)) n,
KConfig q' (λj. (λp. endmarker_dec (le_ktm M) (ts j p))(n j := a' j))
(λj. go_move (move j) (n j)))
∈ ktm_step (delta_ktm M)"
proof (rule ktm_step.step)
show "(q, λj. (λp. endmarker_dec (le_ktm M) (ts j p)) (n j), q', a', move) ∈ delta_ktm M"
using tr a_eq by simp
qed
moreover have "(λj p. endmarker_dec (le_ktm M) (((ts j)(n j := b' j)) p))
= (λj. (λp. endmarker_dec (le_ktm M) (ts j p))(n j := a' j))"
unfolding wr by (simp add: fun_eq_iff endmarker_dec_write)
ultimately show ?thesis
using step(1,2) by (simp add: endmarker_dec_config_def)
qed
lemma endmarker_normal_run_rev:
assumes "(c, c') ∈ (ktm_step (delta_ktm (endmarker_normal M))) ^^ n"
shows "(endmarker_dec_config (le_ktm M) c, endmarker_dec_config (le_ktm M) c') ∈ (ktm_step (delta_ktm M)) ^^ n"
using assms
proof (induct n arbitrary: c')
case 0 then show ?case by simp
next
case (Suc n)
from Suc.prems obtain e where ce: "(c, e) ∈ (ktm_step (delta_ktm (endmarker_normal M))) ^^ n"
and ec': "(e, c') ∈ ktm_step (delta_ktm (endmarker_normal M))" by auto
from Suc.hyps [OF ce] endmarker_normal_step_rev [OF ec'] show ?case by auto
qed
lemma endmarker_dec_init_config:
"endmarker_dec_config (le_ktm M) (init_config_ktm (endmarker_normal M) (map Some w)) = init_config_ktm M w"
proof (cases M)
case (KTM Q Sg Gm bl le D s t r k)
then show ?thesis
by (auto simp: endmarker_normal_def endmarker_dec_config_def fun_eq_iff)
qed
lemma endmarker_normal_accepts_in_time_rev:
assumes "accepts_in_time_ktm (endmarker_normal M) (map Some w) n"
shows "accepts_in_time_ktm M w n"
proof -
from assms obtain m c
where m: "m ≤ n"
and run: "(init_config_ktm (endmarker_normal M) (map Some w), c)
∈ (ktm_step (delta_ktm (endmarker_normal M))) ^^ m"
and acc: "ktc_state c = t_ktm (endmarker_normal M)"
by (auto simp: accepts_in_time_ktm_def)
from endmarker_normal_run_rev [OF run]
have "(init_config_ktm M w, endmarker_dec_config (le_ktm M) c) ∈ (ktm_step (delta_ktm M)) ^^ m"
by (simp add: endmarker_dec_init_config)
moreover have "ktc_state (endmarker_dec_config (le_ktm M) c) = t_ktm M" using acc by simp
ultimately show ?thesis
unfolding accepts_in_time_ktm_def using m by blast
qed
subsection ‹Encoding: every run of the machine is a run of the copy›
text ‹An endmarker away from cell 0 is encoded as \<^term>‹None›, and so is
one on a tape at or above the tape count, where it can only be a blank that
is the endmarker. The step goes through because cell 0 of every tape below
the tape count holds the real endmarker, so a transition that writes the
endmarker at cell 0 is reading the real one there; above the tape count
every read and write is a blank.›
definition endmarker_enc :: "'a ⇒ nat ⇒ nat ⇒ nat ⇒ 'a ⇒ 'a option" where
"endmarker_enc le k j p x = (if (p ≠ 0 ∨ k ≤ j) ∧ x = le then None else Some x)"
definition endmarker_enc_config :: "'a ⇒ nat ⇒ ('a, 'q) ktc_config ⇒ ('a option, 'q) ktc_config"
where
"endmarker_enc_config le k c =
KConfig (ktc_state c) (λj p. endmarker_enc le k j p (ktc_tape c j p)) (ktc_pos c)"
lemma endmarker_enc_config_state [simp]: "ktc_state (endmarker_enc_config le k c) = ktc_state c"
by (simp add: endmarker_enc_config_def)
lemma endmarker_normal_step:
assumes vM: "valid_ktm M"
and st: "(c, c') ∈ ktm_step (delta_ktm M)"
and at0: "⋀j. j < k_ktm M ⟹ ktc_tape c j 0 = le_ktm M"
shows "(endmarker_enc_config (le_ktm M) (k_ktm M) c, endmarker_enc_config (le_ktm M) (k_ktm M) c')
∈ ktm_step (delta_ktm (endmarker_normal M))"
using st
proof (cases rule: ktm_step.cases)
case (step q ts n q' a' move)
let ?le = "le_ktm M" and ?k = "k_ktm M" and ?nb = "endmarker_blank (le_ktm M) (bl_ktm M)"
define b where "b j = endmarker_enc ?le ?k j (n j) (ts j (n j))" for j
have rd: "b ∈ endmarker_reads ?le (λj. ts j (n j))"
unfolding endmarker_reads_def b_def endmarker_enc_def by auto
have sup: "ts j (n j) = bl_ktm M ∧ a' j = bl_ktm M" if "?k ≤ j" for j
using valid_ktm_delta_support [OF vM step(3) that] by simp
have kb: "b j = ?nb" if "?k ≤ j" for j
using sup [OF that] that by (simp add: b_def endmarker_enc_def endmarker_blank_def)
have tr': "(q, b, q', endmarker_write ?le b a', move) ∈ delta_ktm (endmarker_normal M)"
using endmarker_normal_delta_I [OF step(3) rd kb] by simp
have wr: "endmarker_write ?le b a' j = endmarker_enc ?le ?k j (n j) (a' j)" for j
proof (cases "?k ≤ j")
case True
then show ?thesis
using sup [OF True] kb [OF True] by (simp add: endmarker_write_def endmarker_enc_def endmarker_blank_def)
next
case False
then have jk: "j < ?k" by simp
show ?thesis
proof (cases "n j = 0")
case n0: True
have "ts j 0 = ?le" using at0 [OF jk] step(1) by simp
then have "b j = Some ?le" unfolding b_def endmarker_enc_def using n0 jk by simp
then show ?thesis unfolding endmarker_write_def endmarker_enc_def using n0 jk by simp
next
case False
have "b j ≠ Some ?le" unfolding b_def endmarker_enc_def using False by simp
then show ?thesis unfolding endmarker_write_def endmarker_enc_def using False by simp
qed
qed
have "(KConfig q (λj p. endmarker_enc ?le ?k j p (ts j p)) n,
KConfig q' (λj. (λp. endmarker_enc ?le ?k j p (ts j p))(n j := endmarker_write ?le b a' j))
(λj. go_move (move j) (n j)))
∈ ktm_step (delta_ktm (endmarker_normal M))"
proof (rule ktm_step.step)
show "(q, λj. (λp. endmarker_enc ?le ?k j p (ts j p)) (n j), q',
λj. endmarker_write ?le b a' j, move) ∈ delta_ktm (endmarker_normal M)"
using tr' unfolding b_def by simp
qed
moreover have "(λj p. endmarker_enc ?le ?k j p (((ts j)(n j := a' j)) p))
= (λj. (λp. endmarker_enc ?le ?k j p (ts j p))(n j := endmarker_write ?le b a' j))"
by (simp add: fun_eq_iff wr)
ultimately show ?thesis
using step(1,2) by (simp add: endmarker_enc_config_def)
qed
lemma endmarker_normal_run:
assumes vM: "valid_ktm M"
and run: "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
and at0: "⋀j. j < k_ktm M ⟹ ktc_tape c j 0 = le_ktm M"
shows "(endmarker_enc_config (le_ktm M) (k_ktm M) c, endmarker_enc_config (le_ktm M) (k_ktm M) c')
∈ (ktm_step (delta_ktm (endmarker_normal M))) ^^ n"
proof (rule relpow_map [where h = "endmarker_enc_config (le_ktm M) (k_ktm M)", OF _ run])
fix m e e'
assume ce: "(c, e) ∈ (ktm_step (delta_ktm M)) ^^ m"
and ee': "(e, e') ∈ ktm_step (delta_ktm M)"
have at0e: "ktc_tape e j 0 = le_ktm M" if "j < k_ktm M" for j
by (rule ktm_relpow_LE_pos0_preserve [OF vM ce at0 [OF that]])
show "(endmarker_enc_config (le_ktm M) (k_ktm M) e,
endmarker_enc_config (le_ktm M) (k_ktm M) e')
∈ ktm_step (delta_ktm (endmarker_normal M))"
by (rule endmarker_normal_step [OF vM ee' at0e])
qed
lemma endmarker_enc_init_config:
assumes vM: "valid_ktm M" and w: "set w ⊆ Sigma_ktm M"
shows "endmarker_enc_config (le_ktm M) (k_ktm M) (init_config_ktm M w)
= init_config_ktm (endmarker_normal M) (map Some w)"
proof (cases M)
case M_eq: (KTM Q Sg Gm bl le D s t r k)
have wle: "w ! i ≠ le" if "i < length w" for i
using valid_ktm_LE_not_Sigma [OF vM] w nth_mem [OF that] M_eq by auto
have wle': "(w ! (p - Suc 0) = le) = False" if "0 < p" and "p ≤ length w" for p
using wle [of "p - Suc 0"] that by simp
have mapS: "map Some w ! (p - Suc 0) = Some (w ! (p - Suc 0))"
if "0 < p" and "p ≤ length w" for p
using that by simp
show ?thesis
proof (cases "bl = le")
case True
then show ?thesis
using M_eq by (simp add: endmarker_normal_def endmarker_enc_config_def endmarker_enc_def fun_eq_iff wle' mapS)
next
case False
then have bl: "(bl = le) = False" by simp
show ?thesis
using M_eq by (simp add: endmarker_normal_def endmarker_enc_config_def endmarker_enc_def fun_eq_iff wle' mapS bl)
qed
qed
lemma init_config_at0:
"j < k_ktm M ⟹ ktc_tape (init_config_ktm M w) j 0 = le_ktm M"
by (cases M) simp
lemma endmarker_normal_accepts_in_time:
assumes vM: "valid_ktm M"
and w: "set w ⊆ Sigma_ktm M"
and acc: "accepts_in_time_ktm M w n"
shows "accepts_in_time_ktm (endmarker_normal M) (map Some w) n"
proof -
from acc obtain m c
where m: "m ≤ n"
and run: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ m"
and tc: "ktc_state c = t_ktm M"
by (auto simp: accepts_in_time_ktm_def)
from endmarker_normal_run [OF vM run init_config_at0]
have "(init_config_ktm (endmarker_normal M) (map Some w), endmarker_enc_config (le_ktm M) (k_ktm M) c)
∈ (ktm_step (delta_ktm (endmarker_normal M))) ^^ m"
by (simp add: endmarker_enc_init_config [OF vM w])
moreover have "ktc_state (endmarker_enc_config (le_ktm M) (k_ktm M) c) = t_ktm (endmarker_normal M)"
using tc by simp
ultimately show ?thesis
unfolding accepts_in_time_ktm_def using m by blast
qed
subsection ‹The headline›
theorem endmarker_normal_lang:
assumes vM: "valid_ktm M"
shows "Lang_ktm (endmarker_normal M) = map Some ` Lang_ktm M"
proof (rule set_eqI, rule iffI)
fix v assume v: "v ∈ Lang_ktm (endmarker_normal M)"
then have "v ∈ lists (Some ` Sigma_ktm M)" by (auto simp: Lang_ktm_def)
then obtain w where wv: "v = map Some w" and w: "set w ⊆ Sigma_ktm M"
by (auto simp: lists_image)
from v wv obtain e j
where "(init_config_ktm (endmarker_normal M) (map Some w), e)
∈ (ktm_step (delta_ktm (endmarker_normal M))) ^^ j"
and te: "ktc_state e = t_ktm (endmarker_normal M)"
by (auto simp: Lang_ktm_def rtrancl_power)
then have "accepts_in_time_ktm (endmarker_normal M) (map Some w) j"
unfolding accepts_in_time_ktm_def by blast
from endmarker_normal_accepts_in_time_rev [OF this]
obtain i c where "i ≤ j"
and "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ i"
and "ktc_state c = t_ktm M"
by (auto simp: accepts_in_time_ktm_def)
then have "w ∈ Lang_ktm M"
using w by (cases c) (auto simp: Lang_ktm_def rtrancl_power)
with wv show "v ∈ map Some ` Lang_ktm M" by blast
next
fix v assume "v ∈ map Some ` Lang_ktm M"
then obtain w where wv: "v = map Some w" and w: "w ∈ Lang_ktm M" by blast
from w have wS: "set w ⊆ Sigma_ktm M" by (simp add: Lang_ktm_def)
from w obtain c j where run: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ j"
and tc: "ktc_state c = t_ktm M"
by (cases M) (auto simp: Lang_ktm_def rtrancl_power)
then have "accepts_in_time_ktm M w j"
unfolding accepts_in_time_ktm_def by blast
from endmarker_normal_accepts_in_time [OF vM wS this]
obtain i e where "i ≤ j"
and "(init_config_ktm (endmarker_normal M) (map Some w), e)
∈ (ktm_step (delta_ktm (endmarker_normal M))) ^^ i"
and "ktc_state e = t_ktm (endmarker_normal M)"
by (auto simp: accepts_in_time_ktm_def)
moreover have "set (map Some w) ⊆ Sigma_ktm (endmarker_normal M)" using wS by auto
ultimately show "v ∈ Lang_ktm (endmarker_normal M)"
unfolding wv by (cases e) (auto simp: Lang_ktm_def rtrancl_power)
qed
end