Theory Multitape_Relabelling
theory Multitape_Relabelling
imports Multitape_Run_Facts
begin
section ‹Transporting a machine along injections›
text ‹Many constructions on machines change the machine's ∗‹type› as well
as its behaviour: ‹alphabet_enlarge› in ‹Multitape_Alphabet_Enlargement›,
for instance, takes a ‹('q, 'a) ktm› to a machine over a block alphabet
‹'c ⇒ 'a›. That is the right design for results whose statements
quantify over the source machine's type. It is the wrong shape for anything
that must collect machines in one concrete type, such as an enumeration
‹nat ⇒ (nat, nat) ktm›. HOL has no quantification over types, so a
class of machines "with any alphabet" has to be represented by a fixed
universe of machines that is shown to be complete.
This theory is the bridge. A machine is transported along an injection on
states and an injection on the tape alphabet, which changes only the names of
things, and so preserves the language up to the alphabet map and the running
time ∗‹exactly›. Two field-level combinators on the tapes follow:
‹widen_tapes› raises the tape count, and ‹swap_tapes› exchanges two
tapes. Last comes the injection arithmetic that supplies the relabelling's
hypotheses.
‹Multitape_Run_Facts› holds the facts about runs that mention no
combinator, and this theory sits over it. ‹Multitape_Embedding› holds the
composite machinery, which builds no machine at all and is a
∗‹sibling› rather than a layer: neither theory cites the other.›
subsection ‹The combinator›
text ‹‹relabel_ktm f g M› renames states along ‹f› and tape symbols along
‹g›. Transition tuples are rewritten componentwise; the direction
component is untouched, and the tape count is carried across, so the
transported machine has the same tape count and the same branching
structure.›
definition relabel_delta ::
"('q ⇒ 'p) ⇒ ('a ⇒ 'b)
⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set
⇒ ('p × (nat ⇒ 'b) × 'p × (nat ⇒ 'b) × (nat ⇒ move)) set" where
"relabel_delta f g D =
(λ(q, a, q', a', d). (f q, g ∘ a, f q', g ∘ a', d)) ` D"
definition relabel_ktm ::
"('q ⇒ 'p) ⇒ ('a ⇒ 'b) ⇒ ('q, 'a) ktm ⇒ ('p, 'b) ktm" where
"relabel_ktm f g M =
KTM
(f ` Q_ktm M)
(g ` Sigma_ktm M)
(g ` Γ_ktm M)
(g (bl_ktm M))
(g (le_ktm M))
(relabel_delta f g (delta_ktm M))
(f (s_ktm M))
(f (t_ktm M))
(f (r_ktm M))
(k_ktm M)"
subsection ‹Structural preservation›
text ‹The selectors go through by construction; these are the lemmas every
downstream hypothesis discharge needs, and they should all be one-liners
off \<^const>‹relabel_ktm›'s definition.›
lemma relabel_Q_ktm [simp]: "Q_ktm (relabel_ktm f g M) = f ` Q_ktm M"
by (simp add: relabel_ktm_def)
lemma relabel_k_ktm [simp]: "k_ktm (relabel_ktm f g M) = k_ktm M"
by (simp add: relabel_ktm_def)
lemma relabel_Sigma_ktm [simp]:
"Sigma_ktm (relabel_ktm f g M) = g ` Sigma_ktm M"
by (simp add: relabel_ktm_def)
lemma relabel_Gamma_ktm [simp]:
"Γ_ktm (relabel_ktm f g M) = g ` Γ_ktm M"
by (simp add: relabel_ktm_def)
lemma relabel_bl_ktm [simp]: "bl_ktm (relabel_ktm f g M) = g (bl_ktm M)"
by (simp add: relabel_ktm_def)
lemma relabel_le_ktm [simp]: "le_ktm (relabel_ktm f g M) = g (le_ktm M)"
by (simp add: relabel_ktm_def)
lemma relabel_s_ktm [simp]: "s_ktm (relabel_ktm f g M) = f (s_ktm M)"
by (simp add: relabel_ktm_def)
lemma relabel_t_ktm [simp]: "t_ktm (relabel_ktm f g M) = f (t_ktm M)"
by (simp add: relabel_ktm_def)
lemma relabel_r_ktm [simp]: "r_ktm (relabel_ktm f g M) = f (r_ktm M)"
by (simp add: relabel_ktm_def)
subsection ‹Validity›
text ‹Validity transports under injectivity on the two carriers. Both
injectivity hypotheses are needed and neither is decorative: ‹f› injective
keeps ‹t ≠ r› apart, and ‹g› injective keeps ‹bl ∉ Σ›, ‹le ∉ Σ› and the
left-endmarker discipline intact. Injectivity is asked for only ∗‹on the
machine's own carriers› rather than globally, which is what lets the
enumeration's encoding be a partial numbering.›
lemma relabel_source:
assumes "(q, a, q', a', d) ∈ relabel_delta f g D"
obtains p b p' b'
where "(p, b, p', b', d) ∈ D"
and "q = f p" and "q' = f p'" and "a = g ∘ b" and "a' = g ∘ b'"
using assms by (auto simp: relabel_delta_def)
lemma relabel_valid:
assumes vM: "valid_ktm M"
and injf: "inj_on f (Q_ktm M)"
and injg: "inj_on g (Γ_ktm M)"
shows "valid_ktm (relabel_ktm f g M)"
proof (cases M)
case M_eq: (KTM Q Sg Gm bl le D s t r k)
have R: "relabel_ktm f g M
= KTM (f ` Q) (g ` Sg) (g ` Gm) (g bl) (g le)
(relabel_delta f g D) (f s) (f t) (f r) k"
using M_eq by (simp add: relabel_ktm_def)
have Qf: "inj_on f Q" and Gg: "inj_on g Gm"
using injf injg M_eq by simp_all
have base: "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 vM M_eq by auto
have notin: "g x ∉ g ` Sg" if x: "x ∈ Gm" and xS: "x ∉ Sg" for x
proof
assume "g x ∈ g ` Sg"
then obtain y where y: "y ∈ Sg" and gy: "g x = g y" by blast
from y base(3) have "y ∈ Gm" by blast
with x gy Gg have "x = y" by (auto dest: inj_onD)
with y xS show False by simp
qed
have tuple: "q ∈ f ` Q - {f t, f r} ∧ q' ∈ f ` Q
∧ (∀j. a j ∈ g ` Gm) ∧ (∀j. a' j ∈ g ` Gm)"
if tr: "(q, a, q', a', d) ∈ relabel_delta f g D" for q a q' a' d
proof -
from tr obtain p b p' b'
where trD: "(p, b, p', b', d) ∈ D"
and qp: "q = f p" and qp': "q' = f p'"
and ab: "a = g ∘ b" and ab': "a' = g ∘ b'"
by (rule relabel_source)
from trD M_eq have trM: "(p, b, p', b', d) ∈ delta_ktm M" by simp
from valid_ktm_delta_set [OF vM] trM M_eq
have p: "p ∈ Q - {t, r}" and p': "p' ∈ Q"
and bG: "∀j. b j ∈ Gm" and bG': "∀j. b' j ∈ Gm"
by (auto simp: Pi_iff)
have "f p ≠ f t" "f p ≠ f r"
using p base(5,6) Qf by (auto dest: inj_onD)
with p p' bG bG' qp qp' ab ab' show ?thesis by auto
qed
have LEdisc: "a' j = g le ∧ d j ∈ {MoveN, MoveR}"
if tr: "(q, a, q', a', d) ∈ relabel_delta f g D" and aj: "a j = g le"
for q a q' a' d j
proof -
from tr obtain p b p' b'
where trD: "(p, b, p', b', d) ∈ D"
and ab: "a = g ∘ b" and ab': "a' = g ∘ b'"
by (rule relabel_source)
from trD M_eq have trM: "(p, b, p', b', d) ∈ delta_ktm M" by simp
from valid_ktm_delta_set [OF vM] trM M_eq have "b j ∈ Gm"
by (auto simp: Pi_iff)
with aj ab base(9) Gg have "b j = le_ktm M"
using M_eq by (auto dest: inj_onD)
from valid_ktm_deltaLE [OF vM trM this] ab' M_eq show ?thesis by simp
qed
have supp: "a j = g bl ∧ a' j = g bl ∧ d j = MoveN"
if tr: "(q, a, q', a', d) ∈ relabel_delta f g D" and j: "k ≤ j"
for q a q' a' d j
proof -
from tr obtain p b p' b'
where trD: "(p, b, p', b', d) ∈ D"
and ab: "a = g ∘ b" and ab': "a' = g ∘ b'"
by (rule relabel_source)
from trD M_eq have trM: "(p, b, p', b', d) ∈ delta_ktm M" by simp
from j M_eq have "k_ktm M ≤ j" by simp
from valid_ktm_delta_support [OF vM trM this] ab ab' M_eq
show ?thesis by simp
qed
have sub: "relabel_delta f g D
⊆ (f ` Q - {f t, f r}) × (UNIV → g ` Gm) × f ` Q
× (UNIV → g ` Gm) × (UNIV → UNIV)"
proof (rule subsetI)
fix x assume x: "x ∈ relabel_delta f g D"
obtain q a q' a' d where xe: "x = (q, a, q', a', d)" by (cases x) auto
from tuple [OF x [unfolded xe]] xe
show "x ∈ (f ` Q - {f t, f r}) × (UNIV → g ` Gm) × f ` Q
× (UNIV → g ` Gm) × (UNIV → UNIV)"
by (simp add: Pi_iff)
qed
have tr_neq: "f t ≠ f r" using base(5,6,11) Qf by (auto dest: inj_onD)
show ?thesis
unfolding R valid_ktm.simps
proof (intro conjI)
show "finite (f ` Q)" using base(1) by simp
show "finite (g ` Gm)" using base(2) by simp
show "g ` Sg ⊆ g ` Gm" using base(3) by blast
show "f s ∈ f ` Q" using base(4) by simp
show "f t ∈ f ` Q" using base(5) by simp
show "f r ∈ f ` Q" using base(6) by simp
show "g bl ∈ g ` Gm" using base(7) by simp
show "g bl ∉ g ` Sg" by (rule notin [OF base(7) base(8)])
show "g le ∈ g ` Gm" using base(9) by simp
show "g le ∉ g ` Sg" by (rule notin [OF base(9) base(10)])
show "f t ≠ f r" by (rule tr_neq)
show "0 < k" by (rule base(12))
show "relabel_delta f g D
⊆ (f ` Q - {f t, f r}) × (UNIV → g ` Gm) × f ` Q
× (UNIV → g ` Gm) × (UNIV → UNIV)"
by (rule sub)
show "∀q a q' a' d j. (q, a, q', a', d) ∈ relabel_delta f g D ⟶
a j = g le ⟶ a' j = g le ∧ d j ∈ {MoveN, MoveR}"
using LEdisc by blast
show "∀q a q' a' d. (q, a, q', a', d) ∈ relabel_delta f g D ⟶
(∀j ≥ k. a j = g bl ∧ a' j = g bl ∧ d j = MoveN)"
using supp by blast
qed
qed
text ‹Determinism is a property of the transition relation's shape, so it
transports for the same reason. Both injectivity hypotheses are used here
and used differently: ‹f› injective is what identifies the two source
states, and ‹g› injective is what identifies the two read vectors
pointwise --- without either, two distinct transitions of ‹M› could be
merged into one branch point.›
lemma relabel_det:
assumes vM: "valid_ktm M"
and injf: "inj_on f (Q_ktm M)"
and injg: "inj_on g (Γ_ktm M)"
and dM: "det_ktm M"
shows "det_ktm (relabel_ktm f g M)"
unfolding det_ktm_def
proof (intro allI impI)
fix q a p⇩1 b⇩1 d⇩1 p⇩2 b⇩2 d⇩2
assume "(q, a, p⇩1, b⇩1, d⇩1) ∈ delta_ktm (relabel_ktm f g M)"
and "(q, a, p⇩2, b⇩2, d⇩2) ∈ delta_ktm (relabel_ktm f g M)"
then have t⇩1: "(q, a, p⇩1, b⇩1, d⇩1) ∈ relabel_delta f g (delta_ktm M)"
and t⇩2: "(q, a, p⇩2, b⇩2, d⇩2) ∈ relabel_delta f g (delta_ktm M)"
by (simp_all add: relabel_ktm_def)
from t⇩1 obtain u c u' c'
where s⇩1: "(u, c, u', c', d⇩1) ∈ delta_ktm M"
and q⇩1: "q = f u" and p⇩1: "p⇩1 = f u'"
and a⇩1: "a = g ∘ c" and b⇩1: "b⇩1 = g ∘ c'"
by (rule relabel_source)
from t⇩2 obtain v e v' e'
where s⇩2: "(v, e, v', e', d⇩2) ∈ delta_ktm M"
and q⇩2: "q = f v" and p⇩2: "p⇩2 = f v'"
and a⇩2: "a = g ∘ e" and b⇩2: "b⇩2 = g ∘ e'"
by (rule relabel_source)
from valid_ktm_delta_set [OF vM] s⇩1 s⇩2
have uQ: "u ∈ Q_ktm M" and vQ: "v ∈ Q_ktm M"
and cG: "∀j. c j ∈ Γ_ktm M" and eG: "∀j. e j ∈ Γ_ktm M"
by (auto simp: Pi_iff)
from q⇩1 q⇩2 uQ vQ injf have uv: "u = v" by (auto dest: inj_onD)
have ce: "c = e"
proof
fix j
from a⇩1 a⇩2 have "g (c j) = g (e j)" by (simp add: fun_eq_iff)
with cG eG injg show "c j = e j" by (auto dest: inj_onD)
qed
from dM s⇩1 s⇩2 [unfolded uv [symmetric] ce [symmetric]]
have "(u', c', d⇩1) = (v', e', d⇩2)" by (simp add: det_ktm_def)
with p⇩1 p⇩2 b⇩1 b⇩2 show "(p⇩1, b⇩1, d⇩1) = (p⇩2, b⇩2, d⇩2)" by simp
qed
text ‹The endmarker write discipline transports too, and unlike the two above
it spends only ∗‹one› of the injectivities: \<^const>‹le_unique› says nothing
about states, so ‹f› may collapse them freely. What ‹g› injective buys is
the one inference the proof turns on --- from \<^term>‹g (b j) = g (le_ktm M)›
back to \<^term>‹b j = le_ktm M› --- and validity is what places both sides
inside ‹Γ›, where injectivity is assumed. Without it a relabelling could
identify the endmarker with an ordinary symbol and manufacture a write that
the original never made.›
lemma relabel_le_unique:
assumes vM: "valid_ktm M"
and injg: "inj_on g (Γ_ktm M)"
and lu: "le_unique M"
shows "le_unique (relabel_ktm f g M)"
unfolding le_unique_def
proof (intro allI impI)
fix q a q' a' d and j :: nat
assume "(q, a, q', a', d) ∈ delta_ktm (relabel_ktm f g M)"
then have t: "(q, a, q', a', d) ∈ relabel_delta f g (delta_ktm M)"
by (simp add: relabel_ktm_def)
then obtain p b p' b'
where s: "(p, b, p', b', d) ∈ delta_ktm M"
and "q = f p" and "q' = f p'"
and ab: "a = g ∘ b" and ab': "a' = g ∘ b'"
by (rule relabel_source)
assume "a' j = le_ktm (relabel_ktm f g M)"
then have geq: "g (b' j) = g (le_ktm M)" using ab' by simp
have b'G: "b' j ∈ Γ_ktm M" by (rule valid_ktm_delta (4) [OF vM s])
have leG: "le_ktm M ∈ Γ_ktm M" by (rule valid_ktm_LE_in_Gamma [OF vM])
from geq b'G leG injg have "b' j = le_ktm M" by (auto dest: inj_onD)
with lu s have "b j = le_ktm M" unfolding le_unique_def by blast
then show "a j = le_ktm (relabel_ktm f g M)" using ab by simp
qed
subsection ‹Semantic preservation›
text ‹The point of the combinator. A relabelling is a bijection on
configurations, so runs correspond step for step: no step is added and none
is lost, and the time bound is preserved ∗‹with no constant at all›. This
is what distinguishes relabelling from the sibling combinators, every one
of which pays a multiplicative or additive price.›
definition relabel_config ::
"('q ⇒ 'p) ⇒ ('a ⇒ 'b) ⇒ ('a, 'q) ktc_config ⇒ ('b, 'p) ktc_config" where
"relabel_config f g c =
KConfig (f (ktc_state c)) (λj p. g (ktc_tape c j p)) (ktc_pos c)"
lemma relabel_config_simps [simp]:
"ktc_state (relabel_config f g c) = f (ktc_state c)"
"ktc_tape (relabel_config f g c) = (λj p. g (ktc_tape c j p))"
"ktc_pos (relabel_config f g c) = ktc_pos c"
by (simp_all add: relabel_config_def)
lemma relabel_delta_ktm [simp]:
"delta_ktm (relabel_ktm f g M) = relabel_delta f g (delta_ktm M)"
by (simp add: relabel_ktm_def)
lemma relabel_delta_I:
"(q, a, q', a', d) ∈ D ⟹
(f q, λj. g (a j), f q', λj. g (a' j), d) ∈ relabel_delta f g D"
by (force simp: relabel_delta_def comp_def)
text ‹The initial configuration is the relabelling of the initial
configuration, which is what makes the input word \<^term>‹map g w› and not
something needing a separate encoding argument.›
lemma relabel_init_config:
"relabel_config f g (init_config_ktm M w)
= init_config_ktm (relabel_ktm f g M) (map g w)"
proof (cases M)
case (KTM Q Sg Gm bl le D s t r k)
then show ?thesis
by (auto simp: relabel_config_def relabel_ktm_def fun_eq_iff)
qed
text ‹One step of ‹M› is one step of the relabelling, with no hypotheses at
all: the forward direction needs neither validity nor injectivity, because
a transition of ‹M› maps to a transition of the image by construction.
Injectivity is what the ∗‹reverse› direction costs, and it is charged
there.›
lemma relabel_step:
assumes "(c, c') ∈ ktm_step (delta_ktm M)"
shows "(relabel_config f g c, relabel_config f g c')
∈ ktm_step (delta_ktm (relabel_ktm f g M))"
using assms
proof (cases rule: ktm_step.cases)
case (step q ts n q' a move)
have "(KConfig (f q) (λj p. g (ts j p)) n,
KConfig (f q') (λj. (λp. g (ts j p))(n j := g (a j)))
(λj. go_move (move j) (n j)))
∈ ktm_step (delta_ktm (relabel_ktm f g M))"
proof (rule ktm_step.step)
show "(f q, λj. (λp. g (ts j p)) (n j), f q', λj. g (a j), move)
∈ delta_ktm (relabel_ktm f g M)"
using relabel_delta_I [OF step(3)] by simp
qed
moreover have "(λj p. g (((ts j)(n j := a j)) p))
= (λj. (λp. g (ts j p))(n j := g (a j)))"
by (simp add: fun_eq_iff)
ultimately show ?thesis
using step(1,2) by (simp add: relabel_config_def)
qed
lemma relabel_run:
assumes "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
shows "(relabel_config f g c, relabel_config f g c')
∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ n"
by (rule relpow_map [where h = "relabel_config f g", OF _ assms])
(erule relabel_step)
lemma relabel_accepts_in_time:
assumes "valid_ktm M" and "inj_on f (Q_ktm M)" and "inj_on g (Γ_ktm M)"
and "set w ⊆ Sigma_ktm M"
and "accepts_in_time_ktm M w n"
shows "accepts_in_time_ktm (relabel_ktm f g M) (map g w) n"
proof -
from assms(5) obtain m c
where m: "m ≤ n"
and run: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ m"
and acc: "ktc_state c = t_ktm M"
by (auto simp: accepts_in_time_ktm_def)
from relabel_run [OF run]
have "(init_config_ktm (relabel_ktm f g M) (map g w), relabel_config f g c)
∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ m"
by (simp add: relabel_init_config)
moreover have "ktc_state (relabel_config f g c) = t_ktm (relabel_ktm f g M)"
using acc by simp
ultimately show ?thesis
unfolding accepts_in_time_ktm_def using m by blast
qed
text ‹❙‹Where the injectivity hypotheses are spent.› Inverting a step of the
relabelling needs to know that the transition it came from is ∗‹the›
transition of ‹M› and not merely one with the same image, and that is two
separate identifications: ‹f› injective recovers the source state and ‹g›
injective recovers the read vector cell by cell. Both need their arguments
to lie in the machine's carriers, which is why the configuration must be
valid --- \<^const>‹valid_config_ktm› supplies exactly the two facts, the
state in \<^term>‹Q_ktm M› and every tape cell in \<^term>‹Γ_ktm M›.›
lemma relabel_step_rev:
assumes vM: "valid_ktm M"
and injf: "inj_on f (Q_ktm M)"
and injg: "inj_on g (Γ_ktm M)"
and valc: "valid_config_ktm M c"
and step: "(relabel_config f g c, e)
∈ ktm_step (delta_ktm (relabel_ktm f g M))"
obtains c' where "(c, c') ∈ ktm_step (delta_ktm M)"
and "e = relabel_config f g c'"
proof -
obtain q ts n where c: "c = KConfig q ts n" by (cases c) auto
from valc c have qQ: "q ∈ Q_ktm M" and tsG: "⋀j p. ts j p ∈ Γ_ktm M"
by (cases M; simp; blast)+
from step c obtain Q' A D
where tr: "(f q, λj. g (ts j (n j)), Q', A, D)
∈ relabel_delta f g (delta_ktm M)"
and e: "e = KConfig Q' (λj. (λp. g (ts j p))(n j := A j))
(λj. go_move (D j) (n j))"
by (auto simp: relabel_config_def elim!: ktm_step.cases)
from tr obtain p b p' b'
where trM: "(p, b, p', b', D) ∈ delta_ktm M"
and fp: "f q = f p" and Q'e: "Q' = f p'"
and bg: "(λj. g (ts j (n j))) = g ∘ b" and Ae: "A = g ∘ b'"
by (rule relabel_source)
from valid_ktm_delta_set [OF vM] trM
have pQ: "p ∈ Q_ktm M" and bG: "⋀j. b j ∈ Γ_ktm M" by (auto simp: Pi_iff)
from fp qQ pQ injf have pq: "p = q" by (auto dest: inj_onD)
have "b = (λj. ts j (n j))"
proof
fix j
from bg have "g (ts j (n j)) = g (b j)" by (simp add: fun_eq_iff)
with tsG bG injg show "b j = ts j (n j)" by (auto dest: inj_onD)
qed
with trM pq have trq: "(q, λj. ts j (n j), p', b', D) ∈ delta_ktm M" by simp
let ?c' = "KConfig p' (λj. (ts j)(n j := b' j)) (λj. go_move (D j) (n j))"
have "(KConfig q ts n, ?c') ∈ ktm_step (delta_ktm M)"
by (rule ktm_step.step) (rule trq)
then have "(c, ?c') ∈ ktm_step (delta_ktm M)" unfolding c .
moreover have "e = relabel_config f g ?c'"
using e Q'e Ae by (simp add: relabel_config_def fun_eq_iff)
ultimately show thesis by (rule that)
qed
lemma relabel_run_rev:
assumes vM: "valid_ktm M"
and injf: "inj_on f (Q_ktm M)"
and injg: "inj_on g (Γ_ktm M)"
and valc: "valid_config_ktm M c"
and run: "(relabel_config f g c, e)
∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ n"
obtains c' where "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
and "e = relabel_config f g c'"
using run
proof (induct n arbitrary: e thesis)
case 0 then show ?case by simp
next
case (Suc n)
from Suc.prems(2) obtain d
where cd: "(relabel_config f g c, d)
∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ n"
and de: "(d, e) ∈ ktm_step (delta_ktm (relabel_ktm f g M))" by auto
from Suc.hyps [OF _ cd] obtain c''
where cc'': "(c, c'') ∈ (ktm_step (delta_ktm M)) ^^ n"
and dc'': "d = relabel_config f g c''" by blast
from valid_reach_relpow_ktm [OF vM valc cc'']
have valc'': "valid_config_ktm M c''" .
from de [unfolded dc''] obtain c'
where c''c': "(c'', c') ∈ ktm_step (delta_ktm M)"
and ec': "e = relabel_config f g c'"
by (rule relabel_step_rev [OF vM injf injg valc''])
from cc'' c''c' have "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ Suc n" by auto
from Suc.prems(1) [OF this ec'] show ?case .
qed
lemma relabel_accepts_in_time_rev:
assumes vM: "valid_ktm M" and injf: "inj_on f (Q_ktm M)"
and injg: "inj_on g (Γ_ktm M)"
and w: "set w ⊆ Sigma_ktm M"
and acc: "accepts_in_time_ktm (relabel_ktm f g M) (map g w) n"
shows "accepts_in_time_ktm M w n"
proof -
from acc obtain m e
where m: "m ≤ n"
and run: "(init_config_ktm (relabel_ktm f g M) (map g w), e)
∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ m"
and te: "ktc_state e = t_ktm (relabel_ktm f g M)"
by (auto simp: accepts_in_time_ktm_def)
have valinit: "valid_config_ktm M (init_config_ktm M w)"
by (rule valid_init_config_ktm [OF vM w])
from run [folded relabel_init_config] obtain c'
where run': "(init_config_ktm M w, c') ∈ (ktm_step (delta_ktm M)) ^^ m"
and ec': "e = relabel_config f g c'"
by (rule relabel_run_rev [OF vM injf injg valinit])
from valid_reach_relpow_ktm [OF vM valinit run']
have "ktc_state c' ∈ Q_ktm M" by (cases M; cases c') simp
moreover have "t_ktm M ∈ Q_ktm M" by (rule valid_ktm_t_in_Q [OF vM])
moreover from te ec' have "f (ktc_state c') = f (t_ktm M)" by simp
ultimately have "ktc_state c' = t_ktm M" using injf by (auto dest: inj_onD)
with run' m show ?thesis unfolding accepts_in_time_ktm_def by blast
qed
theorem relabel_lang:
assumes vM: "valid_ktm M" and injf: "inj_on f (Q_ktm M)"
and injg: "inj_on g (Γ_ktm M)"
shows "Lang_ktm (relabel_ktm f g M) = map g ` Lang_ktm M"
proof (rule set_eqI, rule iffI)
fix v assume v: "v ∈ Lang_ktm (relabel_ktm f g M)"
then have "v ∈ lists (g ` Sigma_ktm M)" by (auto simp: Lang_ktm_def)
then obtain w where wv: "v = map g w" and w: "set w ⊆ Sigma_ktm M"
by (auto simp: lists_image)
from v wv obtain e j
where "(init_config_ktm (relabel_ktm f g M) (map g w), e)
∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ j"
and te: "ktc_state e = t_ktm (relabel_ktm f g M)"
by (auto simp: Lang_ktm_def rtrancl_power)
then have "accepts_in_time_ktm (relabel_ktm f g M) (map g w) j"
unfolding accepts_in_time_ktm_def by blast
from relabel_accepts_in_time_rev [OF vM injf injg w 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 g ` Lang_ktm M" by blast
next
fix v assume "v ∈ map g ` Lang_ktm M"
then obtain w where wv: "v = map g 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)
from relabel_run [OF run]
have "(init_config_ktm (relabel_ktm f g M) (map g w), relabel_config f g c)
∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ j"
by (simp add: relabel_init_config)
moreover have "ktc_state (relabel_config f g c)
= t_ktm (relabel_ktm f g M)" using tc by simp
moreover have "set (map g w) ⊆ Sigma_ktm (relabel_ktm f g M)"
using wS by auto
ultimately show "v ∈ Lang_ktm (relabel_ktm f g M)"
unfolding wv
by (cases "relabel_config f g c")
(auto simp: Lang_ktm_def rtrancl_power)
qed
subsection ‹Widening the tape count›
text ‹Textbook arguments that move a machine into a class with more tapes
say "a ‹k›-tape machine is a ‹k'›-tape machine with unused extra tapes"
and move on. On the value-level substrate that sentence is not just true but
∗‹free›, and it is worth seeing why.
❙‹It is not a field update, and the reason is worth stating because the
plausible argument for "free" is nearly right.› Validity does constrain
transitions only ∗‹beyond› the tape count --- for ‹j ≥ k› a transition
must read blank, write blank and stay --- so raising ‹k› weakens that
obligation and a machine's own transition relation stays legal at the larger
count. ‹widen_valid› really is free.
But ‹k› has a second consumer. \<^const>‹init_config_ktm› reads it to decide
which tapes ∗‹exist›, and every tape below ‹k› starts with the left
endmarker in cell 0 while every tape at or above ‹k› is uniformly blank.
Raising the count therefore ∗‹adds› endmarkers, on exactly the tapes whose
transitions are required to read blank --- so a bare field update leaves a
machine that cannot take its first step at all, for any input. The two
consumers of ‹k› move in opposite directions.
So the widening also patches the transition relation, replacing the blank
that \<^const>‹valid_ktm› forces on tapes ‹[k, k')› with the endmarker those
tapes now carry. The heads there never move (the direction component is
already stationary beyond ‹k›), so each new tape holds its endmarker in
cell 0 for the whole run and reads it every step. The correspondence with
‹M›'s own run is still step for step and the time bound is still exact ---
what is lost is only the claim that no proof obligation arises.
This remains a place where the value-level tape count pays for itself. With
the count trapped in a type parameter, as in the AFP source this substrate
was forked from, the same step would be a transport across two different
types and would need the machinery above on top of this patch.›
definition widen_delta ::
"nat ⇒ nat ⇒ 'a
⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set
⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set" where
"widen_delta k k' le D =
(λ(q, a, q', a', d).
(q, λj. if k ≤ j ∧ j < k' then le else a j,
q', λj. if k ≤ j ∧ j < k' then le else a' j, d)) ` D"
definition widen_tapes :: "nat ⇒ ('q, 'a) ktm ⇒ ('q, 'a) ktm" where
"widen_tapes k' M =
KTM (Q_ktm M) (Sigma_ktm M) (Γ_ktm M) (bl_ktm M) (le_ktm M)
(widen_delta (k_ktm M) k' (le_ktm M) (delta_ktm M))
(s_ktm M) (t_ktm M) (r_ktm M) k'"
lemma widen_k_ktm [simp]: "k_ktm (widen_tapes k' M) = k'"
by (simp add: widen_tapes_def)
lemma widen_delta_ktm [simp]:
"delta_ktm (widen_tapes k' M)
= widen_delta (k_ktm M) k' (le_ktm M) (delta_ktm M)"
by (simp add: widen_tapes_def)
lemma widen_Sigma_ktm [simp]: "Sigma_ktm (widen_tapes k' M) = Sigma_ktm M"
by (simp add: widen_tapes_def)
lemma widen_Gamma_ktm [simp]: "Γ_ktm (widen_tapes k' M) = Γ_ktm M"
by (simp add: widen_tapes_def)
lemma widen_bl_ktm [simp]: "bl_ktm (widen_tapes k' M) = bl_ktm M"
by (simp add: widen_tapes_def)
lemma widen_le_ktm [simp]: "le_ktm (widen_tapes k' M) = le_ktm M"
by (simp add: widen_tapes_def)
lemma widen_t_ktm [simp]: "t_ktm (widen_tapes k' M) = t_ktm M"
by (simp add: widen_tapes_def)
text ‹The patched tuple's four obligations, each read off ‹M›'s own. The
endmarker case is the one the bare field update could not meet: on
‹[k, k')› the read is now ‹le›, and what licenses it is that ‹M›'s support
invariant already makes the direction stationary there, so the endmarker
discipline's ‹d j ∈ {N, R}› is satisfied without choosing anything.›
lemma widen_valid:
assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'" and pos: "0 < k'"
shows "valid_ktm (widen_tapes k' M)"
proof (cases M)
case M_eq: (KTM Q Sg Gm bl le D s t r k)
have kD: "k_ktm M = k" "le_ktm M = le" "bl_ktm M = bl" "delta_ktm M = D"
using M_eq by simp_all
have W: "widen_tapes k' M
= KTM Q Sg Gm bl le (widen_delta k k' le D) s t r k'"
using M_eq by (simp add: widen_tapes_def)
have kle: "k ≤ k'" using kk kD by simp
have leG: "le ∈ Gm" using valid_ktm_LE_in_Gamma [OF vM] M_eq by simp
have split: "∃b b'. (q, b, q', b', d) ∈ delta_ktm M
∧ a = (λj. if k ≤ j ∧ j < k' then le else b j)
∧ a' = (λj. if k ≤ j ∧ j < k' then le else b' j)"
if "(q, a, q', a', d) ∈ widen_delta k k' le D" for q a q' a' d
using that kD by (auto simp: widen_delta_def)
have tuple: "q ∈ Q - {t, r} ∧ q' ∈ Q
∧ (∀j. a j ∈ Gm) ∧ (∀j. a' j ∈ Gm)"
if tr: "(q, a, q', a', d) ∈ widen_delta k k' le D" for q a q' a' d
proof -
from split [OF tr] obtain b b'
where trM: "(q, b, q', b', d) ∈ delta_ktm M"
and ae: "a = (λj. if k ≤ j ∧ j < k' then le else b j)"
and ae': "a' = (λj. if k ≤ j ∧ j < k' then le else b' j)" by blast
from valid_ktm_delta_set [OF vM] trM M_eq
have "q ∈ Q - {t, r}" "q' ∈ Q" "∀j. b j ∈ Gm" "∀j. b' j ∈ Gm"
by (auto simp: Pi_iff)
with leG ae ae' show ?thesis by simp
qed
have LEdisc: "a' j = le ∧ d j ∈ {MoveN, MoveR}"
if tr: "(q, a, q', a', d) ∈ widen_delta k k' le D" and aj: "a j = le"
for q a q' a' d j
proof -
from split [OF tr] obtain b b'
where trM: "(q, b, q', b', d) ∈ delta_ktm M"
and ae: "a = (λj. if k ≤ j ∧ j < k' then le else b j)"
and ae': "a' = (λj. if k ≤ j ∧ j < k' then le else b' j)" by blast
show ?thesis
proof (cases "k ≤ j ∧ j < k'")
case True
then have "d j = MoveN"
using valid_ktm_delta_support [OF vM trM] kD by simp
with True ae' show ?thesis by simp
next
case False
with aj ae have "b j = le_ktm M" using kD by simp
from valid_ktm_deltaLE [OF vM trM this] False ae' kD
show ?thesis by simp
qed
qed
have supp: "a j = bl ∧ a' j = bl ∧ d j = MoveN"
if tr: "(q, a, q', a', d) ∈ widen_delta k k' le D" and j: "k' ≤ j"
for q a q' a' d j
proof -
from split [OF tr] obtain b b'
where trM: "(q, b, q', b', d) ∈ delta_ktm M"
and ae: "a = (λj. if k ≤ j ∧ j < k' then le else b j)"
and ae': "a' = (λj. if k ≤ j ∧ j < k' then le else b' j)" by blast
from j kle have "k_ktm M ≤ j" using kD by simp
from valid_ktm_delta_support [OF vM trM this] j ae ae' kD
show ?thesis by simp
qed
have sub: "widen_delta k k' le D
⊆ (Q - {t, r}) × (UNIV → Gm) × Q × (UNIV → Gm)
× (UNIV → UNIV)"
proof (rule subsetI)
fix x assume x: "x ∈ widen_delta k k' le D"
obtain q a q' a' d where xe: "x = (q, a, q', a', d)"
by (cases x) auto
from tuple [OF x [unfolded xe]] xe
show "x ∈ (Q - {t, r}) × (UNIV → Gm) × Q × (UNIV → Gm)
× (UNIV → UNIV)"
by (simp add: Pi_iff)
qed
have base: "finite Q" "finite Gm" "Sg ⊆ Gm" "s ∈ Q" "t ∈ Q" "r ∈ Q"
"bl ∈ Gm" "bl ∉ Sg" "le ∈ Gm" "le ∉ Sg" "t ≠ r"
using vM M_eq by auto
show ?thesis
unfolding W valid_ktm.simps
using base pos sub LEdisc supp by blast
qed
text ‹❙‹And \<^const>‹le_unique›, which the widening preserves for the reason
it is stated the way it is.› On the tapes it invents the read and the write
are the ∗‹same› endmarker, so the implication holds there with nothing to
prove; elsewhere the vectors are ‹M›'s own. A pipeline of
constructions that has to deliver a machine with the property needs every
stage to preserve it.›
lemma widen_le_unique:
assumes lu: "le_unique M"
shows "le_unique (widen_tapes k' M)"
using lu by (fastforce simp: le_unique_def widen_tapes_def widen_delta_def)
text ‹The configuration correspondence. On ‹[k, k')› the widened machine
shows the endmarker in cell 0 and blanks beyond it, and its head there never
moves; everywhere else it is ‹M›'s own configuration. What makes this an
∗‹equality› of runs rather than a simulation is that \<^const>‹valid_config_ktm›
already forces ‹M›'s tapes beyond ‹k› to be uniformly blank with the head at
the origin, so nothing on those tapes is being thrown away.›
definition widen_config ::
"nat ⇒ nat ⇒ 'a ⇒ 'a ⇒ ('a, 'q) ktc_config ⇒ ('a, 'q) ktc_config" where
"widen_config k k' le bl c =
KConfig (ktc_state c)
(λj p. if k ≤ j ∧ j < k'
then (if p = 0 then le else bl) else ktc_tape c j p)
(ktc_pos c)"
lemma widen_config_simps [simp]:
"ktc_state (widen_config k k' le bl c) = ktc_state c"
"ktc_pos (widen_config k k' le bl c) = ktc_pos c"
by (simp_all add: widen_config_def)
lemma widen_init_config:
assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
shows "widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) (init_config_ktm M w)
= init_config_ktm (widen_tapes k' M) w"
using kk valid_ktm_k_pos [OF vM]
by (cases M) (auto simp: widen_config_def widen_tapes_def fun_eq_iff)
lemma widen_delta_I:
"(q, a, q', a', d) ∈ D ⟹
(q, λj. if k ≤ j ∧ j < k' then le else a j, q',
λj. if k ≤ j ∧ j < k' then le else a' j, d) ∈ widen_delta k k' le D"
by (force simp: widen_delta_def)
lemma widen_step:
assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
and valc: "valid_config_ktm M c"
and hp: "heads_parked (k_ktm M) c"
and step: "(c, c') ∈ ktm_step (delta_ktm M)"
shows "(widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c,
widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c')
∈ ktm_step (delta_ktm (widen_tapes k' M))"
proof -
let ?k = "k_ktm M" and ?le = "le_ktm M" and ?bl = "bl_ktm M"
from step obtain q ts n q' a d
where c: "c = KConfig q ts n"
and c': "c' = KConfig q' (λj. (ts j)(n j := a j))
(λj. go_move (d j) (n j))"
and tr: "(q, λj. ts j (n j), q', a, d) ∈ delta_ktm M"
by (auto elim!: ktm_step.cases)
have pos0: "n j = 0" if "?k ≤ j" for j
using hp c that by (simp add: heads_parked_def)
let ?tw = "λj p. if ?k ≤ j ∧ j < k' then (if p = 0 then ?le else ?bl)
else ts j p"
let ?aw = "λj. if ?k ≤ j ∧ j < k' then ?le else a j"
have wc: "widen_config ?k k' ?le ?bl c = KConfig q ?tw n"
unfolding c widen_config_def by (auto simp: fun_eq_iff)
have wc': "widen_config ?k k' ?le ?bl c'
= KConfig q' (λj. (?tw j)(n j := ?aw j))
(λj. go_move (d j) (n j))"
unfolding c' widen_config_def using pos0 by (auto simp: fun_eq_iff)
have read: "(λj. ?tw j (n j)) = (λj. if ?k ≤ j ∧ j < k' then ?le
else ts j (n j))"
using pos0 by (auto simp: fun_eq_iff)
show ?thesis
unfolding wc wc'
proof (rule ktm_step.step)
show "(q, λj. ?tw j (n j), q', ?aw, d) ∈ delta_ktm (widen_tapes k' M)"
using widen_delta_I [OF tr] read by simp
qed
qed
lemma widen_run:
assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
and valc: "valid_config_ktm M c"
and hp: "heads_parked (k_ktm M) c"
and run: "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
shows "(widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c,
widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c')
∈ (ktm_step (delta_ktm (widen_tapes k' M))) ^^ n"
by (rule relpow_map [where h = "widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M)", OF _ run])
(rule widen_step [OF vM kk valid_reach_relpow_ktm [OF vM valc]
heads_parked_run [OF vM hp]])
text ‹The reverse direction reuses the forward one rather than repeating the
correspondence: ‹widen_tapes› does not change the state set, so an accepting
run of the widened machine is a run of ‹M› read back through the same
bijection on configurations. Stating it as ‹relabel_ktm›'s reverse would
need a second inversion argument; instead the widened step relation is
inverted directly, which is cheap because ‹widen_delta› is injective on the
part of the read vector that matters.›
lemma widen_step_rev:
assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
and valc: "valid_config_ktm M c"
and hp: "heads_parked (k_ktm M) c"
and step: "(widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c, e)
∈ ktm_step (delta_ktm (widen_tapes k' M))"
obtains c' where "(c, c') ∈ ktm_step (delta_ktm M)"
and "e = widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c'"
proof -
let ?k = "k_ktm M" and ?le = "le_ktm M" and ?bl = "bl_ktm M"
obtain q ts n where c: "c = KConfig q ts n" by (cases c) auto
have pos0: "n j = 0" if "?k ≤ j" for j
using hp c that by (simp add: heads_parked_def)
let ?tw = "λj p. if ?k ≤ j ∧ j < k' then (if p = 0 then ?le else ?bl)
else ts j p"
have wc: "widen_config ?k k' ?le ?bl c = KConfig q ?tw n"
unfolding c widen_config_def by (auto simp: fun_eq_iff)
from step [unfolded wc] obtain Q' A D
where tr: "(q, λj. ?tw j (n j), Q', A, D)
∈ widen_delta ?k k' ?le (delta_ktm M)"
and e: "e = KConfig Q' (λj. (?tw j)(n j := A j))
(λj. go_move (D j) (n j))"
by (auto elim!: ktm_step.cases)
from tr obtain b b'
where trM: "(q, b, Q', b', D) ∈ delta_ktm M"
and bw: "(λj. ?tw j (n j))
= (λj. if ?k ≤ j ∧ j < k' then ?le else b j)"
and Aw: "A = (λj. if ?k ≤ j ∧ j < k' then ?le else b' j)"
by (auto simp: widen_delta_def)
have "b = (λj. ts j (n j))"
proof
fix j
show "b j = ts j (n j)"
proof (cases "?k ≤ j ∧ j < k'")
case True
from valid_ktm_delta_support [OF vM trM] True have "b j = ?bl" by simp
moreover from valc c True have "ts j (n j) = ?bl"
by (cases M) (auto simp: valid_config_ktm.simps)
ultimately show ?thesis by simp
next
case False
from bw have "?tw j (n j) = (if ?k ≤ j ∧ j < k' then ?le else b j)"
by (simp add: fun_eq_iff)
with False show ?thesis by (auto split: if_splits)
qed
qed
with trM have trq: "(q, λj. ts j (n j), Q', b', D) ∈ delta_ktm M" by simp
let ?c' = "KConfig Q' (λj. (ts j)(n j := b' j)) (λj. go_move (D j) (n j))"
have "(KConfig q ts n, ?c') ∈ ktm_step (delta_ktm M)"
by (rule ktm_step.step) (rule trq)
then have "(c, ?c') ∈ ktm_step (delta_ktm M)" unfolding c .
moreover have "e = widen_config ?k k' ?le ?bl ?c'"
using e Aw pos0 by (auto simp: widen_config_def fun_eq_iff)
ultimately show thesis by (rule that)
qed
lemma widen_run_rev:
assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
and valc: "valid_config_ktm M c"
and hp: "heads_parked (k_ktm M) c"
and run: "(widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c, e)
∈ (ktm_step (delta_ktm (widen_tapes k' M))) ^^ n"
obtains c' where "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
and "e = widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c'"
using run
proof (induct n arbitrary: e thesis)
case 0 then show ?case by simp
next
case (Suc n)
from Suc.prems(2) obtain d
where cd: "(widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c, d)
∈ (ktm_step (delta_ktm (widen_tapes k' M))) ^^ n"
and de: "(d, e) ∈ ktm_step (delta_ktm (widen_tapes k' M))" by auto
from Suc.hyps [OF _ cd] obtain c''
where cc'': "(c, c'') ∈ (ktm_step (delta_ktm M)) ^^ n"
and dc'': "d = widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c''" by blast
from valid_reach_relpow_ktm [OF vM valc cc'']
have valc'': "valid_config_ktm M c''" .
from heads_parked_run [OF vM hp cc''] have hpc'': "heads_parked (k_ktm M) c''" .
from de [unfolded dc''] obtain c'
where c''c': "(c'', c') ∈ ktm_step (delta_ktm M)"
and ec': "e = widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c'"
by (rule widen_step_rev [OF vM kk valc'' hpc''])
from cc'' c''c' have "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ Suc n" by auto
from Suc.prems(1) [OF this ec'] show ?case .
qed
lemma widen_accepts_in_time:
assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
and w: "set w ⊆ Sigma_ktm M"
shows "accepts_in_time_ktm (widen_tapes k' M) w n
⟷ accepts_in_time_ktm M w n"
proof
have valinit: "valid_config_ktm M (init_config_ktm M w)"
by (rule valid_init_config_ktm [OF vM w])
have hpinit: "heads_parked (k_ktm M) (init_config_ktm M w)"
by (rule heads_parked_init)
assume "accepts_in_time_ktm (widen_tapes k' M) w n"
then obtain m e
where m: "m ≤ n"
and run: "(init_config_ktm (widen_tapes k' M) w, e)
∈ (ktm_step (delta_ktm (widen_tapes k' M))) ^^ m"
and te: "ktc_state e = t_ktm (widen_tapes k' M)"
by (auto simp: accepts_in_time_ktm_def)
from run [folded widen_init_config [OF vM kk]] obtain c'
where run': "(init_config_ktm M w, c') ∈ (ktm_step (delta_ktm M)) ^^ m"
and ec': "e = widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c'"
by (rule widen_run_rev [OF vM kk valinit hpinit])
from te ec' have "ktc_state c' = t_ktm M" by (simp add: widen_tapes_def)
with run' m show "accepts_in_time_ktm M w n"
unfolding accepts_in_time_ktm_def by blast
next
have valinit: "valid_config_ktm M (init_config_ktm M w)"
by (rule valid_init_config_ktm [OF vM w])
have hpinit: "heads_parked (k_ktm M) (init_config_ktm M w)"
by (rule heads_parked_init)
assume "accepts_in_time_ktm M w n"
then 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 widen_run [OF vM kk valinit hpinit run]
have run': "(init_config_ktm (widen_tapes k' M) w,
widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c)
∈ (ktm_step (delta_ktm (widen_tapes k' M))) ^^ m"
by (simp add: widen_init_config [OF vM kk])
have "ktc_state (widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c)
= t_ktm (widen_tapes k' M)"
using tc by (simp add: widen_tapes_def)
with run' m show "accepts_in_time_ktm (widen_tapes k' M) w n"
unfolding accepts_in_time_ktm_def by blast
qed
theorem widen_lang:
assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
shows "Lang_ktm (widen_tapes k' M) = Lang_ktm M"
proof (rule set_eqI)
fix w
have "set w ⊆ Sigma_ktm (widen_tapes k' M) ⟷ set w ⊆ Sigma_ktm M"
by (simp add: widen_tapes_def)
then show "w ∈ Lang_ktm (widen_tapes k' M) ⟷ w ∈ Lang_ktm M"
unfolding Lang_ktm_iff
using widen_accepts_in_time [OF vM kk] by blast
qed
subsection ‹Exchanging two tapes›
text ‹The cheapest of the three combinators. Renaming tape indices in the
transition relation renames them in the configuration; the machine cannot
tell the difference, and no step is spent.
❙‹Why a transposition rather than a permutation.› Every permutation of a
finite index set is a product of transpositions, so the single exchange is
enough, and it is what a construction that hands one tape's role to another
needs. ‹tswap› is ‹transpose› of ‹HOL-Combinatorics.Transposition› at
type \<^typ>‹nat›; it is defined here so that this entry does not depend on
that session. Restricting to two indices also keeps the side condition to
‹i < k› and ‹j < k›, which is what the support invariant needs: a
transposition of two indices ∗‹below› the tape count fixes every index at
or above it, so the requirement that transitions read blank, write blank and
stay put beyond ‹k› transports unchanged.
❙‹What it costs, compared with the widening above.› Nothing --- and the
contrast is the point. ‹widen_step› carries \<^const>‹valid_config_ktm› and
\<^const>‹heads_parked› as hypotheses, because widening ∗‹invents› tape
content (endmarkers on tapes that had none) and has to know the discarded
content was blank and its heads at the origin. A transposition invents
nothing: it is a bijection on configurations, so the step correspondence is
an iff with no hypotheses at all, and the reverse direction is the forward
one applied to the exchanged machine rather than a second argument.
❙‹Why a widening often wants one.› The tape \<^const>‹widen_tapes›
adds is not a free tape: widening pins it to the endmarker in cell 0 with
the head stationary. So a tape a construction walks along has to be one the
machine already had, and exchanging tapes moves the pinned role onto a tape
that is no longer needed.›
definition tswap :: "nat ⇒ nat ⇒ nat ⇒ nat" where
"tswap i j m = (if m = i then j else if m = j then i else m)"
lemma tswap_tswap [simp]: "tswap i j (tswap i j m) = m"
by (simp add: tswap_def)
lemma tswap_same [simp]: "tswap i i = id"
by (auto simp: tswap_def)
lemma tswap_out:
assumes "i < k" and "j < k" and "k ≤ m"
shows "tswap i j m = m"
using assms by (simp add: tswap_def)
definition swap_delta ::
"nat ⇒ nat
⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set
⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set" where
"swap_delta i j D =
(λ(q, a, q', a', d).
(q, a ∘ tswap i j, q', a' ∘ tswap i j, d ∘ tswap i j)) ` D"
lemma swap_delta_I:
"(q, a, q', a', d) ∈ D ⟹
(q, a ∘ tswap i j, q', a' ∘ tswap i j, d ∘ tswap i j)
∈ swap_delta i j D"
by (force simp: swap_delta_def)
lemma swap_delta_E:
assumes "(q, a, q', a', d) ∈ swap_delta i j D"
obtains b b' e where "(q, b, q', b', e) ∈ D"
and "a = b ∘ tswap i j" and "a' = b' ∘ tswap i j" and "d = e ∘ tswap i j"
using assms by (auto simp: swap_delta_def)
lemma swap_delta_swap_delta [simp]:
fixes D :: "('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set"
shows "swap_delta i j (swap_delta i j D) = D"
proof (rule set_eqI)
fix x :: "'q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)"
obtain q a q' a' d where xe: "x = (q, a, q', a', d)" by (cases x) auto
show "(x ∈ swap_delta i j (swap_delta i j D)) = (x ∈ D)"
proof
assume "x ∈ swap_delta i j (swap_delta i j D)"
from this [unfolded xe] obtain b b' e
where m: "(q, b, q', b', e) ∈ swap_delta i j D"
and ab: "a = b ∘ tswap i j" and ab': "a' = b' ∘ tswap i j"
and de: "d = e ∘ tswap i j"
by (rule swap_delta_E)
from m obtain c c' f
where mD: "(q, c, q', c', f) ∈ D"
and bc: "b = c ∘ tswap i j" and bc': "b' = c' ∘ tswap i j"
and ef: "e = f ∘ tswap i j"
by (rule swap_delta_E)
have "a = c" "a' = c'" "d = f"
using ab ab' de bc bc' ef by (simp_all add: comp_def)
with mD xe show "x ∈ D" by simp
next
assume "x ∈ D"
from swap_delta_I [OF this [unfolded xe], of i j]
have "(q, a ∘ tswap i j, q', a' ∘ tswap i j, d ∘ tswap i j)
∈ swap_delta i j D" .
from swap_delta_I [OF this, of i j]
show "x ∈ swap_delta i j (swap_delta i j D)"
using xe by (simp add: comp_def)
qed
qed
lemma swap_delta_finite [simp]: "finite (swap_delta i j D) = finite D"
proof
assume "finite (swap_delta i j D)"
then have "finite (swap_delta i j (swap_delta i j D))"
by (simp add: swap_delta_def)
then show "finite D" by simp
qed (simp add: swap_delta_def)
definition swap_tapes :: "nat ⇒ nat ⇒ ('q, 'a) ktm ⇒ ('q, 'a) ktm" where
"swap_tapes i j M =
KTM (Q_ktm M) (Sigma_ktm M) (Γ_ktm M) (bl_ktm M) (le_ktm M)
(swap_delta i j (delta_ktm M))
(s_ktm M) (t_ktm M) (r_ktm M) (k_ktm M)"
lemma swap_fields [simp]:
"Q_ktm (swap_tapes i j M) = Q_ktm M"
"Sigma_ktm (swap_tapes i j M) = Sigma_ktm M"
"Γ_ktm (swap_tapes i j M) = Γ_ktm M"
"bl_ktm (swap_tapes i j M) = bl_ktm M"
"le_ktm (swap_tapes i j M) = le_ktm M"
"s_ktm (swap_tapes i j M) = s_ktm M"
"t_ktm (swap_tapes i j M) = t_ktm M"
"r_ktm (swap_tapes i j M) = r_ktm M"
"k_ktm (swap_tapes i j M) = k_ktm M"
"delta_ktm (swap_tapes i j M) = swap_delta i j (delta_ktm M)"
by (simp_all add: swap_tapes_def)
lemma swap_tapes_swap_tapes [simp]: "swap_tapes i j (swap_tapes i j M) = M"
by (cases M) (simp add: swap_tapes_def)
text ‹Validity, and the only place the side condition is used: the support
invariant speaks about indices at or above ‹k›, and a transposition of two
indices below ‹k› fixes each of them. The endmarker discipline needs no
side condition, because it is a statement about ∗‹every› index and the
exchange only permutes which one is being spoken about.›
lemma swap_valid:
assumes vM: "valid_ktm M" and i: "i < k_ktm M" and j: "j < k_ktm M"
shows "valid_ktm (swap_tapes i j M)"
proof (cases M)
case M_eq: (KTM Q Sg Gm bl le D s t r k)
have kD: "k_ktm M = k" "bl_ktm M = bl" "le_ktm M = le" "delta_ktm M = D"
using M_eq by simp_all
have W: "swap_tapes i j M = KTM Q Sg Gm bl le (swap_delta i j D) s t r k"
using M_eq by (simp add: swap_tapes_def)
have tuple: "q ∈ Q - {t, r} ∧ q' ∈ Q
∧ (∀m. a m ∈ Gm) ∧ (∀m. a' m ∈ Gm)"
if tr: "(q, a, q', a', d) ∈ swap_delta i j D" for q a q' a' d
proof -
from tr [folded kD] obtain b b' e
where trM: "(q, b, q', b', e) ∈ delta_ktm M"
and ab: "a = b ∘ tswap i j" and ab': "a' = b' ∘ tswap i j"
by (rule swap_delta_E)
from valid_ktm_delta_set [OF vM] trM M_eq
have "q ∈ Q - {t, r}" "q' ∈ Q" "∀m. b m ∈ Gm" "∀m. b' m ∈ Gm"
by (auto simp: Pi_iff)
with ab ab' show ?thesis by (simp add: comp_def)
qed
have LEdisc: "a' m = le ∧ d m ∈ {MoveN, MoveR}"
if tr: "(q, a, q', a', d) ∈ swap_delta i j D" and am: "a m = le"
for q a q' a' d m
proof -
from tr [folded kD] obtain b b' e
where trM: "(q, b, q', b', e) ∈ delta_ktm M"
and ab: "a = b ∘ tswap i j" and ab': "a' = b' ∘ tswap i j"
and de: "d = e ∘ tswap i j"
by (rule swap_delta_E)
from am ab kD have "b (tswap i j m) = le_ktm M" by (simp add: comp_def)
from valid_ktm_deltaLE [OF vM trM this] ab' de kD
show ?thesis by (simp add: comp_def)
qed
have supp: "a m = bl ∧ a' m = bl ∧ d m = MoveN"
if tr: "(q, a, q', a', d) ∈ swap_delta i j D" and m: "k ≤ m"
for q a q' a' d m
proof -
from tr [folded kD] obtain b b' e
where trM: "(q, b, q', b', e) ∈ delta_ktm M"
and ab: "a = b ∘ tswap i j" and ab': "a' = b' ∘ tswap i j"
and de: "d = e ∘ tswap i j"
by (rule swap_delta_E)
from i j kD have ik: "i < k" "j < k" by simp_all
have fix_m: "tswap i j m = m" by (rule tswap_out [OF ik m])
from m kD have "k_ktm M ≤ m" by simp
from valid_ktm_delta_support [OF vM trM this] ab ab' de kD fix_m
show ?thesis by (simp add: comp_def)
qed
have sub: "swap_delta i j D
⊆ (Q - {t, r}) × (UNIV → Gm) × Q × (UNIV → Gm)
× (UNIV → UNIV)"
proof (rule subsetI)
fix x assume x: "x ∈ swap_delta i j D"
obtain q a q' a' d where xe: "x = (q, a, q', a', d)" by (cases x) auto
from tuple [OF x [unfolded xe]] xe
show "x ∈ (Q - {t, r}) × (UNIV → Gm) × Q × (UNIV → Gm)
× (UNIV → UNIV)"
by (simp add: Pi_iff)
qed
have base: "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 vM M_eq by auto
show ?thesis
unfolding W valid_ktm.simps
using base sub LEdisc supp by blast
qed
text ‹Determinism too: two transitions of the exchanged machine on one
state and read vector come from two transitions of ‹M› on one read vector,
because composing with the exchange is injective.›
lemma swap_det:
assumes dM: "det_ktm M"
shows "det_ktm (swap_tapes i j M)"
unfolding det_ktm_def swap_fields
proof (intro allI impI)
fix q A p1 b1 e1 p2 b2 e2
assume t1: "(q, A, p1, b1, e1) ∈ swap_delta i j (delta_ktm M)"
and t2: "(q, A, p2, b2, e2) ∈ swap_delta i j (delta_ktm M)"
from swap_delta_E [OF t1] obtain c1 c1' f1
where r1: "(q, c1, p1, c1', f1) ∈ delta_ktm M" and A1: "A = c1 ∘ tswap i j"
and B1: "b1 = c1' ∘ tswap i j" and E1: "e1 = f1 ∘ tswap i j" .
from swap_delta_E [OF t2] obtain c2 c2' f2
where r2: "(q, c2, p2, c2', f2) ∈ delta_ktm M" and A2: "A = c2 ∘ tswap i j"
and B2: "b2 = c2' ∘ tswap i j" and E2: "e2 = f2 ∘ tswap i j" .
have c: "c1 = c2"
proof
fix x
have "c1 x = (c1 ∘ tswap i j) (tswap i j x)" by simp
also have "… = (c2 ∘ tswap i j) (tswap i j x)" using A1 A2 by simp
also have "… = c2 x" by simp
finally show "c1 x = c2 x" .
qed
from dM r1 r2 [folded c] have "(p1, c1', f1) = (p2, c2', f2)"
unfolding det_ktm_def by blast
then show "(p1, b1, e1) = (p2, b2, e2)" using B1 B2 E1 E2 by simp
qed
text ‹And \<^const>‹le_unique› again, which an exchange of two tape indices
preserves because the property is a conjunction over indices and the exchange
permutes them.›
lemma swap_le_unique:
assumes lu: "le_unique M"
shows "le_unique (swap_tapes i j M)"
using lu by (fastforce simp: le_unique_def swap_tapes_def swap_delta_def)
text ‹The configuration correspondence, and it is a bijection rather than an
embedding --- which is what removes every hypothesis from the two run
lemmas below. Nothing is invented and nothing is discarded, so the reverse
direction is the forward one applied to the exchanged machine and needs no
argument of its own.›
definition swap_config ::
"nat ⇒ nat ⇒ ('a, 'q) ktc_config ⇒ ('a, 'q) ktc_config" where
"swap_config i j c =
KConfig (ktc_state c) (ktc_tape c ∘ tswap i j) (ktc_pos c ∘ tswap i j)"
lemma swap_config_Config [simp]:
"swap_config i j (KConfig q ts n)
= KConfig q (ts ∘ tswap i j) (n ∘ tswap i j)"
by (simp add: swap_config_def)
lemma swap_config_simps [simp]:
"ktc_state (swap_config i j c) = ktc_state c"
"ktc_tape (swap_config i j c) = ktc_tape c ∘ tswap i j"
"ktc_pos (swap_config i j c) = ktc_pos c ∘ tswap i j"
by (simp_all add: swap_config_def)
lemma swap_config_swap_config [simp]:
"swap_config i j (swap_config i j c) = c"
by (cases c) (simp add: comp_def)
lemma swap_step:
assumes step: "(c, c') ∈ ktm_step (delta_ktm M)"
shows "(swap_config i j c, swap_config i j c')
∈ ktm_step (delta_ktm (swap_tapes i j M))"
proof -
from step obtain q ts n q' a d
where c: "c = KConfig q ts n"
and c': "c' = KConfig q' (λm. (ts m)(n m := a m))
(λm. go_move (d m) (n m))"
and tr: "(q, λm. ts m (n m), q', a, d) ∈ delta_ktm M"
by (auto elim!: ktm_step.cases)
let ?s = "tswap i j"
have "(KConfig q (ts ∘ ?s) (n ∘ ?s),
KConfig q' (λm. ((ts ∘ ?s) m)((n ∘ ?s) m := (a ∘ ?s) m))
(λm. go_move ((d ∘ ?s) m) ((n ∘ ?s) m)))
∈ ktm_step (delta_ktm (swap_tapes i j M))"
proof (rule ktm_step.step)
show "(q, λm. (ts ∘ ?s) m ((n ∘ ?s) m), q', a ∘ ?s, d ∘ ?s)
∈ delta_ktm (swap_tapes i j M)"
using swap_delta_I [OF tr, of i j] by (simp add: comp_def)
qed
moreover have "swap_config i j c = KConfig q (ts ∘ ?s) (n ∘ ?s)"
unfolding c by simp
moreover have "swap_config i j c'
= KConfig q' (λm. ((ts ∘ ?s) m)((n ∘ ?s) m := (a ∘ ?s) m))
(λm. go_move ((d ∘ ?s) m) ((n ∘ ?s) m))"
unfolding c' by (simp add: comp_def)
ultimately show ?thesis by simp
qed
lemma swap_run:
assumes run: "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
shows "(swap_config i j c, swap_config i j c')
∈ (ktm_step (delta_ktm (swap_tapes i j M))) ^^ n"
by (rule relpow_map [where h = "swap_config i j", OF _ run]) (erule swap_step)
text ‹The reverse direction, and the whole of its proof: exchange the same two
tapes again. ‹widen_run_rev› next door needs its own inversion argument
because widening is not onto; this one does not.›
lemma swap_run_rev:
assumes run: "(swap_config i j c, e)
∈ (ktm_step (delta_ktm (swap_tapes i j M))) ^^ n"
shows "(c, swap_config i j e) ∈ (ktm_step (delta_ktm M)) ^^ n"
proof -
from swap_run [OF run, of i j]
have "(swap_config i j (swap_config i j c), swap_config i j e)
∈ (ktm_step (delta_ktm (swap_tapes i j (swap_tapes i j M)))) ^^ n" .
then show ?thesis by simp
qed
subsection ‹Pinning two points of an injection›
text ‹Pin two elements at chosen values, and push everything else clear of
both and of a given finite set. ∗‹Which›
injection carries the rest is immaterial --- any injection of a finite set
into \<^typ>‹nat› serves, and ‹finite› supplies one --- so all of the content
is in the offset.
Numbering a machine's states and symbols into an initial segment uses it at
the values ‹0› and ‹1› with nothing to avoid. A composite of two machines
uses the general form: one factor's blank and endmarker have to land on
∗‹the other's›, since a machine has only one of each, while its remaining
symbols must stay clear of the other's alphabet, or a step of one factor
would read a symbol meant for the other.
Injectivity needs only ‹x ≠ y› and ‹u ≠ v›, and in particular ∗‹not›
that either point lies in ‹A›. The offset puts the shifted remainder
strictly above ‹u›, ‹v› and all of ‹B› at once, so no collision is possible
whether or not the pinned points are themselves being numbered. That is
what lets one lemma serve every call without a side condition placing the
blank in the alphabet or the start state in ‹Q›.›
lemma inj_on_pin_two_avoiding:
assumes finA: "finite A" and finB: "finite B"
and xy: "x ≠ y" and uv: "u ≠ v"
obtains h :: "'b ⇒ nat"
where "inj_on h A" and "h x = u" and "h y = v"
and "h ` (A - {x, y}) ∩ B = {}"
proof -
from finite_imp_inj_to_nat_seg [OF finA]
obtain e :: "'b ⇒ nat" where inje: "inj_on e A" by blast
define m where "m = Suc (Max (insert u (insert v B)))"
have fin': "finite (insert u (insert v B))" using finB by simp
have lt: "z < m" if "z ∈ insert u (insert v B)" for z
using Max_ge [OF fin' that] by (simp add: m_def)
have um: "u < m" by (rule lt) simp
have vm: "v < m" by (rule lt) simp
have ltB: "z < m" if "z ∈ B" for z using that by (intro lt) simp
let ?h = "λz. if z = x then u else if z = y then v else m + e z"
have inj: "inj_on ?h A"
proof (rule inj_onI)
fix a b
assume a: "a ∈ A" and b: "b ∈ A" and eq: "?h a = ?h b"
show "a = b"
proof (cases "a = x ∨ a = y")
case True
with eq xy uv um vm show ?thesis by (auto split: if_splits)
next
case False
with eq um vm have "b ≠ x" "b ≠ y" by (auto split: if_splits)
with False eq have "e a = e b" by simp
with inje a b show ?thesis by (auto dest: inj_onD)
qed
qed
have notB: "?h z ∉ B" if z: "z ∈ A - {x, y}" for z
proof
assume mem: "?h z ∈ B"
from z have "?h z = m + e z" by simp
with mem have "m + e z ∈ B" by simp
from ltB [OF this] show False by simp
qed
show thesis
proof (rule that)
show "inj_on ?h A" by (rule inj)
show "?h x = u" by simp
show "?h y = v" using xy by simp
show "?h ` (A - {x, y}) ∩ B = {}" using notB by blast
qed
qed
end