Theory Multitape_Embedding
theory Multitape_Embedding
imports Multitape_Run_Facts
begin
section ‹Placing a machine inside a composite›
text ‹A composite machine runs several factors on one frame: each gets a
window of the tapes and a region of the state space, and outside its own
window and region it must be inert. This theory is the machinery for
saying that once --- ‹embed_delta› on the tape side,
‹tag_delta› on the state side, and the correspondences that let a
factor's run be read as the composite's. A factor's transition relation,
placed in this way, is called an ∗‹arm› of the composite.
❙‹It is not a combinator, which is why it is not in
‹Multitape_Relabelling›.› Those take a machine to a machine. Nothing here
builds a machine at all: ‹embed_delta› and ‹tag_delta› place a
∗‹transition relation› into a larger frame, and what assembles the
results into a machine is the consumer, which knows how many factors there
are and what else the composite does. The two theories are siblings over
‹Multitape_Run_Facts› and neither imports the other; the citation graph has no
edge between them in either direction.
The order to read it in is the order it is written: place the tapes, place
the states, then what a run leaves behind --- which is the invariant the
forward direction needs and the one place a factor's \<^const>‹valid_ktm›
is spent.›
subsection ‹Placing a machine among other tapes›
text ‹‹widen_tapes› (‹Multitape_Relabelling›, a sibling this theory does
not import) puts a machine into a wider tape frame at offset
zero, with the added tapes inert because their heads are parked. A composite
of two machines needs the same move at a ∗‹nonzero› offset, and with the
other tapes live --- they are the other factor's, so their heads are wherever
that factor left them and their cells hold whatever it wrote.
That difference is why this is a separate construction rather than a
parameter of the widening. ‹widen_delta› can pad the reads on the
added tapes with a single symbol, the endmarker, because a parked head reads
cell 0 forever. Here there is no such symbol: a transition of one factor has
to be paired with ∗‹every› admissible reading of the other factor's tapes,
which is what ‹free_context› ranges over. The pairing is what makes the arm
inert --- each such reading is written straight back and the head does not
move --- so ‹embed_delta_frozen› below is precisely the hypothesis
‹ktm_step_frozen_tape› asks for.
❙‹The context has to be a finite set, and that is the one real obligation.›
\<^const>‹valid_ktm› requires a finite transition relation, and an arm is a
product of the factor's tuples with the contexts. The substrate's
‹finite_tail_const_funcs› is the tool: its shape is reads ranging in a finite
set and constant beyond an index, which is what a context is. Stating
‹free_context› in that shape --- rather than the more natural "in ‹Γ› below
‹k'›, unconstrained above" --- is what makes the finiteness proof one rule
application instead of a subset argument.›
definition free_context :: "'a set ⇒ 'a ⇒ nat ⇒ (nat ⇒ 'a) set" where
"free_context Γ bl k' =
{b. (∀j. b j ∈ Γ) ∧ (∀j ≥ k'. b j = bl)}"
definition embed_delta ::
"nat ⇒ nat ⇒ nat ⇒ 'a set ⇒ 'a
⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set
⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set" where
"embed_delta off k k' Γ bl D =
(λ((q, a, q', a', d), b).
(q, λj. if off ≤ j ∧ j < off + k then a (j - off) else b j,
q', λj. if off ≤ j ∧ j < off + k then a' (j - off) else b j,
λj. if off ≤ j ∧ j < off + k then d (j - off) else MoveN))
` (D × free_context Γ bl k')"
lemma free_context_finite:
assumes fG: "finite Γ"
shows "finite (free_context Γ bl k')"
unfolding free_context_def
by (rule finite_tail_const_funcs [OF fG])
text ‹The connector to the previous subsection: outside its own window an arm
reads what is there, writes it back, and stays. Stated in the ‹∀›-form
‹ktm_step_frozen_tape› consumes, so the two compose by ‹OF›.›
lemma embed_delta_frozen:
assumes j: "j < off ∨ off + k ≤ j"
shows "∀q a q' a' d. (q, a, q', a', d) ∈ embed_delta off k k' Γ bl D
⟶ a' j = a j ∧ d j = MoveN"
using j by (auto simp: embed_delta_def)
lemma embed_delta_support:
assumes fit: "off + k ≤ k'" and j: "k' ≤ j"
shows "∀q a q' a' d. (q, a, q', a', d) ∈ embed_delta off k k' Γ bl D
⟶ a j = bl ∧ a' j = bl ∧ d j = MoveN"
using fit j by (auto simp: embed_delta_def free_context_def)
text ‹The third connector, and the one an arm needs to inherit its factor's
endmarker discipline. It is the frozen/window split again: inside the window
the write is the factor's own and the hypothesis applies after shifting the
index, and outside it the arm writes back what it read, so there is nothing
to check. Stated on the raw relation rather than on \<^const>‹le_unique›,
because an arm is a set of tuples and not yet a machine --- and in the
‹∀›-form of the two connectors above rather than as a rule with the
membership as a premise. That is not cosmetic: in the premise form both this
lemma and ‹tag_delta_le_unique› leave the window parameters schematic, and
chaining them with ⬚‹OF› reports multiple unifiers. As closed
propositions they compose first-order.›
lemma embed_delta_le_unique:
assumes lu: "∀q a q' a' d j. (q, a, q', a', d) ∈ D
⟶ a' j = le ⟶ a j = le"
shows "∀q a q' a' d j. (q, a, q', a', d) ∈ embed_delta off k k' Γ bl D
⟶ a' j = le ⟶ a j = le"
proof (intro allI impI)
fix q a q' a' d and j :: nat
assume mem: "(q, a, q', a', d) ∈ embed_delta off k k' Γ bl D"
and w: "a' j = le"
from mem obtain p b p' b' e c
where tup: "(p, b, p', b', e) ∈ D"
and a: "a = (λi. if off ≤ i ∧ i < off + k then b (i - off) else c i)"
and a': "a' = (λi. if off ≤ i ∧ i < off + k then b' (i - off) else c i)"
by (auto simp: embed_delta_def)
show "a j = le"
proof (cases "off ≤ j ∧ j < off + k")
case True
with w a' have "b' (j - off) = le" by simp
with lu tup have "b (j - off) = le" by blast
with True a show ?thesis by simp
next
case False
then have out: "¬ (off ≤ j ∧ j < off + k)" by blast
from w a' have "c j = le" by (simp add: if_not_P [OF out])
with a show ?thesis by (simp add: if_not_P [OF out])
qed
qed
lemma embed_delta_finite:
assumes fD: "finite D" and fG: "finite Γ"
shows "finite (embed_delta off k k' Γ bl D)"
unfolding embed_delta_def
using fD free_context_finite [OF fG] by blast
text ‹What a step of an arm does, in the two halves the composite argument
needs. Outside the window it does nothing, which is the previous subsection
applied through ‹embed_delta_frozen› --- a rule application, not a proof.
Inside it, the arm is the factor, which is ‹embed_step_rev› below.›
lemma embed_step_outside:
assumes step: "(C, C') ∈ ktm_step (embed_delta off k k' Γ bl D)"
and j: "j < off ∨ off + k ≤ j"
shows "ktc_tape C' j = ktc_tape C j ∧ ktc_pos C' j = ktc_pos C j"
by (rule ktm_step_frozen_tape [OF step embed_delta_frozen [OF j]])
text ‹The window, read back as a configuration of the factor. Beyond the
factor's own tape count the projection is uniformly blank with the head at
the origin --- not an arbitrary choice, but what \<^const>‹valid_config_ktm›
demands of the factor, so the projection of a composite configuration is a
configuration the factor could actually be in.›
definition proj_config ::
"nat ⇒ nat ⇒ 'a ⇒ ('a, 'q) ktc_config ⇒ ('a, 'q) ktc_config" where
"proj_config off k bl C =
KConfig (ktc_state C)
(λj. if j < k then ktc_tape C (j + off) else (λ_. bl))
(λj. if j < k then ktc_pos C (j + off) else 0)"
lemma proj_config_state [simp]:
"ktc_state (proj_config off k bl C) = ktc_state C"
by (simp add: proj_config_def)
text ‹\<^const>‹ktc_tape› returns a function rather than a value, so its
selector equation rewrites only once the goal is pointwise; ‹fun_eq_iff›
is what makes it fire, as in ‹widen_step›. Doing that once here keeps it out
of every consumer.›
lemma proj_config_Config [simp]:
"proj_config off k bl (KConfig q ts n)
= KConfig q (λj. if j < k then ts (j + off) else (λ_. bl))
(λj. if j < k then n (j + off) else 0)"
by (simp add: proj_config_def fun_eq_iff)
text ‹The same content through the selectors, for the case the rule above
does not reach: an argument that is not literally a \<^const>‹KConfig›. With
the datatype's own ‹ktc_config.expand› (followed by ‹intro conjI›) these
turn an equation between configurations into three equations between
components, which is the form in which the \<^const>‹ktc_tape› eta-problem above
stops mattering --- each component ∗‹is› a function equation, so
‹fun_eq_iff› has something to bite on.›
lemma proj_config_tape [simp]:
"ktc_tape (proj_config off k bl C)
= (λj. if j < k then ktc_tape C (j + off) else (λ_. bl))"
by (simp add: proj_config_def)
lemma proj_config_pos [simp]:
"ktc_pos (proj_config off k bl C)
= (λj. if j < k then ktc_pos C (j + off) else 0)"
by (simp add: proj_config_def)
text ‹❙‹The projection sees the window and nothing else›, which is obvious
from the definition and worth having as a rule because the consumer that
needs it has a composite it cannot rewrite. Two configurations of the whole
machine agreeing on one factor's tapes and heads project to the same
configuration of that factor, whatever they do elsewhere --- so a phase that
writes outside the window leaves every later projection of it alone.›
lemma proj_config_cong:
assumes st: "ktc_state X = ktc_state Y"
and tp: "⋀j. j < k ⟹ ktc_tape X (j + off) = ktc_tape Y (j + off)"
and ps: "⋀j. j < k ⟹ ktc_pos X (j + off) = ktc_pos Y (j + off)"
shows "proj_config off k bl X = proj_config off k bl Y"
using assms by (simp add: proj_config_def fun_eq_iff)
text ‹❙‹The support hypothesis is doing real work and is not decoration.›
Beyond the factor's tape count the projection is blank with a parked head,
and a step has to leave it that way; that holds exactly because a valid
factor's transitions are blank and stationary there. Callers discharge it
from ‹valid_ktm_delta_support›. It is stated in the ‹∀›-form because a
meta-quantified premise passed with ‹OF› is a higher-order pattern that
the unifier cannot solve uniquely, while an object-level one matches
directly.›
lemma embed_step_rev:
assumes step: "(C, C') ∈ ktm_step (embed_delta off k k' Γ bl D)"
and supp: "∀q a q' a' d. (q, a, q', a', d) ∈ D
⟶ (∀j ≥ k. a j = bl ∧ a' j = bl ∧ d j = MoveN)"
shows "(proj_config off k bl C, proj_config off k bl C') ∈ ktm_step D"
proof -
from step obtain q ts n q' A Dd where
C: "C = KConfig q ts n"
and C': "C' = KConfig q' (λj. (ts j)(n j := A j))
(λj. go_move (Dd j) (n j))"
and tr: "(q, λj. ts j (n j), q', A, Dd)
∈ embed_delta off k k' Γ bl D"
by (auto elim!: ktm_step.cases)
from tr obtain a a' d b where
inD: "(q, a, q', a', d) ∈ D"
and rd: "(λj. ts j (n j))
= (λj. if off ≤ j ∧ j < off + k then a (j - off) else b j)"
and wr: "A = (λj. if off ≤ j ∧ j < off + k then a' (j - off) else b j)"
and dd: "Dd = (λj. if off ≤ j ∧ j < off + k
then d (j - off) else MoveN)"
by (auto simp: embed_delta_def)
from supp inD have sa: "⋀j. k ≤ j ⟹ a j = bl"
and sa': "⋀j. k ≤ j ⟹ a' j = bl"
and sd: "⋀j. k ≤ j ⟹ d j = MoveN"
by blast+
let ?tp = "λj. if j < k then ts (j + off) else (λ_. bl)"
let ?np = "λj. if j < k then n (j + off) else 0"
have pc: "proj_config off k bl C = KConfig q ?tp ?np"
unfolding C by simp
have read: "(λj. ?tp j (?np j)) = a"
proof (rule ext)
fix j
show "?tp j (?np j) = a j"
proof (cases "j < k")
case True
from fun_cong [OF rd, of "j + off"] True
have "ts (j + off) (n (j + off)) = a j" by simp
with True show ?thesis by simp
next
case False
with sa show ?thesis by simp
qed
qed
have tape': "(λj. if j < k then (ts (j + off))(n (j + off) := A (j + off))
else (λ_. bl))
= (λj. (?tp j)(?np j := a' j))"
proof (rule ext)
fix j
show "(if j < k then (ts (j + off))(n (j + off) := A (j + off))
else (λ_. bl)) = (?tp j)(?np j := a' j)"
proof (cases "j < k")
case True
from fun_cong [OF wr, of "j + off"] True
have "A (j + off) = a' j" by simp
with True show ?thesis by simp
next
case False
with sa' show ?thesis by (simp add: fun_eq_iff)
qed
qed
have pos': "(λj. if j < k then go_move (Dd (j + off)) (n (j + off)) else 0)
= (λj. go_move (d j) (?np j))"
proof (rule ext)
fix j
show "(if j < k then go_move (Dd (j + off)) (n (j + off)) else 0)
= go_move (d j) (?np j)"
proof (cases "j < k")
case True
from fun_cong [OF dd, of "j + off"] True
have "Dd (j + off) = d j" by simp
with True show ?thesis by simp
next
case False
with sd show ?thesis by simp
qed
qed
have pc': "proj_config off k bl C'
= KConfig q' (λj. (?tp j)(?np j := a' j))
(λj. go_move (d j) (?np j))"
unfolding C' using tape' pos' by simp
show ?thesis
unfolding pc pc'
proof (rule ktm_step.step)
show "(q, λj. ?tp j (?np j), q', a', d) ∈ D"
using read inD by simp
qed
qed
lemma embed_run_rev:
assumes supp: "∀q a q' a' d. (q, a, q', a', d) ∈ D
⟶ (∀j ≥ k. a j = bl ∧ a' j = bl ∧ d j = MoveN)"
and run: "(C, C') ∈ ktm_step (embed_delta off k k' Γ bl D) ^^ N"
shows "(proj_config off k bl C, proj_config off k bl C') ∈ ktm_step D ^^ N"
using run
proof (induction 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 (embed_delta off k k' Γ bl D) ^^ N"
and EC': "(E, C') ∈ ktm_step (embed_delta off k k' Γ bl D)"
by auto
from Suc.IH [OF CE] embed_step_rev [OF EC' supp] show ?case by auto
qed
text ‹The forward direction. Where the reverse lemma projects, this one
∗‹updates›: the factor moves inside the window and everything else stays as
the composite configuration had it.
❙‹The agreement hypothesis is ‹proj_config off k bl C = c› rather than a
predicate of its own›, which is what makes the two directions compose without
a translation step --- the reverse lemma ∗‹produces› exactly this equation.
It also says more than "the window matches": it pins the factor's tapes
beyond its own count to blank with the head at the origin, which is what
\<^const>‹valid_config_ktm› asks of the factor anyway.
❙‹No support hypothesis here, unlike the reverse direction.› Going this way
nothing outside the window is claimed about the factor's transitions: the
frozen tapes are carried by the context ‹b›, which is chosen to be the
composite's own reads, so each is written straight back whatever the factor's
tuple says beyond ‹k›. The obligation that replaces it is ‹ctx›, and that
one is about the ∗‹composite› configuration rather than the factor.›
definition embed_update ::
"nat ⇒ nat ⇒ ('a, 'q) ktc_config ⇒ ('a, 'q) ktc_config
⇒ ('a, 'q) ktc_config" where
"embed_update off k C c' =
KConfig (ktc_state c')
(λj. if off ≤ j ∧ j < off + k then ktc_tape c' (j - off)
else ktc_tape C j)
(λj. if off ≤ j ∧ j < off + k then ktc_pos c' (j - off)
else ktc_pos C j)"
lemma embed_update_Config [simp]:
"embed_update off k (KConfig Q TS N) (KConfig q' T P)
= KConfig q' (λj. if off ≤ j ∧ j < off + k then T (j - off) else TS j)
(λj. if off ≤ j ∧ j < off + k then P (j - off) else N j)"
by (simp add: embed_update_def fun_eq_iff)
text ‹The state selector separately, because the rule above needs both
arguments to be literal \<^const>‹KConfig› terms and the one an iteration
produces is not. The composite takes the factor's state whole: the window
is where the two frames differ, and the state is not in the window.›
lemma embed_update_state [simp]:
"ktc_state (embed_update off k X c') = ktc_state c'"
by (simp add: embed_update_def)
text ‹The tape selectors, one per side of the window boundary, and they are
what a ∗‹value› read off a composite tape needs. \<^const>‹proj_config› answers
the same question for the whole window at once, but a consumer that wants one
tape --- a counter, a numeral, an output --- would have to project, discard
‹k - 1› tapes and index the survivor. Addressing the cell directly is the
same fact with no packaging, and the second form is the one that says a
neighbouring window read the update as if it had not happened.
Stated at \<^term>‹off + l› rather than at an arbitrary ‹j› in range, because
that is the shape a layout produces: an address is built by adding a
factor-local index to the window's base, so the subtraction the definition
performs cancels syntactically instead of by an arithmetic side goal.›
lemma embed_update_tape_in:
assumes "l < k"
shows "ktc_tape (embed_update off k X c') (off + l) = ktc_tape c' l"
using assms by (simp add: embed_update_def)
lemma embed_update_pos_in:
assumes "l < k"
shows "ktc_pos (embed_update off k X c') (off + l) = ktc_pos c' l"
using assms by (simp add: embed_update_def)
lemma embed_update_tape_out:
assumes "j < off ∨ off + k ≤ j"
shows "ktc_tape (embed_update off k X c') j = ktc_tape X j"
using assms by (auto simp: embed_update_def)
text ‹The head half of the clause above. A caller outside the window
usually wants both: that the cells did not change ∗‹and› that the head
did not move, so that what another factor reads on a tape outside the
window survives a step taken inside it.›
lemma embed_update_pos_out:
assumes "j < off ∨ off + k ≤ j"
shows "ktc_pos (embed_update off k X c') j = ktc_pos X j"
using assms by (auto simp: embed_update_def)
lemma embed_step:
assumes step: "(proj_config off k bl C, c') ∈ ktm_step D"
and ctx: "(λj. ktc_tape C j (ktc_pos C j)) ∈ free_context Γ bl k'"
shows "(C, embed_update off k C c')
∈ ktm_step (embed_delta off k k' Γ bl D)"
proof -
obtain Q TS N where C: "C = KConfig Q TS N" by (cases C)
let ?ts = "λi. if i < k then TS (i + off) else (λ_. bl)"
let ?n = "λi. if i < k then N (i + off) else 0"
have pc: "proj_config off k bl C = KConfig Q ?ts ?n"
unfolding C by simp
from step obtain q ts n q' a' d where
pceq: "proj_config off k bl C = KConfig q ts n"
and c': "c' = KConfig q' (λi. (ts i)(n i := a' i))
(λi. go_move (d i) (n i))"
and tr: "(q, λi. ts i (n i), q', a', d) ∈ D"
by (auto elim!: ktm_step.cases)
from pc pceq have q: "q = Q" and ts: "ts = ?ts" and n: "n = ?n" by auto
have win_ts: "ts (j - off) = TS j" if "off ≤ j" and "j < off + k" for j
proof -
from that have "j - off < k" and "j - off + off = j" by auto
then show ?thesis by (simp add: ts)
qed
have win_n: "n (j - off) = N j" if "off ≤ j" and "j < off + k" for j
proof -
from that have "j - off < k" and "j - off + off = j" by auto
then show ?thesis by (simp add: n)
qed
let ?b = "λj. TS j (N j)"
let ?A = "λj. if off ≤ j ∧ j < off + k then a' (j - off) else ?b j"
let ?Dd = "λj. if off ≤ j ∧ j < off + k then d (j - off) else MoveN"
have ctxb: "?b ∈ free_context Γ bl k'" using ctx unfolding C by simp
have read: "(λj. if off ≤ j ∧ j < off + k
then (λi. ts i (n i)) (j - off) else ?b j) = ?b"
proof (rule ext)
fix j
show "(if off ≤ j ∧ j < off + k
then (λi. ts i (n i)) (j - off) else ?b j) = ?b j"
using win_ts win_n by simp
qed
have inarm: "(Q, ?b, q', ?A, ?Dd) ∈ embed_delta off k k' Γ bl D"
unfolding embed_delta_def
proof (rule image_eqI [where x = "((q, λi. ts i (n i), q', a', d), ?b)"])
show "((q, λi. ts i (n i), q', a', d), ?b)
∈ D × free_context Γ bl k'"
using tr ctxb by simp
qed (use q read in simp)
have tp: "(λj. if off ≤ j ∧ j < off + k
then (ts (j - off))(n (j - off) := a' (j - off)) else TS j)
= (λj. (TS j)(N j := ?A j))"
proof (rule ext)
fix j
show "(if off ≤ j ∧ j < off + k
then (ts (j - off))(n (j - off) := a' (j - off)) else TS j)
= (TS j)(N j := ?A j)"
proof (cases "off ≤ j ∧ j < off + k")
case True
then have "ts (j - off) = TS j" and "n (j - off) = N j"
using win_ts win_n by auto
with True show ?thesis by simp
next
case False
then show ?thesis by (simp add: if_not_P [OF False])
qed
qed
have pp: "(λj. if off ≤ j ∧ j < off + k
then go_move (d (j - off)) (n (j - off)) else N j)
= (λj. go_move (?Dd j) (N j))"
proof (rule ext)
fix j
show "(if off ≤ j ∧ j < off + k
then go_move (d (j - off)) (n (j - off)) else N j)
= go_move (?Dd j) (N j)"
proof (cases "off ≤ j ∧ j < off + k")
case True
then have "n (j - off) = N j" using win_n by auto
with True show ?thesis by simp
next
case False
then show ?thesis by (simp add: if_not_P [OF False])
qed
qed
have eu: "embed_update off k (KConfig Q TS N) c'
= KConfig q' (λj. (TS j)(N j := ?A j))
(λj. go_move (?Dd j) (N j))"
unfolding c' using tp pp by simp
show ?thesis
unfolding C eu
proof (rule ktm_step.step)
show "(Q, λj. TS j (N j), q', ?A, ?Dd)
∈ embed_delta off k k' Γ bl D"
by (rule inarm)
qed
qed
text ‹The two directions are inverse on the window, which is what lets
‹embed_step› be iterated: the composite configuration it produces projects
back to the factor configuration it was given. The hypothesis is the
factor's blank-and-parked tail, exactly what \<^const>‹valid_config_ktm›
supplies --- the projection cannot invent it, because beyond ‹k› the window
carries no information.
❙‹Iterating needs ‹ctx› at every intermediate composite configuration,
and that is an invariant of the ∗‹window› rather than of the composite.›
Which is what makes the forward run lemma statable at all, and it is worth
saying why the opposite looked true. The intermediate configurations of the
iteration are not arbitrary composites: every one of them is
\<^term>‹embed_update off k X d›, equal to the starting ‹X› everywhere outside
the window. So the two clauses of ‹ctx› are re-established from different
places --- outside the window from ‹X›'s own ‹ctx›, unchanged; inside it
from the ∗‹factor's› alphabet clause, and the factor is a machine already.
The composite never has to be valid, and never has to exist. ‹embed_run›
below is the iteration; the three lemmas here are the window algebra it
spends, and they hold with no machine in sight.›
lemma proj_embed_update:
assumes tail: "∀i ≥ k. ktc_tape c' i = (λ_. bl) ∧ ktc_pos c' i = 0"
shows "proj_config off k bl (embed_update off k C c') = c'"
proof -
obtain Q TS N where C: "C = KConfig Q TS N" by (cases C)
obtain q' T P where c': "c' = KConfig q' T P" by (cases c')
from tail c' have tT: "⋀i. k ≤ i ⟹ T i = (λ_. bl)"
and tP: "⋀i. k ≤ i ⟹ P i = 0" by auto
show ?thesis
unfolding C c' by (auto simp: fun_eq_iff tT tP)
qed
text ‹The other inverse, and unlike the one above it needs no hypothesis:
updating a window with what that window already holds is the identity. This
is the iteration's base case, where zero steps of the factor have to leave
the composite configuration syntactically unchanged rather than merely
equivalent on the window.›
lemma embed_update_proj_config:
"embed_update off k X (proj_config off k bl X) = X"
proof -
obtain Q TS N where X: "X = KConfig Q TS N" by (cases X)
show ?thesis unfolding X
by (auto simp: embed_update_def proj_config_def fun_eq_iff)
qed
text ‹And the composition: a second update overwrites the first, because the
window is written wholesale and the outside is carried from the same ‹X›
both times. Without this the induction produces a tower of updates one deep
per step instead of the single one the statement claims.›
lemma embed_update_embed_update:
"embed_update off k (embed_update off k X d) c' = embed_update off k X c'"
by (simp add: embed_update_def fun_eq_iff)
text ‹The invariant itself. ‹ctx› asks two things of the composite's read
vector and they come from opposite sides: every cell is in ‹Γ›, which
inside the window is the factor's alphabet clause and outside is ‹X›'s; and
everything from ‹k'› on is blank, which is ‹X›'s alone --- the window sits
below ‹k'›, so the factor is never asked about it. Hence ‹fit›, and hence
no hypothesis about the factor's own blank.›
lemma embed_update_context:
assumes ctx: "(λj. ktc_tape X j (ktc_pos X j)) ∈ free_context Γ bl k'"
and sym: "⋀j p. ktc_tape c j p ∈ Γ"
and fit: "off + k ≤ k'"
shows "(λj. ktc_tape (embed_update off k X c) j
(ktc_pos (embed_update off k X c) j))
∈ free_context Γ bl k'"
proof -
have out: "¬ (off ≤ j ∧ j < off + k)" if "k' ≤ j" for j
using that fit by simp
show ?thesis
using ctx sym out
by (auto simp: free_context_def embed_update_def)
qed
subsection ‹Placing a machine inside a larger state space›
text ‹The state-side counterpart of the previous subsection, and the second
half of an arm. Placing a factor among other tapes says where it acts; this
says who it is while it acts. A composite of two machines taking turns has
states ‹'q⇩N × 'q⇩D × bool›, and an arm is the moving factor's transitions with
the other factor's state carried along untouched and the turn flipped.
❙‹This is not ‹relabel_delta›, and the difference is the whole
point.› A relabelling applies ∗‹one› map to both ends of a tuple, which is
what makes it a bijection on configurations and lets its language theorem go
through. Here the two ends need ∗‹different› maps, because the turn
component differs between them: an ‹N›-turn tuple starts in a state whose turn
says ‹N› and ends in one whose turn says ‹D›. So this is a genuinely weaker
construction --- no bijection, no language theorem --- and correspondingly it
gets only the two step lemmas a union of arms actually consumes.
‹tag_delta› leaves the tape components of every tuple alone. That is what
lets the previous subsection's facts be reused through it: the frozen and
support properties are conditions on those components, so they survive
tagging verbatim, and ‹tag_delta_frozen› and ‹tag_delta_support› below are
the connectors that say so.›
definition ktc_set_state :: "'r ⇒ ('a, 'q) ktc_config ⇒ ('a, 'r) ktc_config" where
"ktc_set_state p C = KConfig p (ktc_tape C) (ktc_pos C)"
text ‹
The embedding relation carries an arbitrary context on the tapes outside
the factor window. Determinism therefore needs the factor's support
invariant: beyond its own tape count every source read is the fixed blank.
With that invariant, equal composite reads determine equal factor reads in
the window and the support determines the tail; the context is then fixed
outside the window as well.
›
lemma embed_delta_det:
assumes det:
"⋀q a p⇩1 b⇩1 d⇩1 p⇩2 b⇩2 d⇩2.
(q, a, p⇩1, b⇩1, d⇩1) ∈ D ⟹
(q, a, p⇩2, b⇩2, d⇩2) ∈ D ⟹
(p⇩1, b⇩1, d⇩1) = (p⇩2, b⇩2, d⇩2)"
and supp:
"⋀q a p b d. (q, a, p, b, d) ∈ D ⟹
(⋀j. k ≤ j ⟹ a j = bl)"
and tr⇩1: "(Q, A, Q⇩1, A⇩1, E⇩1)
∈ embed_delta off k k' Γ bl D"
and tr⇩2: "(Q, A, Q⇩2, A⇩2, E⇩2)
∈ embed_delta off k k' Γ bl D"
shows "(Q⇩1, A⇩1, E⇩1) = (Q⇩2, A⇩2, E⇩2)"
proof -
from tr⇩1 obtain q⇩1 a⇩1 p⇩1 b⇩1 d⇩1 c⇩1
where in⇩1: "(q⇩1, a⇩1, p⇩1, b⇩1, d⇩1) ∈ D"
and c⇩1: "c⇩1 ∈ free_context Γ bl k'"
and Q⇩1: "Q = q⇩1"
and T⇩1: "Q⇩1 = p⇩1"
and A⇩1: "A = (λj. if off ≤ j ∧ j < off + k
then a⇩1 (j - off) else c⇩1 j)"
and W⇩1: "A⇩1 = (λj. if off ≤ j ∧ j < off + k
then b⇩1 (j - off) else c⇩1 j)"
and M⇩1: "E⇩1 = (λj. if off ≤ j ∧ j < off + k
then d⇩1 (j - off) else MoveN)"
by (auto simp: embed_delta_def)
from tr⇩2 obtain q⇩2 a⇩2 p⇩2 b⇩2 d⇩2 c⇩2
where in⇩2: "(q⇩2, a⇩2, p⇩2, b⇩2, d⇩2) ∈ D"
and c⇩2: "c⇩2 ∈ free_context Γ bl k'"
and Q⇩2: "Q = q⇩2"
and T⇩2: "Q⇩2 = p⇩2"
and A⇩2: "A = (λj. if off ≤ j ∧ j < off + k
then a⇩2 (j - off) else c⇩2 j)"
and W⇩2: "A⇩2 = (λj. if off ≤ j ∧ j < off + k
then b⇩2 (j - off) else c⇩2 j)"
and M⇩2: "E⇩2 = (λj. if off ≤ j ∧ j < off + k
then d⇩2 (j - off) else MoveN)"
by (auto simp: embed_delta_def)
have qeq: "q⇩1 = q⇩2" using Q⇩1 Q⇩2 by simp
have aread: "a⇩1 = a⇩2"
proof (rule ext)
fix j
show "a⇩1 j = a⇩2 j"
proof (cases "j < k")
case True
have x⇩1: "A (j + off) = a⇩1 j"
using fun_cong [OF A⇩1, of "j + off"] True by simp
have x⇩2: "A (j + off) = a⇩2 j"
using fun_cong [OF A⇩2, of "j + off"] True by simp
from x⇩1 x⇩2 show ?thesis by simp
next
case False
have jge: "k ≤ j" using False by simp
have s⇩1: "a⇩1 j = bl"
using supp [OF in⇩1] jge by blast
have s⇩2: "a⇩2 j = bl"
using supp [OF in⇩2] jge by blast
from s⇩1 s⇩2 show ?thesis by simp
qed
qed
have in⇩2': "(q⇩1, a⇩1, p⇩2, b⇩2, d⇩2) ∈ D"
using in⇩2 qeq aread by simp
have out: "(p⇩1, b⇩1, d⇩1) = (p⇩2, b⇩2, d⇩2)"
by (rule det [OF in⇩1 in⇩2'])
have beq: "b⇩1 = b⇩2" using out by (simp add: prod_eq_iff)
have deq: "d⇩1 = d⇩2" using out by (simp add: prod_eq_iff)
have ceq: "⋀j. ¬ (off ≤ j ∧ j < off + k)
⟹ c⇩1 j = c⇩2 j"
proof -
fix j
assume outside: "¬ (off ≤ j ∧ j < off + k)"
have x⇩1: "A j = c⇩1 j"
using fun_cong [OF A⇩1, of j] outside by simp
have x⇩2: "A j = c⇩2 j"
using fun_cong [OF A⇩2, of j] outside by simp
from x⇩1 x⇩2 show "c⇩1 j = c⇩2 j" by simp
qed
have Weq: "A⇩1 = A⇩2"
proof (rule ext)
fix j
show "A⇩1 j = A⇩2 j"
proof (cases "off ≤ j ∧ j < off + k")
case True
have w⇩1j: "A⇩1 j = b⇩1 (j - off)"
using fun_cong [OF W⇩1, of j] True by simp
have w⇩2j: "A⇩2 j = b⇩2 (j - off)"
using fun_cong [OF W⇩2, of j] True by simp
from w⇩1j w⇩2j beq show ?thesis by simp
next
case False
have w⇩1j: "A⇩1 j = c⇩1 j"
using fun_cong [OF W⇩1, of j] False by simp
have w⇩2j: "A⇩2 j = c⇩2 j"
using fun_cong [OF W⇩2, of j] False by simp
from w⇩1j w⇩2j ceq [OF False] show ?thesis by simp
qed
qed
have Meq: "E⇩1 = E⇩2"
proof (rule ext)
fix j
show "E⇩1 j = E⇩2 j"
proof (cases "off ≤ j ∧ j < off + k")
case True
have m⇩1j: "E⇩1 j = d⇩1 (j - off)"
using fun_cong [OF M⇩1, of j] True by simp
have m⇩2j: "E⇩2 j = d⇩2 (j - off)"
using fun_cong [OF M⇩2, of j] True by simp
from m⇩1j m⇩2j deq show ?thesis by simp
next
case False
have m⇩1j: "E⇩1 j = MoveN"
using fun_cong [OF M⇩1, of j] False by simp
have m⇩2j: "E⇩2 j = MoveN"
using fun_cong [OF M⇩2, of j] False by simp
from m⇩1j m⇩2j show ?thesis by simp
qed
qed
from out have "p⇩1 = p⇩2" by simp
with Q⇩1 Q⇩2 T⇩1 T⇩2 Weq Meq show ?thesis by simp
qed
definition tag_delta ::
"('q ⇒ 'r) ⇒ ('q ⇒ 'r)
⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set
⇒ ('r × (nat ⇒ 'a) × 'r × (nat ⇒ 'a) × (nat ⇒ move)) set" where
"tag_delta u v D = (λ(q, a, q', a', d). (u q, a, v q', a', d)) ` D"
text ‹Tagging keeps a functional relation functional when the source tag is
injective: the tagged source names the untagged one, and the rest of a
tuple is carried unchanged.›
lemma tag_delta_det:
assumes u: "inj u"
and det:
"⋀q a p⇩1 b⇩1 d⇩1 p⇩2 b⇩2 d⇩2.
(q, a, p⇩1, b⇩1, d⇩1) ∈ D ⟹
(q, a, p⇩2, b⇩2, d⇩2) ∈ D ⟹
(p⇩1, b⇩1, d⇩1) = (p⇩2, b⇩2, d⇩2)"
and tr⇩1: "(Q, A, Q⇩1, A⇩1, E⇩1) ∈ tag_delta u v D"
and tr⇩2: "(Q, A, Q⇩2, A⇩2, E⇩2) ∈ tag_delta u v D"
shows "(Q⇩1, A⇩1, E⇩1) = (Q⇩2, A⇩2, E⇩2)"
proof -
from tr⇩1 obtain q⇩1 q⇩1' where t⇩1: "(q⇩1, A, q⇩1', A⇩1, E⇩1) ∈ D"
and Q⇩1: "Q = u q⇩1" and T⇩1: "Q⇩1 = v q⇩1'"
unfolding tag_delta_def by auto
from tr⇩2 obtain q⇩2 q⇩2' where t⇩2: "(q⇩2, A, q⇩2', A⇩2, E⇩2) ∈ D"
and Q⇩2: "Q = u q⇩2" and T⇩2: "Q⇩2 = v q⇩2'"
unfolding tag_delta_def by auto
from Q⇩1 Q⇩2 have "u q⇩2 = u q⇩1" by simp
then have "q⇩2 = q⇩1" by (rule injD [OF u])
with t⇩2 have "(q⇩1, A, q⇩2', A⇩2, E⇩2) ∈ D" by simp
from det [OF t⇩1 this] have "(q⇩1', A⇩1, E⇩1) = (q⇩2', A⇩2, E⇩2)" .
with T⇩1 T⇩2 show ?thesis by simp
qed
lemma ktc_set_state_Config [simp]: "ktc_set_state p (KConfig q ts n) = KConfig p ts n"
by (simp add: ktc_set_state_def)
lemma ktc_set_state_state [simp]: "ktc_state (ktc_set_state p C) = p"
by (simp add: ktc_set_state_def)
lemma ktc_set_state_pos [simp]: "ktc_pos (ktc_set_state p C) = ktc_pos C"
by (simp add: ktc_set_state_def)
lemma ktc_set_state_tape [simp]: "ktc_tape (ktc_set_state p C) = ktc_tape C"
by (cases C) simp
text ‹❙‹Re-stating commutes with everything on the tape side, and saying so
once is what keeps it out of the way.› A composite argument alternates
between the two: the tape machinery moves a factor's window, and
\<^const>‹ktc_set_state› puts the composite's state back on top. Left alone the two
interleave, and a \<^const>‹ktc_set_state› sitting between \<^const>‹proj_config› and
its argument blocks every rewrite underneath it --- the simplifier cannot see
past it to the window at all.
The four rules below push \<^const>‹ktc_set_state› outwards until it meets either
another \<^const>‹ktc_set_state› or the state it already carries, at which point it
disappears. \<^const>‹embed_update› and \<^const>‹proj_config› read only tapes and
head positions, and \<^const>‹ktc_set_state› changes neither, so all four are
immediate once unfolded; the value is entirely in their being oriented and
⬚‹simp›.›
lemma ktc_set_state_set_state [simp]: "ktc_set_state p (ktc_set_state q C) = ktc_set_state p C"
by (simp add: ktc_set_state_def)
lemma ktc_set_state_self [simp]: "ktc_set_state (ktc_state C) C = C"
by (cases C) (simp add: ktc_set_state_def)
lemma embed_update_set_state [simp]:
"embed_update off k (ktc_set_state q C) c' = embed_update off k C c'"
by (simp add: embed_update_def fun_eq_iff)
lemma proj_config_set_state [simp]:
"proj_config off k bl (ktc_set_state q C) = ktc_set_state q (proj_config off k bl C)"
by (simp add: proj_config_def ktc_set_state_def fun_eq_iff)
text ‹‹ktc_set_state_self› does not reach the shape an arm step actually produces.
\<^term>‹embed_update off k C c'› carries the factor's new state, so re-stating
it to \<^term>‹ktc_state c'› is a no-op --- but the two state terms are not
syntactically equal, and ‹embed_update_state› points the wrong way to make
them so. Hence a rule of its own.›
lemma ktc_set_state_embed_update [simp]:
"ktc_set_state (ktc_state c') (embed_update off k C c') = embed_update off k C c'"
by (simp add: embed_update_def ktc_set_state_def)
text ‹The other half of what a composite needs: a window the update did not
touch reads exactly as it did before. ‹embed_step_outside› says this one
index at a time about a ∗‹step›; this says it about the whole window at
once, for the update the forward direction produces, and it is the fact that
makes one arm's move invisible to the other factor's projection.
One statement covers both arms because the two windows can be disjoint in
either order: one factor updates below the other's window, and the other
above it.
❙‹The \<^const>‹ktc_set_state› is not decoration --- without it the statement is
false.› Disjoint windows make the tapes and the head positions agree, but
\<^const>‹proj_config› also copies the state through, and \<^const>‹embed_update›
replaces it with the moving factor's. So the two projections genuinely
differ, in exactly the one component the composite was going to overwrite
anyway. The wrapper is what every consumer has around it in any case, since
a factor's projection may not carry a composite state.›
lemma proj_embed_update_disjoint:
assumes disj: "off + k ≤ off' ∨ off' + k' ≤ off"
shows "ktc_set_state q (proj_config off' k' bl (embed_update off k C c'))
= ktc_set_state q (proj_config off' k' bl C)"
proof -
have "¬ (off ≤ j + off' ∧ j + off' < off + k)" if "j < k'" for j
using disj that by auto
then show ?thesis
by (auto simp: ktc_set_state_def proj_config_def embed_update_def fun_eq_iff)
qed
text ‹The connectors to the tape side. Tagging rewrites only the two state
components, so a hypothesis about the reads, the writes and the directions
passes straight through --- which is what lets an arm be built as
‹tag_delta u v (embed_delta …)› and still satisfy everything
‹ktm_step_frozen_tape› and \<^const>‹valid_ktm› ask of it.›
lemma tag_delta_frozen:
assumes "∀q a q' a' d. (q, a, q', a', d) ∈ D ⟶ a' j = a j ∧ d j = MoveN"
shows "∀q a q' a' d. (q, a, q', a', d) ∈ tag_delta u v D
⟶ a' j = a j ∧ d j = MoveN"
using assms by (auto simp: tag_delta_def)
text ‹The support connector is proved by hand rather than by ⬚‹auto›, and
the reason is worth recording. Its conclusion mentions the free variable
‹bl›, so the simplifier orients the instance ‹a j = bl› it derives from the
hypothesis as a rewrite ∗‹toward› ‹bl› --- eliminating ‹bl› from the goal
and leaving the second conjunct as ‹a' j = a j›, which does not follow. The
frozen connector above escapes this because its conclusion has no free
variable to rewrite away.›
lemma tag_delta_support:
assumes sup: "∀q a q' a' d. (q, a, q', a', d) ∈ D
⟶ a j = bl ∧ a' j = bl ∧ d j = MoveN"
shows "∀q a q' a' d. (q, a, q', a', d) ∈ tag_delta u v D
⟶ a j = bl ∧ a' j = bl ∧ d j = MoveN"
proof (intro allI impI)
fix q a q' a' d
assume "(q, a, q', a', d) ∈ tag_delta u v D"
then obtain p p' where "(p, a, p', a', d) ∈ D"
by (auto simp: tag_delta_def)
from sup [rule_format, OF this]
show "a j = bl ∧ a' j = bl ∧ d j = MoveN" .
qed
text ‹The endmarker discipline is a statement about the reads and the writes
alone, so tagging leaves it exactly where it was. It is stated in the
per-tuple form ‹embed_delta_le_unique› produces and consumes, so an arm's
two layers compose by ⬚‹OF›.›
lemma tag_delta_le_unique:
assumes lu: "∀q a q' a' d j. (q, a, q', a', d) ∈ D
⟶ a' j = le ⟶ a j = le"
shows "∀q a q' a' d j. (q, a, q', a', d) ∈ tag_delta u v D
⟶ a' j = le ⟶ a j = le"
proof (intro allI impI)
fix q a q' a' d and j :: nat
assume "(q, a, q', a', d) ∈ tag_delta u v D" and w: "a' j = le"
then obtain p p' where "(p, a, p', a', d) ∈ D"
by (auto simp: tag_delta_def)
with lu w show "a j = le" by blast
qed
lemma tag_delta_finite:
assumes "finite D"
shows "finite (tag_delta u v D)"
using assms by (simp add: tag_delta_def)
lemma tag_delta_states:
assumes "(Q, a, Q', a', d) ∈ tag_delta u v D"
shows "Q ∈ range u ∧ Q' ∈ range v"
using assms by (auto simp: tag_delta_def)
text ‹The two step correspondences. Both are stated with \<^const>‹ktc_set_state›
rather than on constructor patterns, because the consumer meets its
configurations as opaque terms; the constructor forms follow by
⬚‹simp›.›
lemma tag_step:
assumes step: "(c, c') ∈ ktm_step D"
shows "(ktc_set_state (u (ktc_state c)) c, ktc_set_state (v (ktc_state c')) c')
∈ ktm_step (tag_delta u v D)"
proof -
from step obtain q ts n q' a dr where
c_eq: "c = KConfig q ts n"
and c'_eq: "c' = KConfig q'
(λk. (ts k)(n k := a k))
(λk. go_move (dr k) (n k))"
and tr: "(q, λk. ts k (n k), q', a, dr) ∈ D"
by (auto elim: ktm_step.cases)
have "(KConfig (u q) ts n,
KConfig (v q')
(λk. (ts k)(n k := a k))
(λk. go_move (dr k) (n k)))
∈ ktm_step (tag_delta u v D)"
proof (rule ktm_step.step)
show "(u q, λk. ts k (n k), v q', a, dr) ∈ tag_delta u v D"
using tr by (force simp: tag_delta_def)
qed
then show ?thesis by (simp add: c_eq c'_eq)
qed
lemma tag_step_rev:
assumes step: "(C, C') ∈ ktm_step (tag_delta u v D)"
obtains q q' where "ktc_state C = u q" and "ktc_state C' = v q'"
and "(ktc_set_state q C, ktc_set_state q' C') ∈ ktm_step D"
proof -
from step obtain Q ts n Q' a dr where
C_eq: "C = KConfig Q ts n"
and C'_eq: "C' = KConfig Q'
(λk. (ts k)(n k := a k))
(λk. go_move (dr k) (n k))"
and tr: "(Q, λk. ts k (n k), Q', a, dr) ∈ tag_delta u v D"
by (auto elim: ktm_step.cases)
from tr obtain q q' where inD: "(q, λk. ts k (n k), q', a, dr) ∈ D"
and uq: "Q = u q" and vq': "Q' = v q'"
by (auto simp: tag_delta_def)
have inner: "(KConfig q ts n,
KConfig q'
(λk. (ts k)(n k := a k))
(λk. go_move (dr k) (n k)))
∈ ktm_step D"
proof (rule ktm_step.step)
show "(q, λk. ts k (n k), q', a, dr) ∈ D" by (rule inD)
qed
show ?thesis
proof (rule that)
show "ktc_state C = u q" by (simp add: C_eq uq)
show "ktc_state C' = v q'" by (simp add: C'_eq vq')
show "(ktc_set_state q C, ktc_set_state q' C') ∈ ktm_step D"
using inner by (simp add: C_eq C'_eq)
qed
qed
text ‹The forward correspondence iterated. Only the same-tag case is wanted:
a run stays inside the tagged copy, so its two ends carry the same
injection, and that is exactly what lets the steps chain --- the
configuration each step ends on is the one the next begins on, tag and
all. With two different tags the endpoints would not meet and there would
be no run to state.›
lemma tag_run:
assumes run: "(C, C') ∈ (ktm_step D) ^^ n"
shows "(ktc_set_state (u (ktc_state C)) C, ktc_set_state (u (ktc_state C')) C')
∈ (ktm_step (tag_delta u u D)) ^^ n"
by (rule relpow_map [where h = "λC. ktc_set_state (u (ktc_state C)) C", OF _ run])
(erule tag_step)
text ‹The reverse correspondence iterated, and the one hypothesis it needs
that the single step does not: the tag must be injective. ‹tag_step_rev›
hands back ∗‹some› untagged state at each end, and chaining two of them
requires the state the first leg arrives at to be the state the second leg
departs from --- which is a fact about the untagged copy, and only
injectivity gets it back across the tag. Every consumer tags with a
datatype constructor, so it is free where it is spent.
The starting state is a hypothesis rather than an output because the caller
always knows it: a run inverted this way begins at a configuration the
forward direction built.›
lemma tag_run_rev:
assumes inj: "⋀x y. u x = u y ⟹ x = y"
and run: "(C, C') ∈ (ktm_step (tag_delta u u D)) ^^ n"
and st: "ktc_state C = u q"
shows "∃q'. ktc_state C' = u q'
∧ (ktc_set_state q C, ktc_set_state q' C') ∈ (ktm_step D) ^^ n"
using run
proof (induction n arbitrary: C')
case 0
then have "C' = C" by simp
with st show ?case by auto
next
case (Suc n)
from Suc.prems obtain d where d1: "(C, d) ∈ (ktm_step (tag_delta u u D)) ^^ n"
and d2: "(d, C') ∈ ktm_step (tag_delta u u D)" by auto
from Suc.IH [OF d1] obtain p
where p: "ktc_state d = u p"
and left: "(ktc_set_state q C, ktc_set_state p d) ∈ (ktm_step D) ^^ n" by blast
from d2 obtain r r' where r: "ktc_state d = u r" and r': "ktc_state C' = u r'"
and right: "(ktc_set_state r d, ktc_set_state r' C') ∈ ktm_step D"
by (rule tag_step_rev)
from p r have "u p = u r" by simp
then have "p = r" by (rule inj)
with left right have "(ktc_set_state q C, ktc_set_state r' C') ∈ (ktm_step D) ^^ Suc n"
by (auto intro: relpow_Suc_I)
with r' show ?case by blast
qed
text ‹An arm read back to the tuple it came from. The two combinators are
images, so this is nothing but their two definitions composed and
⬚‹auto› would find it each time --- but each time it would leave the caller
to name the six components by hand, and the caller is checking
\<^const>‹valid_ktm›, where every clause needs them. It is the arm-shaped
counterpart of ‹relabel_source›, and stated in the same style.
The order of the two combinators is fixed by the arm's own shape ---
placement inside, tagging outside --- because \<^const>‹tag_delta› changes the
state type and \<^const>‹embed_delta› would then be embedding tuples of the
wrong one.›
lemma arm_source:
assumes "(Q, A, Q', A', E) ∈ tag_delta u v (embed_delta off k k' Γ bl D)"
obtains q a q' a' d b
where "(q, a, q', a', d) ∈ D"
and "b ∈ free_context Γ bl k'"
and "Q = u q" and "Q' = v q'"
and "A = (λj. if off ≤ j ∧ j < off + k then a (j - off) else b j)"
and "A' = (λj. if off ≤ j ∧ j < off + k then a' (j - off) else b j)"
and "E = (λj. if off ≤ j ∧ j < off + k then d (j - off) else MoveN)"
using assms by (auto simp: tag_delta_def embed_delta_def)
subsection ‹What a run leaves behind›
text ‹\<^const>‹free_context› is a hypothesis of every step lemma that carries a
factor's step into an arm, so
something has to supply it, and what supplies it is an invariant of the run
rather than a fact about any one configuration. ‹ktc_tapes_fit› is that
invariant: every cell of every tape holds a symbol of the alphabet, and
every tape above the count is blank throughout --- not merely at the head,
which is what makes it survive a step whose head has moved.
❙‹It is the substrate's \<^const>‹valid_config_ktm›, two clauses of it,
detached from the machine.› The detachment is the point and not an
oversight: a composite carries its two factors' tapes side by side, and the
configuration this has to hold of is not a configuration of either factor,
so there is no machine to name. ‹valid_config_tapes_fit› is the bridge, and
it is one-way --- the substrate's predicate also pins the state and the
endmarker column, neither of which a bare carrier has. Everything about
∗‹establishing› it therefore stays upstream, in ‹valid_reach_ktm› and
‹valid_reach_relpow_ktm›; nothing here re-proves it.
‹heads_parked› is the one genuinely missing half. \<^const>‹valid_config_ktm›
says nothing about head positions, and ‹proj_embed_update› needs the tapes
above the count to be blank ∗‹and› their heads parked, so this much has to
be proved here. ‹frame_tail› is the two together, in the shape that lemma
asks for.›
definition ktc_tapes_fit :: "'a set ⇒ 'a ⇒ nat ⇒ ('a, 'q) ktc_config ⇒ bool"
where
"ktc_tapes_fit Γ bl k C ⟷
(∀j m. ktc_tape C j m ∈ Γ)
∧ (∀j m. k ≤ j ⟶ ktc_tape C j m = bl)"
lemma ktc_tapes_fit_set_state [simp]:
"ktc_tapes_fit Γ bl k (ktc_set_state p C) = ktc_tapes_fit Γ bl k C"
by (simp add: ktc_tapes_fit_def)
lemma ktc_tapes_fit_context:
assumes "ktc_tapes_fit Γ bl k C"
shows "(λj. ktc_tape C j (ktc_pos C j)) ∈ free_context Γ bl k"
using assms by (auto simp: ktc_tapes_fit_def free_context_def)
lemma valid_config_tapes_fit:
assumes "valid_config_ktm M C"
shows "ktc_tapes_fit (Γ_ktm M) (bl_ktm M) (k_ktm M) C"
using assms
by (cases M; cases C) (auto simp: ktc_tapes_fit_def image_subset_iff)
lemma valid_config_state:
assumes "valid_config_ktm M C"
shows "ktc_state C ∈ Q_ktm M"
using assms by (cases M; cases C) auto
text ‹The two together, in the shape ‹proj_embed_update› asks for: beyond
the machine's own tape count the configuration is blank with a parked head,
so the window carries no information the projection has to invent.›
lemma frame_tail:
assumes T: "ktc_tapes_fit Γ bl k C" and H: "heads_parked k C"
shows "∀i ≥ k. ktc_tape C i = (λ_. bl) ∧ ktc_pos C i = 0"
using T H by (auto simp: ktc_tapes_fit_def heads_parked_def fun_eq_iff)
text ‹The forward run, which is what the last three subsections were for: a
run of the factor is a run of the arm, and the composite configuration moves
only inside the window. ‹embed_step› iterated, with the two things
iteration needs supplied at each stage.
❙‹Every hypothesis is the factor's, and that is the whole point.› The
induction re-establishes ‹ctx› at each intermediate composite configuration
from ‹embed_update_context›, whose alphabet side is
\<^term>‹Γ_ktm M ⊆ Γ› and whose blank side is the starting ‹ctx› untouched;
and it re-establishes the projection from ‹proj_embed_update›, whose tail
hypothesis is ‹frame_tail› of the factor's own validity. So the composite
is never required to be a valid machine --- it is never required to be a
machine. \<^const>‹valid_config_ktm› appears once, applied to ‹M›.
‹fit› is the only hypothesis relating the two frames, and it is needed for
one thing: the window must sit below ‹k'› so that the blank tail of ‹ctx›
is never a claim about the factor.›
lemma embed_run:
assumes vM: "valid_ktm M"
and vc: "valid_config_ktm M c"
and hc: "heads_parked (k_ktm M) c"
and proj: "proj_config off (k_ktm M) (bl_ktm M) X = c"
and ctx: "(λj. ktc_tape X j (ktc_pos X j))
∈ free_context Γ (bl_ktm M) k'"
and gam: "Γ_ktm M ⊆ Γ"
and fit: "off + k_ktm M ≤ k'"
and run: "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
shows "(X, embed_update off (k_ktm M) X c')
∈ (ktm_step
(embed_delta off (k_ktm M) k' Γ (bl_ktm M) (delta_ktm M))) ^^ n"
using run
proof (induction n arbitrary: c')
case 0
then have "c' = c" by simp
moreover have "embed_update off (k_ktm M) X c = X"
using proj embed_update_proj_config [of off "k_ktm M" X "bl_ktm M"] by simp
ultimately show ?case by simp
next
case (Suc n)
from Suc.prems obtain d
where cd: "(c, d) ∈ (ktm_step (delta_ktm M)) ^^ n"
and dc': "(d, c') ∈ ktm_step (delta_ktm M)" by auto
note IH = Suc.IH [OF cd]
from valid_reach_relpow_ktm [OF vM vc cd] have vd: "valid_config_ktm M d" .
from valid_config_tapes_fit [OF vd]
have Td: "ktc_tapes_fit (Γ_ktm M) (bl_ktm M) (k_ktm M) d" .
from proj_embed_update [OF frame_tail [OF Td heads_parked_run [OF vM hc cd]]]
have pd: "proj_config off (k_ktm M) (bl_ktm M)
(embed_update off (k_ktm M) X d) = d" .
have ctxd: "(λj. ktc_tape (embed_update off (k_ktm M) X d) j
(ktc_pos (embed_update off (k_ktm M) X d) j))
∈ free_context Γ (bl_ktm M) k'"
proof (rule embed_update_context [OF ctx _ fit])
fix j p
show "ktc_tape d j p ∈ Γ" using Td gam by (auto simp: ktc_tapes_fit_def)
qed
from dc' pd
have "(proj_config off (k_ktm M) (bl_ktm M) (embed_update off (k_ktm M) X d), c')
∈ ktm_step (delta_ktm M)" by simp
from embed_step [OF this ctxd]
have "(embed_update off (k_ktm M) X d, embed_update off (k_ktm M) X c')
∈ ktm_step
(embed_delta off (k_ktm M) k' Γ (bl_ktm M) (delta_ktm M))"
by (simp add: embed_update_embed_update)
from relpow_Suc_I [OF IH this] show ?case .
qed
subsection ‹Two machines taking turns›
text ‹What the previous two subsections were for. A composite whose
transition relation is ‹δ⇩A ∪ δ⇩B›, where every ‹A›-tuple runs from a state
whose turn flag is set to one where it is clear and every ‹B›-tuple does the
reverse, has runs that alternate strictly --- and a run of ‹N› steps from an
‹A›-turn state therefore contains ‹⌈N/2⌉› steps of ‹A› and ‹⌊N/2⌋› of ‹B›,
at the even and odd ticks respectively.
❙‹Which arm took a step is decided by the state alone, not searched for.›
That is the entire dividend of the union shape: ‹ktm_step_Un› turns the
composite step into a disjunction, and ‹ktm_step_state_rel› kills whichever
disjunct disagrees with the turn flag. Neither is available for a lockstep
product, where a step is one joint transition that has to be taken apart.
The conclusion hands back an indexed sequence rather than a pair of runs.
Induction on the iteration count peels from one end, which is the wrong shape
for a claim about ∗‹positions›; ‹relpow_fun_conv› converts once and parity is
ordinary induction on the index. Extracting the two factor runs from the
sequence is the composite's job, because only it knows the windows.
❙‹The asymmetry at odd ‹N› is the point, not an artefact.› Starting on
‹A›'s turn, ‹A› is never behind: after ‹2m› steps each factor has
taken ‹m›, and after ‹2m + 1› the factor ‹A› has taken one more. A
composite that counts one factor's steps can therefore read off the other's
exactly.
❙‹A step may end the run.› A step into a state with no successors
--- ‹final›, which no tuple of either arm leaves --- may land on either turn
flag, so both arms can share an accepting or rejecting state. Such a state
can only be the last of a run, so the alternation is untouched, and parity
is claimed only at the states that are not final.›
lemma arms_alternate:
assumes A_turn: "∀q a q' a' d. (q, a, q', a', d) ∈ δ⇩A
⟶ turn q ∧ ¬ final q ∧ (turn q' ⟶ final q')"
and B_turn: "∀q a q' a' d. (q, a, q', a', d) ∈ δ⇩B
⟶ ¬ turn q ∧ ¬ final q ∧ (¬ turn q' ⟶ final q')"
and run: "(C, C') ∈ ktm_step (δ⇩A ∪ δ⇩B) ^^ N"
and start: "turn (ktc_state C)"
obtains f where "f 0 = C" and "f N = C'"
and "⋀i. i ≤ N ⟹ ¬ final (ktc_state (f i))
⟹ turn (ktc_state (f i)) = even i"
and "⋀i. i < N ⟹ even i ⟹ (f i, f (Suc i)) ∈ ktm_step δ⇩A"
and "⋀i. i < N ⟹ odd i ⟹ (f i, f (Suc i)) ∈ ktm_step δ⇩B"
proof -
let ?RA = "λq q'. turn q ∧ ¬ final q ∧ (turn q' ⟶ final q')"
let ?RB = "λq q'. ¬ turn q ∧ ¬ final q ∧ (¬ turn q' ⟶ final q')"
from run obtain f where f0: "f 0 = C" and fN: "f N = C'"
and fstep: "⋀i. i < N ⟹ (f i, f (Suc i)) ∈ ktm_step (δ⇩A ∪ δ⇩B)"
by (auto simp: relpow_fun_conv)
have split: "(f i, f (Suc i)) ∈ ktm_step δ⇩A
∨ (f i, f (Suc i)) ∈ ktm_step δ⇩B"
if "i < N" for i
using fstep [OF that] by (simp add: ktm_step_Un)
have live: "¬ final (ktc_state (f i))" if iN: "i < N" for i
proof -
from split [OF iN] show ?thesis
proof
assume "(f i, f (Suc i)) ∈ ktm_step δ⇩A"
from ktm_step_state_rel [where R = ?RA, OF this A_turn] show ?thesis by simp
next
assume "(f i, f (Suc i)) ∈ ktm_step δ⇩B"
from ktm_step_state_rel [where R = ?RB, OF this B_turn] show ?thesis by simp
qed
qed
have parity: "i ≤ N ⟶ ¬ final (ktc_state (f i))
⟶ turn (ktc_state (f i)) = even i" for i
proof (induction i)
case 0
show ?case using f0 start by simp
next
case (Suc i)
show ?case
proof (intro impI)
assume sN: "Suc i ≤ N" and nf: "¬ final (ktc_state (f (Suc i)))"
then have iN: "i < N" by simp
from Suc.IH iN live [OF iN] have ih: "turn (ktc_state (f i)) = even i" by simp
from split [OF iN] show "turn (ktc_state (f (Suc i))) = even (Suc i)"
proof
assume "(f i, f (Suc i)) ∈ ktm_step δ⇩A"
from ktm_step_state_rel [where R = ?RA, OF this A_turn]
have "turn (ktc_state (f i))" and "¬ turn (ktc_state (f (Suc i)))"
using nf by simp_all
with ih show ?thesis by simp
next
assume "(f i, f (Suc i)) ∈ ktm_step δ⇩B"
from ktm_step_state_rel [where R = ?RB, OF this B_turn]
have "turn (ktc_state (f (Suc i)))" and "¬ turn (ktc_state (f i))"
using nf by simp_all
with ih show ?thesis by simp
qed
qed
qed
have selA: "(f i, f (Suc i)) ∈ ktm_step δ⇩A"
if iN: "i < N" and ev: "even i" for i
proof (cases "(f i, f (Suc i)) ∈ ktm_step δ⇩A")
case True
then show ?thesis .
next
case False
with split [OF iN] have inB: "(f i, f (Suc i)) ∈ ktm_step δ⇩B" by blast
from ktm_step_state_rel [where R = ?RB, OF inB B_turn]
have "¬ turn (ktc_state (f i))" by simp
moreover have "turn (ktc_state (f i))" using parity live [OF iN] iN ev by simp
ultimately show ?thesis by simp
qed
have selB: "(f i, f (Suc i)) ∈ ktm_step δ⇩B"
if iN: "i < N" and od: "odd i" for i
proof (cases "(f i, f (Suc i)) ∈ ktm_step δ⇩B")
case True
then show ?thesis .
next
case False
with split [OF iN] have inA: "(f i, f (Suc i)) ∈ ktm_step δ⇩A" by blast
from ktm_step_state_rel [where R = ?RA, OF inA A_turn]
have "turn (ktc_state (f i))" by simp
moreover have "¬ turn (ktc_state (f i))" using parity live [OF iN] iN od by simp
ultimately show ?thesis by simp
qed
show thesis
proof (rule that)
show "f 0 = C" by (rule f0)
show "f N = C'" by (rule fN)
show "⋀i. i ≤ N ⟹ ¬ final (ktc_state (f i))
⟹ turn (ktc_state (f i)) = even i" using parity by simp
show "⋀i. i < N ⟹ even i ⟹ (f i, f (Suc i)) ∈ ktm_step δ⇩A"
by (rule selA)
show "⋀i. i < N ⟹ odd i ⟹ (f i, f (Suc i)) ∈ ktm_step δ⇩B"
by (rule selB)
qed
qed
end