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
    ― ‹the negated window condition is a ∗‹conjunction›, whose normal form is
        an implication and so not a rewrite ⬚‹simp› can fire on the
        ⬚‹if›; ‹if_not_P› turns it into one›
    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
  ― ‹inside the window the factor's tapes are the composite's, shifted›
  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
  ― ‹stated in ‹C›-normal form: ⬚‹unfolding› normalises with all its
      equations at once, so an ‹eu› mentioning ‹C› could never match›
  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 ‹'qN × 'qD × 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 p1 b1 d1 p2 b2 d2.
       (q, a, p1, b1, d1) ∈ D ⟹
       (q, a, p2, b2, d2) ∈ D ⟹
       (p1, b1, d1) = (p2, b2, d2)"
      and supp:
    "⋀q a p b d. (q, a, p, b, d) ∈ D ⟹
      (⋀j. k ≤ j ⟹ a j = bl)"
      and tr1: "(Q, A, Q1, A1, E1)
                    ∈ embed_delta off k k' Γ bl D"
      and tr2: "(Q, A, Q2, A2, E2)
                    ∈ embed_delta off k k' Γ bl D"
  shows "(Q1, A1, E1) = (Q2, A2, E2)"
proof -
  from tr1 obtain q1 a1 p1 b1 d1 c1
    where in1: "(q1, a1, p1, b1, d1) ∈ D"
      and c1: "c1 ∈ free_context Γ bl k'"
      and Q1: "Q = q1"
      and T1: "Q1 = p1"
      and A1: "A = (λj. if off ≤ j ∧ j < off + k
                              then a1 (j - off) else c1 j)"
      and W1: "A1 = (λj. if off ≤ j ∧ j < off + k
                              then b1 (j - off) else c1 j)"
      and M1: "E1 = (λj. if off ≤ j ∧ j < off + k
                              then d1 (j - off) else MoveN)"
    by (auto simp: embed_delta_def)
  from tr2 obtain q2 a2 p2 b2 d2 c2
    where in2: "(q2, a2, p2, b2, d2) ∈ D"
      and c2: "c2 ∈ free_context Γ bl k'"
      and Q2: "Q = q2"
      and T2: "Q2 = p2"
      and A2: "A = (λj. if off ≤ j ∧ j < off + k
                              then a2 (j - off) else c2 j)"
      and W2: "A2 = (λj. if off ≤ j ∧ j < off + k
                              then b2 (j - off) else c2 j)"
      and M2: "E2 = (λj. if off ≤ j ∧ j < off + k
                              then d2 (j - off) else MoveN)"
    by (auto simp: embed_delta_def)
  have qeq: "q1 = q2" using Q1 Q2 by simp
  have aread: "a1 = a2"
  proof (rule ext)
    fix j
    show "a1 j = a2 j"
    proof (cases "j < k")
      case True
      have x1: "A (j + off) = a1 j"
        using fun_cong [OF A1, of "j + off"] True by simp
      have x2: "A (j + off) = a2 j"
        using fun_cong [OF A2, of "j + off"] True by simp
      from x1 x2 show ?thesis by simp
    next
      case False
      have jge: "k ≤ j" using False by simp
      have s1: "a1 j = bl"
        using supp [OF in1] jge by blast
      have s2: "a2 j = bl"
        using supp [OF in2] jge by blast
      from s1 s2 show ?thesis by simp
    qed
  qed
  have in2': "(q1, a1, p2, b2, d2) ∈ D"
    using in2 qeq aread by simp
  have out: "(p1, b1, d1) = (p2, b2, d2)"
    by (rule det [OF in1 in2'])
  have beq: "b1 = b2" using out by (simp add: prod_eq_iff)
  have deq: "d1 = d2" using out by (simp add: prod_eq_iff)
  have ceq: "⋀j. ¬ (off ≤ j ∧ j < off + k)
                    ⟹ c1 j = c2 j"
  proof -
    fix j
    assume outside: "¬ (off ≤ j ∧ j < off + k)"
    have x1: "A j = c1 j"
      using fun_cong [OF A1, of j] outside by simp
    have x2: "A j = c2 j"
      using fun_cong [OF A2, of j] outside by simp
    from x1 x2 show "c1 j = c2 j" by simp
  qed
  have Weq: "A1 = A2"
  proof (rule ext)
    fix j
    show "A1 j = A2 j"
    proof (cases "off ≤ j ∧ j < off + k")
      case True
      have w1j: "A1 j = b1 (j - off)"
        using fun_cong [OF W1, of j] True by simp
      have w2j: "A2 j = b2 (j - off)"
        using fun_cong [OF W2, of j] True by simp
      from w1j w2j beq show ?thesis by simp
    next
      case False
      have w1j: "A1 j = c1 j"
        using fun_cong [OF W1, of j] False by simp
      have w2j: "A2 j = c2 j"
        using fun_cong [OF W2, of j] False by simp
      from w1j w2j ceq [OF False] show ?thesis by simp
    qed
  qed
  have Meq: "E1 = E2"
  proof (rule ext)
    fix j
    show "E1 j = E2 j"
    proof (cases "off ≤ j ∧ j < off + k")
      case True
      have m1j: "E1 j = d1 (j - off)"
        using fun_cong [OF M1, of j] True by simp
      have m2j: "E2 j = d2 (j - off)"
        using fun_cong [OF M2, of j] True by simp
      from m1j m2j deq show ?thesis by simp
    next
      case False
      have m1j: "E1 j = MoveN"
        using fun_cong [OF M1, of j] False by simp
      have m2j: "E2 j = MoveN"
        using fun_cong [OF M2, of j] False by simp
      from m1j m2j show ?thesis by simp
    qed
  qed
  from out have "p1 = p2" by simp
  with Q1 Q2 T1 T2 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 p1 b1 d1 p2 b2 d2.
       (q, a, p1, b1, d1) ∈ D ⟹
       (q, a, p2, b2, d2) ∈ D ⟹
       (p1, b1, d1) = (p2, b2, d2)"
      and tr1: "(Q, A, Q1, A1, E1) ∈ tag_delta u v D"
      and tr2: "(Q, A, Q2, A2, E2) ∈ tag_delta u v D"
  shows "(Q1, A1, E1) = (Q2, A2, E2)"
proof -
  from tr1 obtain q1 q1' where t1: "(q1, A, q1', A1, E1) ∈ D"
      and Q1: "Q = u q1" and T1: "Q1 = v q1'"
    unfolding tag_delta_def by auto
  from tr2 obtain q2 q2' where t2: "(q2, A, q2', A2, E2) ∈ D"
      and Q2: "Q = u q2" and T2: "Q2 = v q2'"
    unfolding tag_delta_def by auto
  from Q1 Q2 have "u q2 = u q1" by simp
  then have "q2 = q1" by (rule injD [OF u])
  with t2 have "(q1, A, q2', A2, E2) ∈ D" by simp
  from det [OF t1 this] have "(q1', A1, E1) = (q2', A2, E2)" .
  with T1 T2 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"
  ― ‹read back to the tuple it came from before the discipline is applied;
      handed the image directly, ⬚‹auto› rewrites with ‹w› and loses ‹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)
  ― ‹every step leaves a state that is not final, whichever arm took it›
  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