Theory Multitape_Substrate

theory Multitape_Substrate
  imports Multitape_Substrate_Core
begin

section ‹Basic facts about machines and runs›

text ‹The substrate metatheory --- ∗‹our› additions over the
  Dalvit--Thiemann definition surface isolated in ‹Multitape_Substrate_Core›:
  relation-power and finiteness utilities, the ‹valid_ktm›
  axiom-extraction toolkit, per-step and reachability validity
  preservation, and the displacement / left-endmarker / no-write tape
  tools.  The core (‹Multitape_Substrate_Core›) carries the datatypes, accessors,
  step relation, and the validity / language definitions.›


subsection ‹Relation powers and finiteness›

lemma finite_UNIV_move [simp, intro]: "finite (UNIV :: move set)"
proof -
  have id: "UNIV = {MoveL, MoveR, MoveN}"
    using move.exhaust by auto
  show ?thesis unfolding id by auto
qed

text ‹Blank-tail finiteness: the set of total functions ‹nat ⇒ 'b›
  ranging in a finite codomain ‹B› and ∗‹constant ‹c› beyond an
  index ‹k›› is finite.  This replaces the function-space finiteness
  lemmas (‹fin_funcsetI› / ‹finite_UNIV_fun_dir›) that the AFP source
  relied on: those are false at the value-level ‹nat› index, where
  the domain is infinite.  Finiteness is recovered from the support
  bound — a blank-tail function is determined by its restriction to
  ‹{..<k}›, of which there are finitely many.  Used to re-derive
  ‹finite δ› for constructed machines (‹valid_ktm_finite_delta›),
  with codomain ‹Γ› (blank tail) for read/write tuples and ‹move›
  (‹MoveN› tail) for the move tuples.›

lemma finite_tail_const_funcs:
  fixes B :: "'b set" and k :: nat and c :: 'b
  assumes finB: "finite B"
  shows "finite {f :: nat ⇒ 'b. (∀j. f j ∈ B) ∧ (∀j ≥ k. f j = c)}"
proof -
  let ?S = "{f :: nat ⇒ 'b. (∀j. f j ∈ B) ∧ (∀j ≥ k. f j = c)}"
  have inj: "inj_on (λf. restrict f {..<k}) ?S"
  proof (rule inj_onI)
    fix f g
    assume f: "f ∈ ?S" and g: "g ∈ ?S"
      and eq: "restrict f {..<k} = restrict g {..<k}"
    show "f = g"
    proof
      fix j
      show "f j = g j"
      proof (cases "j < k")
        case True
        have "restrict f {..<k} j = restrict g {..<k} j" using eq by simp
        thus ?thesis using True by (simp add: restrict_def)
      next
        case False
        hence "k ≤ j" by simp
        with f g show ?thesis by simp
      qed
    qed
  qed
  have rng: "(λf. restrict f {..<k}) ` ?S ⊆ ({..<k} →E B)"
  proof
    fix h assume "h ∈ (λf. restrict f {..<k}) ` ?S"
    then obtain f where f: "f ∈ ?S" and h: "h = restrict f {..<k}" by blast
    show "h ∈ {..<k} →E B"
      using f unfolding h by (simp add: restrict_PiE Pi_iff)
  qed
  have finPiE: "finite ({..<k} →E B)" using finB by (simp add: finite_PiE)
  have "finite ((λf. restrict f {..<k}) ` ?S)"
    by (rule finite_subset[OF rng finPiE])
  thus "finite ?S" using inj by (rule finite_imageD)
qed

text ‹Runs compose by HOL's ‹relpow_trans›.  Monotonicity in the relation is
  HOL's predicate lemma ‹relpowp_mono›, restated for relations as sets.›

lemma relpow_subset_mono: fixes R :: "'a rel"
  shows "R ⊆ S ⟹ R^^n ⊆ S^^n"
  by (induct n, auto)

text ‹Bounded-iteration combinator: given a single-step law that,
  from any config satisfying an index-parameterised invariant
  ‹P i› with ‹i < n›, takes one ‹R›-step to a config satisfying
  ‹P (Suc i)›, iterate it: from ‹P 0 c0› reach a ‹c'› with
  ‹(c0, c') ∈ Rn› and ‹P n c'›.  A loop whose counter
  starts at some ‹off > 0› instantiates ‹P› to re-index by that
  offset.  Proved by induction generalising ∗‹both› the start
  config and the invariant, so the hypothesis applies to the shifted
  predicate ‹λj. P (Suc j)› after peeling the first step
  (prepended via ‹relpow_Suc_I2›).›

lemma relpow_invariant_chain:
  fixes R :: "('s × 's) set"
    and P :: "nat ⇒ 's ⇒ bool"
  assumes step: "⋀i c. ⟦ i < n; P i c ⟧
                          ⟹ ∃c'. (c, c') ∈ R ∧ P (Suc i) c'"
      and base: "P 0 c0"
  shows "∃c'. (c0, c') ∈ R ^^ n ∧ P n c'"
  using assms
proof (induction n arbitrary: c0)
  case 0
  show ?case using "0.prems"(2) by auto
next
  case (Suc m)
  have step_m:
      "⋀i c. ⟦ i < m; P i c ⟧
              ⟹ ∃c'. (c, c') ∈ R ∧ P (Suc i) c'"
  proof -
    fix i :: nat and c :: 's
    assume "i < m" and "P i c"
    thus "∃c'. (c, c') ∈ R ∧ P (Suc i) c'"
      using Suc.prems(1)[of i c] by simp
  qed
  obtain c_m where chain_m: "(c0, c_m) ∈ R ^^ m" and Pcm: "P m c_m"
    using Suc.IH[OF step_m Suc.prems(2)] by blast
  obtain c' where last_step: "(c_m, c') ∈ R" and Pc': "P (Suc m) c'"
    using Suc.prems(1)[of m c_m] Pcm by auto
  have "(c0, c') ∈ R ^^ Suc m"
    using chain_m last_step by (rule relpow_Suc_I)
  thus ?case using Pc' by blast
qed

text ‹❙‹A step simulation is a run simulation.›  A construction that
  re-encodes configurations by a map ‹h› proves that each step of the
  source is a step of the target on the images, and wants the same of a run
  of any length.  The step may assume its source was reached from the run's
  start: the encodings that are steps only on reachable configurations (a
  valid one, or one with its endmarkers in place) discharge that by the
  relational-power forms of their invariants.›

lemma relpow_map:
  assumes step: "⋀m x y. (a, x) ∈ R ^^ m ⟹ (x, y) ∈ R ⟹ (h x, h y) ∈ S"
      and run: "(a, b) ∈ R ^^ n"
  shows "(h a, h b) ∈ S ^^ n"
  using run
proof (induction n arbitrary: b)
  case 0
  then show ?case by simp
next
  case (Suc n)
  from Suc.prems obtain x where ax: "(a, x) ∈ R ^^ n" and xb: "(x, b) ∈ R"
    by (rule relpow_Suc_E)
  from Suc.IH [OF ax] step [OF ax xb] show ?case by (rule relpow_Suc_I)
qed


subsection ‹Uniqueness on a deterministic region›

text ‹❙‹‹det_ktm_relpow_unique› (below) for a machine that is
  deterministic only somewhere.›  A nondeterministic machine can still have large regions in
  which it branches nowhere, and a run that stays inside one of those is as
  pinned as a deterministic machine's.  What makes the statement usable is
  that both hypotheses are about the ∗‹region› rather than about the
  relation: ‹R› is closed under a step, and a step out of ‹R› is unique.

  The induction cannot be traded for ⬚‹single_valued_relpow› the way
  ‹det_ktm_relpow_unique›'s was.  Restricting the relation to ‹R› does make it
  single-valued, but showing that an unrestricted run ∗‹is› a
  restricted one is the same induction again --- the closure has to be
  carried along the run, and that is precisely what the induction does.

  Stated for a bare relation because nothing here is about machines.›

lemma relpow_unique_on:
  assumes closed: "⋀x y. x ∈ R ⟹ (x, y) ∈ S ⟹ y ∈ R"
      and fn: "⋀x y z. x ∈ R ⟹ (x, y) ∈ S ⟹ (x, z) ∈ S
                       ⟹ y = z"
  shows "x ∈ R ⟹ (x, y) ∈ S ^^ n ⟹ (x, z) ∈ S ^^ n ⟹ y = z"
proof (induct n arbitrary: x y z)
  case 0
  then show ?case by simp
next
  case (Suc n)
  from Suc.prems(2) obtain u where xu: "(x, u) ∈ S" and uy: "(u, y) ∈ S ^^ n"
    by (blast dest: relpow_Suc_D2)
  from Suc.prems(3) obtain v where xv: "(x, v) ∈ S" and vz: "(v, z) ∈ S ^^ n"
    by (blast dest: relpow_Suc_D2)
  from fn [OF Suc.prems(1) xu xv] have uv: "u = v" .
  have uR: "u ∈ R" by (rule closed [OF Suc.prems(1) xu])
  from vz uv have uz: "(u, z) ∈ S ^^ n" by simp
  show ?case by (rule Suc.hyps [OF uR uy uz])
qed

text ‹❙‹What the region buys, stated the way a language argument wants
  it.›  The lemma above compares runs of the ∗‹same› length, which no
  consumer ever has: one is given a path that halts and asked about another
  path that halts, and the two lengths are unrelated.  The bridge is that a
  halting configuration has no successor, so the shorter run cannot be a
  proper prefix of the longer one --- and by uniqueness it is a prefix or
  nothing.  So the two runs have the same length as well as the same end.

  So a branch-free region admits ∗‹at most one› halting configuration
  reachable from a given start, whatever the path and whatever its length.
  That is the form soundness uses: exhibit the run that halts, and every
  other halting run is that one.  The length half is what pins a phase of a
  simulation: two runs of a sub-relation that both end where it stops took
  the same number of steps.›

lemma relpow_halted_le:
  assumes closed: "⋀x y. x ∈ R ⟹ (x, y) ∈ S ⟹ y ∈ R"
      and fn: "⋀x y z. x ∈ R ⟹ (x, y) ∈ S ⟹ (x, z) ∈ S
                       ⟹ y = z"
      and stuck: "⋀u v. u ∈ H ⟹ (u, v) ∈ S ⟹ False"
      and x: "x ∈ R"
      and r1: "(x, y) ∈ S ^^ m" and h1: "y ∈ H"
      and r2: "(x, z) ∈ S ^^ n"
      and mn: "m ≤ n"
  shows "m = n ∧ y = z"
proof -
  ― ‹the split is done to the ∗‹exponent› and then to the relation,
      never by a ⬚‹simp› carrying ‹n = m + (n - m)›: that equation rewrites
      ‹n› into a term containing ‹n››
  have "S ^^ (m + (n - m)) = S ^^ m O S ^^ (n - m)" by (rule relpow_add)
  moreover from mn have "m + (n - m) = n" by simp
  ultimately have "S ^^ n = S ^^ m O S ^^ (n - m)" by simp
  with r2 have "(x, z) ∈ S ^^ m O S ^^ (n - m)" by simp
  then obtain u where xu: "(x, u) ∈ S ^^ m" and uz: "(u, z) ∈ S ^^ (n - m)"
    by auto
  from relpow_unique_on [OF closed fn x r1 xu] have "y = u" .
  with uz have yz: "(y, z) ∈ S ^^ (n - m)" by simp
  show ?thesis
  proof (cases "n - m")
    case 0
    with yz mn show ?thesis by simp
  next
    case (Suc k)
    from yz Suc have "(y, z) ∈ S ^^ Suc k" by simp
    then obtain v where "(y, v) ∈ S" by (blast dest: relpow_Suc_D2)
    from stuck [OF h1 this] show ?thesis ..
  qed
qed

lemma relpow_halted_same_run:
  assumes closed: "⋀x y. x ∈ R ⟹ (x, y) ∈ S ⟹ y ∈ R"
      and fn: "⋀x y z. x ∈ R ⟹ (x, y) ∈ S ⟹ (x, z) ∈ S
                       ⟹ y = z"
      and stuck: "⋀u v. u ∈ H ⟹ (u, v) ∈ S ⟹ False"
      and x: "x ∈ R"
      and r1: "(x, y) ∈ S ^^ m" and h1: "y ∈ H"
      and r2: "(x, z) ∈ S ^^ n" and h2: "z ∈ H"
  shows "m = n ∧ y = z"
  using nat_le_linear [of m n]
proof
  assume mn: "m ≤ n"
  from relpow_halted_le [OF closed fn stuck x r1 h1 r2 mn] show ?thesis .
next
  assume nm: "n ≤ m"
  from relpow_halted_le [OF closed fn stuck x r2 h2 r1 nm] show ?thesis by simp
qed

lemmas relpow_halted_unique_on = relpow_halted_same_run [THEN conjunct2]


subsection ‹The conditions of validity, one at a time›

text ‹Convenience lemmas projecting the substrate's structural
  axioms out of @{const valid_ktm} at the functional layer.
  Each one is a one-shot ‹by (cases M) auto›: the case-decomposition
  rewrites @{term M} into ‹KTM›-form, exposes the @{thm[source] valid_ktm.simps}
  conjunction, and ‹auto› extracts the relevant conjunct.

  These replace what used to be locale-routed retrievals of the
  form ‹multitape_tm.X[OF loc]›.›

lemma valid_ktm_finite_Q:
  assumes "valid_ktm M"
  shows "finite (Q_ktm M)"
  using assms by (cases M) auto

lemma valid_ktm_finite_Gamma:
  assumes "valid_ktm M"
  shows "finite (Γ_ktm M)"
  using assms by (cases M) auto

lemma valid_ktm_Sigma_sub_Gamma:
  assumes "valid_ktm M"
  shows "Sigma_ktm M ⊆ Γ_ktm M"
  using assms by (cases M) auto

lemma valid_ktm_s_in_Q:
  assumes "valid_ktm M"
  shows "s_ktm M ∈ Q_ktm M"
  using assms by (cases M) auto

lemma valid_ktm_t_in_Q:
  assumes "valid_ktm M"
  shows "t_ktm M ∈ Q_ktm M"
  using assms by (cases M) auto

lemma valid_ktm_r_in_Q:
  assumes "valid_ktm M"
  shows "r_ktm M ∈ Q_ktm M"
  using assms by (cases M) auto

lemma valid_ktm_blank_in_Gamma:
  assumes "valid_ktm M"
  shows "bl_ktm M ∈ Γ_ktm M"
  using assms by (cases M) auto

lemma valid_ktm_blank_not_Sigma:
  assumes "valid_ktm M"
  shows "bl_ktm M ∉ Sigma_ktm M"
  using assms by (cases M) auto

lemma valid_ktm_LE_in_Gamma:
  assumes "valid_ktm M"
  shows "le_ktm M ∈ Γ_ktm M"
  using assms by (cases M) auto

lemma valid_ktm_LE_not_Sigma:
  assumes "valid_ktm M"
  shows "le_ktm M ∉ Sigma_ktm M"
  using assms by (cases M) auto

lemma valid_ktm_t_neq_r:
  assumes "valid_ktm M"
  shows "t_ktm M ≠ r_ktm M"
  using assms by (cases M) auto

lemma valid_ktm_k_pos:
  assumes "valid_ktm M"
  shows "0 < k_ktm M"
  using assms by (cases M) auto

lemma valid_ktm_delta_set:
  assumes "valid_ktm M"
  shows "delta_ktm M ⊆
           (Q_ktm M - {t_ktm M, r_ktm M})
             × (UNIV → Γ_ktm M)
             × Q_ktm M
             × (UNIV → Γ_ktm M)
             × (UNIV → UNIV)"
  using assms by (cases M) auto

text ‹Range typing for transition tuples: pulls the four
  per-component facts from a single transition membership.›

lemma valid_ktm_delta:
  assumes vM: "valid_ktm M"
    and tr: "(q, a, q', b, d) ∈ delta_ktm M"
  shows "q ∈ Q_ktm M" "a k ∈ Γ_ktm M" "q' ∈ Q_ktm M" "b k ∈ Γ_ktm M"
  using valid_ktm_delta_set[OF vM] tr by auto

text ‹Left-endmarker discipline: transitions reading ‹le› must
  rewrite ‹le› with itself and move only ‹N› or ‹R›.›

lemma valid_ktm_deltaLE:
  assumes vM: "valid_ktm M"
    and tr: "(q, a, q', a', d) ∈ delta_ktm M"
    and LE: "a k = le_ktm M"
  shows "a' k = le_ktm M ∧ d k ∈ {MoveN, MoveR}"
  using vM tr LE by (cases M) auto

text ‹Left-endmarker write discipline: a transition writes ‹le› on
  tape ‹k› only when it was reading ‹le› on the same tape.  This is
  exactly the content of @{const le_unique} specialised to one tape /
  transition; it is the sole place that fact is extracted.  Needed by
  ‹ae_coupled_run_aux› to preserve the "no LE in window" invariant
  across an M-step.  Takes @{const le_unique} (not @{const valid_ktm}):
  it is the property a machine may forgo, so consumers thread it
  explicitly rather than reading it off ‹valid_ktm›.›

lemma valid_ktm_deltaLE_no_write:
  assumes lu: "le_unique M"
    and tr: "(q, a, q', a', d) ∈ delta_ktm M"
    and LE': "a' k = le_ktm M"
  shows "a k = le_ktm M"
  using lu[unfolded le_unique_def] tr LE' by blast

text ‹Support invariant: every transition of a valid machine is
  blank on reads and writes, and stationary, at every tape index
  ‹j ≥ k_ktm M›.  The value-level confinement of a ‹k›-tape machine's
  action to tapes ‹0 … k - 1›.›

lemma valid_ktm_delta_support:
  assumes vM: "valid_ktm M"
    and tr: "(q, a, q', a', d) ∈ delta_ktm M"
    and j: "j ≥ k_ktm M"
  shows "a j = bl_ktm M ∧ a' j = bl_ktm M ∧ d j = MoveN"
proof -
  obtain Q Σ Γ bl le δ s t r K where M_eq:
      "M = KTM Q Σ Γ bl le δ s t r K"
    by (cases M)
  have supp:
      "∀q a q' a' d. (q, a, q', a', d) ∈ δ ⟶
                       (∀j ≥ K. a j = bl ∧ a' j = bl ∧ d j = MoveN)"
    using vM[unfolded M_eq valid_ktm.simps] by blast
  from tr M_eq have tr_delta: "(q, a, q', a', d) ∈ δ" by simp
  from j M_eq have jK: "j ≥ K" by simp
  have bleq: "bl_ktm M = bl" using M_eq by simp
  from supp tr_delta jK have "a j = bl ∧ a' j = bl ∧ d j = MoveN" by blast
  thus ?thesis using bleq by simp
qed

text ‹Finiteness of ‹δ› from bounded support: a valid machine's
  transition relation is finite.  The value-level replacement for
  the AFP source's function-space finiteness over a finite tape
  type.  Each transition's read / write tuples range in the finite
  @{term Γ} and are blank beyond ‹k›, each move tuple is ‹N›
  beyond ‹k›; by @{thm[source] finite_tail_const_funcs} there are
  finitely many of each, so ‹δ› embeds in a finite product.›

lemma valid_ktm_finite_delta:
  assumes vM: "valid_ktm M"
  shows "finite (delta_ktm M)"
proof -
  obtain Q Σ Γ bl le δ s t r K where M_eq:
      "M = KTM Q Σ Γ bl le δ s t r K"
    by (cases M)
  have finQ: "finite Q" using valid_ktm_finite_Q[OF vM] M_eq by simp
  have finG: "finite Γ" using valid_ktm_finite_Gamma[OF vM] M_eq by simp
  let ?A = "{a. (∀j. a j ∈ Γ) ∧ (∀j ≥ K. a j = bl)}"
  let ?D = "{d. (∀j. d j ∈ (UNIV :: move set)) ∧ (∀j ≥ K. d j = MoveN)}"
  have finA: "finite ?A" by (rule finite_tail_const_funcs[OF finG, of K bl])
  have finD: "finite ?D" by (rule finite_tail_const_funcs[OF finite_UNIV_move, of K MoveN])
  have finprod: "finite ((Q - {t, r}) × ?A × Q × ?A × ?D)"
    using finQ finA finD by (intro finite_cartesian_product) auto
  have sub: "delta_ktm M ⊆ (Q - {t, r}) × ?A × Q × ?A × ?D"
  proof
    fix x assume xd: "x ∈ delta_ktm M"
    obtain q a q' a' d where x: "x = (q, a, q', a', d)"
      by (cases x)
    from valid_ktm_delta_set[OF vM] xd x M_eq
    have q_mem: "q ∈ Q - {t, r}" and a_pi: "a ∈ UNIV → Γ"
      and q'_mem: "q' ∈ Q" and a'_pi: "a' ∈ UNIV → Γ"
      by auto
    from a_pi have aG: "∀j. a j ∈ Γ" by (auto simp: Pi_iff)
    from a'_pi have a'G: "∀j. a' j ∈ Γ" by (auto simp: Pi_iff)
    have trM: "(q, a, q', a', d) ∈ delta_ktm M" using xd x by simp
    have supp: "∀j ≥ K. a j = bl ∧ a' j = bl ∧ d j = MoveN"
    proof (intro allI impI)
      fix j assume "K ≤ j"
      hence "j ≥ k_ktm M" using M_eq by simp
      thus "a j = bl ∧ a' j = bl ∧ d j = MoveN"
        using valid_ktm_delta_support[OF vM trM] M_eq by simp
    qed
    have "a ∈ ?A" using aG supp by auto
    moreover have "a' ∈ ?A" using a'G supp by auto
    moreover have "d ∈ ?D" using supp by auto
    ultimately show "x ∈ (Q - {t, r}) × ?A × Q × ?A × ?D"
      using x q_mem q'_mem by auto
  qed
  show ?thesis using sub finprod by (rule finite_subset)
qed

text ‹State membership at the source of an ‹ktm_step›: the
  source state is in ‹Q_ktm M› and is neither the accept nor
  the reject state.  Direct consequence of the ‹ktm_step›
  introduction rule plus ‹valid_ktm_delta_set›'s range typing
  (which excludes halting states from the source projection of
  ‹delta_ktm M›).

  Used by the chunked-induction engine
  ‹ae_simulation_phase_chunked›: when the M-trace
  ‹(cM, cM_final) ∈ ktm_step (delta_ktm M) ^^ (Suc n)›
  is non-empty, the first step exists and forces ‹cM›'s state
  to be non-halt and in ‹Q›, which feeds
  ‹ae_simulates_forward_stage_general›'s ‹qM_in_Q› /
  ‹q_neq_t› / ‹q_neq_r› hypotheses.›

lemma ktm_step_src:
  fixes M :: "('q, 'a) ktm"
  assumes vM:   "valid_ktm M"
    and step: "(c, c') ∈ ktm_step (delta_ktm M)"
  shows ktm_step_src_in_Q:    "ktc_state c ∈ Q_ktm M"
    and ktm_step_src_neq_t:   "ktc_state c ≠ t_ktm M"
    and ktm_step_src_neq_r:   "ktc_state c ≠ r_ktm M"
proof -
  from step obtain q ts n q' a move where
      c_eq: "c = KConfig q ts n"
    and tr: "(q, λk. ts k (n k), q', a, move) ∈ delta_ktm M"
    by (auto elim: ktm_step.cases)
  have q_eq: "ktc_state c = q" using c_eq by simp
  have q_in_strict: "q ∈ Q_ktm M - {t_ktm M, r_ktm M}"
    using valid_ktm_delta_set[OF vM] tr by auto
  show "ktc_state c ∈ Q_ktm M"  using q_eq q_in_strict by simp
  show "ktc_state c ≠ t_ktm M" using q_eq q_in_strict by simp
  show "ktc_state c ≠ r_ktm M" using q_eq q_in_strict by simp
qed


subsection ‹A step preserves valid configurations›

text ‹Per-step preservation of @{const valid_config_ktm}: a valid
  configuration steps only to valid configurations.  Re-derived
  directly from @{thm[source] valid_ktm_delta} (range typing),
  @{thm[source] valid_ktm_deltaLE} (left-endmarker discipline),
  and @{thm[source] valid_ktm_delta_support} (the new inactive-tape
  blank-tail case).›

lemma valid_step_ktm:
  fixes M :: "('q, 'a) ktm"
  assumes vM:    "valid_ktm M"
    and step:    "(c, c') ∈ ktm_step (delta_ktm M)"
    and val_c:   "valid_config_ktm M c"
  shows "valid_config_ktm M c'"
proof -
  obtain Q Σ Γ bl le δ s t r K where M_eq:
      "M = KTM Q Σ Γ bl le δ s t r K"
    by (cases M)
  obtain q ts n where c_eq: "c = KConfig q ts n"
    by (cases c)
  from step M_eq c_eq have step_delta:
      "(KConfig q ts n, c') ∈ ktm_step δ"
    by simp
  obtain q' a move where c'_eq:
      "c' = KConfig q' (λk. (ts k)(n k := a k))
                       (λk. go_move (move k) (n k))"
    and tr: "(q, (λk. ts k (n k)), q', a, move) ∈ δ"
    using step_delta by (auto elim: ktm_step.cases)
  from val_c c_eq M_eq have q_in: "q ∈ Q"
    and ts_Gamma: "⋀k. range (ts k) ⊆ Γ"
    and ts_LE: "⋀k. k < K ⟹ ts k 0 = le"
    and ts_blank: "⋀k p. k ≥ K ⟹ ts k p = bl"
    by auto
  from tr M_eq have tr_M: "(q, (λk. ts k (n k)), q', a, move) ∈ delta_ktm M"
    by simp
  have q'_in: "q' ∈ Q_ktm M" and a_Gamma: "⋀k. a k ∈ Γ_ktm M"
    using valid_ktm_delta[OF vM tr_M] by auto
  hence q'_in_Q: "q' ∈ Q" and a_Gamma_set: "⋀k. a k ∈ Γ"
    using M_eq by auto
  have new_ts_Gamma: "⋀k. range ((ts k)(n k := a k)) ⊆ Γ"
    using ts_Gamma a_Gamma_set by auto
  have new_LE: "⋀k. k < K ⟹ ((ts k)(n k := a k)) 0 = le"
  proof -
    fix k assume kK: "k < K"
    show "((ts k)(n k := a k)) 0 = le"
    proof (cases "n k = 0")
      case True
      have read_LE: "(λj. ts j (n j)) k = le"
        using ts_LE[OF kK] True by simp
      have read_LE_le: "(λj. ts j (n j)) k = le_ktm M"
        using read_LE M_eq by simp
      have "a k = le_ktm M"
        using valid_ktm_deltaLE[OF vM tr_M read_LE_le] by simp
      hence "a k = le" using M_eq by simp
      with True show ?thesis by simp
    next
      case False
      thus ?thesis using ts_LE[OF kK] by simp
    qed
  qed
  have new_blank: "⋀k p. k ≥ K ⟹ ((ts k)(n k := a k)) p = bl"
  proof -
    fix k p assume kK: "k ≥ K"
    have ak_bl: "a k = bl"
    proof -
      have "k ≥ k_ktm M" using kK M_eq by simp
      hence "a k = bl_ktm M"
        using valid_ktm_delta_support[OF vM tr_M] by simp
      thus ?thesis using M_eq by simp
    qed
    show "((ts k)(n k := a k)) p = bl"
      using ts_blank[OF kK] ak_bl by (cases "p = n k") auto
  qed
  show ?thesis
    unfolding M_eq c'_eq valid_config_ktm.simps
  proof (intro conjI allI impI)
    show "q' ∈ Q" using q'_in_Q .
  next
    fix i
    show "range ((λk. (ts k)(n k := a k)) i) ⊆ Γ"
      using new_ts_Gamma by simp
  next
    fix i assume "i < K"
    show "(λk. (ts k)(n k := a k)) i 0 = le"
      using new_LE[OF ‹i < K›] by simp
  next
    fix i p assume "K ≤ i"
    show "(λk. (ts k)(n k := a k)) i p = bl"
      using new_blank[OF ‹K ≤ i›] by simp
  qed
qed

text ‹Initial-configuration accessors, in terms of the machine's
  structural projections.  const‹init_config_ktm› is a ⬚‹fun› over
  the ‹KTM› constructor, so without these a proof reads the start tape,
  state or heads only after an inline ‹cases M›.  The head positions are
  a ⬚‹simp› rule, since every head starts at the origin.›

lemma ktc_tape_init_config:
  "ktc_tape (init_config_ktm M w)
     = (λk n. if k < k_ktm M
              then (if n = 0 then le_ktm M
                    else if k = 0 ∧ n ≤ length w then w ! (n - 1)
                    else bl_ktm M)
              else bl_ktm M)"
proof (cases M)
  case (KTM Q Sg Gm bl le dl s tt rr kk)
  then have lhs: "ktc_tape (init_config_ktm M w)
                    = (λk n. if k < kk
                             then (if n = 0 then le
                                   else if k = 0 ∧ n ≤ length w then w ! (n - 1)
                                   else bl)
                             else bl)"
    and le': "le_ktm M = le" and bl': "bl_ktm M = bl" and kk': "k_ktm M = kk"
    by simp_all
  show ?thesis by (simp only: lhs le' bl' kk')
qed

lemma ktc_state_init_config [simp]:
  "ktc_state (init_config_ktm M w) = s_ktm M"
proof (cases M)
  case (KTM Q Sg Gm bl le dl s tt rr kk)
  then have lhs: "ktc_state (init_config_ktm M w) = s" and s': "s_ktm M = s"
    by simp_all
  show ?thesis by (simp only: lhs s')
qed

lemma ktc_pos_init_config [simp]:
  "ktc_pos (init_config_ktm M w) = (λ_. 0)"
  by (cases M) simp

text ‹Initial-configuration validity: a valid ‹M›'s initial
  configuration on a valid input is itself valid.›

lemma valid_init_config_ktm:
  fixes M :: "('q, 'a) ktm"
  assumes vM: "valid_ktm M"
    and w:    "set w ⊆ Sigma_ktm M"
  shows "valid_config_ktm M (init_config_ktm M w)"
proof -
  obtain Q Σ Γ bl le δ s t r K where M_eq:
      "M = KTM Q Σ Γ bl le δ s t r K"
    by (cases M)
  have w_Sigma: "set w ⊆ Σ"
    using w M_eq by simp
  have s_in: "s ∈ Q" using valid_ktm_s_in_Q[OF vM] M_eq by simp
  have Sigma_sub: "Σ ⊆ Γ" using valid_ktm_Sigma_sub_Gamma[OF vM] M_eq by simp
  have bl_in: "bl ∈ Γ" using valid_ktm_blank_in_Gamma[OF vM] M_eq by simp
  have le_in: "le ∈ Γ" using valid_ktm_LE_in_Gamma[OF vM] M_eq by simp
  show ?thesis
    unfolding M_eq init_config_ktm.simps valid_config_ktm.simps
  proof (intro conjI allI impI)
    show "s ∈ Q" using s_in .
  next
    fix i
    show "range (λn. if i < K
                     then (if n = 0 then le
                           else if i = 0 ∧ n ≤ length w then w ! (n - 1)
                           else bl)
                     else bl) ⊆ Γ"
    proof (cases "i < K")
      case True
      show ?thesis
        using bl_in le_in Sigma_sub w_Sigma True
        by (force simp: set_conv_nth)
    next
      case False
      show ?thesis using bl_in False by simp
    qed
  next
    fix i assume "i < K"
    show "(if i < K
            then (if (0::nat) = 0 then le
                  else if i = 0 ∧ 0 ≤ length w then w ! (0 - 1)
                  else bl)
            else bl) = le"
      using ‹i < K› by simp
  next
    fix i p assume "K ≤ i"
    show "(if i < K
            then (if p = 0 then le
                  else if i = 0 ∧ p ≤ length w then w ! (p - 1)
                  else bl)
            else bl) = bl"
      using ‹K ≤ i› by simp
  qed
qed

text ‹Reachability lift: every configuration reachable from a
  valid initial configuration is itself valid.›

lemma valid_reach_ktm:
  fixes M :: "('q, 'a) ktm"
  assumes vM:    "valid_ktm M"
    and w:       "set w ⊆ Sigma_ktm M"
    and reach:   "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M))*"
  shows "valid_config_ktm M c"
  using reach
proof induction
  case base
  show ?case using valid_init_config_ktm[OF vM w] .
next
  case (step y z)
  show ?case using valid_step_ktm[OF vM step.hyps(2) step.IH] .
qed

text ‹Blank-tail accessor for a valid configuration: beyond the
  machine's tape count ‹k_ktm M› every cell holds the blank
  ‹bl_ktm M›.  Used on the reverse lift's padding tapes, where the
  per-tape window invariant is unavailable (it constrains the LE
  home cell, which is blank on padding) and the read-match must
  instead come from the substrate blank-tail.›

lemma valid_config_ktm_blank_tail:
  assumes valc: "valid_config_ktm M c"
      and kge:  "i ≥ k_ktm M"
  shows "ktc_tape c i p = bl_ktm M"
proof -
  obtain Q Σ Γ bl le δ s t r K where
      M_eq: "M = KTM Q Σ Γ bl le δ s t r K"
    by (cases M)
  obtain q ts n where c_eq: "c = KConfig q ts n" by (cases c)
  from valc kge show ?thesis
    unfolding M_eq c_eq by auto
qed

text ‹Validity preservation along an ‹n›-step substrate trace
  from an arbitrary valid configuration (generic relpow closure of
  @{thm[source] valid_step_ktm}; @{thm[source] valid_reach_ktm}
  anchors only at ‹init_config_ktm›).  Threads the blank-tail
  validity of the reverse lift's intermediate configs ‹cM_n'›
  through the chain induction.›

lemma valid_reach_relpow_ktm:
  assumes vM:    "valid_ktm M"
      and valc:  "valid_config_ktm M c"
      and reach: "(c, c') ∈ ktm_step (delta_ktm M) ^^ n"
  shows "valid_config_ktm M c'"
  using relpow_imp_rtrancl [OF reach]
  by (induction rule: rtrancl_induct) (auto intro: valc valid_step_ktm [OF vM])

text ‹Per-tape LE-pinning corollary: along any reachable trace
  from a valid initial configuration, every ∗‹active› tape
  (index ‹k < k_ktm M›) carries ‹le_ktm M› at position 0.

  Note: ‹valid_config_ktm› only encodes the position-0 = LE
  constraint on active tapes, not the converse (positions ‹p ≠ 0›
  may legally hold LE in an arbitrary valid config).  The "LE only
  at position 0" property is reach-specific and proved separately
  in the companion lemma below.›

lemma valid_reach_LE_pos0_ktm:
  fixes M :: "('q, 'a) ktm"
  assumes vM:  "valid_ktm M"
    and w:     "set w ⊆ Sigma_ktm M"
    and reach: "(init_config_ktm M w, KConfig q ts n)
                  ∈ (ktm_step (delta_ktm M))*"
    and kK:    "k < k_ktm M"
  shows "ts k 0 = le_ktm M"
proof -
  have val: "valid_config_ktm M (KConfig q ts n)"
    using valid_reach_ktm[OF vM w reach] .
  obtain Q Σ Γ bl le δ sM t r K where M_eq:
      "M = KTM Q Σ Γ bl le δ sM t r K"
    by (cases M)
  have "k < K" using kK M_eq by simp
  thus ?thesis using val M_eq by simp
qed

text ‹Dual to @{thm[source] valid_reach_LE_pos0_ktm}: along any reachable
  trace from a valid initial configuration whose blank symbol differs
  from the left endmarker, every cell at a position ‹p ≠ 0› on any
  tape is not the left endmarker.  Proof: induction on the
  reachability relation.  Base: ‹init_config_ktm› places ‹le›
  only at position 0 of active tapes (input cells are in ‹Σ› hence
  ‹≠ le›; other active cells and all inactive cells are ‹bl› which
  by hypothesis ‹≠ le›).  Step: cells away from the head are
  preserved (substrate update is ‹(ts k)(n k := a k)›); at the head,
  the substrate's ‹δLE›-no-write rule says the write equals ‹le›
  only if the read did, which by IH is impossible since the read
  sits at the head position ‹n k› (and if ‹n k = p ≠ 0› the IH
  gives the read is not ‹le›; if ‹n k = 0› then ‹p ≠ n k› and the
  off-head case fires).›

lemma valid_reach_LE_only_pos0_ktm:
  fixes M :: "('q, 'a) ktm"
    and c :: "('a, 'q) ktc_config"
    and k :: nat
    and p :: nat
  assumes vM:        "valid_ktm M"
    and lu:          "le_unique M"
    and w:           "set w ⊆ Sigma_ktm M"
    and reach:       "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M))*"
    and p_ne_0:      "p ≠ 0"
    and bl_neq_le:   "bl_ktm M ≠ le_ktm M"
  shows "ktc_tape c k p ≠ le_ktm M"
proof -
  obtain Q Σ Γ bl le δ sM tt rr K where M_eq:
      "M = KTM Q Σ Γ bl le δ sM tt rr K"
    by (cases M)
  have le_eq:  "le_ktm M = le"  using M_eq by simp
  have bl_eq:  "bl_ktm M = bl"  using M_eq by simp
  have bl_ne_le: "bl ≠ le" using bl_neq_le le_eq bl_eq by simp
  have le_not_Sigma: "le ∉ Σ"
    using valid_ktm_LE_not_Sigma[OF vM] M_eq by simp
  have w_Sigma: "set w ⊆ Σ" using w M_eq by simp
  have main:
    "∀c'. (init_config_ktm M w, c') ∈ (ktm_step (delta_ktm M))*
            ⟶ ktc_tape c' k p ≠ le_ktm M"
  proof (intro allI impI)
    fix c'
    assume r: "(init_config_ktm M w, c') ∈ (ktm_step (delta_ktm M))*"
    show "ktc_tape c' k p ≠ le_ktm M"
      using r
    proof induction
      case base
      have tape_p_init:
          "ktc_tape (init_config_ktm M w) k p
             = (if k < K
                then (if p = 0 then le
                      else if k = 0 ∧ p ≤ length w then w ! (p - 1)
                      else bl)
                else bl)"
        unfolding M_eq init_config_ktm.simps by simp
      show ?case
      proof (cases "k = 0 ∧ p ≤ length w")
        case True
        have K_pos: "0 < K" using valid_ktm_k_pos[OF vM] M_eq by simp
        have kK: "k < K" using True K_pos by simp
        have p_ge_1: "p ≥ 1" using p_ne_0 by simp
        have idx_lt: "p - 1 < length w" using True p_ge_1 by linarith
        have in_w: "w ! (p - 1) ∈ set w"
          using idx_lt by (auto simp: set_conv_nth)
        with w_Sigma have "w ! (p - 1) ∈ Σ" by blast
        with le_not_Sigma have "w ! (p - 1) ≠ le" by blast
        thus ?thesis using tape_p_init True kK p_ne_0 le_eq by simp
      next
        case False
        have "ktc_tape (init_config_ktm M w) k p = bl"
          using tape_p_init False p_ne_0 by (cases "k < K") auto
        thus ?thesis using bl_ne_le le_eq by simp
      qed
    next
      case (step y z)
      have ne_y: "ktc_tape y k p ≠ le_ktm M" using step.IH .
      obtain qy ts n where y_eq: "y = KConfig qy ts n"
        by (cases y)
      from step.hyps(2) y_eq obtain q' a dr where
          z_eq: "z = KConfig q'
                       (λkk. (ts kk)(n kk := a kk))
                       (λkk. go_move (dr kk) (n kk))"
          and tr: "(qy, (λkk. ts kk (n kk)), q', a, dr) ∈ delta_ktm M"
        by (auto elim: ktm_step.cases)
      show ?case
      proof (cases "n k = p")
        case False
        have "ktc_tape z k p = ((ts k)(n k := a k)) p" using z_eq by simp
        also have "… = ts k p" using False by simp
        also have "… = ktc_tape y k p" using y_eq by simp
        finally have "ktc_tape z k p = ktc_tape y k p" .
        thus ?thesis using ne_y by simp
      next
        case True
        have read_at_p: "ts k (n k) = ktc_tape y k p"
          using y_eq True by simp
        have read_ne: "ts k (n k) ≠ le_ktm M"
          using ne_y read_at_p by simp
        have a_ne: "a k ≠ le_ktm M"
        proof
          assume a_le: "a k = le_ktm M"
          have "(λkk. ts kk (n kk)) k = le_ktm M"
            using valid_ktm_deltaLE_no_write[OF lu tr a_le] by simp
          hence "ts k (n k) = le_ktm M" by simp
          thus False using read_ne by simp
        qed
        have "ktc_tape z k p = ((ts k)(n k := a k)) p" using z_eq by simp
        also have "… = a k" using True by simp
        finally have "ktc_tape z k p = a k" .
        thus ?thesis using a_ne by simp
      qed
    qed
  qed
  show ?thesis using main reach by blast
qed


subsection ‹Step locality: non-head cells preserved, head moves by ‹≤› 1›

text ‹Two structural facts about ‹ktm_step› that fall directly out
  of the single rule's body ‹(ts k)(n k := a k)› and
  ‹go_move (move k) (n k)›: a single step modifies only the head
  cell on each tape, and the head displaces by at most one position
  per tape per step.  These are generic over ‹δ› and used by
  alphabet-enlargement / -reduction to argue that cells outside a
  bounded window are unchanged after ‹n› steps.›

lemma ktm_step_tape_off_head:
  assumes step: "(c, c') ∈ ktm_step δ"
    and ne:     "p ≠ ktc_pos c k"
  shows "ktc_tape c' k p = ktc_tape c k p"
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))"
    by (auto elim: ktm_step.cases)
  from ne c_eq have "p ≠ n k" by simp
  thus ?thesis by (simp add: c_eq c'_eq)
qed

lemma ktm_step_pos_displacement:
  assumes step: "(c, c') ∈ ktm_step δ"
  shows "ktc_pos c' k ≤ ktc_pos c k + 1
         ∧ ktc_pos c k ≤ ktc_pos c' k + 1"
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))"
    by (auto elim: ktm_step.cases)
  have pos: "ktc_pos c k = n k" by (simp add: c_eq)
  have pos': "ktc_pos c' k = go_move (dr k) (n k)" by (simp add: c'_eq)
  show ?thesis
    unfolding pos pos' by (cases "dr k") auto
qed

text ‹‹n›-step lift: after ‹n› steps, head displacement on each
  tape is at most ‹n›.›

lemma ktm_relpow_pos_displacement:
  assumes "(c, c') ∈ ktm_step δ ^^ n"
  shows "ktc_pos c' k ≤ ktc_pos c k + n
         ∧ ktc_pos c k ≤ ktc_pos c' k + n"
  using assms
proof (induction n arbitrary: c')
  case 0
  thus ?case by simp
next
  case (Suc n)
  from Suc.prems obtain c'' where
      ih: "(c, c'') ∈ ktm_step δ ^^ n"
    and step: "(c'', c') ∈ ktm_step δ"
    by (auto elim: relpow_Suc_E)
  have h1: "ktc_pos c'' k ≤ ktc_pos c k + n
            ∧ ktc_pos c k ≤ ktc_pos c'' k + n"
    using Suc.IH[OF ih] .
  have h2: "ktc_pos c' k ≤ ktc_pos c'' k + 1
            ∧ ktc_pos c'' k ≤ ktc_pos c' k + 1"
    using ktm_step_pos_displacement[OF step] .
  from h1 h2 show ?case by linarith
qed

text ‹‹n›-step lift: cells more than ‹n› away from the start head
  position are unchanged after ‹n› steps.›

lemma ktm_relpow_tape_off_window:
  assumes "(c, c') ∈ ktm_step δ ^^ n"
    and "p > ktc_pos c k + n ∨ p + n < ktc_pos c k"
  shows "ktc_tape c' k p = ktc_tape c k p"
  using assms
proof (induction n arbitrary: c')
  case 0
  thus ?case by simp
next
  case (Suc n)
  from Suc.prems(1) obtain c'' where
      ih: "(c, c'') ∈ ktm_step δ ^^ n"
    and step: "(c'', c') ∈ ktm_step δ"
    by (auto elim: relpow_Suc_E)
  have far: "p > ktc_pos c k + n ∨ p + n < ktc_pos c k"
    using Suc.prems(2) by linarith
  have eq_ih: "ktc_tape c'' k p = ktc_tape c k p"
    using Suc.IH[OF ih far] .
  have disp: "ktc_pos c'' k ≤ ktc_pos c k + n
              ∧ ktc_pos c k ≤ ktc_pos c'' k + n"
    using ktm_relpow_pos_displacement[OF ih] .
  have ne: "p ≠ ktc_pos c'' k"
    using Suc.prems(2) disp by linarith
  have eq_step: "ktc_tape c' k p = ktc_tape c'' k p"
    using ktm_step_tape_off_head[OF step ne] .
  show ?case using eq_step eq_ih by simp
qed


subsection ‹The left endmarker stays at cell 0›

text ‹Local LE-pinning: any step of a valid M from a config whose
  tape ‹k› already has ‹le_ktm M› at position 0 ends with a config
  whose tape ‹k› still has ‹le_ktm M› at position 0.  Standalone
  variant of ‹valid_step_ktm›'s position-0-= LE conjunct,
  stripped of the ‹valid_config_ktm› precondition: only the
  per-tape LE-at-0 fact is needed (not Q-membership or ‹Γ›-typing).
  Case-split on whether the head is at position 0: at-head fires
  ‹δLE› (read LE forces write LE); off-head uses
  ‹ktm_step_tape_off_head› directly.›

lemma ktm_step_LE_pos0_preserve:
  fixes M :: "('q, 'a) ktm"
  assumes vM:    "valid_ktm M"
    and step:    "(c, c') ∈ ktm_step (delta_ktm M)"
    and LE_at0:  "ktc_tape c k 0 = le_ktm M"
  shows "ktc_tape c' k 0 = le_ktm M"
proof (cases "ktc_pos c k = 0")
  case True
  from step obtain q ts n q' a dr where
      c_eq:  "c = KConfig q ts n"
    and c'_eq: "c' = KConfig q'
                       (λkk. (ts kk)(n kk := a kk))
                       (λkk. go_move (dr kk) (n kk))"
    and tr:    "(q, λkk. ts kk (n kk), q', a, dr) ∈ delta_ktm M"
    by (auto elim: ktm_step.cases)
  have nk_0: "n k = 0" using True c_eq by simp
  have ts_k_0_le: "ts k 0 = le_ktm M" using LE_at0 c_eq by simp
  have read_LE: "(λkk. ts kk (n kk)) k = le_ktm M"
    using ts_k_0_le nk_0 by simp
  have write_LE: "a k = le_ktm M"
    using valid_ktm_deltaLE[OF vM tr read_LE] by simp
  have "ktc_tape c' k 0 = ((ts k)(n k := a k)) 0"
    using c'_eq by simp
  also have "… = a k" using nk_0 by simp
  also have "… = le_ktm M" using write_LE .
  finally show ?thesis .
next
  case False
  have ne_0: "(0 :: nat) ≠ ktc_pos c k" using False by simp
  have unchanged: "ktc_tape c' k 0 = ktc_tape c k 0"
    using ktm_step_tape_off_head[OF step ne_0] .
  show ?thesis using unchanged LE_at0 by simp
qed

text ‹‹n›-step lift of @{thm[source] ktm_step_LE_pos0_preserve}: along
  any chain of M-steps, ‹le_ktm M› at position 0 is preserved
  on every tape.  Used in AE's LE-edge forward stage to derive
  ‹cM_k›'s position-0 = LE without recourse to reachability
  from init.›

lemma ktm_relpow_LE_pos0_preserve:
  fixes M :: "('q, 'a) ktm"
  assumes vM:    "valid_ktm M"
    and chain:   "(c, c') ∈ ktm_step (delta_ktm M) ^^ n"
    and LE_at0:  "ktc_tape c k 0 = le_ktm M"
  shows "ktc_tape c' k 0 = le_ktm M"
  using relpow_imp_rtrancl [OF chain]
  by (induction rule: rtrancl_induct)
     (auto intro: LE_at0 ktm_step_LE_pos0_preserve [OF vM])


subsection ‹Decomposing a step›

text ‹Packages ‹ktm_step.cases› with the post-state position +
  tape equations on each tape: a single ‹obtains› rule that
  yields all four useful facts (pre-state's state, post-state's
  state, the per-tape position equation ‹go_move (dr k) (n k)›,
  and the per-tape head-cell update).  Chain proofs in
  AE / AR / TR avoid re-doing the case-analysis at every
  per-substep position-trajectory step.›

lemma ktm_step_obtain_action:
  assumes step: "(c, c') ∈ ktm_step δ"
  obtains q q' a dr where
      "ktc_state c = q"
    and "ktc_state c' = q'"
    and "(q, λk. ktc_tape c k (ktc_pos c k), q', a, dr) ∈ δ"
    and "⋀kk. ktc_pos c' kk = go_move (dr kk) (ktc_pos c kk)"
    and "⋀kk p. p ≠ ktc_pos c kk
                  ⟹ ktc_tape c' kk p = ktc_tape c kk p"
    and "⋀kk. ktc_tape c' kk (ktc_pos c kk) = a kk"
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) ∈ δ"
    by (auto elim: ktm_step.cases)
  have st_c: "ktc_state c = q" using c_eq by simp
  have st_c': "ktc_state c' = q'" using c'_eq by simp
  have pos_c: "⋀kk. ktc_pos c kk = n kk" using c_eq by simp
  have pos_c': "⋀kk. ktc_pos c' kk = go_move (dr kk) (n kk)"
    using c'_eq by simp
  have tape_c: "⋀kk. ktc_tape c kk = ts kk" using c_eq by simp
  have tape_c': "⋀kk. ktc_tape c' kk = (ts kk)(n kk := a kk)"
    using c'_eq by simp
  have tr': "(q, λk. ktc_tape c k (ktc_pos c k), q', a, dr) ∈ δ"
    using tr c_eq by simp
  show thesis
  proof (rule that[OF st_c st_c' tr'])
    fix kk show "ktc_pos c' kk = go_move (dr kk) (ktc_pos c kk)"
      using pos_c' pos_c by simp
  next
    fix kk p assume "p ≠ ktc_pos c kk"
    thus "ktc_tape c' kk p = ktc_tape c kk p"
      using tape_c' tape_c pos_c by simp
  next
    fix kk show "ktc_tape c' kk (ktc_pos c kk) = a kk"
      using tape_c' pos_c by simp
  qed
qed


subsection ‹Transitions that write nothing›

text ‹For a transition relation in which every tuple's
  read-component equals its write-component, a single step
  preserves the entire tape function (the substrate update
  ‹f(x := f x)› is the identity).  Used by the alphabet-
  enlargement chain proof for the read-only buffer-loading
  substeps SS1‹→›SS2, SS2‹→›SS3, SS3‹→›SS4, SS4‹→›SS5.›

lemma ktm_step_no_write_tape:
  assumes step: "(c, c') ∈ ktm_step δ"
    and no_write: "⋀q a q' a' d. (q, a, q', a', d) ∈ δ ⟹ a' = a"
  shows "ktc_tape c' = ktc_tape c"
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) ∈ δ"
    by (auto elim: ktm_step.cases)
  from no_write[OF tr] have "a = (λk. ts k (n k))" by simp
  hence "(λk. (ts k)(n k := a k)) = ts" by auto
  thus ?thesis by (simp add: c_eq c'_eq)
qed


subsection ‹Read-only steps and head walks›

text ‹The introduction direction of the same fact.  A tuple that writes back
  what it read leaves the tape function as it was, so its step is determined by
  the state change and the moves alone.  Repeated in one state with one move
  vector, it is a ∗‹walk›: the commonest subroutine of a multi-pass machine,
  which returns a head to its origin, skips a field, or seeks a marker.›

lemma ktm_step_read_only:
  assumes "(q, λi. ts i (pos i), q', λi. ts i (pos i), mv) ∈ δ"
  shows "(KConfig q ts pos, KConfig q' ts (λi. go_move (mv i) (pos i)))
           ∈ ktm_step δ"
proof -
  have "(KConfig q ts pos,
         KConfig q' (λi. (ts i)(pos i := ts i (pos i)))
                    (λi. go_move (mv i) (pos i))) ∈ ktm_step δ"
    by (rule ktm_step.step) (rule assms)
  then show ?thesis by simp
qed

text ‹The walk in its general form: the head positions after ‹m› steps are
  ‹pos m›, and every head moves by ‹mv› at every step.  Several heads may
  move at once, in different directions.›

lemma ktm_read_only_run:
  assumes tr: "⋀m. m < n ⟹
                 (q, λi. ts i (pos m i), q, λi. ts i (pos m i), mv) ∈ δ"
      and mv: "⋀m. m < n ⟹ pos (Suc m) = (λi. go_move (mv i) (pos m i))"
  shows "(KConfig q ts (pos 0), KConfig q ts (pos n)) ∈ ktm_step δ ^^ n"
  using tr mv
proof (induction n)
  case 0
  show ?case by simp
next
  case (Suc n)
  have run: "(KConfig q ts (pos 0), KConfig q ts (pos n)) ∈ ktm_step δ ^^ n"
    by (rule Suc.IH) (simp_all add: Suc.prems)
  have "(KConfig q ts (pos n), KConfig q ts (λi. go_move (mv i) (pos n i)))
          ∈ ktm_step δ"
    by (rule ktm_step_read_only) (simp add: Suc.prems)
  then have "(KConfig q ts (pos n), KConfig q ts (pos (Suc n))) ∈ ktm_step δ"
    by (simp add: Suc.prems)
  with run show ?case by (rule relpow_Suc_I)
qed

text ‹The usual case moves one head.›

definition move_one :: "nat ⇒ move ⇒ (nat ⇒ move)" where
  "move_one tp d = (λj. if j = tp then d else MoveN)"

lemma move_one_same [simp]: "move_one tp d tp = d"
  by (simp add: move_one_def)

lemma move_one_other [simp]: "j ≠ tp ⟹ move_one tp d j = MoveN"
  by (simp add: move_one_def)

text ‹Two heads moving, possibly in different directions.  The first tape
  wins where the two coincide.›

definition move_pair :: "nat ⇒ move ⇒ nat ⇒ move ⇒ (nat ⇒ move)" where
  "move_pair tp1 d1 tp2 d2 =
     (λj. if j = tp1 then d1 else if j = tp2 then d2 else MoveN)"

lemma move_pair_fst [simp]: "move_pair tp1 d1 tp2 d2 tp1 = d1"
  by (simp add: move_pair_def)

lemma move_pair_snd [simp]:
  "tp2 ≠ tp1 ⟹ move_pair tp1 d1 tp2 d2 tp2 = d2"
  by (simp add: move_pair_def)

lemma move_pair_other [simp]:
  "j ≠ tp1 ⟹ j ≠ tp2 ⟹ move_pair tp1 d1 tp2 d2 j = MoveN"
  by (simp add: move_pair_def)

text ‹On machines over typ‹nat› symbols with blank ‹0›, the read vector of
  a one-tape arc: tape ‹0› reads ‹x›, and every other index reads the blank.›

definition one_tape_read :: "nat ⇒ nat ⇒ nat" where
  "one_tape_read x = (λj. if j = 0 then x else 0)"

lemma one_tape_read_inj: "one_tape_read x = one_tape_read y ⟹ x = y"
  by (drule fun_cong [of _ _ 0]) (simp add: one_tape_read_def)

text ‹A one-head walk, leftwards from cell ‹P + n› to cell ‹P› and rightwards
  from ‹P› to ‹P + n›.  The hypothesis names each cell the head reads, so a
  caller states it as a property of a stretch of tape (``every cell here holds
  an input symbol'').  A walk that stops on a cell it recognises adds one exit
  step, ‹ktm_step_read_only› again but into another state.›

lemma ktm_walk_left:
  assumes tr: "⋀m. P < m ⟹ m ≤ P + n ⟹
                 (q, λi. ts i ((pos(tp := m)) i), q, λi. ts i ((pos(tp := m)) i),
                  move_one tp MoveL) ∈ δ"
  shows "(KConfig q ts (pos(tp := P + n)), KConfig q ts (pos(tp := P)))
           ∈ ktm_step δ ^^ n"
proof -
  have "(KConfig q ts (pos(tp := P + n - 0)), KConfig q ts (pos(tp := P + n - n)))
          ∈ ktm_step δ ^^ n"
  proof (rule ktm_read_only_run [where pos = "λm. pos(tp := P + n - m)"
                                  and mv = "move_one tp MoveL"])
    fix m assume "m < n"
    then show "(q, λi. ts i ((pos(tp := P + n - m)) i), q,
                λi. ts i ((pos(tp := P + n - m)) i), move_one tp MoveL) ∈ δ"
      using tr [of "P + n - m"] by simp
  next
    fix m assume "m < n"
    then show "pos(tp := P + n - Suc m)
                 = (λi. go_move (move_one tp MoveL i) ((pos(tp := P + n - m)) i))"
      by (simp add: fun_eq_iff move_one_def)
  qed
  then show ?thesis by simp
qed

lemma ktm_walk_right:
  assumes tr: "⋀m. P ≤ m ⟹ m < P + n ⟹
                 (q, λi. ts i ((pos(tp := m)) i), q, λi. ts i ((pos(tp := m)) i),
                  move_one tp MoveR) ∈ δ"
  shows "(KConfig q ts (pos(tp := P)), KConfig q ts (pos(tp := P + n)))
           ∈ ktm_step δ ^^ n"
proof -
  have "(KConfig q ts (pos(tp := P + 0)), KConfig q ts (pos(tp := P + n)))
          ∈ ktm_step δ ^^ n"
  proof (rule ktm_read_only_run [where pos = "λm. pos(tp := P + m)"
                                  and mv = "move_one tp MoveR"])
    fix m assume "m < n"
    then show "(q, λi. ts i ((pos(tp := P + m)) i), q,
                λi. ts i ((pos(tp := P + m)) i), move_one tp MoveR) ∈ δ"
      using tr [of "P + m"] by simp
  next
    fix m assume "m < n"
    then show "pos(tp := P + Suc m)
                 = (λi. go_move (move_one tp MoveR i) ((pos(tp := P + m)) i))"
      by (simp add: fun_eq_iff move_one_def)
  qed
  then show ?thesis by simp
qed


subsection ‹What a composite needs from the step relation›

text ‹Facts about const‹ktm_step› that belong to the substrate rather
  than to any construction.

  ❙‹The union laws are what make a turn-taking composite cheap.›
  const‹ktm_step› is defined by a single introduction rule whose only premise
  is that one tuple lies in ‹δ›, and nothing in the rule quantifies over ‹δ›
  --- so the step relation of a union is the union of the step relations, on
  the nose.  A composite whose transition relation is a union of arms therefore
  splits a step into "which arm took it" by rewriting, and each arm can then be
  analysed on its own.  There is no corresponding law for a ∗‹lockstep›
  product, whose transition relation is a join of the two factors' sets rather
  than a union; that asymmetry, not the running time, is why a clocked
  composite takes turns.

  ‹ktm_step_state_rel› is the state-side counterpart of the tape-side
  ‹ktm_step_frozen_tape› (‹Multitape_Run_Facts›), and is much the weaker statement of the two:
  the state is carried through a step untouched, so any relation holding
  between the two ends of every tuple holds across the step.  It is general in
  ‹R› because the composite needs two instances of it --- one frozen component
  (the factor that is not moving keeps its state) and one that changes (the
  turn flips).  The tape lemma cannot be stated this way, because there the
  tuple's read component has to be matched against what is actually under the
  head.›

lemma ktm_step_mono:
  assumes "δ1 ⊆ δ2"
  shows "ktm_step δ1 ⊆ ktm_step δ2"
  using assms by (auto elim!: ktm_step.cases intro: ktm_step.step)

lemma ktm_step_Un:
  "ktm_step (δ1 ∪ δ2) = ktm_step δ1 ∪ ktm_step δ2"
  by (auto elim!: ktm_step.cases intro: ktm_step.step)

lemma ktm_step_UN:
  "ktm_step (⋃i∈I. δ i) = (⋃i∈I. ktm_step (δ i))"
  by (auto elim!: ktm_step.cases intro: ktm_step.step)

text ‹‹ktm_step_mono› needs only the tuples the step can use, and those
  are the ones out of the configuration's state.  So a step of a union whose
  source state is known lies in the part of the union that state can fire:
  the routing fact for the tuples, ‹sub›, lifts to the step relation
  without the client taking the step apart.

  ❙‹Apply it by ⬚‹rule›, not ⬚‹OF›.›  Given the routing fact
  by ⬚‹OF›, ‹P q› is matched against a condition on a ∗‹schematic›
  source state, which is not a pattern, and ⬚‹OF› reports multiple
  unifiers.  Closing ‹sub› by ⬚‹erule› with the routing fact binds that
  state to ‹q› first, after which ‹P› is fixed by pattern unification and
  the state hypothesis closes the last goal.›

lemma ktm_step_restrict_src:
  assumes step: "(C, C') ∈ ktm_step δ"
      and sub: "⋀q a q' a' d. (q, a, q', a', d) ∈ δ ⟹ P q
                  ⟹ (q, a, q', a', d) ∈ δ'"
      and src: "P (ktc_state C)"
  shows "(C, C') ∈ ktm_step δ'"
proof -
  from step obtain q ts n q' a d where
      C: "C = KConfig q ts n"
    and C': "C' = KConfig q' (λk. (ts k)(n k := a k)) (λk. go_move (d k) (n k))"
    and t: "(q, λk. ts k (n k), q', a, d) ∈ δ"
    by (auto elim: ktm_step.cases)
  from src C have "P q" by simp
  with t have "(q, λk. ts k (n k), q', a, d) ∈ δ'" by (rule sub)
  then show ?thesis
    unfolding C C' by (rule ktm_step.step [where ts = ts and n = n])
qed

text ‹The run-level form of ‹ktm_step_mono›: a run of
  one arm of a composite is a run of the composite.›

lemma ktm_run_mono:
  assumes sub: "δ1 ⊆ δ2"
      and run: "(c, c') ∈ (ktm_step δ1) ^^ n"
  shows "(c, c') ∈ (ktm_step δ2) ^^ n"
  using relpow_subset_mono [OF ktm_step_mono [OF sub]] run ..

text ‹Both ends of a step as one tuple, and nothing else.  ‹ktm_step.cases›
  exposes the whole anatomy --- tape frame, read, write, directions --- and a
  ∗‹routing› argument wants none of it: which part of a union a step came from
  is settled by the source state alone.  This is the projection that says so.

  ❙‹The read component stays existential.›  It is determined ---
  it is term‹λk. ktc_tape C k (ktc_pos C k)› --- but naming it would put the
  tape frame back into every consumer, which is the thing being avoided.  A
  consumer that needs the read still has ‹ktm_step.cases›.›

lemma ktm_step_states:
  assumes step: "(C, C') ∈ ktm_step δ"
  obtains a a' d where "(ktc_state C, a, ktc_state C', a', 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) ∈ δ"
    by (auto elim: ktm_step.cases)
  have "(ktc_state C, λk. ts k (n k), ktc_state C', a, dr) ∈ δ"
    using tr by (simp add: c_eq c'_eq)
  then show thesis by (rule that)
qed

lemma ktm_step_state_rel:
  assumes step: "(c, c') ∈ ktm_step δ"
    and rel: "∀q a q' a' d. (q, a, q', a', d) ∈ δ ⟶ R q q'"
  shows "R (ktc_state c) (ktc_state c')"
proof -
  from step obtain a a' d where "(ktc_state c, a, ktc_state c', a', d) ∈ δ"
    by (rule ktm_step_states)
  with rel show ?thesis by blast
qed

text ‹❙‹The halting states are dead ends, so a configuration that can still
  move is not in one.›  const‹valid_ktm› restricts ‹δ›'s source component to
  term‹Q_ktm M - {t_ktm M, r_ktm M}›, which is usually read as a well-formedness
  condition and is also a ∗‹tool›: it converts "there is a next step" into
  "the state is neither halting state" (‹ktm_step_src›), and that is the only
  way to learn anything about the ∗‹intermediate› configurations of a run
  whose endpoints are all that is stated.

  The run form below is the one a race wants.  A run of ‹n› steps that ends
  accepting says nothing directly about step ‹k < n›; but the remainder is
  non-empty, so a step leaves that configuration, so it has not halted.  This
  is what lets a caller with only "the machine halts in exactly ‹g n›
  steps" conclude that it is ∗‹still running› at any earlier time.›

lemma ktm_relpow_not_halted:
  assumes vM: "valid_ktm M"
      and run: "(C, C') ∈ (ktm_step (delta_ktm M)) ^^ n" and k: "k < n"
  obtains D
    where "(C, D) ∈ (ktm_step (delta_ktm M)) ^^ k"
      and "ktc_state D ≠ t_ktm M" and "ktc_state D ≠ r_ktm M"
proof -
  ― ‹the remainder is named by arithmetic and not by ‹less_iff_Suc_add›:
      handing ⬚‹blast› an iff whose right-hand side is an existential over the
      same variable it is solving for does not terminate›
  obtain c where n: "n = k + Suc c"
  proof -
    from k have "n = k + Suc (n - Suc k)" by simp
    then show thesis by (rule that)
  qed
  from run [unfolded n relpow_add] obtain D
    where CD: "(C, D) ∈ (ktm_step (delta_ktm M)) ^^ k"
      and rest: "(D, C') ∈ (ktm_step (delta_ktm M)) ^^ Suc c" by auto
  ― ‹the ∗‹first› step of the remainder, which is why the decomposition is
      named: ⬚‹auto›'s default peels the last one, and the last step is the one
      whose source says nothing about ‹D››
  obtain E where "(D, E) ∈ ktm_step (delta_ktm M)"
    using relpow_Suc_D2 [OF rest] by blast
  from CD ktm_step_src_neq_t [OF vM this] ktm_step_src_neq_r [OF vM this]
  show thesis by (rule that)
qed

text ‹Single-valuedness, transported from the tuples to the configurations.
  const‹det_ktm› is stated of a whole machine, but a composite is
  deterministic only in ∗‹parts› --- its setup phase is forced while its arms
  are not --- so the useful form is generic in ‹δ› and the machine-level
  reading is the corollary.  A typical use is a converse walk: it peels a
  step, instantiates a forward lemma about the same configuration, and pins
  the two together, so the transformed tape content is never inverted.

  The read component is what carries the argument.  Two steps out of one
  configuration read the same frame term‹λk. ts k (n k)›, so the tuple
  hypothesis applies at a common ‹a› and the write and the direction come
  back equal --- whereupon the two successors are equal as functions of the
  ∗‹same› ‹ts› and ‹n›.

  The hypothesis is asked for ∗‹at the state the configuration is in›, not at
  every state, because a phase-wise deterministic composite is exactly the case
  this is for: the argument never leaves term‹ktc_state C›, so demanding more
  would be demanding what the consumer cannot supply.  The uniform reading is
  ‹ktm_step_functional› below, and ‹det_ktm_step› states it for a
  deterministic machine.›

lemma ktm_step_det_at:
  assumes det: "⋀a p1 b1 d1 p2 b2 d2.
                  (ktc_state C, a, p1, b1, d1) ∈ δ
                    ⟹ (ktc_state C, a, p2, b2, d2) ∈ δ
                    ⟹ (p1, b1, d1) = (p2, b2, d2)"
      and s1: "(C, C1) ∈ ktm_step δ"
      and s2: "(C, C2) ∈ ktm_step δ"
  shows "C1 = C2"
proof -
  from s1 obtain q ts n q1 a1 d1 where
      C: "C = KConfig q ts n"
    and C1: "C1 = KConfig q1 (λk. (ts k)(n k := a1 k))
                            (λk. go_move (d1 k) (n k))"
    and t1: "(q, λk. ts k (n k), q1, a1, d1) ∈ δ"
    by (auto elim: ktm_step.cases)
  from s2 obtain q' ts' n' q2 a2 d2 where
      C': "C = KConfig q' ts' n'"
    and C2: "C2 = KConfig q2 (λk. (ts' k)(n' k := a2 k))
                            (λk. go_move (d2 k) (n' k))"
    and t2: "(q', λk. ts' k (n' k), q2, a2, d2) ∈ δ"
    by (auto elim: ktm_step.cases)
  have "KConfig q ts n = KConfig q' ts' n'" using C C' by simp
  then have qe: "q' = q" and te: "ts' = ts" and ne: "n' = n" by auto
  from t2 [unfolded qe te ne] have t2': "(q, λk. ts k (n k), q2, a2, d2) ∈ δ" .
  from t1 have u1: "(ktc_state C, λk. ts k (n k), q1, a1, d1) ∈ δ"
    by (simp add: C)
  from t2' have u2: "(ktc_state C, λk. ts k (n k), q2, a2, d2) ∈ δ"
    by (simp add: C)
  have "(q1, a1, d1) = (q2, a2, d2)" by (rule det [OF u1 u2])
  then show ?thesis by (simp add: C1 C2 te ne)
qed

lemma det_ktm_step:
  assumes det: "det_ktm M"
      and s1: "(C, C1) ∈ ktm_step (delta_ktm M)"
      and s2: "(C, C2) ∈ ktm_step (delta_ktm M)"
  shows "C1 = C2"
proof (rule ktm_step_det_at [OF _ s1 s2])
  fix a p1 b1 d1 p2 b2 d2
  assume "(ktc_state C, a, p1, b1, d1) ∈ delta_ktm M"
     and "(ktc_state C, a, p2, b2, d2) ∈ delta_ktm M"
  with det show "(p1, b1, d1) = (p2, b2, d2)" unfolding det_ktm_def by blast
qed

text ‹The same fact once more in the library's vocabulary, which is what
  buys the run-level statement for nothing: ⬚‹single_valued_relpow› lifts
  single-valuedness along ‹^^ n›, so a deterministic machine's runs of a
  ∗‹given› length are unique without an induction here.  The step-level and
  run-level readings are wanted in different places --- the step level pins a
  converse walk, the run level pins an alarm --- so both names earn their
  keep.›

lemma det_ktm_single_valued:
  assumes det: "det_ktm M"
  shows "single_valued (ktm_step (delta_ktm M))"
  by (blast intro: single_valuedI det_ktm_step [OF det])

lemma det_ktm_relpow_unique:
  assumes det: "det_ktm M"
      and r1: "(C, C1) ∈ (ktm_step (delta_ktm M)) ^^ n"
      and r2: "(C, C2) ∈ (ktm_step (delta_ktm M)) ^^ n"
  shows "C1 = C2"
  by (rule single_valuedD
        [OF single_valued_relpow [OF det_ktm_single_valued [OF det]] r1 r2])

lemma det_ktm_dead_end_no_longer_run:
  assumes det: "det_ktm M"
      and stopped: "(initial, final) ∈ (ktm_step (delta_ktm M)) ^^ amount"
      and dead_end: "∀following. (final, following) ∉ ktm_step (delta_ktm M)"
      and longer_run: "(initial, other) ∈ (ktm_step (delta_ktm M)) ^^ longer"
      and longer: "amount < longer"
  shows False
proof -
  have "amount = longer ∧ final = other"
    by (rule relpow_halted_le [where R = UNIV and H = "{final}",
                               OF _ _ _ _ stopped _ longer_run])
       (use dead_end longer det_ktm_step [OF det] in auto)
  with longer show False by simp
qed


subsection ‹Step determinism and acceptance monotonicity›

text ‹Two general facts promoted from the finite-control layer: a step of
  a functional transition relation is deterministic (a configuration has at
  most one successor), which is ‹ktm_step_det_at› with the hypothesis asked
  at every state, and weak time-bounded acceptance is monotone in the time
  budget.›

lemma ktm_step_functional:
  assumes fdet: "∀q a p1 b1 d1 p2 b2 d2.
      (q, a, p1, b1, d1) ∈ δ ⟶ (q, a, p2, b2, d2) ∈ δ
        ⟶ (p1, b1, d1) = (p2, b2, d2)"
    and step1: "(c, c1) ∈ ktm_step δ"
    and step2: "(c, c2) ∈ ktm_step δ"
  shows "c1 = c2"
  using fdet by (blast intro: ktm_step_det_at [OF _ step1 step2])

text ‹Weak time-bounded acceptance is monotone in the time budget.›

lemma accepts_in_time_ktm_mono:
  "accepts_in_time_ktm M w t ⟹ t ≤ t' ⟹ accepts_in_time_ktm M w t'"
  unfolding accepts_in_time_ktm_def by (meson order_trans)


subsection ‹Reaching a given state within a time bound›

text ‹Bounded acceptance names the accept state.  A simulation argument
  usually never uses which halting state a run ends in, and a client that
  bounds rejection as well as acceptance needs the same statement for the
  reject state; so the bound is stated once for an arbitrary state, and
  acceptance is its instance at @{term "t_ktm M"}.›

definition reaches_state_in_time_ktm ::
  "('q, 'a) ktm ⇒ 'a list ⇒ 'q ⇒ nat ⇒ bool" where
  "reaches_state_in_time_ktm M w q T ⟷
     (∃n c. n ≤ T
       ∧ (init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n
       ∧ ktc_state c = q)"

lemma reaches_state_in_time_ktmI:
  assumes "n ≤ T"
      and "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n"
      and "ktc_state c = q"
  shows "reaches_state_in_time_ktm M w q T"
  using assms unfolding reaches_state_in_time_ktm_def by blast

lemma reaches_state_in_time_ktmE:
  assumes "reaches_state_in_time_ktm M w q T"
  obtains n c where "n ≤ T"
    and "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n"
    and "ktc_state c = q"
  using assms unfolding reaches_state_in_time_ktm_def by blast

lemma reaches_state_in_time_ktm_mono:
  assumes "reaches_state_in_time_ktm M w q T" and "T ≤ T'"
  shows "reaches_state_in_time_ktm M w q T'"
proof -
  from assms(1) obtain n c where n: "n ≤ T"
    and run: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n"
    and state: "ktc_state c = q"
    by (rule reaches_state_in_time_ktmE)
  from order_trans [OF n assms(2)] run state show ?thesis
    by (rule reaches_state_in_time_ktmI)
qed

lemma accepts_in_time_ktm_iff_reaches:
  "accepts_in_time_ktm M w T
     ⟷ reaches_state_in_time_ktm M w (t_ktm M) T"
  unfolding accepts_in_time_ktm_def reaches_state_in_time_ktm_def by blast

end