Theory Multitape_Relabelling

theory Multitape_Relabelling
  imports Multitape_Run_Facts
begin

section ‹Transporting a machine along injections›

text ‹Many constructions on machines change the machine's ∗‹type› as well
  as its behaviour: ‹alphabet_enlarge› in ‹Multitape_Alphabet_Enlargement›,
  for instance, takes a ‹('q, 'a) ktm› to a machine over a block alphabet
  ‹'c ⇒ 'a›.  That is the right design for results whose statements
  quantify over the source machine's type.  It is the wrong shape for anything
  that must collect machines in one concrete type, such as an enumeration
  ‹nat ⇒ (nat, nat) ktm›.  HOL has no quantification over types, so a
  class of machines "with any alphabet" has to be represented by a fixed
  universe of machines that is shown to be complete.

  This theory is the bridge.  A machine is transported along an injection on
  states and an injection on the tape alphabet, which changes only the names of
  things, and so preserves the language up to the alphabet map and the running
  time ∗‹exactly›.  Two field-level combinators on the tapes follow:
  ‹widen_tapes› raises the tape count, and ‹swap_tapes› exchanges two
  tapes.  Last comes the injection arithmetic that supplies the relabelling's
  hypotheses.

  ‹Multitape_Run_Facts› holds the facts about runs that mention no
  combinator, and this theory sits over it.  ‹Multitape_Embedding› holds the
  composite machinery, which builds no machine at all and is a
  ∗‹sibling› rather than a layer: neither theory cites the other.›


subsection ‹The combinator›

text ‹‹relabel_ktm f g M› renames states along ‹f› and tape symbols along
  ‹g›.  Transition tuples are rewritten componentwise; the direction
  component is untouched, and the tape count is carried across, so the
  transported machine has the same tape count and the same branching
  structure.›

definition relabel_delta ::
  "('q ⇒ 'p) ⇒ ('a ⇒ 'b)
     ⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set
     ⇒ ('p × (nat ⇒ 'b) × 'p × (nat ⇒ 'b) × (nat ⇒ move)) set" where
  "relabel_delta f g D =
     (λ(q, a, q', a', d). (f q, g ∘ a, f q', g ∘ a', d)) ` D"

definition relabel_ktm ::
  "('q ⇒ 'p) ⇒ ('a ⇒ 'b) ⇒ ('q, 'a) ktm ⇒ ('p, 'b) ktm" where
  "relabel_ktm f g M =
     KTM
       (f ` Q_ktm M)
       (g ` Sigma_ktm M)
       (g ` Γ_ktm M)
       (g (bl_ktm M))
       (g (le_ktm M))
       (relabel_delta f g (delta_ktm M))
       (f (s_ktm M))
       (f (t_ktm M))
       (f (r_ktm M))
       (k_ktm M)"


subsection ‹Structural preservation›

text ‹The selectors go through by construction; these are the lemmas every
  downstream hypothesis discharge needs, and they should all be one-liners
  off const‹relabel_ktm›'s definition.›

lemma relabel_Q_ktm [simp]: "Q_ktm (relabel_ktm f g M) = f ` Q_ktm M"
  by (simp add: relabel_ktm_def)

lemma relabel_k_ktm [simp]: "k_ktm (relabel_ktm f g M) = k_ktm M"
  by (simp add: relabel_ktm_def)

lemma relabel_Sigma_ktm [simp]:
  "Sigma_ktm (relabel_ktm f g M) = g ` Sigma_ktm M"
  by (simp add: relabel_ktm_def)

lemma relabel_Gamma_ktm [simp]:
  "Γ_ktm (relabel_ktm f g M) = g ` Γ_ktm M"
  by (simp add: relabel_ktm_def)

lemma relabel_bl_ktm [simp]: "bl_ktm (relabel_ktm f g M) = g (bl_ktm M)"
  by (simp add: relabel_ktm_def)

lemma relabel_le_ktm [simp]: "le_ktm (relabel_ktm f g M) = g (le_ktm M)"
  by (simp add: relabel_ktm_def)

lemma relabel_s_ktm [simp]: "s_ktm (relabel_ktm f g M) = f (s_ktm M)"
  by (simp add: relabel_ktm_def)

lemma relabel_t_ktm [simp]: "t_ktm (relabel_ktm f g M) = f (t_ktm M)"
  by (simp add: relabel_ktm_def)

lemma relabel_r_ktm [simp]: "r_ktm (relabel_ktm f g M) = f (r_ktm M)"
  by (simp add: relabel_ktm_def)


subsection ‹Validity›

text ‹Validity transports under injectivity on the two carriers.  Both
  injectivity hypotheses are needed and neither is decorative: ‹f› injective
  keeps ‹t ≠ r› apart, and ‹g› injective keeps ‹bl ∉ Σ›, ‹le ∉ Σ› and the
  left-endmarker discipline intact.  Injectivity is asked for only ∗‹on the
  machine's own carriers› rather than globally, which is what lets the
  enumeration's encoding be a partial numbering.›

lemma relabel_source:
  assumes "(q, a, q', a', d) ∈ relabel_delta f g D"
  obtains p b p' b'
  where "(p, b, p', b', d) ∈ D"
    and "q = f p" and "q' = f p'" and "a = g ∘ b" and "a' = g ∘ b'"
  using assms by (auto simp: relabel_delta_def)

lemma relabel_valid:
  assumes vM: "valid_ktm M"
      and injf: "inj_on f (Q_ktm M)"
      and injg: "inj_on g (Γ_ktm M)"
  shows "valid_ktm (relabel_ktm f g M)"
proof (cases M)
  case M_eq: (KTM Q Sg Gm bl le D s t r k)
  have R: "relabel_ktm f g M
             = KTM (f ` Q) (g ` Sg) (g ` Gm) (g bl) (g le)
                    (relabel_delta f g D) (f s) (f t) (f r) k"
    using M_eq by (simp add: relabel_ktm_def)
  have Qf: "inj_on f Q" and Gg: "inj_on g Gm"
    using injf injg M_eq by simp_all
  have base: "finite Q" "finite Gm" "Sg ⊆ Gm" "s ∈ Q" "t ∈ Q" "r ∈ Q"
             "bl ∈ Gm" "bl ∉ Sg" "le ∈ Gm" "le ∉ Sg" "t ≠ r" "0 < k"
    using vM M_eq by auto

  ― ‹the endmarker and blank stay outside the input alphabet only because
      ‹g› is injective on the whole tape alphabet, not merely on ‹Sg››
  have notin: "g x ∉ g ` Sg" if x: "x ∈ Gm" and xS: "x ∉ Sg" for x
  proof
    assume "g x ∈ g ` Sg"
    then obtain y where y: "y ∈ Sg" and gy: "g x = g y" by blast
    from y base(3) have "y ∈ Gm" by blast
    with x gy Gg have "x = y" by (auto dest: inj_onD)
    with y xS show False by simp
  qed

  have tuple: "q ∈ f ` Q - {f t, f r} ∧ q' ∈ f ` Q
               ∧ (∀j. a j ∈ g ` Gm) ∧ (∀j. a' j ∈ g ` Gm)"
    if tr: "(q, a, q', a', d) ∈ relabel_delta f g D" for q a q' a' d
  proof -
    from tr obtain p b p' b'
      where trD: "(p, b, p', b', d) ∈ D"
        and qp: "q = f p" and qp': "q' = f p'"
        and ab: "a = g ∘ b" and ab': "a' = g ∘ b'"
      by (rule relabel_source)
    from trD M_eq have trM: "(p, b, p', b', d) ∈ delta_ktm M" by simp
    from valid_ktm_delta_set [OF vM] trM M_eq
    have p: "p ∈ Q - {t, r}" and p': "p' ∈ Q"
      and bG: "∀j. b j ∈ Gm" and bG': "∀j. b' j ∈ Gm"
      by (auto simp: Pi_iff)
    have "f p ≠ f t" "f p ≠ f r"
      using p base(5,6) Qf by (auto dest: inj_onD)
    with p p' bG bG' qp qp' ab ab' show ?thesis by auto
  qed

  have LEdisc: "a' j = g le ∧ d j ∈ {MoveN, MoveR}"
    if tr: "(q, a, q', a', d) ∈ relabel_delta f g D" and aj: "a j = g le"
    for q a q' a' d j
  proof -
    from tr obtain p b p' b'
      where trD: "(p, b, p', b', d) ∈ D"
        and ab: "a = g ∘ b" and ab': "a' = g ∘ b'"
      by (rule relabel_source)
    from trD M_eq have trM: "(p, b, p', b', d) ∈ delta_ktm M" by simp
    from valid_ktm_delta_set [OF vM] trM M_eq have "b j ∈ Gm"
      by (auto simp: Pi_iff)
    with aj ab base(9) Gg have "b j = le_ktm M"
      using M_eq by (auto dest: inj_onD)
    from valid_ktm_deltaLE [OF vM trM this] ab' M_eq show ?thesis by simp
  qed

  have supp: "a j = g bl ∧ a' j = g bl ∧ d j = MoveN"
    if tr: "(q, a, q', a', d) ∈ relabel_delta f g D" and j: "k ≤ j"
    for q a q' a' d j
  proof -
    from tr obtain p b p' b'
      where trD: "(p, b, p', b', d) ∈ D"
        and ab: "a = g ∘ b" and ab': "a' = g ∘ b'"
      by (rule relabel_source)
    from trD M_eq have trM: "(p, b, p', b', d) ∈ delta_ktm M" by simp
    from j M_eq have "k_ktm M ≤ j" by simp
    from valid_ktm_delta_support [OF vM trM this] ab ab' M_eq
    show ?thesis by simp
  qed

  have sub: "relabel_delta f g D
               ⊆ (f ` Q - {f t, f r}) × (UNIV → g ` Gm) × f ` Q
                   × (UNIV → g ` Gm) × (UNIV → UNIV)"
  proof (rule subsetI)
    fix x assume x: "x ∈ relabel_delta f g D"
    obtain q a q' a' d where xe: "x = (q, a, q', a', d)" by (cases x) auto
    from tuple [OF x [unfolded xe]] xe
    show "x ∈ (f ` Q - {f t, f r}) × (UNIV → g ` Gm) × f ` Q
                × (UNIV → g ` Gm) × (UNIV → UNIV)"
      by (simp add: Pi_iff)
  qed

  have tr_neq: "f t ≠ f r" using base(5,6,11) Qf by (auto dest: inj_onD)

  show ?thesis
    unfolding R valid_ktm.simps
  proof (intro conjI)
    show "finite (f ` Q)" using base(1) by simp
    show "finite (g ` Gm)" using base(2) by simp
    show "g ` Sg ⊆ g ` Gm" using base(3) by blast
    show "f s ∈ f ` Q" using base(4) by simp
    show "f t ∈ f ` Q" using base(5) by simp
    show "f r ∈ f ` Q" using base(6) by simp
    show "g bl ∈ g ` Gm" using base(7) by simp
    show "g bl ∉ g ` Sg" by (rule notin [OF base(7) base(8)])
    show "g le ∈ g ` Gm" using base(9) by simp
    show "g le ∉ g ` Sg" by (rule notin [OF base(9) base(10)])
    show "f t ≠ f r" by (rule tr_neq)
    show "0 < k" by (rule base(12))
    show "relabel_delta f g D
            ⊆ (f ` Q - {f t, f r}) × (UNIV → g ` Gm) × f ` Q
                × (UNIV → g ` Gm) × (UNIV → UNIV)"
      by (rule sub)
    show "∀q a q' a' d j. (q, a, q', a', d) ∈ relabel_delta f g D ⟶
            a j = g le ⟶ a' j = g le ∧ d j ∈ {MoveN, MoveR}"
      using LEdisc by blast
    show "∀q a q' a' d. (q, a, q', a', d) ∈ relabel_delta f g D ⟶
            (∀j ≥ k. a j = g bl ∧ a' j = g bl ∧ d j = MoveN)"
      using supp by blast
  qed
qed

text ‹Determinism is a property of the transition relation's shape, so it
  transports for the same reason.  Both injectivity hypotheses are used here
  and used differently: ‹f› injective is what identifies the two source
  states, and ‹g› injective is what identifies the two read vectors
  pointwise --- without either, two distinct transitions of ‹M› could be
  merged into one branch point.›

lemma relabel_det:
  assumes vM: "valid_ktm M"
      and injf: "inj_on f (Q_ktm M)"
      and injg: "inj_on g (Γ_ktm M)"
      and dM: "det_ktm M"
  shows "det_ktm (relabel_ktm f g M)"
  unfolding det_ktm_def
proof (intro allI impI)
  fix q a p1 b1 d1 p2 b2 d2
  assume "(q, a, p1, b1, d1) ∈ delta_ktm (relabel_ktm f g M)"
     and "(q, a, p2, b2, d2) ∈ delta_ktm (relabel_ktm f g M)"
  then have t1: "(q, a, p1, b1, d1) ∈ relabel_delta f g (delta_ktm M)"
    and t2: "(q, a, p2, b2, d2) ∈ relabel_delta f g (delta_ktm M)"
    by (simp_all add: relabel_ktm_def)
  from t1 obtain u c u' c'
    where s1: "(u, c, u', c', d1) ∈ delta_ktm M"
      and q1: "q = f u" and p1: "p1 = f u'"
      and a1: "a = g ∘ c" and b1: "b1 = g ∘ c'"
    by (rule relabel_source)
  from t2 obtain v e v' e'
    where s2: "(v, e, v', e', d2) ∈ delta_ktm M"
      and q2: "q = f v" and p2: "p2 = f v'"
      and a2: "a = g ∘ e" and b2: "b2 = g ∘ e'"
    by (rule relabel_source)
  from valid_ktm_delta_set [OF vM] s1 s2
  have uQ: "u ∈ Q_ktm M" and vQ: "v ∈ Q_ktm M"
    and cG: "∀j. c j ∈ Γ_ktm M" and eG: "∀j. e j ∈ Γ_ktm M"
    by (auto simp: Pi_iff)
  from q1 q2 uQ vQ injf have uv: "u = v" by (auto dest: inj_onD)
  have ce: "c = e"
  proof
    fix j
    from a1 a2 have "g (c j) = g (e j)" by (simp add: fun_eq_iff)
    with cG eG injg show "c j = e j" by (auto dest: inj_onD)
  qed
  from dM s1 s2 [unfolded uv [symmetric] ce [symmetric]]
  have "(u', c', d1) = (v', e', d2)" by (simp add: det_ktm_def)
  with p1 p2 b1 b2 show "(p1, b1, d1) = (p2, b2, d2)" by simp
qed

text ‹The endmarker write discipline transports too, and unlike the two above
  it spends only ∗‹one› of the injectivities: const‹le_unique› says nothing
  about states, so ‹f› may collapse them freely.  What ‹g› injective buys is
  the one inference the proof turns on --- from term‹g (b j) = g (le_ktm M)›
  back to term‹b j = le_ktm M› --- and validity is what places both sides
  inside ‹Γ›, where injectivity is assumed.  Without it a relabelling could
  identify the endmarker with an ordinary symbol and manufacture a write that
  the original never made.›

lemma relabel_le_unique:
  assumes vM: "valid_ktm M"
      and injg: "inj_on g (Γ_ktm M)"
      and lu: "le_unique M"
  shows "le_unique (relabel_ktm f g M)"
  unfolding le_unique_def
proof (intro allI impI)
  fix q a q' a' d and j :: nat
  assume "(q, a, q', a', d) ∈ delta_ktm (relabel_ktm f g M)"
  then have t: "(q, a, q', a', d) ∈ relabel_delta f g (delta_ktm M)"
    by (simp add: relabel_ktm_def)
  then obtain p b p' b'
    where s: "(p, b, p', b', d) ∈ delta_ktm M"
      and "q = f p" and "q' = f p'"
      and ab: "a = g ∘ b" and ab': "a' = g ∘ b'"
    by (rule relabel_source)
  assume "a' j = le_ktm (relabel_ktm f g M)"
  then have geq: "g (b' j) = g (le_ktm M)" using ab' by simp
  have b'G: "b' j ∈ Γ_ktm M" by (rule valid_ktm_delta (4) [OF vM s])
  have leG: "le_ktm M ∈ Γ_ktm M" by (rule valid_ktm_LE_in_Gamma [OF vM])
  from geq b'G leG injg have "b' j = le_ktm M" by (auto dest: inj_onD)
  with lu s have "b j = le_ktm M" unfolding le_unique_def by blast
  then show "a j = le_ktm (relabel_ktm f g M)" using ab by simp
qed


subsection ‹Semantic preservation›

text ‹The point of the combinator.  A relabelling is a bijection on
  configurations, so runs correspond step for step: no step is added and none
  is lost, and the time bound is preserved ∗‹with no constant at all›.  This
  is what distinguishes relabelling from the sibling combinators, every one
  of which pays a multiplicative or additive price.›

definition relabel_config ::
  "('q ⇒ 'p) ⇒ ('a ⇒ 'b) ⇒ ('a, 'q) ktc_config ⇒ ('b, 'p) ktc_config" where
  "relabel_config f g c =
     KConfig (f (ktc_state c)) (λj p. g (ktc_tape c j p)) (ktc_pos c)"

lemma relabel_config_simps [simp]:
  "ktc_state (relabel_config f g c) = f (ktc_state c)"
  "ktc_tape (relabel_config f g c) = (λj p. g (ktc_tape c j p))"
  "ktc_pos (relabel_config f g c) = ktc_pos c"
  by (simp_all add: relabel_config_def)

lemma relabel_delta_ktm [simp]:
  "delta_ktm (relabel_ktm f g M) = relabel_delta f g (delta_ktm M)"
  by (simp add: relabel_ktm_def)

lemma relabel_delta_I:
  "(q, a, q', a', d) ∈ D ⟹
     (f q, λj. g (a j), f q', λj. g (a' j), d) ∈ relabel_delta f g D"
  by (force simp: relabel_delta_def comp_def)

text ‹The initial configuration is the relabelling of the initial
  configuration, which is what makes the input word term‹map g w› and not
  something needing a separate encoding argument.›

lemma relabel_init_config:
  "relabel_config f g (init_config_ktm M w)
     = init_config_ktm (relabel_ktm f g M) (map g w)"
proof (cases M)
  case (KTM Q Sg Gm bl le D s t r k)
  then show ?thesis
    by (auto simp: relabel_config_def relabel_ktm_def fun_eq_iff)
qed

text ‹One step of ‹M› is one step of the relabelling, with no hypotheses at
  all: the forward direction needs neither validity nor injectivity, because
  a transition of ‹M› maps to a transition of the image by construction.
  Injectivity is what the ∗‹reverse› direction costs, and it is charged
  there.›

lemma relabel_step:
  assumes "(c, c') ∈ ktm_step (delta_ktm M)"
  shows "(relabel_config f g c, relabel_config f g c')
           ∈ ktm_step (delta_ktm (relabel_ktm f g M))"
  using assms
proof (cases rule: ktm_step.cases)
  case (step q ts n q' a move)
  have "(KConfig (f q) (λj p. g (ts j p)) n,
         KConfig (f q') (λj. (λp. g (ts j p))(n j := g (a j)))
                        (λj. go_move (move j) (n j)))
          ∈ ktm_step (delta_ktm (relabel_ktm f g M))"
  proof (rule ktm_step.step)
    show "(f q, λj. (λp. g (ts j p)) (n j), f q', λj. g (a j), move)
            ∈ delta_ktm (relabel_ktm f g M)"
      using relabel_delta_I [OF step(3)] by simp
  qed
  moreover have "(λj p. g (((ts j)(n j := a j)) p))
                   = (λj. (λp. g (ts j p))(n j := g (a j)))"
    by (simp add: fun_eq_iff)
  ultimately show ?thesis
    using step(1,2) by (simp add: relabel_config_def)
qed

lemma relabel_run:
  assumes "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
  shows "(relabel_config f g c, relabel_config f g c')
           ∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ n"
  by (rule relpow_map [where h = "relabel_config f g", OF _ assms])
     (erule relabel_step)

lemma relabel_accepts_in_time:
  assumes "valid_ktm M" and "inj_on f (Q_ktm M)" and "inj_on g (Γ_ktm M)"
      and "set w ⊆ Sigma_ktm M"
      and "accepts_in_time_ktm M w n"
  shows "accepts_in_time_ktm (relabel_ktm f g M) (map g w) n"
proof -
  from assms(5) obtain m c
    where m: "m ≤ n"
      and run: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ m"
      and acc: "ktc_state c = t_ktm M"
    by (auto simp: accepts_in_time_ktm_def)
  from relabel_run [OF run]
  have "(init_config_ktm (relabel_ktm f g M) (map g w), relabel_config f g c)
          ∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ m"
    by (simp add: relabel_init_config)
  moreover have "ktc_state (relabel_config f g c) = t_ktm (relabel_ktm f g M)"
    using acc by simp
  ultimately show ?thesis
    unfolding accepts_in_time_ktm_def using m by blast
qed

text ‹❙‹Where the injectivity hypotheses are spent.›  Inverting a step of the
  relabelling needs to know that the transition it came from is ∗‹the›
  transition of ‹M› and not merely one with the same image, and that is two
  separate identifications: ‹f› injective recovers the source state and ‹g›
  injective recovers the read vector cell by cell.  Both need their arguments
  to lie in the machine's carriers, which is why the configuration must be
  valid --- const‹valid_config_ktm› supplies exactly the two facts, the
  state in term‹Q_ktm M› and every tape cell in term‹Γ_ktm M›.›

lemma relabel_step_rev:
  assumes vM: "valid_ktm M"
      and injf: "inj_on f (Q_ktm M)"
      and injg: "inj_on g (Γ_ktm M)"
      and valc: "valid_config_ktm M c"
      and step: "(relabel_config f g c, e)
                   ∈ ktm_step (delta_ktm (relabel_ktm f g M))"
  obtains c' where "(c, c') ∈ ktm_step (delta_ktm M)"
    and "e = relabel_config f g c'"
proof -
  obtain q ts n where c: "c = KConfig q ts n" by (cases c) auto
  from valc c have qQ: "q ∈ Q_ktm M" and tsG: "⋀j p. ts j p ∈ Γ_ktm M"
    by (cases M; simp; blast)+
  from step c obtain Q' A D
    where tr: "(f q, λj. g (ts j (n j)), Q', A, D)
                 ∈ relabel_delta f g (delta_ktm M)"
      and e: "e = KConfig Q' (λj. (λp. g (ts j p))(n j := A j))
                            (λj. go_move (D j) (n j))"
    by (auto simp: relabel_config_def elim!: ktm_step.cases)
  from tr obtain p b p' b'
    where trM: "(p, b, p', b', D) ∈ delta_ktm M"
      and fp: "f q = f p" and Q'e: "Q' = f p'"
      and bg: "(λj. g (ts j (n j))) = g ∘ b" and Ae: "A = g ∘ b'"
    by (rule relabel_source)
  from valid_ktm_delta_set [OF vM] trM
  have pQ: "p ∈ Q_ktm M" and bG: "⋀j. b j ∈ Γ_ktm M" by (auto simp: Pi_iff)
  from fp qQ pQ injf have pq: "p = q" by (auto dest: inj_onD)
  have "b = (λj. ts j (n j))"
  proof
    fix j
    from bg have "g (ts j (n j)) = g (b j)" by (simp add: fun_eq_iff)
    with tsG bG injg show "b j = ts j (n j)" by (auto dest: inj_onD)
  qed
  with trM pq have trq: "(q, λj. ts j (n j), p', b', D) ∈ delta_ktm M" by simp
  let ?c' = "KConfig p' (λj. (ts j)(n j := b' j)) (λj. go_move (D j) (n j))"
  have "(KConfig q ts n, ?c') ∈ ktm_step (delta_ktm M)"
    by (rule ktm_step.step) (rule trq)
  then have "(c, ?c') ∈ ktm_step (delta_ktm M)" unfolding c .
  moreover have "e = relabel_config f g ?c'"
    using e Q'e Ae by (simp add: relabel_config_def fun_eq_iff)
  ultimately show thesis by (rule that)
qed

lemma relabel_run_rev:
  assumes vM: "valid_ktm M"
      and injf: "inj_on f (Q_ktm M)"
      and injg: "inj_on g (Γ_ktm M)"
      and valc: "valid_config_ktm M c"
      and run: "(relabel_config f g c, e)
                  ∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ n"
  obtains c' where "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
    and "e = relabel_config f g c'"
  using run
proof (induct n arbitrary: e thesis)
  case 0 then show ?case by simp
next
  case (Suc n)
  from Suc.prems(2) obtain d
    where cd: "(relabel_config f g c, d)
                 ∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ n"
      and de: "(d, e) ∈ ktm_step (delta_ktm (relabel_ktm f g M))" by auto
  from Suc.hyps [OF _ cd] obtain c''
    where cc'': "(c, c'') ∈ (ktm_step (delta_ktm M)) ^^ n"
      and dc'': "d = relabel_config f g c''" by blast
  from valid_reach_relpow_ktm [OF vM valc cc'']
  have valc'': "valid_config_ktm M c''" .
  from de [unfolded dc''] obtain c'
    where c''c': "(c'', c') ∈ ktm_step (delta_ktm M)"
      and ec': "e = relabel_config f g c'"
    by (rule relabel_step_rev [OF vM injf injg valc''])
  from cc'' c''c' have "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ Suc n" by auto
  from Suc.prems(1) [OF this ec'] show ?case .
qed

lemma relabel_accepts_in_time_rev:
  assumes vM: "valid_ktm M" and injf: "inj_on f (Q_ktm M)"
      and injg: "inj_on g (Γ_ktm M)"
      and w: "set w ⊆ Sigma_ktm M"
      and acc: "accepts_in_time_ktm (relabel_ktm f g M) (map g w) n"
  shows "accepts_in_time_ktm M w n"
proof -
  from acc obtain m e
    where m: "m ≤ n"
      and run: "(init_config_ktm (relabel_ktm f g M) (map g w), e)
                  ∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ m"
      and te: "ktc_state e = t_ktm (relabel_ktm f g M)"
    by (auto simp: accepts_in_time_ktm_def)
  have valinit: "valid_config_ktm M (init_config_ktm M w)"
    by (rule valid_init_config_ktm [OF vM w])
  from run [folded relabel_init_config] obtain c'
    where run': "(init_config_ktm M w, c') ∈ (ktm_step (delta_ktm M)) ^^ m"
      and ec': "e = relabel_config f g c'"
    by (rule relabel_run_rev [OF vM injf injg valinit])
  from valid_reach_relpow_ktm [OF vM valinit run']
  have "ktc_state c' ∈ Q_ktm M" by (cases M; cases c') simp
  moreover have "t_ktm M ∈ Q_ktm M" by (rule valid_ktm_t_in_Q [OF vM])
  moreover from te ec' have "f (ktc_state c') = f (t_ktm M)" by simp
  ultimately have "ktc_state c' = t_ktm M" using injf by (auto dest: inj_onD)
  with run' m show ?thesis unfolding accepts_in_time_ktm_def by blast
qed

theorem relabel_lang:
  assumes vM: "valid_ktm M" and injf: "inj_on f (Q_ktm M)"
      and injg: "inj_on g (Γ_ktm M)"
  shows "Lang_ktm (relabel_ktm f g M) = map g ` Lang_ktm M"
proof (rule set_eqI, rule iffI)
  fix v assume v: "v ∈ Lang_ktm (relabel_ktm f g M)"
  then have "v ∈ lists (g ` Sigma_ktm M)" by (auto simp: Lang_ktm_def)
  then obtain w where wv: "v = map g w" and w: "set w ⊆ Sigma_ktm M"
    by (auto simp: lists_image)
  from v wv obtain e j
    where "(init_config_ktm (relabel_ktm f g M) (map g w), e)
             ∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ j"
      and te: "ktc_state e = t_ktm (relabel_ktm f g M)"
    by (auto simp: Lang_ktm_def rtrancl_power)
  then have "accepts_in_time_ktm (relabel_ktm f g M) (map g w) j"
    unfolding accepts_in_time_ktm_def by blast
  from relabel_accepts_in_time_rev [OF vM injf injg w this]
  obtain i c where "i ≤ j"
    and "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ i"
    and "ktc_state c = t_ktm M"
    by (auto simp: accepts_in_time_ktm_def)
  then have "w ∈ Lang_ktm M"
    using w by (cases c) (auto simp: Lang_ktm_def rtrancl_power)
  with wv show "v ∈ map g ` Lang_ktm M" by blast
next
  fix v assume "v ∈ map g ` Lang_ktm M"
  then obtain w where wv: "v = map g w" and w: "w ∈ Lang_ktm M" by blast
  from w have wS: "set w ⊆ Sigma_ktm M" by (simp add: Lang_ktm_def)
  from w obtain c j where run: "(init_config_ktm M w, c)
                                  ∈ (ktm_step (delta_ktm M)) ^^ j"
    and tc: "ktc_state c = t_ktm M"
    by (cases M) (auto simp: Lang_ktm_def rtrancl_power)
  from relabel_run [OF run]
  have "(init_config_ktm (relabel_ktm f g M) (map g w), relabel_config f g c)
          ∈ (ktm_step (delta_ktm (relabel_ktm f g M))) ^^ j"
    by (simp add: relabel_init_config)
  moreover have "ktc_state (relabel_config f g c)
                   = t_ktm (relabel_ktm f g M)" using tc by simp
  moreover have "set (map g w) ⊆ Sigma_ktm (relabel_ktm f g M)"
    using wS by auto
  ultimately show "v ∈ Lang_ktm (relabel_ktm f g M)"
    unfolding wv
    by (cases "relabel_config f g c")
       (auto simp: Lang_ktm_def rtrancl_power)
qed


subsection ‹Widening the tape count›

text ‹Textbook arguments that move a machine into a class with more tapes
  say "a ‹k›-tape machine is a ‹k'›-tape machine with unused extra tapes"
  and move on.  On the value-level substrate that sentence is not just true but
  ∗‹free›, and it is worth seeing why.

  ❙‹It is not a field update, and the reason is worth stating because the
  plausible argument for "free" is nearly right.›  Validity does constrain
  transitions only ∗‹beyond› the tape count --- for ‹j ≥ k› a transition
  must read blank, write blank and stay --- so raising ‹k› weakens that
  obligation and a machine's own transition relation stays legal at the larger
  count.  ‹widen_valid› really is free.

  But ‹k› has a second consumer.  const‹init_config_ktm› reads it to decide
  which tapes ∗‹exist›, and every tape below ‹k› starts with the left
  endmarker in cell 0 while every tape at or above ‹k› is uniformly blank.
  Raising the count therefore ∗‹adds› endmarkers, on exactly the tapes whose
  transitions are required to read blank --- so a bare field update leaves a
  machine that cannot take its first step at all, for any input.  The two
  consumers of ‹k› move in opposite directions.

  So the widening also patches the transition relation, replacing the blank
  that const‹valid_ktm› forces on tapes ‹[k, k')› with the endmarker those
  tapes now carry.  The heads there never move (the direction component is
  already stationary beyond ‹k›), so each new tape holds its endmarker in
  cell 0 for the whole run and reads it every step.  The correspondence with
  ‹M›'s own run is still step for step and the time bound is still exact ---
  what is lost is only the claim that no proof obligation arises.

  This remains a place where the value-level tape count pays for itself.  With
  the count trapped in a type parameter, as in the AFP source this substrate
  was forked from, the same step would be a transport across two different
  types and would need the machinery above on top of this patch.›

definition widen_delta ::
  "nat ⇒ nat ⇒ 'a
     ⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set
     ⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set" where
  "widen_delta k k' le D =
     (λ(q, a, q', a', d).
        (q, λj. if k ≤ j ∧ j < k' then le else a j,
         q', λj. if k ≤ j ∧ j < k' then le else a' j, d)) ` D"

definition widen_tapes :: "nat ⇒ ('q, 'a) ktm ⇒ ('q, 'a) ktm" where
  "widen_tapes k' M =
     KTM (Q_ktm M) (Sigma_ktm M) (Γ_ktm M) (bl_ktm M) (le_ktm M)
          (widen_delta (k_ktm M) k' (le_ktm M) (delta_ktm M))
          (s_ktm M) (t_ktm M) (r_ktm M) k'"

lemma widen_k_ktm [simp]: "k_ktm (widen_tapes k' M) = k'"
  by (simp add: widen_tapes_def)

lemma widen_delta_ktm [simp]:
  "delta_ktm (widen_tapes k' M)
     = widen_delta (k_ktm M) k' (le_ktm M) (delta_ktm M)"
  by (simp add: widen_tapes_def)

lemma widen_Sigma_ktm [simp]: "Sigma_ktm (widen_tapes k' M) = Sigma_ktm M"
  by (simp add: widen_tapes_def)

lemma widen_Gamma_ktm [simp]: "Γ_ktm (widen_tapes k' M) = Γ_ktm M"
  by (simp add: widen_tapes_def)

lemma widen_bl_ktm [simp]: "bl_ktm (widen_tapes k' M) = bl_ktm M"
  by (simp add: widen_tapes_def)

lemma widen_le_ktm [simp]: "le_ktm (widen_tapes k' M) = le_ktm M"
  by (simp add: widen_tapes_def)

lemma widen_t_ktm [simp]: "t_ktm (widen_tapes k' M) = t_ktm M"
  by (simp add: widen_tapes_def)

text ‹The patched tuple's four obligations, each read off ‹M›'s own.  The
  endmarker case is the one the bare field update could not meet: on
  ‹[k, k')› the read is now ‹le›, and what licenses it is that ‹M›'s support
  invariant already makes the direction stationary there, so the endmarker
  discipline's ‹d j ∈ {N, R}› is satisfied without choosing anything.›

lemma widen_valid:
  assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'" and pos: "0 < k'"
  shows "valid_ktm (widen_tapes k' M)"
proof (cases M)
  case M_eq: (KTM Q Sg Gm bl le D s t r k)
  have kD: "k_ktm M = k" "le_ktm M = le" "bl_ktm M = bl" "delta_ktm M = D"
    using M_eq by simp_all
  have W: "widen_tapes k' M
             = KTM Q Sg Gm bl le (widen_delta k k' le D) s t r k'"
    using M_eq by (simp add: widen_tapes_def)
  have kle: "k ≤ k'" using kk kD by simp
  have leG: "le ∈ Gm" using valid_ktm_LE_in_Gamma [OF vM] M_eq by simp

  have split: "∃b b'. (q, b, q', b', d) ∈ delta_ktm M
                      ∧ a = (λj. if k ≤ j ∧ j < k' then le else b j)
                      ∧ a' = (λj. if k ≤ j ∧ j < k' then le else b' j)"
    if "(q, a, q', a', d) ∈ widen_delta k k' le D" for q a q' a' d
    using that kD by (auto simp: widen_delta_def)

  have tuple: "q ∈ Q - {t, r} ∧ q' ∈ Q
               ∧ (∀j. a j ∈ Gm) ∧ (∀j. a' j ∈ Gm)"
    if tr: "(q, a, q', a', d) ∈ widen_delta k k' le D" for q a q' a' d
  proof -
    from split [OF tr] obtain b b'
      where trM: "(q, b, q', b', d) ∈ delta_ktm M"
        and ae: "a = (λj. if k ≤ j ∧ j < k' then le else b j)"
        and ae': "a' = (λj. if k ≤ j ∧ j < k' then le else b' j)" by blast
    from valid_ktm_delta_set [OF vM] trM M_eq
    have "q ∈ Q - {t, r}" "q' ∈ Q" "∀j. b j ∈ Gm" "∀j. b' j ∈ Gm"
      by (auto simp: Pi_iff)
    with leG ae ae' show ?thesis by simp
  qed

  have LEdisc: "a' j = le ∧ d j ∈ {MoveN, MoveR}"
    if tr: "(q, a, q', a', d) ∈ widen_delta k k' le D" and aj: "a j = le"
    for q a q' a' d j
  proof -
    from split [OF tr] obtain b b'
      where trM: "(q, b, q', b', d) ∈ delta_ktm M"
        and ae: "a = (λj. if k ≤ j ∧ j < k' then le else b j)"
        and ae': "a' = (λj. if k ≤ j ∧ j < k' then le else b' j)" by blast
    show ?thesis
    proof (cases "k ≤ j ∧ j < k'")
      case True
      then have "d j = MoveN"
        using valid_ktm_delta_support [OF vM trM] kD by simp
      with True ae' show ?thesis by simp
    next
      case False
      with aj ae have "b j = le_ktm M" using kD by simp
      from valid_ktm_deltaLE [OF vM trM this] False ae' kD
      show ?thesis by simp
    qed
  qed

  have supp: "a j = bl ∧ a' j = bl ∧ d j = MoveN"
    if tr: "(q, a, q', a', d) ∈ widen_delta k k' le D" and j: "k' ≤ j"
    for q a q' a' d j
  proof -
    from split [OF tr] obtain b b'
      where trM: "(q, b, q', b', d) ∈ delta_ktm M"
        and ae: "a = (λj. if k ≤ j ∧ j < k' then le else b j)"
        and ae': "a' = (λj. if k ≤ j ∧ j < k' then le else b' j)" by blast
    from j kle have "k_ktm M ≤ j" using kD by simp
    from valid_ktm_delta_support [OF vM trM this] j ae ae' kD
    show ?thesis by simp
  qed

  have sub: "widen_delta k k' le D
               ⊆ (Q - {t, r}) × (UNIV → Gm) × Q × (UNIV → Gm)
                   × (UNIV → UNIV)"
  proof (rule subsetI)
    fix x assume x: "x ∈ widen_delta k k' le D"
    obtain q a q' a' d where xe: "x = (q, a, q', a', d)"
      by (cases x) auto
    from tuple [OF x [unfolded xe]] xe
    show "x ∈ (Q - {t, r}) × (UNIV → Gm) × Q × (UNIV → Gm)
                × (UNIV → UNIV)"
      by (simp add: Pi_iff)
  qed

  have base: "finite Q" "finite Gm" "Sg ⊆ Gm" "s ∈ Q" "t ∈ Q" "r ∈ Q"
             "bl ∈ Gm" "bl ∉ Sg" "le ∈ Gm" "le ∉ Sg" "t ≠ r"
    using vM M_eq by auto

  show ?thesis
    unfolding W valid_ktm.simps
    using base pos sub LEdisc supp by blast
qed

text ‹❙‹And const‹le_unique›, which the widening preserves for the reason
  it is stated the way it is.›  On the tapes it invents the read and the write
  are the ∗‹same› endmarker, so the implication holds there with nothing to
  prove; elsewhere the vectors are ‹M›'s own.  A pipeline of
  constructions that has to deliver a machine with the property needs every
  stage to preserve it.›

lemma widen_le_unique:
  assumes lu: "le_unique M"
  shows "le_unique (widen_tapes k' M)"
  using lu by (fastforce simp: le_unique_def widen_tapes_def widen_delta_def)

text ‹The configuration correspondence.  On ‹[k, k')› the widened machine
  shows the endmarker in cell 0 and blanks beyond it, and its head there never
  moves; everywhere else it is ‹M›'s own configuration.  What makes this an
  ∗‹equality› of runs rather than a simulation is that const‹valid_config_ktm›
  already forces ‹M›'s tapes beyond ‹k› to be uniformly blank with the head at
  the origin, so nothing on those tapes is being thrown away.›

definition widen_config ::
  "nat ⇒ nat ⇒ 'a ⇒ 'a ⇒ ('a, 'q) ktc_config ⇒ ('a, 'q) ktc_config" where
  "widen_config k k' le bl c =
     KConfig (ktc_state c)
       (λj p. if k ≤ j ∧ j < k'
              then (if p = 0 then le else bl) else ktc_tape c j p)
       (ktc_pos c)"

lemma widen_config_simps [simp]:
  "ktc_state (widen_config k k' le bl c) = ktc_state c"
  "ktc_pos (widen_config k k' le bl c) = ktc_pos c"
  by (simp_all add: widen_config_def)

lemma widen_init_config:
  assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
  shows "widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) (init_config_ktm M w)
           = init_config_ktm (widen_tapes k' M) w"
  using kk valid_ktm_k_pos [OF vM]
  by (cases M) (auto simp: widen_config_def widen_tapes_def fun_eq_iff)

lemma widen_delta_I:
  "(q, a, q', a', d) ∈ D ⟹
     (q, λj. if k ≤ j ∧ j < k' then le else a j, q',
      λj. if k ≤ j ∧ j < k' then le else a' j, d) ∈ widen_delta k k' le D"
  by (force simp: widen_delta_def)

lemma widen_step:
  assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
      and valc: "valid_config_ktm M c"
      and hp: "heads_parked (k_ktm M) c"
      and step: "(c, c') ∈ ktm_step (delta_ktm M)"
  shows "(widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c,
          widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c')
           ∈ ktm_step (delta_ktm (widen_tapes k' M))"
proof -
  let ?k = "k_ktm M" and ?le = "le_ktm M" and ?bl = "bl_ktm M"
  from step obtain q ts n q' a d
    where c: "c = KConfig q ts n"
      and c': "c' = KConfig q' (λj. (ts j)(n j := a j))
                              (λj. go_move (d j) (n j))"
      and tr: "(q, λj. ts j (n j), q', a, d) ∈ delta_ktm M"
    by (auto elim!: ktm_step.cases)
  ― ‹beyond ‹k› the head is at the origin and stays there›
  have pos0: "n j = 0" if "?k ≤ j" for j
    using hp c that by (simp add: heads_parked_def)
  let ?tw = "λj p. if ?k ≤ j ∧ j < k' then (if p = 0 then ?le else ?bl)
                   else ts j p"
  let ?aw = "λj. if ?k ≤ j ∧ j < k' then ?le else a j"
  have wc: "widen_config ?k k' ?le ?bl c = KConfig q ?tw n"
    unfolding c widen_config_def by (auto simp: fun_eq_iff)
  have wc': "widen_config ?k k' ?le ?bl c'
               = KConfig q' (λj. (?tw j)(n j := ?aw j))
                            (λj. go_move (d j) (n j))"
    unfolding c' widen_config_def using pos0 by (auto simp: fun_eq_iff)
  have read: "(λj. ?tw j (n j)) = (λj. if ?k ≤ j ∧ j < k' then ?le
                                        else ts j (n j))"
    using pos0 by (auto simp: fun_eq_iff)
  show ?thesis
    unfolding wc wc'
  proof (rule ktm_step.step)
    show "(q, λj. ?tw j (n j), q', ?aw, d) ∈ delta_ktm (widen_tapes k' M)"
      using widen_delta_I [OF tr] read by simp
  qed
qed

lemma widen_run:
  assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
      and valc: "valid_config_ktm M c"
      and hp: "heads_parked (k_ktm M) c"
      and run: "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
  shows "(widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c,
          widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c')
           ∈ (ktm_step (delta_ktm (widen_tapes k' M))) ^^ n"
  by (rule relpow_map [where h = "widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M)", OF _ run])
     (rule widen_step [OF vM kk valid_reach_relpow_ktm [OF vM valc]
                       heads_parked_run [OF vM hp]])

text ‹The reverse direction reuses the forward one rather than repeating the
  correspondence: ‹widen_tapes› does not change the state set, so an accepting
  run of the widened machine is a run of ‹M› read back through the same
  bijection on configurations.  Stating it as ‹relabel_ktm›'s reverse would
  need a second inversion argument; instead the widened step relation is
  inverted directly, which is cheap because ‹widen_delta› is injective on the
  part of the read vector that matters.›

lemma widen_step_rev:
  assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
      and valc: "valid_config_ktm M c"
      and hp: "heads_parked (k_ktm M) c"
      and step: "(widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c, e)
                   ∈ ktm_step (delta_ktm (widen_tapes k' M))"
  obtains c' where "(c, c') ∈ ktm_step (delta_ktm M)"
    and "e = widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c'"
proof -
  let ?k = "k_ktm M" and ?le = "le_ktm M" and ?bl = "bl_ktm M"
  obtain q ts n where c: "c = KConfig q ts n" by (cases c) auto
  have pos0: "n j = 0" if "?k ≤ j" for j
    using hp c that by (simp add: heads_parked_def)
  let ?tw = "λj p. if ?k ≤ j ∧ j < k' then (if p = 0 then ?le else ?bl)
                   else ts j p"
  have wc: "widen_config ?k k' ?le ?bl c = KConfig q ?tw n"
    unfolding c widen_config_def by (auto simp: fun_eq_iff)
  from step [unfolded wc] obtain Q' A D
    where tr: "(q, λj. ?tw j (n j), Q', A, D)
                 ∈ widen_delta ?k k' ?le (delta_ktm M)"
      and e: "e = KConfig Q' (λj. (?tw j)(n j := A j))
                            (λj. go_move (D j) (n j))"
    by (auto elim!: ktm_step.cases)
  from tr obtain b b'
    where trM: "(q, b, Q', b', D) ∈ delta_ktm M"
      and bw: "(λj. ?tw j (n j))
                 = (λj. if ?k ≤ j ∧ j < k' then ?le else b j)"
      and Aw: "A = (λj. if ?k ≤ j ∧ j < k' then ?le else b' j)"
    by (auto simp: widen_delta_def)
  have "b = (λj. ts j (n j))"
  proof
    fix j
    show "b j = ts j (n j)"
    proof (cases "?k ≤ j ∧ j < k'")
      case True
      from valid_ktm_delta_support [OF vM trM] True have "b j = ?bl" by simp
      moreover from valc c True have "ts j (n j) = ?bl"
        by (cases M) (auto simp: valid_config_ktm.simps)
      ultimately show ?thesis by simp
    next
      case False
      from bw have "?tw j (n j) = (if ?k ≤ j ∧ j < k' then ?le else b j)"
        by (simp add: fun_eq_iff)
      with False show ?thesis by (auto split: if_splits)
    qed
  qed
  with trM have trq: "(q, λj. ts j (n j), Q', b', D) ∈ delta_ktm M" by simp
  let ?c' = "KConfig Q' (λj. (ts j)(n j := b' j)) (λj. go_move (D j) (n j))"
  have "(KConfig q ts n, ?c') ∈ ktm_step (delta_ktm M)"
    by (rule ktm_step.step) (rule trq)
  then have "(c, ?c') ∈ ktm_step (delta_ktm M)" unfolding c .
  moreover have "e = widen_config ?k k' ?le ?bl ?c'"
    using e Aw pos0 by (auto simp: widen_config_def fun_eq_iff)
  ultimately show thesis by (rule that)
qed

lemma widen_run_rev:
  assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
      and valc: "valid_config_ktm M c"
      and hp: "heads_parked (k_ktm M) c"
      and run: "(widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c, e)
                  ∈ (ktm_step (delta_ktm (widen_tapes k' M))) ^^ n"
  obtains c' where "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
    and "e = widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c'"
  using run
proof (induct n arbitrary: e thesis)
  case 0 then show ?case by simp
next
  case (Suc n)
  from Suc.prems(2) obtain d
    where cd: "(widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c, d)
                 ∈ (ktm_step (delta_ktm (widen_tapes k' M))) ^^ n"
      and de: "(d, e) ∈ ktm_step (delta_ktm (widen_tapes k' M))" by auto
  from Suc.hyps [OF _ cd] obtain c''
    where cc'': "(c, c'') ∈ (ktm_step (delta_ktm M)) ^^ n"
      and dc'': "d = widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c''" by blast
  from valid_reach_relpow_ktm [OF vM valc cc'']
  have valc'': "valid_config_ktm M c''" .
  from heads_parked_run [OF vM hp cc''] have hpc'': "heads_parked (k_ktm M) c''" .
  from de [unfolded dc''] obtain c'
    where c''c': "(c'', c') ∈ ktm_step (delta_ktm M)"
      and ec': "e = widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c'"
    by (rule widen_step_rev [OF vM kk valc'' hpc''])
  from cc'' c''c' have "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ Suc n" by auto
  from Suc.prems(1) [OF this ec'] show ?case .
qed

lemma widen_accepts_in_time:
  assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
      and w: "set w ⊆ Sigma_ktm M"
  shows "accepts_in_time_ktm (widen_tapes k' M) w n
           ⟷ accepts_in_time_ktm M w n"
proof
  have valinit: "valid_config_ktm M (init_config_ktm M w)"
    by (rule valid_init_config_ktm [OF vM w])
  have hpinit: "heads_parked (k_ktm M) (init_config_ktm M w)"
    by (rule heads_parked_init)
  assume "accepts_in_time_ktm (widen_tapes k' M) w n"
  then obtain m e
    where m: "m ≤ n"
      and run: "(init_config_ktm (widen_tapes k' M) w, e)
                  ∈ (ktm_step (delta_ktm (widen_tapes k' M))) ^^ m"
      and te: "ktc_state e = t_ktm (widen_tapes k' M)"
    by (auto simp: accepts_in_time_ktm_def)
  from run [folded widen_init_config [OF vM kk]] obtain c'
    where run': "(init_config_ktm M w, c') ∈ (ktm_step (delta_ktm M)) ^^ m"
      and ec': "e = widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c'"
    by (rule widen_run_rev [OF vM kk valinit hpinit])
  from te ec' have "ktc_state c' = t_ktm M" by (simp add: widen_tapes_def)
  with run' m show "accepts_in_time_ktm M w n"
    unfolding accepts_in_time_ktm_def by blast
next
  have valinit: "valid_config_ktm M (init_config_ktm M w)"
    by (rule valid_init_config_ktm [OF vM w])
  have hpinit: "heads_parked (k_ktm M) (init_config_ktm M w)"
    by (rule heads_parked_init)
  assume "accepts_in_time_ktm M w n"
  then obtain m c
    where m: "m ≤ n"
      and run: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ m"
      and tc: "ktc_state c = t_ktm M"
    by (auto simp: accepts_in_time_ktm_def)
  from widen_run [OF vM kk valinit hpinit run]
  have run': "(init_config_ktm (widen_tapes k' M) w,
               widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c)
                ∈ (ktm_step (delta_ktm (widen_tapes k' M))) ^^ m"
    by (simp add: widen_init_config [OF vM kk])
  have "ktc_state (widen_config (k_ktm M) k' (le_ktm M) (bl_ktm M) c)
          = t_ktm (widen_tapes k' M)"
    using tc by (simp add: widen_tapes_def)
  with run' m show "accepts_in_time_ktm (widen_tapes k' M) w n"
    unfolding accepts_in_time_ktm_def by blast
qed

theorem widen_lang:
  assumes vM: "valid_ktm M" and kk: "k_ktm M ≤ k'"
  shows "Lang_ktm (widen_tapes k' M) = Lang_ktm M"
proof (rule set_eqI)
  fix w
  have "set w ⊆ Sigma_ktm (widen_tapes k' M) ⟷ set w ⊆ Sigma_ktm M"
    by (simp add: widen_tapes_def)
  then show "w ∈ Lang_ktm (widen_tapes k' M) ⟷ w ∈ Lang_ktm M"
    unfolding Lang_ktm_iff
    using widen_accepts_in_time [OF vM kk] by blast
qed


subsection ‹Exchanging two tapes›

text ‹The cheapest of the three combinators.  Renaming tape indices in the
  transition relation renames them in the configuration; the machine cannot
  tell the difference, and no step is spent.

  ❙‹Why a transposition rather than a permutation.›  Every permutation of a
  finite index set is a product of transpositions, so the single exchange is
  enough, and it is what a construction that hands one tape's role to another
  needs.  ‹tswap› is ‹transpose› of ‹HOL-Combinatorics.Transposition› at
  type typ‹nat›; it is defined here so that this entry does not depend on
  that session.  Restricting to two indices also keeps the side condition to
  ‹i < k› and ‹j < k›, which is what the support invariant needs: a
  transposition of two indices ∗‹below› the tape count fixes every index at
  or above it, so the requirement that transitions read blank, write blank and
  stay put beyond ‹k› transports unchanged.

  ❙‹What it costs, compared with the widening above.›  Nothing --- and the
  contrast is the point.  ‹widen_step› carries const‹valid_config_ktm› and
  const‹heads_parked› as hypotheses, because widening ∗‹invents› tape
  content (endmarkers on tapes that had none) and has to know the discarded
  content was blank and its heads at the origin.  A transposition invents
  nothing: it is a bijection on configurations, so the step correspondence is
  an iff with no hypotheses at all, and the reverse direction is the forward
  one applied to the exchanged machine rather than a second argument.

  ❙‹Why a widening often wants one.›  The tape const‹widen_tapes›
  adds is not a free tape: widening pins it to the endmarker in cell 0 with
  the head stationary.  So a tape a construction walks along has to be one the
  machine already had, and exchanging tapes moves the pinned role onto a tape
  that is no longer needed.›

definition tswap :: "nat ⇒ nat ⇒ nat ⇒ nat" where
  "tswap i j m = (if m = i then j else if m = j then i else m)"

lemma tswap_tswap [simp]: "tswap i j (tswap i j m) = m"
  by (simp add: tswap_def)

lemma tswap_same [simp]: "tswap i i = id"
  by (auto simp: tswap_def)

lemma tswap_out:
  assumes "i < k" and "j < k" and "k ≤ m"
  shows "tswap i j m = m"
  using assms by (simp add: tswap_def)

definition swap_delta ::
  "nat ⇒ nat
     ⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set
     ⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set" where
  "swap_delta i j D =
     (λ(q, a, q', a', d).
        (q, a ∘ tswap i j, q', a' ∘ tswap i j, d ∘ tswap i j)) ` D"

lemma swap_delta_I:
  "(q, a, q', a', d) ∈ D ⟹
     (q, a ∘ tswap i j, q', a' ∘ tswap i j, d ∘ tswap i j)
       ∈ swap_delta i j D"
  by (force simp: swap_delta_def)

lemma swap_delta_E:
  assumes "(q, a, q', a', d) ∈ swap_delta i j D"
  obtains b b' e where "(q, b, q', b', e) ∈ D"
    and "a = b ∘ tswap i j" and "a' = b' ∘ tswap i j" and "d = e ∘ tswap i j"
  using assms by (auto simp: swap_delta_def)

lemma swap_delta_swap_delta [simp]:
  fixes D :: "('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set"
  shows "swap_delta i j (swap_delta i j D) = D"
proof (rule set_eqI)
  fix x :: "'q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)"
  obtain q a q' a' d where xe: "x = (q, a, q', a', d)" by (cases x) auto
  show "(x ∈ swap_delta i j (swap_delta i j D)) = (x ∈ D)"
  proof
    assume "x ∈ swap_delta i j (swap_delta i j D)"
    from this [unfolded xe] obtain b b' e
      where m: "(q, b, q', b', e) ∈ swap_delta i j D"
        and ab: "a = b ∘ tswap i j" and ab': "a' = b' ∘ tswap i j"
        and de: "d = e ∘ tswap i j"
      by (rule swap_delta_E)
    from m obtain c c' f
      where mD: "(q, c, q', c', f) ∈ D"
        and bc: "b = c ∘ tswap i j" and bc': "b' = c' ∘ tswap i j"
        and ef: "e = f ∘ tswap i j"
      by (rule swap_delta_E)
    have "a = c" "a' = c'" "d = f"
      using ab ab' de bc bc' ef by (simp_all add: comp_def)
    with mD xe show "x ∈ D" by simp
  next
    assume "x ∈ D"
    from swap_delta_I [OF this [unfolded xe], of i j]
    have "(q, a ∘ tswap i j, q', a' ∘ tswap i j, d ∘ tswap i j)
            ∈ swap_delta i j D" .
    from swap_delta_I [OF this, of i j]
    show "x ∈ swap_delta i j (swap_delta i j D)"
      using xe by (simp add: comp_def)
  qed
qed

lemma swap_delta_finite [simp]: "finite (swap_delta i j D) = finite D"
proof
  assume "finite (swap_delta i j D)"
  then have "finite (swap_delta i j (swap_delta i j D))"
    by (simp add: swap_delta_def)
  then show "finite D" by simp
qed (simp add: swap_delta_def)

definition swap_tapes :: "nat ⇒ nat ⇒ ('q, 'a) ktm ⇒ ('q, 'a) ktm" where
  "swap_tapes i j M =
     KTM (Q_ktm M) (Sigma_ktm M) (Γ_ktm M) (bl_ktm M) (le_ktm M)
          (swap_delta i j (delta_ktm M))
          (s_ktm M) (t_ktm M) (r_ktm M) (k_ktm M)"

lemma swap_fields [simp]:
  "Q_ktm (swap_tapes i j M) = Q_ktm M"
  "Sigma_ktm (swap_tapes i j M) = Sigma_ktm M"
  "Γ_ktm (swap_tapes i j M) = Γ_ktm M"
  "bl_ktm (swap_tapes i j M) = bl_ktm M"
  "le_ktm (swap_tapes i j M) = le_ktm M"
  "s_ktm (swap_tapes i j M) = s_ktm M"
  "t_ktm (swap_tapes i j M) = t_ktm M"
  "r_ktm (swap_tapes i j M) = r_ktm M"
  "k_ktm (swap_tapes i j M) = k_ktm M"
  "delta_ktm (swap_tapes i j M) = swap_delta i j (delta_ktm M)"
  by (simp_all add: swap_tapes_def)

lemma swap_tapes_swap_tapes [simp]: "swap_tapes i j (swap_tapes i j M) = M"
  by (cases M) (simp add: swap_tapes_def)

text ‹Validity, and the only place the side condition is used: the support
  invariant speaks about indices at or above ‹k›, and a transposition of two
  indices below ‹k› fixes each of them.  The endmarker discipline needs no
  side condition, because it is a statement about ∗‹every› index and the
  exchange only permutes which one is being spoken about.›

lemma swap_valid:
  assumes vM: "valid_ktm M" and i: "i < k_ktm M" and j: "j < k_ktm M"
  shows "valid_ktm (swap_tapes i j M)"
proof (cases M)
  case M_eq: (KTM Q Sg Gm bl le D s t r k)
  have kD: "k_ktm M = k" "bl_ktm M = bl" "le_ktm M = le" "delta_ktm M = D"
    using M_eq by simp_all
  have W: "swap_tapes i j M = KTM Q Sg Gm bl le (swap_delta i j D) s t r k"
    using M_eq by (simp add: swap_tapes_def)

  have tuple: "q ∈ Q - {t, r} ∧ q' ∈ Q
               ∧ (∀m. a m ∈ Gm) ∧ (∀m. a' m ∈ Gm)"
    if tr: "(q, a, q', a', d) ∈ swap_delta i j D" for q a q' a' d
  proof -
    from tr [folded kD] obtain b b' e
      where trM: "(q, b, q', b', e) ∈ delta_ktm M"
        and ab: "a = b ∘ tswap i j" and ab': "a' = b' ∘ tswap i j"
      by (rule swap_delta_E)
    from valid_ktm_delta_set [OF vM] trM M_eq
    have "q ∈ Q - {t, r}" "q' ∈ Q" "∀m. b m ∈ Gm" "∀m. b' m ∈ Gm"
      by (auto simp: Pi_iff)
    with ab ab' show ?thesis by (simp add: comp_def)
  qed

  have LEdisc: "a' m = le ∧ d m ∈ {MoveN, MoveR}"
    if tr: "(q, a, q', a', d) ∈ swap_delta i j D" and am: "a m = le"
    for q a q' a' d m
  proof -
    from tr [folded kD] obtain b b' e
      where trM: "(q, b, q', b', e) ∈ delta_ktm M"
        and ab: "a = b ∘ tswap i j" and ab': "a' = b' ∘ tswap i j"
        and de: "d = e ∘ tswap i j"
      by (rule swap_delta_E)
    from am ab kD have "b (tswap i j m) = le_ktm M" by (simp add: comp_def)
    from valid_ktm_deltaLE [OF vM trM this] ab' de kD
    show ?thesis by (simp add: comp_def)
  qed

  have supp: "a m = bl ∧ a' m = bl ∧ d m = MoveN"
    if tr: "(q, a, q', a', d) ∈ swap_delta i j D" and m: "k ≤ m"
    for q a q' a' d m
  proof -
    from tr [folded kD] obtain b b' e
      where trM: "(q, b, q', b', e) ∈ delta_ktm M"
        and ab: "a = b ∘ tswap i j" and ab': "a' = b' ∘ tswap i j"
        and de: "d = e ∘ tswap i j"
      by (rule swap_delta_E)
    from i j kD have ik: "i < k" "j < k" by simp_all
    have fix_m: "tswap i j m = m" by (rule tswap_out [OF ik m])
    from m kD have "k_ktm M ≤ m" by simp
    from valid_ktm_delta_support [OF vM trM this] ab ab' de kD fix_m
    show ?thesis by (simp add: comp_def)
  qed

  have sub: "swap_delta i j D
               ⊆ (Q - {t, r}) × (UNIV → Gm) × Q × (UNIV → Gm)
                   × (UNIV → UNIV)"
  proof (rule subsetI)
    fix x assume x: "x ∈ swap_delta i j D"
    obtain q a q' a' d where xe: "x = (q, a, q', a', d)" by (cases x) auto
    from tuple [OF x [unfolded xe]] xe
    show "x ∈ (Q - {t, r}) × (UNIV → Gm) × Q × (UNIV → Gm)
                × (UNIV → UNIV)"
      by (simp add: Pi_iff)
  qed

  have base: "finite Q" "finite Gm" "Sg ⊆ Gm" "s ∈ Q" "t ∈ Q" "r ∈ Q"
             "bl ∈ Gm" "bl ∉ Sg" "le ∈ Gm" "le ∉ Sg" "t ≠ r" "0 < k"
    using vM M_eq by auto

  show ?thesis
    unfolding W valid_ktm.simps
    using base sub LEdisc supp by blast
qed

text ‹Determinism too: two transitions of the exchanged machine on one
  state and read vector come from two transitions of ‹M› on one read vector,
  because composing with the exchange is injective.›

lemma swap_det:
  assumes dM: "det_ktm M"
  shows "det_ktm (swap_tapes i j M)"
  unfolding det_ktm_def swap_fields
proof (intro allI impI)
  fix q A p1 b1 e1 p2 b2 e2
  assume t1: "(q, A, p1, b1, e1) ∈ swap_delta i j (delta_ktm M)"
    and t2: "(q, A, p2, b2, e2) ∈ swap_delta i j (delta_ktm M)"
  from swap_delta_E [OF t1] obtain c1 c1' f1
    where r1: "(q, c1, p1, c1', f1) ∈ delta_ktm M" and A1: "A = c1 ∘ tswap i j"
      and B1: "b1 = c1' ∘ tswap i j" and E1: "e1 = f1 ∘ tswap i j" .
  from swap_delta_E [OF t2] obtain c2 c2' f2
    where r2: "(q, c2, p2, c2', f2) ∈ delta_ktm M" and A2: "A = c2 ∘ tswap i j"
      and B2: "b2 = c2' ∘ tswap i j" and E2: "e2 = f2 ∘ tswap i j" .
  have c: "c1 = c2"
  proof
    fix x
    have "c1 x = (c1 ∘ tswap i j) (tswap i j x)" by simp
    also have "… = (c2 ∘ tswap i j) (tswap i j x)" using A1 A2 by simp
    also have "… = c2 x" by simp
    finally show "c1 x = c2 x" .
  qed
  from dM r1 r2 [folded c] have "(p1, c1', f1) = (p2, c2', f2)"
    unfolding det_ktm_def by blast
  then show "(p1, b1, e1) = (p2, b2, e2)" using B1 B2 E1 E2 by simp
qed

text ‹And const‹le_unique› again, which an exchange of two tape indices
  preserves because the property is a conjunction over indices and the exchange
  permutes them.›

lemma swap_le_unique:
  assumes lu: "le_unique M"
  shows "le_unique (swap_tapes i j M)"
  using lu by (fastforce simp: le_unique_def swap_tapes_def swap_delta_def)

text ‹The configuration correspondence, and it is a bijection rather than an
  embedding --- which is what removes every hypothesis from the two run
  lemmas below.  Nothing is invented and nothing is discarded, so the reverse
  direction is the forward one applied to the exchanged machine and needs no
  argument of its own.›

definition swap_config ::
  "nat ⇒ nat ⇒ ('a, 'q) ktc_config ⇒ ('a, 'q) ktc_config" where
  "swap_config i j c =
     KConfig (ktc_state c) (ktc_tape c ∘ tswap i j) (ktc_pos c ∘ tswap i j)"

lemma swap_config_Config [simp]:
  "swap_config i j (KConfig q ts n)
     = KConfig q (ts ∘ tswap i j) (n ∘ tswap i j)"
  by (simp add: swap_config_def)

lemma swap_config_simps [simp]:
  "ktc_state (swap_config i j c) = ktc_state c"
  "ktc_tape (swap_config i j c) = ktc_tape c ∘ tswap i j"
  "ktc_pos (swap_config i j c) = ktc_pos c ∘ tswap i j"
  by (simp_all add: swap_config_def)

lemma swap_config_swap_config [simp]:
  "swap_config i j (swap_config i j c) = c"
  by (cases c) (simp add: comp_def)

lemma swap_step:
  assumes step: "(c, c') ∈ ktm_step (delta_ktm M)"
  shows "(swap_config i j c, swap_config i j c')
           ∈ ktm_step (delta_ktm (swap_tapes i j M))"
proof -
  from step obtain q ts n q' a d
    where c: "c = KConfig q ts n"
      and c': "c' = KConfig q' (λm. (ts m)(n m := a m))
                              (λm. go_move (d m) (n m))"
      and tr: "(q, λm. ts m (n m), q', a, d) ∈ delta_ktm M"
    by (auto elim!: ktm_step.cases)
  let ?s = "tswap i j"
  have "(KConfig q (ts ∘ ?s) (n ∘ ?s),
         KConfig q' (λm. ((ts ∘ ?s) m)((n ∘ ?s) m := (a ∘ ?s) m))
                    (λm. go_move ((d ∘ ?s) m) ((n ∘ ?s) m)))
          ∈ ktm_step (delta_ktm (swap_tapes i j M))"
  proof (rule ktm_step.step)
    show "(q, λm. (ts ∘ ?s) m ((n ∘ ?s) m), q', a ∘ ?s, d ∘ ?s)
            ∈ delta_ktm (swap_tapes i j M)"
      using swap_delta_I [OF tr, of i j] by (simp add: comp_def)
  qed
  moreover have "swap_config i j c = KConfig q (ts ∘ ?s) (n ∘ ?s)"
    unfolding c by simp
  moreover have "swap_config i j c'
                   = KConfig q' (λm. ((ts ∘ ?s) m)((n ∘ ?s) m := (a ∘ ?s) m))
                                (λm. go_move ((d ∘ ?s) m) ((n ∘ ?s) m))"
    unfolding c' by (simp add: comp_def)
  ultimately show ?thesis by simp
qed

lemma swap_run:
  assumes run: "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
  shows "(swap_config i j c, swap_config i j c')
           ∈ (ktm_step (delta_ktm (swap_tapes i j M))) ^^ n"
  by (rule relpow_map [where h = "swap_config i j", OF _ run]) (erule swap_step)

text ‹The reverse direction, and the whole of its proof: exchange the same two
  tapes again.  ‹widen_run_rev› next door needs its own inversion argument
  because widening is not onto; this one does not.›

lemma swap_run_rev:
  assumes run: "(swap_config i j c, e)
                  ∈ (ktm_step (delta_ktm (swap_tapes i j M))) ^^ n"
  shows "(c, swap_config i j e) ∈ (ktm_step (delta_ktm M)) ^^ n"
proof -
  from swap_run [OF run, of i j]
  have "(swap_config i j (swap_config i j c), swap_config i j e)
          ∈ (ktm_step (delta_ktm (swap_tapes i j (swap_tapes i j M)))) ^^ n" .
  then show ?thesis by simp
qed


subsection ‹Pinning two points of an injection›

text ‹Pin two elements at chosen values, and push everything else clear of
  both and of a given finite set.  ∗‹Which›
  injection carries the rest is immaterial --- any injection of a finite set
  into typ‹nat› serves, and ‹finite› supplies one --- so all of the content
  is in the offset.

  Numbering a machine's states and symbols into an initial segment uses it at
  the values ‹0› and ‹1› with nothing to avoid.  A composite of two machines
  uses the general form: one factor's blank and endmarker have to land on
  ∗‹the other's›, since a machine has only one of each, while its remaining
  symbols must stay clear of the other's alphabet, or a step of one factor
  would read a symbol meant for the other.

  Injectivity needs only ‹x ≠ y› and ‹u ≠ v›, and in particular ∗‹not›
  that either point lies in ‹A›.  The offset puts the shifted remainder
  strictly above ‹u›, ‹v› and all of ‹B› at once, so no collision is possible
  whether or not the pinned points are themselves being numbered.  That is
  what lets one lemma serve every call without a side condition placing the
  blank in the alphabet or the start state in ‹Q›.›

lemma inj_on_pin_two_avoiding:
  assumes finA: "finite A" and finB: "finite B"
    and xy: "x ≠ y" and uv: "u ≠ v"
  obtains h :: "'b ⇒ nat"
  where "inj_on h A" and "h x = u" and "h y = v"
    and "h ` (A - {x, y}) ∩ B = {}"
proof -
  from finite_imp_inj_to_nat_seg [OF finA]
  obtain e :: "'b ⇒ nat" where inje: "inj_on e A" by blast
  define m where "m = Suc (Max (insert u (insert v B)))"
  have fin': "finite (insert u (insert v B))" using finB by simp
  have lt: "z < m" if "z ∈ insert u (insert v B)" for z
    using Max_ge [OF fin' that] by (simp add: m_def)
  have um: "u < m" by (rule lt) simp
  have vm: "v < m" by (rule lt) simp
  have ltB: "z < m" if "z ∈ B" for z using that by (intro lt) simp
  let ?h = "λz. if z = x then u else if z = y then v else m + e z"
  have inj: "inj_on ?h A"
  proof (rule inj_onI)
    fix a b
    assume a: "a ∈ A" and b: "b ∈ A" and eq: "?h a = ?h b"
    show "a = b"
    proof (cases "a = x ∨ a = y")
      case True
      with eq xy uv um vm show ?thesis by (auto split: if_splits)
    next
      case False
      with eq um vm have "b ≠ x" "b ≠ y" by (auto split: if_splits)
      with False eq have "e a = e b" by simp
      with inje a b show ?thesis by (auto dest: inj_onD)
    qed
  qed
  have notB: "?h z ∉ B" if z: "z ∈ A - {x, y}" for z
  proof
    assume mem: "?h z ∈ B"
    from z have "?h z = m + e z" by simp
    with mem have "m + e z ∈ B" by simp
    from ltB [OF this] show False by simp
  qed
  show thesis
  proof (rule that)
    show "inj_on ?h A" by (rule inj)
    show "?h x = u" by simp
    show "?h y = v" using xy by simp
    show "?h ` (A - {x, y}) ∩ B = {}" using notB by blast
  qed
qed

end