Theory Multitape_Clock_Product

theory Multitape_Clock_Product
  imports Multitape_Clock_Interface Multitape_Embedding Multitape_Relabelling
begin

section ‹A machine paired with an exact alarm clock›

text ‹The product keeps a machine ‹N› and a clock ‹D› on disjoint tapes.
  It writes the unary input for the clock, then alternates their steps.
  A step of ‹N› into its accepting state reaches CAcc, and one into its
  rejecting state reaches CRej; a step of the clock into either terminal state
  reaches CRej.  So the product stops as soon as either factor does: the alarm
  bounds every path, accepting or not.  Each factor's part of the transition
  relation is called its ∗‹arm›.  Both arms may step into CRej, which is
  why ‹arms_alternate› lets a step into a final state carry either turn
  flag.  Nothing here asks ‹N› to be deterministic, so the product serves
  nondeterministic and deterministic machines alike.›

datatype clock_state =
    CWalk | CBack | CRun nat nat bool | CAcc | CRej


fun cturn :: "clock_state ⇒ bool" where
  "cturn (CRun q p b) = b"
| "cturn CAcc = False"
| "cturn CWalk = True"
| "cturn CBack = True"
| "cturn CRej = True"


definition clock_tapes :: "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ nat" where
  "clock_tapes N D = k_ktm N + k_ktm D"

definition clock_Gamma ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ nat ⇒ nat set" where
  "clock_Gamma N D one = insert one (Γ_ktm N ∪ Γ_ktm D)"

definition clock_Q ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ clock_state set" where
  "clock_Q N D =
     {CWalk, CBack, CAcc, CRej}
       ∪ {CRun q p b | q p b. q ∈ Q_ktm N ∧ p ∈ Q_ktm D}"

definition clock_ctx ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ nat ⇒ (nat ⇒ nat) set" where
  "clock_ctx N D one =
     free_context (clock_Gamma N D one) (bl_ktm N) (clock_tapes N D)"


subsection ‹Each factor's transitions in the product›


definition arm_N ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ nat
     ⇒ (clock_state × (nat ⇒ nat) × clock_state × (nat ⇒ nat)
          × (nat ⇒ move)) set" where
  "arm_N N D one =
     (⋃p ∈ Q_ktm D.
        tag_delta (λq. CRun q p True)
                  (λq'. if q' = t_ktm N then CAcc else if q' = r_ktm N then CRej else CRun q' p False)
                  (embed_delta 0 (k_ktm N) (clock_tapes N D)
                     (clock_Gamma N D one) (bl_ktm N) (delta_ktm N)))"

definition arm_D ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ nat
     ⇒ (clock_state × (nat ⇒ nat) × clock_state × (nat ⇒ nat)
          × (nat ⇒ move)) set" where
  "arm_D N D one =
     (⋃q ∈ Q_ktm N.
        tag_delta (λp. CRun q p False)
                  (λp'. if p' = t_ktm D ∨ p' = r_ktm D then CRej
                        else CRun q p' True)
                  (embed_delta (k_ktm N) (k_ktm D) (clock_tapes N D)
                     (clock_Gamma N D one) (bl_ktm N) (delta_ktm D)))"


subsection ‹The setup phase›


definition clock_start_state ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ clock_state" where
  "clock_start_state N D =
     (if s_ktm N = t_ktm N then CAcc
      else if s_ktm N = r_ktm N then CRej
      else if s_ktm D = t_ktm D ∨ s_ktm D = r_ktm D then CRej
      else CRun (s_ktm N) (s_ktm D) True)"

text ‹The last setup step dispatches terminal initial states without an
  extra transition.  The contestant has priority over the alarm, just as a
  contestant step precedes the corresponding alarm step during alternation.
  Thus even a zero-step decision is retained when the alarm is terminal.›

definition move_two :: "nat ⇒ move ⇒ (nat ⇒ move)" where
  "move_two m e = (λj. if j = 0 ∨ j = m then e else MoveN)"

definition setup_delta ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ nat
     ⇒ (clock_state × (nat ⇒ nat) × clock_state × (nat ⇒ nat)
          × (nat ⇒ move)) set" where
  "setup_delta N D one =
       {(CWalk, a, CWalk, a, move_two (k_ktm N) MoveR)
          | a. a ∈ clock_ctx N D one ∧ a 0 ≠ bl_ktm N}
     ∪ {(CWalk, a, CBack, a, move_two (k_ktm N) MoveL)
          | a. a ∈ clock_ctx N D one ∧ a 0 = bl_ktm N
               ∧ a (k_ktm N) ≠ le_ktm N}
     ∪ {(CBack, a, CBack, a(k_ktm N := one), move_two (k_ktm N) MoveL)
          | a. a ∈ clock_ctx N D one ∧ a 0 ≠ le_ktm N
               ∧ a (k_ktm N) ≠ le_ktm N}
     ∪ {(CBack, a, clock_start_state N D, a, λ_. MoveN)
          | a. a ∈ clock_ctx N D one ∧ a 0 = le_ktm N}"


subsection ‹The composite machine›


definition clock_product ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ nat ⇒ (clock_state, nat) ktm" where
  "clock_product N D one =
     KTM (clock_Q N D) (Sigma_ktm N) (clock_Gamma N D one)
          (bl_ktm N) (le_ktm N)
          (setup_delta N D one ∪ arm_N N D one ∪ arm_D N D one)
          CWalk CAcc CRej (clock_tapes N D)"

lemma clock_product_simps [simp]:
  "Q_ktm (clock_product N D one) = clock_Q N D"
  "Sigma_ktm (clock_product N D one) = Sigma_ktm N"
  "Γ_ktm (clock_product N D one) = clock_Gamma N D one"
  "bl_ktm (clock_product N D one) = bl_ktm N"
  "le_ktm (clock_product N D one) = le_ktm N"
  "delta_ktm (clock_product N D one)
     = setup_delta N D one ∪ arm_N N D one ∪ arm_D N D one"
  "s_ktm (clock_product N D one) = CWalk"
  "t_ktm (clock_product N D one) = CAcc"
  "r_ktm (clock_product N D one) = CRej"
  "k_ktm (clock_product N D one) = clock_tapes N D"
  by (simp_all add: clock_product_def)


subsection ‹Validity›


definition clock_ok ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ nat
     ⇒ clock_state ⇒ (nat ⇒ nat) ⇒ clock_state ⇒ (nat ⇒ nat)
     ⇒ (nat ⇒ move) ⇒ bool" where
  "clock_ok N D one Q A Q' A' E ⟷
     Q ∈ clock_Q N D - {CAcc, CRej} ∧ Q' ∈ clock_Q N D
     ∧ (∀j. A j ∈ clock_Gamma N D one)
     ∧ (∀j. A' j ∈ clock_Gamma N D one)
     ∧ (∀j. A j = le_ktm N ⟶ A' j = le_ktm N ∧ E j ∈ {MoveN, MoveR})
     ∧ (∀j ≥ clock_tapes N D.
           A j = bl_ktm N ∧ A' j = bl_ktm N ∧ E j = MoveN)"


lemma arm_N_ok:
  assumes vN: "valid_ktm N"
      and tr: "(Q, A, Q', A', E) ∈ arm_N N D one"
  shows "clock_ok N D one Q A Q' A' E"
proof -
  from tr obtain p where p: "p ∈ Q_ktm D"
    and tr': "(Q, A, Q', A', E)
                ∈ tag_delta (λq. CRun q p True)
                     (λq'. if q' = t_ktm N then CAcc else if q' = r_ktm N then CRej else CRun q' p False)
                     (embed_delta 0 (k_ktm N) (clock_tapes N D)
                        (clock_Gamma N D one) (bl_ktm N) (delta_ktm N))"
    by (auto simp: arm_N_def)
  from tr' obtain q a q' a' d b
    where trN: "(q, a, q', a', d) ∈ delta_ktm N"
      and b: "b ∈ free_context (clock_Gamma N D one) (bl_ktm N)
                     (clock_tapes N D)"
      and Q: "Q = CRun q p True"
      and Q': "Q' = (if q' = t_ktm N then CAcc else if q' = r_ktm N then CRej else CRun q' p False)"
      and Aeq: "A = (λj. if 0 ≤ j ∧ j < 0 + k_ktm N then a (j - 0) else b j)"
      and A'eq: "A' = (λj. if 0 ≤ j ∧ j < 0 + k_ktm N then a' (j - 0) else b j)"
      and Eeq: "E = (λj. if 0 ≤ j ∧ j < 0 + k_ktm N then d (j - 0) else MoveN)"
    by (rule arm_source)
  have Aj: "A j = (if j < k_ktm N then a j else b j)" for j by (simp add: Aeq)
  have A'j: "A' j = (if j < k_ktm N then a' j else b j)" for j by (simp add: A'eq)
  have Ej: "E j = (if j < k_ktm N then d j else MoveN)" for j by (simp add: Eeq)

  from valid_ktm_delta_set [OF vN] trN
  have qN: "q ∈ Q_ktm N - {t_ktm N, r_ktm N}" and q'N: "q' ∈ Q_ktm N"
    and aG: "∀j. a j ∈ Γ_ktm N" and a'G: "∀j. a' j ∈ Γ_ktm N"
    by (auto simp: Pi_iff)
  from b have bG: "∀j. b j ∈ clock_Gamma N D one"
    and bbl: "∀j ≥ clock_tapes N D. b j = bl_ktm N"
    by (auto simp: free_context_def)
  have kle: "k_ktm N ≤ clock_tapes N D" by (simp add: clock_tapes_def)

  have "Q ∈ clock_Q N D - {CAcc, CRej}"
    using Q qN p by (auto simp: clock_Q_def)
  moreover have "Q' ∈ clock_Q N D"
    using Q' q'N p by (auto simp: clock_Q_def)
  moreover have "∀j. A j ∈ clock_Gamma N D one"
    using aG bG by (auto simp: Aj clock_Gamma_def)
  moreover have "∀j. A' j ∈ clock_Gamma N D one"
    using a'G bG by (auto simp: A'j clock_Gamma_def)
  moreover
  have "∀j. A j = le_ktm N ⟶ A' j = le_ktm N ∧ E j ∈ {MoveN, MoveR}"
    using valid_ktm_deltaLE [OF vN trN] by (auto simp: Aj A'j Ej)
  moreover
  have "∀j ≥ clock_tapes N D. A j = bl_ktm N ∧ A' j = bl_ktm N ∧ E j = MoveN"
    using bbl kle by (auto simp: Aj A'j Ej)
  ultimately show ?thesis by (simp add: clock_ok_def)
qed



lemma arm_D_ok:
  assumes vD: "valid_ktm D"
      and blD: "bl_ktm D = bl_ktm N"
      and leD: "le_ktm D = le_ktm N"
      and tr: "(Q, A, Q', A', E) ∈ arm_D N D one"
  shows "clock_ok N D one Q A Q' A' E"
proof -
  from tr obtain q where q: "q ∈ Q_ktm N"
    and tr': "(Q, A, Q', A', E)
                ∈ tag_delta (λp. CRun q p False)
                     (λp'. if p' = t_ktm D ∨ p' = r_ktm D then CRej
                           else CRun q p' True)
                     (embed_delta (k_ktm N) (k_ktm D) (clock_tapes N D)
                        (clock_Gamma N D one) (bl_ktm N) (delta_ktm D))"
    by (auto simp: arm_D_def)
  from tr' obtain p a p' a' d b
    where trD: "(p, a, p', a', d) ∈ delta_ktm D"
      and b: "b ∈ free_context (clock_Gamma N D one) (bl_ktm N)
                     (clock_tapes N D)"
      and Q: "Q = CRun q p False"
      and Q': "Q' = (if p' = t_ktm D ∨ p' = r_ktm D then CRej
                     else CRun q p' True)"
      and Aeq: "A = (λj. if k_ktm N ≤ j ∧ j < k_ktm N + k_ktm D
                         then a (j - k_ktm N) else b j)"
      and A'eq: "A' = (λj. if k_ktm N ≤ j ∧ j < k_ktm N + k_ktm D
                           then a' (j - k_ktm N) else b j)"
      and Eeq: "E = (λj. if k_ktm N ≤ j ∧ j < k_ktm N + k_ktm D
                         then d (j - k_ktm N) else MoveN)"
    by (rule arm_source)
  have win: "¬ (k_ktm N ≤ j ∧ j < k_ktm N + k_ktm D)"
    if "j ≥ clock_tapes N D" for j
    using that by (simp add: clock_tapes_def)

  from valid_ktm_delta_set [OF vD] trD
  have pD: "p ∈ Q_ktm D - {t_ktm D, r_ktm D}" and p'D: "p' ∈ Q_ktm D"
    and aG: "∀j. a j ∈ Γ_ktm D" and a'G: "∀j. a' j ∈ Γ_ktm D"
    by (auto simp: Pi_iff)
  from b have bG: "∀j. b j ∈ clock_Gamma N D one"
    and bbl: "∀j ≥ clock_tapes N D. b j = bl_ktm N"
    by (auto simp: free_context_def)

  have "Q ∈ clock_Q N D - {CAcc, CRej}"
    using Q pD q by (auto simp: clock_Q_def)
  moreover have "Q' ∈ clock_Q N D"
    using Q' p'D q by (auto simp: clock_Q_def)
  moreover have "∀j. A j ∈ clock_Gamma N D one"
    using aG bG by (auto simp: Aeq clock_Gamma_def)
  moreover have "∀j. A' j ∈ clock_Gamma N D one"
    using a'G bG by (auto simp: A'eq clock_Gamma_def)
  moreover
  have "∀j. A j = le_ktm N ⟶ A' j = le_ktm N ∧ E j ∈ {MoveN, MoveR}"
    using valid_ktm_deltaLE [OF vD trD] leD
    by (auto simp: Aeq A'eq Eeq)
  moreover
  have "∀j ≥ clock_tapes N D. A j = bl_ktm N ∧ A' j = bl_ktm N ∧ E j = MoveN"
    using bbl by (auto simp: Aeq A'eq Eeq win)
  ultimately show ?thesis by (simp add: clock_ok_def)
qed



lemma setup_ok:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and tr: "(Q, A, Q', A', E) ∈ setup_delta N D one"
  shows "clock_ok N D one Q A Q' A' E"
proof -
  have oneG: "one ∈ clock_Gamma N D one" by (simp add: clock_Gamma_def)
  have sN: "s_ktm N ∈ Q_ktm N" using vN by (cases N) auto
  have sD: "s_ktm D ∈ Q_ktm D" using vD by (cases D) auto
  have kless: "k_ktm N < clock_tapes N D"
    using vD by (cases D) (simp add: clock_tapes_def)
  have kpos: "0 < clock_tapes N D"
    using vN by (cases N) (simp add: clock_tapes_def)
  from tr consider
      (walk) a where "Q = CWalk" "A = a" "Q' = CWalk" "A' = a"
                     "E = move_two (k_ktm N) MoveR"
                     "∀j. a j ∈ clock_Gamma N D one"
                     "∀j ≥ clock_tapes N D. a j = bl_ktm N"
                     "a 0 ≠ bl_ktm N"
    | (turn) a where "Q = CWalk" "A = a" "Q' = CBack" "A' = a"
                     "E = move_two (k_ktm N) MoveL"
                     "∀j. a j ∈ clock_Gamma N D one"
                     "∀j ≥ clock_tapes N D. a j = bl_ktm N"
                     "a 0 = bl_ktm N" "a (k_ktm N) ≠ le_ktm N"
    | (rewind) a where "Q = CBack" "A = a" "Q' = CBack"
                     "A' = a(k_ktm N := one)"
                     "E = move_two (k_ktm N) MoveL"
                     "∀j. a j ∈ clock_Gamma N D one"
                     "∀j ≥ clock_tapes N D. a j = bl_ktm N"
                     "a 0 ≠ le_ktm N" "a (k_ktm N) ≠ le_ktm N"
    | (home) a where "Q = CBack" "A = a"
                     "Q' = clock_start_state N D" "A' = a"
                     "E = (λ_. MoveN)"
                     "∀j. a j ∈ clock_Gamma N D one"
                     "∀j ≥ clock_tapes N D. a j = bl_ktm N"
                     "a 0 = le_ktm N"
    by (auto simp: setup_delta_def clock_ctx_def free_context_def)
  then show ?thesis
  proof cases
    case (walk a)
    then show ?thesis
      using kless kpos by (auto simp: clock_ok_def clock_Q_def move_two_def)
  next
    case (turn a)
    then show ?thesis
      using kless kpos blle
      by (auto simp: clock_ok_def clock_Q_def move_two_def)
  next
    case (rewind a)
    then show ?thesis
      using kless kpos oneG
      by (auto simp: clock_ok_def clock_Q_def move_two_def)
  next
    case (home a)
    then show ?thesis
      using kless kpos sN sD
      by (auto simp: clock_ok_def clock_Q_def move_two_def clock_start_state_def)
  qed
qed



theorem clock_product_valid:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and blD: "bl_ktm D = bl_ktm N" and leD: "le_ktm D = le_ktm N"
  shows "valid_ktm (clock_product N D one)"
proof -
  have vN': "finite (Q_ktm N) ∧ finite (Γ_ktm N) ∧ Sigma_ktm N ⊆ Γ_ktm N
             ∧ bl_ktm N ∈ Γ_ktm N ∧ bl_ktm N ∉ Sigma_ktm N
             ∧ le_ktm N ∈ Γ_ktm N ∧ le_ktm N ∉ Sigma_ktm N ∧ 0 < k_ktm N"
    using vN by (cases N) auto
  have vD': "finite (Q_ktm D) ∧ finite (Γ_ktm D) ∧ 0 < k_ktm D"
    using vD by (cases D) auto

  have ok: "clock_ok N D one Q A Q' A' E"
    if "(Q, A, Q', A', E)
          ∈ setup_delta N D one ∪ arm_N N D one ∪ arm_D N D one"
    for Q A Q' A' E
    using that setup_ok [OF vN vD blle] arm_N_ok [OF vN]
          arm_D_ok [OF vD blD leD] by blast

  have finQ: "finite (clock_Q N D)"
  proof -
    let ?f = "λ(q, p, b). CRun q p b"
    let ?T = "Q_ktm N × Q_ktm D × (UNIV :: bool set)"
    have "{CRun q p b | q p b. q ∈ Q_ktm N ∧ p ∈ Q_ktm D} ⊆ ?f ` ?T"
    proof
      fix x assume "x ∈ {CRun q p b | q p b. q ∈ Q_ktm N ∧ p ∈ Q_ktm D}"
      then obtain q p b where x: "x = CRun q p b"
        and q: "q ∈ Q_ktm N" and p: "p ∈ Q_ktm D" by blast
      from q p have "(q, p, b) ∈ ?T" by simp
      then have "?f (q, p, b) ∈ ?f ` ?T" by (rule imageI)
      with x show "x ∈ ?f ` ?T" by simp
    qed
    moreover have "finite (?f ` ?T)" using vN' vD' by simp
    ultimately have "finite {CRun q p b | q p b. q ∈ Q_ktm N ∧ p ∈ Q_ktm D}"
      by (rule finite_subset)
    then show ?thesis by (simp add: clock_Q_def)
  qed
  have finG: "finite (clock_Gamma N D one)"
    using vN' vD' by (simp add: clock_Gamma_def)
  have SgG: "Sigma_ktm N ⊆ clock_Gamma N D one"
    using vN' by (auto simp: clock_Gamma_def)
  have QW: "CWalk ∈ clock_Q N D" and QA: "CAcc ∈ clock_Q N D"
    and QR: "CRej ∈ clock_Q N D" by (auto simp: clock_Q_def)
  have blG: "bl_ktm N ∈ clock_Gamma N D one"
    and leG: "le_ktm N ∈ clock_Gamma N D one"
    using vN' by (auto simp: clock_Gamma_def)
  have kpos: "0 < clock_tapes N D" using vN' by (simp add: clock_tapes_def)

  let ?d = "setup_delta N D one ∪ arm_N N D one ∪ arm_D N D one"
  have dsub: "?d ⊆ (clock_Q N D - {CAcc, CRej})
                     × (UNIV → clock_Gamma N D one)
                     × clock_Q N D
                     × (UNIV → clock_Gamma N D one)
                     × (UNIV → UNIV)"
  proof (rule subsetI)
    fix x assume x: "x ∈ ?d"
    obtain Q A Q' A' E where xe: "x = (Q, A, Q', A', E)"
      using prod_cases5 by blast
    from ok [OF x [unfolded xe]] show "x ∈ (clock_Q N D - {CAcc, CRej})
                     × (UNIV → clock_Gamma N D one)
                     × clock_Q N D
                     × (UNIV → clock_Gamma N D one)
                     × (UNIV → UNIV)"
      unfolding xe by (simp add: clock_ok_def Pi_iff)
  qed
  have dle1: "a' j = le_ktm N ∧ d j ∈ {MoveN, MoveR}"
    if "(q, a, q', a', d) ∈ ?d" and "a j = le_ktm N" for q a q' a' d j
    using ok [OF that(1)] that(2) by (simp add: clock_ok_def)
  have dle: "∀q a q' a' d j. (q, a, q', a', d) ∈ ?d ⟶ a j = le_ktm N
                ⟶ a' j = le_ktm N ∧ d j ∈ {MoveN, MoveR}"
    using dle1 by blast
  have dsupp1: "a j = bl_ktm N ∧ a' j = bl_ktm N ∧ d j = MoveN"
    if "(q, a, q', a', d) ∈ ?d" and "j ≥ clock_tapes N D" for q a q' a' d j
    using ok [OF that(1)] that(2) by (simp add: clock_ok_def)
  have dsupp: "∀q a q' a' d. (q, a, q', a', d) ∈ ?d
                  ⟶ (∀j ≥ clock_tapes N D.
                          a j = bl_ktm N ∧ a' j = bl_ktm N ∧ d j = MoveN)"
    using dsupp1 by blast

  have tne: "(CAcc :: clock_state) ≠ CRej" by simp
  show ?thesis
    unfolding clock_product_def valid_ktm.simps
    using finQ finG SgG QW QA QR blG leG vN' kpos tne dsub dle dsupp by blast
qed


lemma clock_product_le_unique:
  assumes luN: "le_unique N"
      and luD: "le_unique D"
      and leD: "le_ktm D = le_ktm N"
      and one: "one ≠ le_ktm N"
  shows "le_unique (clock_product N D one)"
proof -
  have luN': "∀q a q' a' d j. (q, a, q', a', d) ∈ delta_ktm N
                 ⟶ a' j = le_ktm N ⟶ a j = le_ktm N"
    using luN unfolding le_unique_def by blast
  have luD': "∀q a q' a' d j. (q, a, q', a', d) ∈ delta_ktm D
                 ⟶ a' j = le_ktm N ⟶ a j = le_ktm N"
  proof (intro allI impI)
    fix q a q' a' d and j :: nat
    assume m: "(q, a, q', a', d) ∈ delta_ktm D" and wD: "a' j = le_ktm N"
    from wD leD have "a' j = le_ktm D" by simp
    with luD m have "a j = le_ktm D" unfolding le_unique_def by blast
    with leD show "a j = le_ktm N" by simp
  qed
  show ?thesis
    unfolding le_unique_def
  proof (intro allI impI)
    fix q a q' a' d and j :: nat
    assume mem: "(q, a, q', a', d) ∈ delta_ktm (clock_product N D one)"
       and w: "a' j = le_ktm (clock_product N D one)"
    from w have w': "a' j = le_ktm N" by simp
    from mem
    consider (phase) "(q, a, q', a', d) ∈ setup_delta N D one"
      | (armN) "(q, a, q', a', d) ∈ arm_N N D one"
      | (armD) "(q, a, q', a', d) ∈ arm_D N D one"
      by auto
    then have "a j = le_ktm N"
    proof cases
      case phase
      then show ?thesis
        using w' one by (auto simp: setup_delta_def split: if_split_asm)
    next
      case armN
      then obtain p
        where t: "(q, a, q', a', d)
                    ∈ tag_delta (λu. CRun u p True)
                        (λu'. if u' = t_ktm N then CAcc else if u' = r_ktm N then CRej else CRun u' p False)
                        (embed_delta 0 (k_ktm N) (clock_tapes N D)
                           (clock_Gamma N D one) (bl_ktm N) (delta_ktm N))"
        unfolding arm_N_def by blast
      show ?thesis
        by (rule tag_delta_le_unique [OF embed_delta_le_unique [OF luN'],
                                      rule_format, OF t w'])
    next
      case armD
      then obtain u
        where t: "(q, a, q', a', d)
                    ∈ tag_delta (λp. CRun u p False)
                        (λp'. if p' = t_ktm D ∨ p' = r_ktm D then CRej
                              else CRun u p' True)
                        (embed_delta (k_ktm N) (k_ktm D) (clock_tapes N D)
                           (clock_Gamma N D one) (bl_ktm N) (delta_ktm D))"
        unfolding arm_D_def by blast
      show ?thesis
        by (rule tag_delta_le_unique [OF embed_delta_le_unique [OF luD'],
                                      rule_format, OF t w'])
    qed
    then show "a j = le_ktm (clock_product N D one)" by simp
  qed
qed


subsection ‹Running the setup phase›


definition setup_tape ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ nat ⇒ nat list ⇒ nat
     ⇒ nat ⇒ nat ⇒ nat" where
  "setup_tape N D one w p i m =
     (if i = k_ktm N ∧ p < m ∧ m ≤ length w then one
      else if i < clock_tapes N D
           then (if m = 0 then le_ktm N
                 else if i = 0 ∧ m ≤ length w then w ! (m - 1)
                 else bl_ktm N)
           else bl_ktm N)"

definition setup_pos :: "nat ⇒ nat ⇒ nat ⇒ nat" where
  "setup_pos kN p = (λj. if j = 0 ∨ j = kN then p else 0)"

lemma clock_init_config:
  "init_config_ktm (clock_product N D one) w
     = KConfig CWalk (setup_tape N D one w (length w)) (setup_pos (k_ktm N) 0)"
  by (simp add: clock_product_def setup_tape_def setup_pos_def fun_eq_iff)


lemma setup_tape_ctx:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and w: "set w ⊆ Sigma_ktm N"
  shows "(λj. setup_tape N D one w p j (pos j)) ∈ clock_ctx N D one"
proof -
  have vN': "Sigma_ktm N ⊆ Γ_ktm N ∧ bl_ktm N ∈ Γ_ktm N ∧ le_ktm N ∈ Γ_ktm N"
    using vN by (cases N) auto
  have SgG: "Sigma_ktm N ⊆ clock_Gamma N D one"
    using vN' by (auto simp: clock_Gamma_def)
  have blG: "bl_ktm N ∈ clock_Gamma N D one"
    and leG: "le_ktm N ∈ clock_Gamma N D one"
    using vN' by (auto simp: clock_Gamma_def)
  have oneG: "one ∈ clock_Gamma N D one" by (simp add: clock_Gamma_def)
  have kless: "k_ktm N < clock_tapes N D"
    using vD by (cases D) (simp add: clock_tapes_def)
  have wG: "w ! (m - 1) ∈ clock_Gamma N D one" if "m ≤ length w" and "0 < m"
    for m
  proof -
    from that have "w ! (m - 1) ∈ set w" by simp
    with w SgG show ?thesis by blast
  qed
  show ?thesis
    unfolding clock_ctx_def free_context_def setup_tape_def
    using blG leG oneG wG kless by auto
qed


lemma setup_step:
  assumes tup: "(Q, (λj. ts j (pos j)), Q', a', d) ∈ setup_delta N D one"
  shows "(KConfig Q ts pos,
          KConfig Q' (λj. (ts j)(pos j := a' j)) (λj. go_move (d j) (pos j)))
           ∈ ktm_step (delta_ktm (clock_product N D one))"
proof (rule ktm_step.step)
  show "(Q, λj. ts j (pos j), Q', a', d)
          ∈ delta_ktm (clock_product N D one)"
    using tup by simp
qed



lemma setup_walk_step:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
      and p: "p ≤ length w"
  shows "(KConfig CWalk (setup_tape N D one w (length w))
                      (setup_pos (k_ktm N) p),
          KConfig CWalk (setup_tape N D one w (length w))
                      (setup_pos (k_ktm N) (Suc p)))
           ∈ ktm_step (delta_ktm (clock_product N D one))"
proof -
  let ?ts = "setup_tape N D one w (length w)"
  let ?pos = "setup_pos (k_ktm N) p"
  let ?a = "λj. ?ts j (?pos j)"
  have kN: "0 < k_ktm N" using vN by (cases N) auto
  have blS: "bl_ktm N ∉ Sigma_ktm N" using vN by (cases N) auto
  have a0: "?a 0 ≠ bl_ktm N"
  proof (cases "p = 0")
    case True
    then show ?thesis
      using blle kN
      by (simp add: setup_tape_def setup_pos_def clock_tapes_def)
  next
    case False
    with p have "w ! (p - 1) ∈ set w" by simp
    with w blS have "w ! (p - 1) ≠ bl_ktm N" by auto
    with False p kN show ?thesis
      by (simp add: setup_tape_def setup_pos_def clock_tapes_def)
  qed
  have mem: "(CWalk, ?a, CWalk, ?a, move_two (k_ktm N) MoveR)
               ∈ setup_delta N D one"
    using setup_tape_ctx [OF vN vD w] a0 by (auto simp: setup_delta_def)
  from setup_step [where ts = "?ts" and pos = "?pos", OF mem]
  have "(KConfig CWalk ?ts ?pos,
         KConfig CWalk (λj. (?ts j)(?pos j := ?a j))
                     (λj. go_move (move_two (k_ktm N) MoveR j) (?pos j)))
          ∈ ktm_step (delta_ktm (clock_product N D one))" .
  moreover have "(λj. (?ts j)(?pos j := ?a j)) = ?ts" by (simp add: fun_eq_iff)
  moreover have "(λj. go_move (move_two (k_ktm N) MoveR j) (?pos j))
                   = setup_pos (k_ktm N) (Suc p)"
    by (simp add: fun_eq_iff move_two_def setup_pos_def)
  ultimately show ?thesis by simp
qed


lemma setup_turn_step:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
  shows "(KConfig CWalk (setup_tape N D one w (length w))
                      (setup_pos (k_ktm N) (Suc (length w))),
          KConfig CBack (setup_tape N D one w (length w))
                      (setup_pos (k_ktm N) (length w)))
           ∈ ktm_step (delta_ktm (clock_product N D one))"
proof -
  let ?ts = "setup_tape N D one w (length w)"
  let ?pos = "setup_pos (k_ktm N) (Suc (length w))"
  let ?a = "λj. ?ts j (?pos j)"
  have kN: "0 < k_ktm N" using vN by (cases N) auto
  have kless: "k_ktm N < clock_tapes N D"
    using vD by (cases D) (simp add: clock_tapes_def)
  have a0: "?a 0 = bl_ktm N"
    using kN by (simp add: setup_tape_def setup_pos_def clock_tapes_def)
  have ak: "?a (k_ktm N) ≠ le_ktm N"
    using kN kless blle by (simp add: setup_tape_def setup_pos_def)
  have mem: "(CWalk, ?a, CBack, ?a, move_two (k_ktm N) MoveL)
               ∈ setup_delta N D one"
    using setup_tape_ctx [OF vN vD w] a0 ak by (auto simp: setup_delta_def)
  from setup_step [where ts = "?ts" and pos = "?pos", OF mem]
  have "(KConfig CWalk ?ts ?pos,
         KConfig CBack (λj. (?ts j)(?pos j := ?a j))
                     (λj. go_move (move_two (k_ktm N) MoveL j) (?pos j)))
          ∈ ktm_step (delta_ktm (clock_product N D one))" .
  moreover have "(λj. (?ts j)(?pos j := ?a j)) = ?ts" by (simp add: fun_eq_iff)
  moreover have "(λj. go_move (move_two (k_ktm N) MoveL j) (?pos j))
                   = setup_pos (k_ktm N) (length w)"
    by (simp add: fun_eq_iff move_two_def setup_pos_def)
  ultimately show ?thesis by simp
qed



lemma setup_rewind_step:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
      and p1: "0 < p" and pn: "p ≤ length w"
  shows "(KConfig CBack (setup_tape N D one w p) (setup_pos (k_ktm N) p),
          KConfig CBack (setup_tape N D one w (p - 1))
                      (setup_pos (k_ktm N) (p - 1)))
           ∈ ktm_step (delta_ktm (clock_product N D one))"
proof -
  let ?ts = "setup_tape N D one w p"
  let ?pos = "setup_pos (k_ktm N) p"
  let ?a = "λj. ?ts j (?pos j)"
  have kN: "0 < k_ktm N" using vN by (cases N) auto
  have leS: "le_ktm N ∉ Sigma_ktm N" using vN by (cases N) auto
  have kless: "k_ktm N < clock_tapes N D"
    using vD by (cases D) (simp add: clock_tapes_def)
  from p1 pn have "w ! (p - 1) ∈ set w" by simp
  with w leS have wne: "w ! (p - 1) ≠ le_ktm N" by auto
  have a0: "?a 0 ≠ le_ktm N"
    using wne p1 pn kN by (simp add: setup_tape_def setup_pos_def clock_tapes_def)
  have ak: "?a (k_ktm N) ≠ le_ktm N"
    using kN kless p1 blle by (simp add: setup_tape_def setup_pos_def)
  have mem: "(CBack, ?a, CBack, ?a(k_ktm N := one), move_two (k_ktm N) MoveL)
               ∈ setup_delta N D one"
    using setup_tape_ctx [OF vN vD w] a0 ak by (auto simp: setup_delta_def)
  from setup_step [where ts = "?ts" and pos = "?pos", OF mem]
  have "(KConfig CBack ?ts ?pos,
         KConfig CBack (λj. (?ts j)(?pos j := (?a(k_ktm N := one)) j))
                     (λj. go_move (move_two (k_ktm N) MoveL j) (?pos j)))
          ∈ ktm_step (delta_ktm (clock_product N D one))" .
  moreover
  have "(λj. (?ts j)(?pos j := (?a(k_ktm N := one)) j))
          = setup_tape N D one w (p - 1)"
    using p1 pn kN kless by (auto simp: fun_eq_iff setup_tape_def setup_pos_def)
  moreover have "(λj. go_move (move_two (k_ktm N) MoveL j) (?pos j))
                   = setup_pos (k_ktm N) (p - 1)"
    by (simp add: fun_eq_iff move_two_def setup_pos_def)
  ultimately show ?thesis by simp
qed


lemma setup_home_step:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and w: "set w ⊆ Sigma_ktm N"
  shows "(KConfig CBack (setup_tape N D one w 0) (setup_pos (k_ktm N) 0),
          KConfig (clock_start_state N D) (setup_tape N D one w 0)
                  (setup_pos (k_ktm N) 0))
           ∈ ktm_step (delta_ktm (clock_product N D one))"
proof -
  let ?ts = "setup_tape N D one w 0"
  let ?pos = "setup_pos (k_ktm N) 0"
  let ?a = "λj. ?ts j (?pos j)"
  have kN: "0 < k_ktm N" using vN by (cases N) auto
  have a0: "?a 0 = le_ktm N"
    using kN by (simp add: setup_tape_def setup_pos_def clock_tapes_def)
  have mem: "(CBack, ?a, clock_start_state N D, ?a, λ_. MoveN)
               ∈ setup_delta N D one"
    using setup_tape_ctx [OF vN vD w] a0 by (auto simp: setup_delta_def)
  from setup_step [where ts = "?ts" and pos = "?pos", OF mem]
  have "(KConfig CBack ?ts ?pos,
         KConfig (clock_start_state N D)
                 (λj. (?ts j)(?pos j := ?a j))
                 (λj. go_move ((λ_. MoveN) j) (?pos j)))
          ∈ ktm_step (delta_ktm (clock_product N D one))" .
  moreover have "(λj. (?ts j)(?pos j := ?a j)) = ?ts" by (simp add: fun_eq_iff)
  moreover have "(λj. go_move ((λ_. MoveN) j) (?pos j)) = ?pos"
    by (simp add: fun_eq_iff)
  ultimately show ?thesis by simp
qed



lemma setup_walk_run:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
      and p: "p ≤ Suc (length w)"
  shows "(KConfig CWalk (setup_tape N D one w (length w))
                      (setup_pos (k_ktm N) 0),
          KConfig CWalk (setup_tape N D one w (length w))
                      (setup_pos (k_ktm N) p))
           ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ p"
  using p
proof (induction p)
  case 0
  show ?case by simp
next
  case (Suc q)
  from Suc.prems have q: "q ≤ length w" by simp
  then have q': "q ≤ Suc (length w)" by simp
  from Suc.IH [OF q'] setup_walk_step [OF vN vD blle w q]
  show ?case by (rule relpow_Suc_I)
qed

lemma setup_rewind_run:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
      and r: "r ≤ length w"
  shows "(KConfig CBack (setup_tape N D one w (length w))
                      (setup_pos (k_ktm N) (length w)),
          KConfig CBack (setup_tape N D one w (length w - r))
                      (setup_pos (k_ktm N) (length w - r)))
           ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ r"
  using r
proof (induction r)
  case 0
  show ?case by simp
next
  case (Suc r)
  from Suc.prems have r: "r ≤ length w" by simp
  have pos: "0 < length w - r" using Suc.prems by simp
  have le: "length w - r ≤ length w" by simp
  from Suc.IH [OF r] setup_rewind_step [OF vN vD blle w pos le]
  have "(KConfig CBack (setup_tape N D one w (length w))
                     (setup_pos (k_ktm N) (length w)),
         KConfig CBack (setup_tape N D one w (length w - r - 1))
                     (setup_pos (k_ktm N) (length w - r - 1)))
          ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ Suc r"
    by (rule relpow_Suc_I)
  then show ?case by simp
qed


lemma setup_run:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
  shows "(init_config_ktm (clock_product N D one) w,
          KConfig (clock_start_state N D) (setup_tape N D one w 0)
                  (setup_pos (k_ktm N) 0))
           ∈ (ktm_step (delta_ktm (clock_product N D one)))
                ^^ (2 * length w + 3)"
proof -
  let ?R = "ktm_step (delta_ktm (clock_product N D one))"
  let ?ts = "setup_tape N D one w (length w)"
  let ?n = "length w"
  have walk: "(KConfig CWalk ?ts (setup_pos (k_ktm N) 0),
               KConfig CWalk ?ts (setup_pos (k_ktm N) (Suc ?n))) ∈ ?R ^^ Suc ?n"
    by (rule setup_walk_run [OF vN vD blle w le_refl])
  from walk setup_turn_step [OF vN vD blle w]
  have turned: "(KConfig CWalk ?ts (setup_pos (k_ktm N) 0),
                 KConfig CBack ?ts (setup_pos (k_ktm N) ?n))
                  ∈ ?R ^^ Suc (Suc ?n)"
    by (rule relpow_Suc_I)
  have homeward: "(KConfig CBack ?ts (setup_pos (k_ktm N) ?n),
               KConfig CBack (setup_tape N D one w 0) (setup_pos (k_ktm N) 0))
                ∈ ?R ^^ ?n"
    using setup_rewind_run [OF vN vD blle w le_refl] by simp
  from turned homeward
  have "(KConfig CWalk ?ts (setup_pos (k_ktm N) 0),
         KConfig CBack (setup_tape N D one w 0) (setup_pos (k_ktm N) 0))
          ∈ ?R ^^ (Suc (Suc ?n) + ?n)"
    unfolding relpow_add by (rule relcompI)
  from this setup_home_step [OF vN vD w]
  have whole: "(KConfig CWalk ?ts (setup_pos (k_ktm N) 0),
                KConfig (clock_start_state N D) (setup_tape N D one w 0)
                        (setup_pos (k_ktm N) 0))
                 ∈ ?R ^^ Suc (Suc (Suc ?n) + ?n)"
    by (rule relpow_Suc_I)
  have eq: "2 * ?n + 3 = Suc (Suc (Suc ?n) + ?n)" by simp
  show ?thesis unfolding clock_init_config eq by (rule whole)
qed



definition setup_config ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ nat ⇒ nat list ⇒ nat
     ⇒ (nat, clock_state) ktc_config" where
  "setup_config N D one w i =
     (if i ≤ Suc (length w)
      then KConfig CWalk (setup_tape N D one w (length w))
                        (setup_pos (k_ktm N) i)
      else if i ≤ 2 * length w + 2
      then KConfig CBack (setup_tape N D one w (2 * length w + 2 - i))
                        (setup_pos (k_ktm N) (2 * length w + 2 - i))
      else KConfig (clock_start_state N D)
                   (setup_tape N D one w 0) (setup_pos (k_ktm N) 0))"

lemma setup_config_0:
  "setup_config N D one w 0 = init_config_ktm (clock_product N D one) w"
  by (simp add: setup_config_def clock_init_config)

lemma setup_config_end:
  "setup_config N D one w (2 * length w + 3)
     = KConfig (clock_start_state N D)
               (setup_tape N D one w 0) (setup_pos (k_ktm N) 0)"
  by (simp add: setup_config_def)


lemma setup_config_step:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
      and i: "i < 2 * length w + 3"
  shows "(setup_config N D one w i, setup_config N D one w (Suc i))
           ∈ ktm_step (delta_ktm (clock_product N D one))"
proof -
  let ?n = "length w"
  consider (Walk) "i ≤ ?n" | (Turn) "i = Suc ?n"
    | (Back) "Suc ?n < i" and "i ≤ 2 * ?n + 1"
    | (Home) "i = 2 * ?n + 2"
    using i by linarith
  then show ?thesis
  proof cases
    case Walk
    then have "setup_config N D one w i
                 = KConfig CWalk (setup_tape N D one w ?n) (setup_pos (k_ktm N) i)"
      and "setup_config N D one w (Suc i)
                 = KConfig CWalk (setup_tape N D one w ?n)
                                (setup_pos (k_ktm N) (Suc i))"
      by (simp_all add: setup_config_def)
    with setup_walk_step [OF vN vD blle w Walk] show ?thesis by simp
  next
    case Turn
    then have "setup_config N D one w i
                 = KConfig CWalk (setup_tape N D one w ?n)
                                (setup_pos (k_ktm N) (Suc ?n))"
      and "setup_config N D one w (Suc i)
                 = KConfig CBack (setup_tape N D one w ?n) (setup_pos (k_ktm N) ?n)"
      by (simp_all add: setup_config_def)
    with setup_turn_step [OF vN vD blle w] show ?thesis by simp
  next
    case Back
    define p where "p = 2 * ?n + 2 - i"
    from Back have p1: "0 < p" and pn: "p ≤ ?n" by (simp_all add: p_def)
    from Back have "setup_config N D one w i
                      = KConfig CBack (setup_tape N D one w p) (setup_pos (k_ktm N) p)"
      by (simp add: setup_config_def p_def)
    moreover from Back have "setup_config N D one w (Suc i)
                      = KConfig CBack (setup_tape N D one w (p - 1))
                                     (setup_pos (k_ktm N) (p - 1))"
      by (simp add: setup_config_def p_def)
    ultimately show ?thesis
      using setup_rewind_step [OF vN vD blle w p1 pn] by simp
  next
    case Home
    then have "setup_config N D one w i
                 = KConfig CBack (setup_tape N D one w 0) (setup_pos (k_ktm N) 0)"
      and "setup_config N D one w (Suc i)
                 = KConfig (clock_start_state N D)
                           (setup_tape N D one w 0) (setup_pos (k_ktm N) 0)"
      by (simp_all add: setup_config_def)
    with setup_home_step [OF vN vD w] show ?thesis by simp
  qed
qed


subsection ‹A step of a factor is a step of the product›


lemma arm_N_step:
  assumes p: "p ∈ Q_ktm D"
      and step: "(proj_config 0 (k_ktm N) (bl_ktm N) C, c')
                   ∈ ktm_step (delta_ktm N)"
      and ctx: "(λj. ktc_tape C j (ktc_pos C j))
                  ∈ free_context (clock_Gamma N D one) (bl_ktm N)
                        (clock_tapes N D)"
  shows "(ktc_set_state (CRun (ktc_state C) p True) C,
          ktc_set_state (if ktc_state c' = t_ktm N then CAcc
                   else if ktc_state c' = r_ktm N then CRej
                   else CRun (ktc_state c') p False)
                  (embed_update 0 (k_ktm N) C c'))
           ∈ ktm_step (arm_N N D one)"
proof -
  let ?u = "λq. CRun q p True"
  let ?v = "λq'. if q' = t_ktm N then CAcc else if q' = r_ktm N then CRej else CRun q' p False"
  let ?E = "embed_delta 0 (k_ktm N) (clock_tapes N D)
              (clock_Gamma N D one) (bl_ktm N) (delta_ktm N)"
  have inner: "(ktc_set_state (?u (ktc_state C)) C,
                ktc_set_state (?v (ktc_state c')) (embed_update 0 (k_ktm N) C c'))
                 ∈ ktm_step (tag_delta ?u ?v ?E)"
    using tag_step [where u = ?u and v = ?v, OF embed_step [OF step ctx]]
    by (simp only: embed_update_state)
  have sub: "tag_delta ?u ?v ?E ⊆ arm_N N D one"
    using p by (auto simp: arm_N_def)
  from ktm_step_mono [OF sub] inner show ?thesis by blast
qed

lemma arm_D_step:
  assumes q: "q ∈ Q_ktm N"
      and step: "(proj_config (k_ktm N) (k_ktm D) (bl_ktm N) C, c')
                   ∈ ktm_step (delta_ktm D)"
      and ctx: "(λj. ktc_tape C j (ktc_pos C j))
                  ∈ free_context (clock_Gamma N D one) (bl_ktm N)
                        (clock_tapes N D)"
  shows "(ktc_set_state (CRun q (ktc_state C) False) C,
          ktc_set_state (if ktc_state c' = t_ktm D ∨ ktc_state c' = r_ktm D then CRej
                   else CRun q (ktc_state c') True)
                  (embed_update (k_ktm N) (k_ktm D) C c'))
           ∈ ktm_step (arm_D N D one)"
proof -
  let ?u = "λr. CRun q r False"
  let ?v = "λr'. if r' = t_ktm D ∨ r' = r_ktm D then CRej else CRun q r' True"
  let ?E = "embed_delta (k_ktm N) (k_ktm D) (clock_tapes N D)
              (clock_Gamma N D one) (bl_ktm N) (delta_ktm D)"
  have inner: "(ktc_set_state (?u (ktc_state C)) C,
                ktc_set_state (?v (ktc_state c'))
                        (embed_update (k_ktm N) (k_ktm D) C c'))
                 ∈ ktm_step (tag_delta ?u ?v ?E)"
    using tag_step [where u = ?u and v = ?v, OF embed_step [OF step ctx]]
    by (simp only: embed_update_state)
  have sub: "tag_delta ?u ?v ?E ⊆ arm_D N D one"
    using q by (auto simp: arm_D_def)
  from ktm_step_mono [OF sub] inner show ?thesis by blast
qed


subsection ‹One turn of the clock›


definition clock_inv ::
  "(nat, nat) ktm ⇒ (nat, nat) ktm ⇒ nat
     ⇒ (nat, nat) ktc_config ⇒ (nat, nat) ktc_config ⇒ (nat, nat) ktc_config
     ⇒ bool" where
  "clock_inv N D one C cN cD ⟷
     proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state (ktc_state cN) C) = cN
   ∧ proj_config (k_ktm N) (k_ktm D) (bl_ktm N) (ktc_set_state (ktc_state cD) C) = cD
   ∧ (∀j m. ktc_tape C j m ∈ clock_Gamma N D one)
   ∧ (∀j m. clock_tapes N D ≤ j ⟶ ktc_tape C j m = bl_ktm N)"


lemma clock_inv_ctx:
  assumes "clock_inv N D one C cN cD"
  shows "(λj. ktc_tape (ktc_set_state Q C) j (ktc_pos (ktc_set_state Q C) j))
           ∈ free_context (clock_Gamma N D one) (bl_ktm N) (clock_tapes N D)"
  using assms by (auto simp: clock_inv_def free_context_def)


lemma clock_inv_set_state [simp]:
  "clock_inv N D one (ktc_set_state p C) cN cD = clock_inv N D one C cN cD"
  by (simp add: clock_inv_def)


lemma clock_step_N:
  assumes p: "p ∈ Q_ktm D"
      and inv: "clock_inv N D one C cN cD"
      and step: "(cN, cN') ∈ ktm_step (delta_ktm N)"
      and tapes: "ktc_tapes_fit (Γ_ktm N) (bl_ktm N) (k_ktm N) cN'"
      and heads: "heads_parked (k_ktm N) cN'"
      and nacc: "ktc_state cN' ≠ t_ktm N"
      and nrej: "ktc_state cN' ≠ r_ktm N"
  obtains C'
  where "(ktc_set_state (CRun (ktc_state cN) p True) C,
          ktc_set_state (CRun (ktc_state cN') p False) C')
           ∈ ktm_step (delta_ktm (clock_product N D one))"
    and "clock_inv N D one C' cN' cD"
proof -
  let ?C = "ktc_set_state (ktc_state cN) C"
  let ?C' = "embed_update 0 (k_ktm N) C cN'"
  from inv have pN: "proj_config 0 (k_ktm N) (bl_ktm N) ?C = cN"
    and pD: "proj_config (k_ktm N) (k_ktm D) (bl_ktm N) (ktc_set_state (ktc_state cD) C) = cD"
    and tG: "⋀j m. ktc_tape C j m ∈ clock_Gamma N D one"
    and tB: "⋀j m. clock_tapes N D ≤ j ⟹ ktc_tape C j m = bl_ktm N"
    by (auto simp: clock_inv_def)

  have step': "(proj_config 0 (k_ktm N) (bl_ktm N) ?C, cN') ∈ ktm_step (delta_ktm N)"
    using pN step by simp
  have arm: "(ktc_set_state (CRun (ktc_state cN) p True) C,
              ktc_set_state (CRun (ktc_state cN') p False) ?C')
               ∈ ktm_step (arm_N N D one)"
    using arm_N_step [OF p step' clock_inv_ctx [OF inv]] nacc nrej by simp
  have sub: "arm_N N D one ⊆ delta_ktm (clock_product N D one)" by auto
  from ktm_step_mono [OF sub] arm
  have theStep: "(ktc_set_state (CRun (ktc_state cN) p True) C,
                  ktc_set_state (CRun (ktc_state cN') p False) ?C')
                   ∈ ktm_step (delta_ktm (clock_product N D one))" by blast

  have pN': "proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state (ktc_state cN') ?C') = cN'"
    by (simp add: proj_embed_update [OF frame_tail [OF tapes heads]])
  have pD': "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
               (ktc_set_state (ktc_state cD) ?C') = cD"
    using pD by (simp add: proj_embed_update_disjoint)

  have inside: "ktc_tape cN' j m ∈ clock_Gamma N D one" for j m
    using tapes by (auto simp: ktc_tapes_fit_def clock_Gamma_def)
  have tG': "ktc_tape ?C' j m ∈ clock_Gamma N D one" for j m
    using inside tG by (simp add: embed_update_def)
  have tB': "ktc_tape ?C' j m = bl_ktm N" if "clock_tapes N D ≤ j" for j m
  proof -
    from that have "¬ j < k_ktm N" by (simp add: clock_tapes_def)
    with that show ?thesis using tB by (simp add: embed_update_def)
  qed
  have inv': "clock_inv N D one ?C' cN' cD"
    unfolding clock_inv_def using pN' pD' tG' tB' by blast
  from theStep inv' show thesis by (rule that)
qed


lemma clock_step_D:
  assumes q: "q ∈ Q_ktm N"
      and inv: "clock_inv N D one C cN cD"
      and step: "(cD, cD') ∈ ktm_step (delta_ktm D)"
      and tapes: "ktc_tapes_fit (Γ_ktm D) (bl_ktm N) (k_ktm D) cD'"
      and heads: "heads_parked (k_ktm D) cD'"
      and nhalt: "ktc_state cD' ≠ t_ktm D" "ktc_state cD' ≠ r_ktm D"
  obtains C'
  where "(ktc_set_state (CRun q (ktc_state cD) False) C,
          ktc_set_state (CRun q (ktc_state cD') True) C')
           ∈ ktm_step (delta_ktm (clock_product N D one))"
    and "clock_inv N D one C' cN cD'"
proof -
  let ?C = "ktc_set_state (ktc_state cD) C"
  let ?C' = "embed_update (k_ktm N) (k_ktm D) C cD'"
  from inv have pN: "proj_config 0 (k_ktm N) (bl_ktm N)
                       (ktc_set_state (ktc_state cN) C) = cN"
    and pD: "proj_config (k_ktm N) (k_ktm D) (bl_ktm N) ?C = cD"
    and tG: "⋀j m. ktc_tape C j m ∈ clock_Gamma N D one"
    and tB: "⋀j m. clock_tapes N D ≤ j ⟹ ktc_tape C j m = bl_ktm N"
    by (auto simp: clock_inv_def)

  have step': "(proj_config (k_ktm N) (k_ktm D) (bl_ktm N) ?C, cD')
                 ∈ ktm_step (delta_ktm D)"
    using pD step by simp
  have arm: "(ktc_set_state (CRun q (ktc_state cD) False) C,
              ktc_set_state (CRun q (ktc_state cD') True) ?C')
               ∈ ktm_step (arm_D N D one)"
    using arm_D_step [OF q step' clock_inv_ctx [OF inv]] nhalt by simp
  have sub: "arm_D N D one ⊆ delta_ktm (clock_product N D one)" by auto
  from ktm_step_mono [OF sub] arm
  have theStep: "(ktc_set_state (CRun q (ktc_state cD) False) C,
                  ktc_set_state (CRun q (ktc_state cD') True) ?C')
                   ∈ ktm_step (delta_ktm (clock_product N D one))" by blast

  have pD': "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
               (ktc_set_state (ktc_state cD') ?C') = cD'"
    by (simp add: proj_embed_update [OF frame_tail [OF tapes heads]])
  have pN': "proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state (ktc_state cN) ?C') = cN"
    using pN by (simp add: proj_embed_update_disjoint)

  have inside: "ktc_tape cD' j m ∈ clock_Gamma N D one" for j m
    using tapes by (auto simp: ktc_tapes_fit_def clock_Gamma_def)
  have tG': "ktc_tape ?C' j m ∈ clock_Gamma N D one" for j m
    using inside tG by (simp add: embed_update_def)
  have tB': "ktc_tape ?C' j m = bl_ktm N" if "clock_tapes N D ≤ j" for j m
  proof -
    from that have "¬ j < k_ktm N + k_ktm D" by (simp add: clock_tapes_def)
    with that show ?thesis using tB by (simp add: embed_update_def)
  qed
  have inv': "clock_inv N D one ?C' cN cD'"
    unfolding clock_inv_def using pN' pD' tG' tB' by blast
  from theStep inv' show thesis by (rule that)
qed


lemma clock_tick:
  assumes inv: "clock_inv N D one C cN cD"
      and blD: "bl_ktm D = bl_ktm N"
      and qD: "ktc_state cD ∈ Q_ktm D"
      and stepN: "(cN, cN') ∈ ktm_step (delta_ktm N)"
      and stepD: "(cD, cD') ∈ ktm_step (delta_ktm D)"
      and vcN: "valid_config_ktm N cN'"
      and vcD: "valid_config_ktm D cD'"
      and headsN: "heads_parked (k_ktm N) cN'"
      and headsD: "heads_parked (k_ktm D) cD'"
      and nacc: "ktc_state cN' ≠ t_ktm N"
      and nrej: "ktc_state cN' ≠ r_ktm N"
      and nhalt: "ktc_state cD' ≠ t_ktm D" "ktc_state cD' ≠ r_ktm D"
  obtains C'
  where "(ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True) C,
          ktc_set_state (CRun (ktc_state cN') (ktc_state cD') True) C')
           ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ 2"
    and "clock_inv N D one C' cN' cD'"
proof -
  have tN: "ktc_tapes_fit (Γ_ktm N) (bl_ktm N) (k_ktm N) cN'"
    by (rule valid_config_tapes_fit [OF vcN])
  have tD: "ktc_tapes_fit (Γ_ktm D) (bl_ktm N) (k_ktm D) cD'"
    using valid_config_tapes_fit [OF vcD] blD by simp
  have qN': "ktc_state cN' ∈ Q_ktm N" by (rule valid_config_state [OF vcN])

  from clock_step_N [OF qD inv stepN tN headsN nacc nrej]
  obtain C1
    where s1: "(ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True) C,
                ktc_set_state (CRun (ktc_state cN') (ktc_state cD) False) C1)
                 ∈ ktm_step (delta_ktm (clock_product N D one))"
      and inv1: "clock_inv N D one C1 cN' cD" by blast
  from clock_step_D [OF qN' inv1 stepD tD headsD nhalt]
  obtain C2
    where s2: "(ktc_set_state (CRun (ktc_state cN') (ktc_state cD) False) C1,
                ktc_set_state (CRun (ktc_state cN') (ktc_state cD') True) C2)
                 ∈ ktm_step (delta_ktm (clock_product N D one))"
      and inv2: "clock_inv N D one C2 cN' cD'" by blast

  have both: "(ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True) C,
               ktc_set_state (CRun (ktc_state cN') (ktc_state cD') True) C2)
                ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ 2"
    using relcompI [OF s1 s2] by (simp add: numeral_2_eq_2)
  from both inv2 show thesis by (rule that)
qed


lemma clock_run:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blD: "bl_ktm D = bl_ktm N"
      and vcN0: "valid_config_ktm N cN0"
      and vcD0: "valid_config_ktm D cD0"
      and hN0: "heads_parked (k_ktm N) cN0"
      and hD0: "heads_parked (k_ktm D) cD0"
      and inv0: "clock_inv N D one C0 cN0 cD0"
      and runN: "(cN0, cN) ∈ (ktm_step (delta_ktm N)) ^^ m"
      and runD: "(cD0, cD) ∈ (ktm_step (delta_ktm D)) ^^ m"
      and nacc: "ktc_state cN ≠ t_ktm N"
      and nrej: "ktc_state cN ≠ r_ktm N"
      and nhalt: "ktc_state cD ≠ t_ktm D" "ktc_state cD ≠ r_ktm D"
    shows "∃C. (ktc_set_state (CRun (ktc_state cN0) (ktc_state cD0) True) C0,
                ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True) C)
                 ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ (2 * m)
             ∧ clock_inv N D one C cN cD"
  using runN runD nacc nrej nhalt
proof (induction m arbitrary: cN cD)
  case 0
  then show ?case using inv0 by auto
next
  case (Suc m)
  from Suc.prems(1) obtain c
    where cRun: "(cN0, c) ∈ (ktm_step (delta_ktm N)) ^^ m"
      and cStep: "(c, cN) ∈ ktm_step (delta_ktm N)" by auto
  from Suc.prems(2) obtain d
    where dRun: "(cD0, d) ∈ (ktm_step (delta_ktm D)) ^^ m"
      and dStep: "(d, cD) ∈ ktm_step (delta_ktm D)" by auto

  from cStep have cAlive: "ktc_state c ∉ {t_ktm N, r_ktm N}"
    using halt_state_sink [OF vN] by blast
  from dStep have dAlive: "ktc_state d ∉ {t_ktm D, r_ktm D}"
    using halt_state_sink [OF vD] by blast

  from Suc.IH [OF cRun dRun] cAlive dAlive obtain C1
    where prefix: "(ktc_set_state (CRun (ktc_state cN0) (ktc_state cD0) True) C0,
                    ktc_set_state (CRun (ktc_state c) (ktc_state d) True) C1)
                     ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ (2 * m)"
      and inv1: "clock_inv N D one C1 c d" by auto

  have qD: "ktc_state d ∈ Q_ktm D"
    by (rule valid_config_state [OF valid_reach_relpow_ktm [OF vD vcD0 dRun]])
  have vcN: "valid_config_ktm N cN"
    by (rule valid_reach_relpow_ktm [OF vN vcN0 Suc.prems(1)])
  have vcD: "valid_config_ktm D cD"
    by (rule valid_reach_relpow_ktm [OF vD vcD0 Suc.prems(2)])
  have hN: "heads_parked (k_ktm N) cN" by (rule heads_parked_run [OF vN hN0 Suc.prems(1)])
  have hD: "heads_parked (k_ktm D) cD" by (rule heads_parked_run [OF vD hD0 Suc.prems(2)])

  from clock_tick [OF inv1 blD qD cStep dStep vcN vcD hN hD
                      Suc.prems(3) Suc.prems(4) Suc.prems(5) Suc.prems(6)]
  obtain C2
    where tick: "(ktc_set_state (CRun (ktc_state c) (ktc_state d) True) C1,
                  ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True) C2)
                   ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ 2"
      and inv2: "clock_inv N D one C2 cN cD" by blast

  have arith: "2 * Suc m = 2 * m + 2" by simp
  from prefix tick
  have "(ktc_set_state (CRun (ktc_state cN0) (ktc_state cD0) True) C0,
         ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True) C2)
          ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ (2 * Suc m)"
    unfolding arith relpow_add by (rule relcompI)
  with inv2 show ?case by blast
qed


lemma clock_setup_inv:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blD: "bl_ktm D = bl_ktm N" and leD: "le_ktm D = le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
  shows "clock_inv N D one
           (KConfig Q (setup_tape N D one w 0) (setup_pos (k_ktm N) 0))
           (init_config_ktm N w)
           (init_config_ktm D (replicate (length w) one))"
proof -
  from vN have kN: "0 < k_ktm N" and SG: "Sigma_ktm N ⊆ Γ_ktm N"
    and blG: "bl_ktm N ∈ Γ_ktm N" and leG: "le_ktm N ∈ Γ_ktm N" by (cases N, auto)+
  from vD have kD: "0 < k_ktm D" by (cases D) auto
  have kt: "clock_tapes N D = k_ktm N + k_ktm D" by (simp add: clock_tapes_def)

  have pN: "proj_config 0 (k_ktm N) (bl_ktm N)
              (ktc_set_state (ktc_state (init_config_ktm N w))
                       (KConfig Q (setup_tape N D one w 0) (setup_pos (k_ktm N) 0)))
                = init_config_ktm N w" (is "?L = ?R")
  proof (rule ktc_config.expand, intro conjI)
    show "ktc_tape ?L = ktc_tape ?R"
      using kN kD
      by (simp add: setup_tape_def kt ktc_tape_init_config fun_eq_iff)
  qed (simp_all add: setup_pos_def fun_eq_iff)

  have pD: "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
              (ktc_set_state (ktc_state (init_config_ktm D (replicate (length w) one)))
                       (KConfig Q (setup_tape N D one w 0) (setup_pos (k_ktm N) 0)))
                = init_config_ktm D (replicate (length w) one)" (is "?L = ?R")
  proof (rule ktc_config.expand, intro conjI)
    have rep: "replicate (length w) one ! (m - Suc 0) = one"
      if "0 < m" and "m ≤ length w" for m
      using that by simp
    show "ktc_tape ?L = ktc_tape ?R"
      using kN kD blD leD
      by (simp add: setup_tape_def kt ktc_tape_init_config fun_eq_iff rep)
  qed (simp_all add: setup_pos_def fun_eq_iff)

  have wG: "w ! (m - 1) ∈ Γ_ktm N" if "m ≤ length w" and "0 < m" for m
  proof -
    from that have "w ! (m - 1) ∈ set w" by simp
    with w SG show ?thesis by blast
  qed
  have tG: "setup_tape N D one w 0 j m ∈ clock_Gamma N D one" for j m
    using wG blG leG by (auto simp: setup_tape_def clock_Gamma_def)
  have tB: "setup_tape N D one w 0 j m = bl_ktm N" if "clock_tapes N D ≤ j" for j m
  proof -
    from that kD have "j ≠ k_ktm N" and "¬ j < clock_tapes N D" by (auto simp: kt)
    then show ?thesis by (simp add: setup_tape_def)
  qed
  show ?thesis unfolding clock_inv_def using pN pD tG tB by simp
qed


lemma clock_accept_step:
  assumes p: "p ∈ Q_ktm D"
      and inv: "clock_inv N D one C cN cD"
      and step: "(cN, cN') ∈ ktm_step (delta_ktm N)"
      and acc: "ktc_state cN' = t_ktm N"
  shows "(ktc_set_state (CRun (ktc_state cN) p True) C,
          ktc_set_state CAcc (embed_update 0 (k_ktm N) C cN'))
           ∈ ktm_step (delta_ktm (clock_product N D one))"
proof -
  from inv have pN: "proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state (ktc_state cN) C) = cN"
    by (simp add: clock_inv_def)
  have step': "(proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state (ktc_state cN) C), cN')
                 ∈ ktm_step (delta_ktm N)"
    using pN step by simp
  have arm: "(ktc_set_state (CRun (ktc_state cN) p True) C,
              ktc_set_state CAcc (embed_update 0 (k_ktm N) C cN'))
               ∈ ktm_step (arm_N N D one)"
    using arm_N_step [OF p step' clock_inv_ctx [OF inv]] acc by simp
  have sub: "arm_N N D one ⊆ delta_ktm (clock_product N D one)" by auto
  from ktm_step_mono [OF sub] arm show ?thesis by blast
qed


subsection ‹Routing a step by its source state›


lemma setup_delta_src:
  assumes "(q, a, q', a', d) ∈ setup_delta N D one"
  shows "q = CWalk ∨ q = CBack"
  using assms by (auto simp: setup_delta_def)

lemma arm_N_src:
  assumes "(q, a, q', a', d) ∈ arm_N N D one"
  obtains r p where "q = CRun r p True"
  using assms by (auto simp: arm_N_def tag_delta_def)

lemma arm_D_src:
  assumes "(q, a, q', a', d) ∈ arm_D N D one"
  obtains r p where "q = CRun r p False"
  using assms by (auto simp: arm_D_def tag_delta_def)

lemma clock_step_cases:
  assumes step: "(C, C') ∈ ktm_step (delta_ktm (clock_product N D one))"
  obtains (Setup) "(C, C') ∈ ktm_step (setup_delta N D one)"
              and "ktc_state C = CWalk ∨ ktc_state C = CBack"
    | (ArmN) r p where "(C, C') ∈ ktm_step (arm_N N D one)"
              and "ktc_state C = CRun r p True"
    | (ArmD) r p where "(C, C') ∈ ktm_step (arm_D N D one)"
              and "ktc_state C = CRun r p False"
proof -
  from step have "(C, C') ∈ ktm_step (setup_delta N D one)
                            ∪ ktm_step (arm_N N D one)
                            ∪ ktm_step (arm_D N D one)"
    by (simp add: ktm_step_Un)
  then consider "(C, C') ∈ ktm_step (setup_delta N D one)"
    | "(C, C') ∈ ktm_step (arm_N N D one)"
    | "(C, C') ∈ ktm_step (arm_D N D one)" by blast
  then show thesis
  proof cases
    case 1
    then obtain a a' d
      where t: "(ktc_state C, a, ktc_state C', a', d) ∈ setup_delta N D one"
      by (rule ktm_step_states)
    from 1 setup_delta_src [OF t] show thesis by (rule Setup)
  next
    case 2
    then obtain a a' d
      where t: "(ktc_state C, a, ktc_state C', a', d) ∈ arm_N N D one"
      by (rule ktm_step_states)
    obtain r p where "ktc_state C = CRun r p True" by (rule arm_N_src [OF t])
    with 2 show thesis by (rule ArmN)
  next
    case 3
    then obtain a a' d
      where t: "(ktc_state C, a, ktc_state C', a', d) ∈ arm_D N D one"
      by (rule ktm_step_states)
    obtain r p where "ktc_state C = CRun r p False" by (rule arm_D_src [OF t])
    with 3 show thesis by (rule ArmD)
  qed
qed

lemma clock_step_setup:
  assumes step: "(C, C') ∈ ktm_step (delta_ktm (clock_product N D one))"
      and q: "ktc_state C = CWalk ∨ ktc_state C = CBack"
  shows "(C, C') ∈ ktm_step (setup_delta N D one)"
proof (rule clock_step_cases [OF step])
  assume "(C, C') ∈ ktm_step (setup_delta N D one)"
  then show ?thesis .
next
  fix r p assume "ktc_state C = CRun r p True"
  with q show ?thesis by simp
next
  fix r p assume "ktc_state C = CRun r p False"
  with q show ?thesis by simp
qed


lemma setup_delta_det:
  assumes "(q, a, q1, a1, d1) ∈ setup_delta N D one"
      and "(q, a, q2, a2, d2) ∈ setup_delta N D one"
  shows "(q1, a1, d1) = (q2, a2, d2)"
  using assms by (auto simp: setup_delta_def)

lemma arm_N_det:
  assumes vN: "valid_ktm N" and detN: "det_ktm N"
      and tr1: "(Q, A, Q1, A1, E1)
                    ∈ arm_N N D one"
      and tr2: "(Q, A, Q2, A2, E2)
                    ∈ arm_N N D one"
  shows "(Q1, A1, E1) = (Q2, A2, E2)"
proof -
  from tr1 obtain p1 where p1: "p1 ∈ Q_ktm D"
    and t1: "(Q, A, Q1, A1, E1)
       ∈ tag_delta (λq. CRun q p1 True)
          (λq'. if q' = t_ktm N then CAcc
                else if q' = r_ktm N then CRej else CRun q' p1 False)
          (embed_delta 0 (k_ktm N) (clock_tapes N D)
             (clock_Gamma N D one) (bl_ktm N) (delta_ktm N))"
    by (auto simp: arm_N_def)
  from tr2 obtain p2 where p2: "p2 ∈ Q_ktm D"
    and t2: "(Q, A, Q2, A2, E2)
       ∈ tag_delta (λq. CRun q p2 True)
          (λq'. if q' = t_ktm N then CAcc
                else if q' = r_ktm N then CRej else CRun q' p2 False)
          (embed_delta 0 (k_ktm N) (clock_tapes N D)
             (clock_Gamma N D one) (bl_ktm N) (delta_ktm N))"
    by (auto simp: arm_N_def)
  have peq: "p1 = p2" using t1 t2 by (auto simp: tag_delta_def)
  have det': "⋀q a p1 b1 d1 p2 b2 d2.
      (q, a, p1, b1, d1) ∈ delta_ktm N ⟹
      (q, a, p2, b2, d2) ∈ delta_ktm N ⟹
      (p1, b1, d1) = (p2, b2, d2)"
    using detN unfolding det_ktm_def by blast
  have sup: "⋀q a p b d. (q, a, p, b, d) ∈ delta_ktm N ⟹
      (⋀j. k_ktm N ≤ j ⟹ a j = bl_ktm N)"
    using valid_ktm_delta_support [OF vN] by blast
  note t2' = t2 [unfolded peq [symmetric]]
  show ?thesis
  proof (rule tag_delta_det [OF _ _ t1 t2'])
    show "inj (λq. CRun q p1 True)" by (auto intro: injI)
  qed (use det' sup in
        ‹rule embed_delta_det [where D = "delta_ktm N" and k = "k_ktm N" and bl = "bl_ktm N"]›)
qed

lemma arm_D_det:
  assumes vD: "valid_ktm D" and detD: "det_ktm D"
      and blD: "bl_ktm D = bl_ktm N"
      and tr1: "(Q, A, Q1, A1, E1)
                    ∈ arm_D N D one"
      and tr2: "(Q, A, Q2, A2, E2)
                    ∈ arm_D N D one"
  shows "(Q1, A1, E1) = (Q2, A2, E2)"
proof -
  from tr1 obtain p1 where p1: "p1 ∈ Q_ktm N"
    and t1: "(Q, A, Q1, A1, E1)
       ∈ tag_delta (λp. CRun p1 p False)
          (λp'. if p' = t_ktm D ∨ p' = r_ktm D then CRej
                else CRun p1 p' True)
          (embed_delta (k_ktm N) (k_ktm D) (clock_tapes N D)
             (clock_Gamma N D one) (bl_ktm N) (delta_ktm D))"
    by (auto simp: arm_D_def)
  from tr2 obtain p2 where p2: "p2 ∈ Q_ktm N"
    and t2: "(Q, A, Q2, A2, E2)
       ∈ tag_delta (λp. CRun p2 p False)
          (λp'. if p' = t_ktm D ∨ p' = r_ktm D then CRej
                else CRun p2 p' True)
          (embed_delta (k_ktm N) (k_ktm D) (clock_tapes N D)
             (clock_Gamma N D one) (bl_ktm N) (delta_ktm D))"
    by (auto simp: arm_D_def)
  have peq: "p1 = p2" using t1 t2 by (auto simp: tag_delta_def)
  have det': "⋀q a p1 b1 d1 p2 b2 d2.
      (q, a, p1, b1, d1) ∈ delta_ktm D ⟹
      (q, a, p2, b2, d2) ∈ delta_ktm D ⟹
      (p1, b1, d1) = (p2, b2, d2)"
    using detD unfolding det_ktm_def by blast
  have sup: "⋀q a p b d. (q, a, p, b, d) ∈ delta_ktm D ⟹
      (⋀j. k_ktm D ≤ j ⟹ a j = bl_ktm N)"
  proof -
    fix q a p b d
    assume tr: "(q, a, p, b, d) ∈ delta_ktm D"
    show "⋀j. k_ktm D ≤ j ⟹ a j = bl_ktm N"
    proof -
      fix j
      assume j: "k_ktm D ≤ j"
      from valid_ktm_delta_support [OF vD tr j]
        show "a j = bl_ktm N" using blD by simp
    qed
  qed
  note t2' = t2 [unfolded peq [symmetric]]
  show ?thesis
  proof (rule tag_delta_det [OF _ _ t1 t2'])
    show "inj (λp. CRun p1 p False)" by (auto intro: injI)
  qed (use det' sup in
        ‹rule embed_delta_det [where D = "delta_ktm D" and k = "k_ktm D" and bl = "bl_ktm N"]›)
qed

lemma clock_product_det:
  assumes vN: "valid_ktm N" and detN: "det_ktm N"
      and vD: "valid_ktm D" and detD: "det_ktm D"
      and blD: "bl_ktm D = bl_ktm N"
  shows "det_ktm (clock_product N D one)"
proof -
  show ?thesis
    unfolding det_ktm_def
  proof (intro allI impI)
    fix q a q1 b1 d1 q2 b2 d2
    assume t1: "(q, a, q1, b1, d1)
                    ∈ delta_ktm (clock_product N D one)"
       and t2: "(q, a, q2, b2, d2)
                    ∈ delta_ktm (clock_product N D one)"
    have t1':
        "(q, a, q1, b1, d1) ∈ setup_delta N D one
       ∨ (q, a, q1, b1, d1) ∈ arm_N N D one
       ∨ (q, a, q1, b1, d1) ∈ arm_D N D one"
      using t1 by (simp add: clock_product_simps)
    have t2':
        "(q, a, q2, b2, d2) ∈ setup_delta N D one
       ∨ (q, a, q2, b2, d2) ∈ arm_N N D one
       ∨ (q, a, q2, b2, d2) ∈ arm_D N D one"
      using t2 by (simp add: clock_product_simps)
    from t1' consider
        (S1) "(q, a, q1, b1, d1) ∈ setup_delta N D one"
      | (N1) "(q, a, q1, b1, d1) ∈ arm_N N D one"
      | (D1) "(q, a, q1, b1, d1) ∈ arm_D N D one"
      by blast
    then show "(q1, b1, d1) = (q2, b2, d2)"
    proof cases
      case S1
      from t2' consider
          (S2) "(q, a, q2, b2, d2) ∈ setup_delta N D one"
        | (N2) "(q, a, q2, b2, d2) ∈ arm_N N D one"
        | (D2) "(q, a, q2, b2, d2) ∈ arm_D N D one"
        by blast
      then show ?thesis
      proof cases
        case S2
        show ?thesis
          by (rule setup_delta_det [OF S1 S2])
      next
        case N2
        obtain r p where "q = CRun r p True"
          by (rule arm_N_src [OF N2])
        moreover have "q = CWalk ∨ q = CBack"
          by (rule setup_delta_src [OF S1])
        ultimately show ?thesis by simp
      next
        case D2
        obtain r p where "q = CRun r p False"
          by (rule arm_D_src [OF D2])
        moreover have "q = CWalk ∨ q = CBack"
          by (rule setup_delta_src [OF S1])
        ultimately show ?thesis by simp
      qed
    next
      case N1
      from t2' consider
          (S2) "(q, a, q2, b2, d2) ∈ setup_delta N D one"
        | (N2) "(q, a, q2, b2, d2) ∈ arm_N N D one"
        | (D2) "(q, a, q2, b2, d2) ∈ arm_D N D one"
        by blast
      then show ?thesis
      proof cases
        case S2
        obtain r p where "q = CRun r p True"
          by (rule arm_N_src [OF N1])
        moreover have "q = CWalk ∨ q = CBack"
          by (rule setup_delta_src [OF S2])
        ultimately show ?thesis by simp
      next
        case N2
        show ?thesis
          by (rule arm_N_det [OF vN detN N1 N2])
      next
        case D2
        obtain r p where "q = CRun r p True"
          by (rule arm_N_src [OF N1])
        moreover obtain r' p' where "q = CRun r' p' False"
          by (rule arm_D_src [OF D2])
        ultimately show ?thesis by simp
      qed
    next
      case D1
      from t2' consider
          (S2) "(q, a, q2, b2, d2) ∈ setup_delta N D one"
        | (N2) "(q, a, q2, b2, d2) ∈ arm_N N D one"
        | (D2) "(q, a, q2, b2, d2) ∈ arm_D N D one"
        by blast
      then show ?thesis
      proof cases
        case S2
        obtain r p where "q = CRun r p False"
          by (rule arm_D_src [OF D1])
        moreover have "q = CWalk ∨ q = CBack"
          by (rule setup_delta_src [OF S2])
        ultimately show ?thesis by simp
      next
        case N2
        obtain r p where "q = CRun r p False"
          by (rule arm_D_src [OF D1])
        moreover obtain r' p' where "q = CRun r' p' True"
          by (rule arm_N_src [OF N2])
        ultimately show ?thesis by simp
      next
        case D2
        show ?thesis
          by (rule arm_D_det [OF vD detD blD D1 D2])
      qed
    qed
  qed
qed

lemma clock_setup_det:
  assumes q: "ktc_state C = CWalk ∨ ktc_state C = CBack"
      and s1: "(C, C1) ∈ ktm_step (delta_ktm (clock_product N D one))"
      and s2: "(C, C2) ∈ ktm_step (delta_ktm (clock_product N D one))"
  shows "C1 = C2"
  by (rule ktm_step_functional
        [OF _ clock_step_setup [OF s1 q] clock_step_setup [OF s2 q]])
     (use setup_delta_det in blast)



lemma arm_N_tgt:
  assumes "(q, a, q', a', d) ∈ arm_N N D one"
  shows "q' ≠ CWalk ∧ q' ≠ CBack"
  using assms by (auto simp: arm_N_def tag_delta_def split: if_splits)

lemma arm_D_tgt:
  assumes "(q, a, q', a', d) ∈ arm_D N D one"
  shows "q' ≠ CWalk ∧ q' ≠ CBack"
  using assms by (auto simp: arm_D_def tag_delta_def split: if_splits)


lemma arm_D_acc:
  assumes "(q, a, q', a', d) ∈ arm_D N D one"
  shows "q' ≠ CAcc"
  using assms by (auto simp: arm_D_def tag_delta_def split: if_splits)

lemma arm_N_turn:
  "∀q a q' a' d. (q, a, q', a', d) ∈ arm_N N D one
      ⟶ cturn q ∧ ¬ (q = CAcc ∨ q = CRej)
          ∧ (cturn q' ⟶ q' = CAcc ∨ q' = CRej)"
  by (auto simp: arm_N_def tag_delta_def split: if_splits)

lemma arm_D_turn:
  "∀q a q' a' d. (q, a, q', a', d) ∈ arm_D N D one
      ⟶ ¬ cturn q ∧ ¬ (q = CAcc ∨ q = CRej)
          ∧ (¬ cturn q' ⟶ q' = CAcc ∨ q' = CRej)"
  by (auto simp: arm_D_def tag_delta_def split: if_splits)


lemma clock_arm_run:
  assumes run: "(C, C') ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ K"
      and qW: "ktc_state C ≠ CWalk" and qB: "ktc_state C ≠ CBack"
  shows "(C, C') ∈ (ktm_step (arm_N N D one ∪ arm_D N D one)) ^^ K"
  using run qW qB
proof (induction K arbitrary: C)
  case 0
  then show ?case by simp
next
  case (Suc K)
  from Suc.prems(1) obtain y
    where step: "(C, y) ∈ ktm_step (delta_ktm (clock_product N D one))"
      and rest: "(y, C') ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ K"
    by (blast dest: relpow_Suc_D2)
  from step have arm: "(C, y) ∈ ktm_step (arm_N N D one ∪ arm_D N D one)"
  proof (rule clock_step_cases)
    assume "ktc_state C = CWalk ∨ ktc_state C = CBack"
    with Suc.prems(2,3) show ?thesis by simp
  next
    fix r p assume "(C, y) ∈ ktm_step (arm_N N D one)"
    then show ?thesis by (simp add: ktm_step_Un)
  next
    fix r p assume "(C, y) ∈ ktm_step (arm_D N D one)"
    then show ?thesis by (simp add: ktm_step_Un)
  qed
  from arm obtain a a' d
    where t: "(ktc_state C, a, ktc_state y, a', d)
                ∈ arm_N N D one ∪ arm_D N D one"
    by (rule ktm_step_states)
  from t have yW: "ktc_state y ≠ CWalk" and yB: "ktc_state y ≠ CBack"
    using arm_N_tgt arm_D_tgt by blast+
  from arm Suc.IH [OF rest yW yB] show ?case by (rule relpow_Suc_I2)
qed


lemma clock_alternates:
  assumes run: "(C, C') ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ K"
      and qW: "ktc_state C ≠ CWalk" and qB: "ktc_state C ≠ CBack"
      and turn: "cturn (ktc_state C)"
  obtains f where "f 0 = C" and "f K = C'"
    and "⋀i. i ≤ K ⟹ ktc_state (f i) ≠ CAcc ⟹ ktc_state (f i) ≠ CRej
               ⟹ cturn (ktc_state (f i)) = even i"
    and "⋀i. i < K ⟹ even i ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_N N D one)"
    and "⋀i. i < K ⟹ odd i ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_D N D one)"
proof (rule arms_alternate
         [where final = "λq. q = CAcc ∨ q = CRej",
          OF arm_N_turn arm_D_turn clock_arm_run [OF run qW qB] turn])
  fix f
  assume f0: "f 0 = C" and fK: "f K = C'"
    and par: "⋀i. i ≤ K ⟹ ¬ (ktc_state (f i) = CAcc ∨ ktc_state (f i) = CRej)
               ⟹ cturn (ktc_state (f i)) = even i"
    and aN: "⋀i. i < K ⟹ even i ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_N N D one)"
    and aD: "⋀i. i < K ⟹ odd i ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_D N D one)"
  have par': "⋀i. i ≤ K ⟹ ktc_state (f i) ≠ CAcc ⟹ ktc_state (f i) ≠ CRej
                ⟹ cturn (ktc_state (f i)) = even i"
    using par by blast
  show thesis by (rule that [OF f0 fK par' aN aD])
qed


lemma clock_alternates_reach:
  assumes armN: "⋀i. i < K ⟹ even i
                   ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_N N D one)"
      and armD: "⋀i. i < K ⟹ odd i
                   ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_D N D one)"
      and i: "i ≤ K"
  shows "(f 0, f i) ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ i"
  using i
proof (induction i)
  case 0
  then show ?case by simp
next
  case (Suc i)
  from Suc.prems have ilt: "i < K" and ile: "i ≤ K" by simp_all
  have "(f i, f (Suc i)) ∈ ktm_step (arm_N N D one ∪ arm_D N D one)"
    using armN [OF ilt] armD [OF ilt] by (cases "even i") (simp_all add: ktm_step_Un)
  then have "(f i, f (Suc i)) ∈ ktm_step (delta_ktm (clock_product N D one))"
    by (simp add: ktm_step_Un)
  with Suc.IH [OF ile] show ?case by (rule relpow_Suc_I)
qed




subsection ‹A product step of one factor is a step of that factor›


lemma clock_inv_from_tapes:
  assumes pN: "proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state (ktc_state cN) C) = cN"
      and pD: "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
                 (ktc_set_state (ktc_state cD) C) = cD"
      and tapes: "ktc_tapes_fit (clock_Gamma N D one) (bl_ktm N) (clock_tapes N D) C"
  shows "clock_inv N D one C cN cD"
  unfolding clock_inv_def using pN pD tapes by (simp add: ktc_tapes_fit_def)

lemma arm_N_rev:
  assumes vN: "valid_ktm N"
      and inv: "clock_inv N D one C cN cD"
      and step: "(ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True) C, C2)
                   ∈ ktm_step (arm_N N D one)"
  obtains cN'
  where "(cN, cN') ∈ ktm_step (delta_ktm N)"
    and "ktc_state C2 = (if ktc_state cN' = t_ktm N then CAcc
                        else if ktc_state cN' = r_ktm N then CRej
                        else CRun (ktc_state cN') (ktc_state cD) False)"
    and "proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state (ktc_state cN') C2) = cN'"
    and "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
           (ktc_set_state (ktc_state cD) C2) = cD"
proof -
  let ?C1 = "ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True) C"
  let ?E = "embed_delta 0 (k_ktm N) (clock_tapes N D)
              (clock_Gamma N D one) (bl_ktm N) (delta_ktm N)"
  from step obtain p where p: "p ∈ Q_ktm D"
    and stepp: "(?C1, C2) ∈ ktm_step
                   (tag_delta (λq. CRun q p True)
                      (λq'. if q' = t_ktm N then CAcc else if q' = r_ktm N then CRej else CRun q' p False) ?E)"
    unfolding arm_N_def ktm_step_UN by blast
  from tag_step_rev [OF stepp] obtain q q'
    where s1: "ktc_state ?C1 = CRun q p True"
      and s2: "ktc_state C2 = (if q' = t_ktm N then CAcc else if q' = r_ktm N then CRej else CRun q' p False)"
      and emb: "(ktc_set_state q ?C1, ktc_set_state q' C2) ∈ ktm_step ?E"
    by blast
  from s1 have q: "q = ktc_state cN" and pd: "p = ktc_state cD" by simp_all

  have supp: "∀q a q' a' d. (q, a, q', a', d) ∈ delta_ktm N
                 ⟶ (∀j ≥ k_ktm N. a j = bl_ktm N ∧ a' j = bl_ktm N
                                     ∧ d j = MoveN)"
    using valid_ktm_delta_support [OF vN] by blast
  from embed_step_rev [OF emb supp]
  have proj: "(proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state q ?C1),
               proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state q' C2))
                ∈ ktm_step (delta_ktm N)" .
  from inv have pN: "proj_config 0 (k_ktm N) (bl_ktm N)
                       (ktc_set_state (ktc_state cN) C) = cN"
    and pD: "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
               (ktc_set_state (ktc_state cD) C) = cD"
    by (simp_all add: clock_inv_def)
  have src: "proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state q ?C1) = cN"
    using pN q by simp

  have outT: "ktc_tape C2 j = ktc_tape C j" if "k_ktm N ≤ j" for j
    using embed_step_outside [OF emb, of j] that by (simp add: ktc_set_state_def)
  have outP: "ktc_pos C2 j = ktc_pos C j" if "k_ktm N ≤ j" for j
    using embed_step_outside [OF emb, of j] that by (simp add: ktc_set_state_def)
  have frozen: "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
                  (ktc_set_state (ktc_state cD) C2)
                  = proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
                      (ktc_set_state (ktc_state cD) C)"
    by (rule ktc_config.expand, intro conjI)
       (simp_all add: proj_config_def ktc_set_state_def fun_eq_iff outT outP)

  show thesis
  proof (rule that)
    show "(cN, proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state q' C2))
            ∈ ktm_step (delta_ktm N)" using proj src by simp
    show "ktc_state C2
            = (if ktc_state (proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state q' C2))
                    = t_ktm N
               then CAcc
               else if ktc_state (proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state q' C2))
                    = r_ktm N
               then CRej
               else CRun (ktc_state (proj_config 0 (k_ktm N) (bl_ktm N)
                                      (ktc_set_state q' C2))) (ktc_state cD) False)"
      using s2 pd by (simp add: proj_config_state)
    show "proj_config 0 (k_ktm N) (bl_ktm N)
            (ktc_set_state (ktc_state (proj_config 0 (k_ktm N) (bl_ktm N)
                                  (ktc_set_state q' C2))) C2)
            = proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state q' C2)"
      by (simp add: proj_config_state)
    show "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
            (ktc_set_state (ktc_state cD) C2) = cD" using frozen pD by simp
  qed
qed



lemma arm_D_rev:
  assumes vD: "valid_ktm D" and blD: "bl_ktm D = bl_ktm N"
      and inv: "clock_inv N D one C cN cD"
      and step: "(ktc_set_state (CRun (ktc_state cN) (ktc_state cD) False) C, C2)
                   ∈ ktm_step (arm_D N D one)"
  obtains cD'
  where "(cD, cD') ∈ ktm_step (delta_ktm D)"
    and "ktc_state C2 = (if ktc_state cD' = t_ktm D ∨ ktc_state cD' = r_ktm D
                        then CRej
                        else CRun (ktc_state cN) (ktc_state cD') True)"
    and "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
           (ktc_set_state (ktc_state cD') C2) = cD'"
    and "proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state (ktc_state cN) C2) = cN"
proof -
  let ?C1 = "ktc_set_state (CRun (ktc_state cN) (ktc_state cD) False) C"
  let ?E = "embed_delta (k_ktm N) (k_ktm D) (clock_tapes N D)
              (clock_Gamma N D one) (bl_ktm N) (delta_ktm D)"
  from step obtain r where r: "r ∈ Q_ktm N"
    and stepr: "(?C1, C2) ∈ ktm_step
                   (tag_delta (λp. CRun r p False)
                      (λp'. if p' = t_ktm D ∨ p' = r_ktm D then CRej
                            else CRun r p' True) ?E)"
    unfolding arm_D_def ktm_step_UN by blast
  from tag_step_rev [OF stepr] obtain p p'
    where s1: "ktc_state ?C1 = CRun r p False"
      and s2: "ktc_state C2 = (if p' = t_ktm D ∨ p' = r_ktm D then CRej
                             else CRun r p' True)"
      and emb: "(ktc_set_state p ?C1, ktc_set_state p' C2) ∈ ktm_step ?E"
    by blast
  from s1 have rn: "r = ktc_state cN" and p: "p = ktc_state cD" by simp_all

  have supp: "∀q a q' a' d. (q, a, q', a', d) ∈ delta_ktm D
                 ⟶ (∀j ≥ k_ktm D. a j = bl_ktm N ∧ a' j = bl_ktm N
                                     ∧ d j = MoveN)"
  proof (intro allI impI)
    fix q a q' a' d j
    assume "(q, a, q', a', d) ∈ delta_ktm D" and "k_ktm D ≤ j"
    from valid_ktm_delta_support [OF vD this(1) this(2)]
    show "a j = bl_ktm N ∧ a' j = bl_ktm N ∧ d j = MoveN" by (simp add: blD)
  qed
  from embed_step_rev [OF emb supp]
  have proj: "(proj_config (k_ktm N) (k_ktm D) (bl_ktm N) (ktc_set_state p ?C1),
               proj_config (k_ktm N) (k_ktm D) (bl_ktm N) (ktc_set_state p' C2))
                ∈ ktm_step (delta_ktm D)" .
  from inv have pN: "proj_config 0 (k_ktm N) (bl_ktm N)
                       (ktc_set_state (ktc_state cN) C) = cN"
    and pD: "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
               (ktc_set_state (ktc_state cD) C) = cD"
    by (simp_all add: clock_inv_def)
  have src: "proj_config (k_ktm N) (k_ktm D) (bl_ktm N) (ktc_set_state p ?C1) = cD"
    using pD p by simp

  have outT: "ktc_tape C2 j = ktc_tape C j" if "j < k_ktm N" for j
    using embed_step_outside [OF emb, of j] that by (simp add: ktc_set_state_def)
  have outP: "ktc_pos C2 j = ktc_pos C j" if "j < k_ktm N" for j
    using embed_step_outside [OF emb, of j] that by (simp add: ktc_set_state_def)
  have frozen: "proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state (ktc_state cN) C2)
                  = proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state (ktc_state cN) C)"
    by (rule ktc_config.expand, intro conjI)
       (simp_all add: proj_config_def ktc_set_state_def fun_eq_iff outT outP)

  show thesis
  proof (rule that)
    show "(cD, proj_config (k_ktm N) (k_ktm D) (bl_ktm N) (ktc_set_state p' C2))
            ∈ ktm_step (delta_ktm D)" using proj src by simp
    show "ktc_state C2
            = (if ktc_state (proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
                              (ktc_set_state p' C2)) = t_ktm D
                  ∨ ktc_state (proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
                                 (ktc_set_state p' C2)) = r_ktm D
               then CRej
               else CRun (ktc_state cN)
                         (ktc_state (proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
                                      (ktc_set_state p' C2))) True)"
      using s2 rn by (simp add: proj_config_state)
    show "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
            (ktc_set_state (ktc_state (proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
                                  (ktc_set_state p' C2))) C2)
            = proj_config (k_ktm N) (k_ktm D) (bl_ktm N) (ktc_set_state p' C2)"
      by (simp add: proj_config_state)
    show "proj_config 0 (k_ktm N) (bl_ktm N) (ktc_set_state (ktc_state cN) C2) = cN"
      using frozen pN by simp
  qed
qed


subsection ‹The setup phase is forced›


lemma setup_config_state:
  assumes "i < 2 * length w + 3"
  shows "ktc_state (setup_config N D one w i) = CWalk
       ∨ ktc_state (setup_config N D one w i) = CBack"
  using assms by (auto simp: setup_config_def)

lemma setup_forced:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
      and run: "(init_config_ktm (clock_product N D one) w, z)
                  ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ i"
      and i: "i ≤ 2 * length w + 3"
  shows "z = setup_config N D one w i"
  using run i
proof (induction i arbitrary: z)
  case 0
  then show ?case by (simp add: setup_config_0)
next
  case (Suc i)
  from Suc.prems(1) obtain y
    where run: "(init_config_ktm (clock_product N D one) w, y)
                  ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ i"
      and step: "(y, z) ∈ ktm_step (delta_ktm (clock_product N D one))" by auto
  from Suc.prems(2) have ilt: "i < 2 * length w + 3" by simp
  from Suc.IH [OF run less_imp_le [OF ilt]] have y: "y = setup_config N D one w i" .
  have fwd: "(setup_config N D one w i, setup_config N D one w (Suc i))
               ∈ ktm_step (delta_ktm (clock_product N D one))"
    by (rule setup_config_step [OF vN vD blle w ilt])
  show ?case
    using clock_setup_det [OF setup_config_state [OF ilt] fwd step [unfolded y]]
    by simp
qed


lemma setup_forced_ge:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
      and run: "(init_config_ktm (clock_product N D one) w, z)
                  ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ M"
      and M: "2 * length w + 3 ≤ M"
  shows "(KConfig (clock_start_state N D)
                  (setup_tape N D one w 0) (setup_pos (k_ktm N) 0), z)
           ∈ (ktm_step (delta_ktm (clock_product N D one)))
                ^^ (M - (2 * length w + 3))"
proof -
  let ?R = "ktm_step (delta_ktm (clock_product N D one))"
  let ?m = "2 * length w + 3"
  from M have "M = ?m + (M - ?m)" by simp
  with run have "(init_config_ktm (clock_product N D one) w, z)
                   ∈ ?R ^^ ?m O ?R ^^ (M - ?m)"
    by (metis relpow_add)
  then obtain y
    where ay: "(init_config_ktm (clock_product N D one) w, y) ∈ ?R ^^ ?m"
      and yz: "(y, z) ∈ ?R ^^ (M - ?m)" by auto
  from setup_forced [OF vN vD blle w ay le_refl]
  have "y = setup_config N D one w ?m" .
  with yz show ?thesis by (simp add: setup_config_end)
qed

lemma clock_terminal_run:
  assumes terminal: "ktc_state C ∈ {CAcc, CRej}"
      and run: "(C, C') ∈
        (ktm_step (delta_ktm (clock_product N D one))) ^^ m"
  shows "m = 0 ∧ C' = C"
proof -
  have sink: "(C, E) ∉ ktm_step (delta_ktm (clock_product N D one))" for E
  proof
    assume step: "(C, E) ∈ ktm_step (delta_ktm (clock_product N D one))"
    show False
      by (rule clock_step_cases [OF step]) (use terminal in auto)
  qed
  have zero: "m = 0"
  proof (cases m)
    case 0
    then show ?thesis .
  next
    case (Suc n)
    from run [unfolded Suc] obtain E
      where "(C, E) ∈ ktm_step (delta_ktm (clock_product N D one))"
      by (blast dest: relpow_Suc_D2)
    with sink show ?thesis by blast
  qed
  with run show ?thesis by simp
qed

lemma clock_setup_terminal_run:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
      and run: "(init_config_ktm (clock_product N D one) w, z)
        ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ M"
      and M: "2 * length w + 3 ≤ M"
      and terminal: "clock_start_state N D ∈ {CAcc, CRej}"
  shows "M = 2 * length w + 3 ∧ ktc_state z = clock_start_state N D"
proof -
  have tail: "(KConfig (clock_start_state N D)
      (setup_tape N D one w 0) (setup_pos (k_ktm N) 0), z)
      ∈ (ktm_step (delta_ktm (clock_product N D one)))
        ^^ (M - (2 * length w + 3))"
    by (rule setup_forced_ge [OF vN vD blle w run M])
  have terminal': "ktc_state (KConfig (clock_start_state N D)
      (setup_tape N D one w 0) (setup_pos (k_ktm N) 0)) ∈ {CAcc, CRej}"
    using terminal by simp
  from clock_terminal_run [OF terminal' tail] M show ?thesis by auto
qed

lemma setup_forced_length:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and w: "set w ⊆ Sigma_ktm N"
      and run: "(init_config_ktm (clock_product N D one) w, z)
                  ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ M"
      and acc: "ktc_state z = CAcc"
  shows "2 * length w + 3 ≤ M"
proof (rule ccontr)
  assume "¬ 2 * length w + 3 ≤ M"
  then have M: "M < 2 * length w + 3" by simp
  from setup_forced [OF vN vD blle w run less_imp_le [OF M]]
  have "z = setup_config N D one w M" .
  with setup_config_state [where N = N and D = D and one = one, OF M] acc
  show False by simp
qed


subsection ‹The forward run›


lemma clock_accepts:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and st: "s_ktm N ≠ t_ktm N"
      and blle: "bl_ktm N ≠ le_ktm N"
      and blD: "bl_ktm D = bl_ktm N" and leD: "le_ktm D = le_ktm N"
      and oneD: "one ∈ Sigma_ktm D"
      and gn: "length w ≤ g (length w)"
      and alarm: "∃cfg. (init_config_ktm D (replicate (length w) one), cfg)
                           ∈ (ktm_step (delta_ktm D)) ^^ (g (length w))"
      and w: "set w ⊆ Sigma_ktm N"
      and acc: "accepts_in_time_ktm N w (g (length w))"
    shows "accepts_in_time_ktm (clock_product N D one) w (4 * g (length w) + 2)"
proof -
  let ?n = "length w"
  let ?R = "ktm_step (delta_ktm (clock_product N D one))"
  let ?cN0 = "init_config_ktm N w"
  let ?cD0 = "init_config_ktm D (replicate ?n one)"
  let ?C0 = "KConfig (undefined :: nat)
                      (setup_tape N D one w 0) (setup_pos (k_ktm N) 0)"

  from acc obtain m cN where mle: "m ≤ g ?n"
    and runN: "(?cN0, cN) ∈ (ktm_step (delta_ktm N)) ^^ m"
    and accN: "ktc_state cN = t_ktm N"
    unfolding accepts_in_time_ktm_def by blast

  have "m ≠ 0"
  proof
    assume "m = 0"
    with runN accN st show False by auto
  qed
  then obtain m' where m: "m = Suc m'" by (cases m) auto
  from runN [unfolded m] obtain cN'
    where runN': "(?cN0, cN') ∈ (ktm_step (delta_ktm N)) ^^ m'"
      and stepN: "(cN', cN) ∈ ktm_step (delta_ktm N)" by auto
  from stepN have aliveN: "ktc_state cN' ∉ {t_ktm N, r_ktm N}"
    using halt_state_sink [OF vN] by blast
  then have naccN: "ktc_state cN' ≠ t_ktm N" and nrejN: "ktc_state cN' ≠ r_ktm N"
    by simp_all

  from mle m have m'lt: "m' < g ?n" by simp
  from alarm obtain cfg
    where alarmD: "(?cD0, cfg) ∈ (ktm_step (delta_ktm D)) ^^ (g ?n)" ..
  have mpos: "0 < m" by (simp add: m)
  have gpos: "0 < g ?n" using mle m by simp
  have home: "clock_start_state N D = CRun (s_ktm N) (s_ktm D) True"
    using alarm_start_alive [OF vN runN mpos]
      alarm_start_alive [OF vD alarmD gpos]
    by (simp add: clock_start_state_def)
  from ktm_relpow_not_halted [OF vD alarmD m'lt] obtain cD'
    where runD': "(?cD0, cD') ∈ (ktm_step (delta_ktm D)) ^^ m'"
      and aliveD: "ktc_state cD' ∉ {t_ktm D, r_ktm D}" by blast
  from aliveD have nhaltD: "ktc_state cD' ≠ t_ktm D" "ktc_state cD' ≠ r_ktm D"
    by simp_all

  have vcN0: "valid_config_ktm N ?cN0" by (rule valid_init_config_ktm [OF vN w])
  have wD: "set (replicate ?n one) ⊆ Sigma_ktm D"
    using oneD by (auto simp: in_set_replicate)
  have vcD0: "valid_config_ktm D ?cD0" by (rule valid_init_config_ktm [OF vD wD])
  have inv0: "clock_inv N D one ?C0 ?cN0 ?cD0"
    by (rule clock_setup_inv [OF vN vD blD leD w])

  have setup_phase: "(init_config_ktm (clock_product N D one) w,
                      ktc_set_state (CRun (ktc_state ?cN0) (ktc_state ?cD0) True) ?C0)
                       ∈ ?R ^^ (2 * ?n + 3)"
    using setup_run [OF vN vD blle w] by (simp add: home ktc_set_state_def)

  from clock_run [OF vN vD blD vcN0 vcD0 heads_parked_init heads_parked_init inv0
                     runN' runD' naccN nrejN nhaltD(1) nhaltD(2)]
  obtain C
    where ticks: "(ktc_set_state (CRun (ktc_state ?cN0) (ktc_state ?cD0) True) ?C0,
                   ktc_set_state (CRun (ktc_state cN') (ktc_state cD') True) C)
                    ∈ ?R ^^ (2 * m')"
      and inv: "clock_inv N D one C cN' cD'" by blast

  from setup_phase ticks
  have prefix: "(init_config_ktm (clock_product N D one) w,
                 ktc_set_state (CRun (ktc_state cN') (ktc_state cD') True) C)
                  ∈ ?R ^^ ((2 * ?n + 3) + 2 * m')"
    unfolding relpow_add by (rule relcompI)

  have qD: "ktc_state cD' ∈ Q_ktm D"
    by (rule valid_config_state [OF valid_reach_relpow_ktm [OF vD vcD0 runD']])
  from prefix clock_accept_step [OF qD inv stepN accN]
  have whole: "(init_config_ktm (clock_product N D one) w,
                ktc_set_state CAcc (embed_update 0 (k_ktm N) C cN))
                 ∈ ?R ^^ Suc ((2 * ?n + 3) + 2 * m')"
    by (rule relpow_Suc_I)

  have bound: "Suc ((2 * ?n + 3) + 2 * m') ≤ 4 * g ?n + 2"
    using gn mle m by simp
  have accC: "ktc_state (ktc_set_state CAcc (embed_update 0 (k_ktm N) C cN))
                = t_ktm (clock_product N D one)"
    by (simp add: ktc_set_state_def)
  show ?thesis
    unfolding accepts_in_time_ktm_def using bound whole accC by blast
qed


subsection ‹The reverse run›


lemma clock_run_rev:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D"
      and blD: "bl_ktm D = bl_ktm N"
      and inv0: "clock_inv N D one C0 cN0 cD0"
      and aliveD0: "ktc_state cD0 ≠ t_ktm D" "ktc_state cD0 ≠ r_ktm D"
      and f0: "f 0 = ktc_set_state (CRun (ktc_state cN0) (ktc_state cD0) True) C0"
      and armN: "⋀i. i < K ⟹ even i
                   ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_N N D one)"
      and armD: "⋀i. i < K ⟹ odd i
                   ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_D N D one)"
      and tapes: "⋀i. i ≤ K ⟹
                    ktc_tapes_fit (clock_Gamma N D one) (bl_ktm N) (clock_tapes N D) (f i)"
      and j: "2 * j < K"
  shows "∃cN cD. (cN0, cN) ∈ (ktm_step (delta_ktm N)) ^^ j
               ∧ (cD0, cD) ∈ (ktm_step (delta_ktm D)) ^^ j
               ∧ ktc_state cD ≠ t_ktm D ∧ ktc_state cD ≠ r_ktm D
               ∧ ktc_state (f (2 * j)) = CRun (ktc_state cN) (ktc_state cD) True
               ∧ clock_inv N D one (ktc_set_state (0::nat) (f (2 * j))) cN cD"
  using j
proof (induction j)
  case 0
  have "(cN0, cN0) ∈ (ktm_step (delta_ktm N)) ^^ 0"
   and "(cD0, cD0) ∈ (ktm_step (delta_ktm D)) ^^ 0" by simp_all
  moreover have "ktc_state (f (2 * 0)) = CRun (ktc_state cN0) (ktc_state cD0) True"
    by (simp add: f0)
  moreover have "clock_inv N D one (ktc_set_state (0::nat) (f (2 * 0))) cN0 cD0"
    using inv0 by (simp add: f0)
  ultimately show ?case using aliveD0 by blast
next
  case (Suc j)
  have idx: "2 * Suc j = Suc (Suc (2 * j))" by simp
  from Suc.prems [unfolded idx] have lt3: "Suc (Suc (2 * j)) < K" .
  note lt2 = Suc_lessD [OF lt3]
  note lt1 = Suc_lessD [OF lt2]
  from Suc.IH [OF lt1] obtain cN cD
    where runN: "(cN0, cN) ∈ (ktm_step (delta_ktm N)) ^^ j"
      and runD: "(cD0, cD) ∈ (ktm_step (delta_ktm D)) ^^ j"
      and stf: "ktc_state (f (2 * j)) = CRun (ktc_state cN) (ktc_state cD) True"
      and inv: "clock_inv N D one (ktc_set_state (0::nat) (f (2 * j))) cN cD"
    by blast
  have ev1: "even (2 * j)" and od2: "odd (Suc (2 * j))"
   and ev3: "even (Suc (Suc (2 * j)))" by simp_all
  note sN = armN [OF lt1 ev1] and sD = armD [OF lt2 od2]
   and sN2 = armN [OF lt3 ev3]

  have srcN: "ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True) (f (2 * j)) = f (2 * j)"
    unfolding stf [symmetric] by simp
  have sN': "(ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True)
                      (ktc_set_state (0::nat) (f (2 * j))), f (Suc (2 * j)))
               ∈ ktm_step (arm_N N D one)"
    using sN by (simp add: srcN)
  from arm_N_rev [OF vN inv sN'] obtain cN'
    where stepN: "(cN, cN') ∈ ktm_step (delta_ktm N)"
      and tgtN: "ktc_state (f (Suc (2 * j)))
                   = (if ktc_state cN' = t_ktm N then CAcc
                      else if ktc_state cN' = r_ktm N then CRej
                      else CRun (ktc_state cN') (ktc_state cD) False)"
      and pN: "proj_config 0 (k_ktm N) (bl_ktm N)
                 (ktc_set_state (ktc_state cN') (f (Suc (2 * j)))) = cN'"
      and pD: "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
                 (ktc_set_state (ktc_state cD) (f (Suc (2 * j)))) = cD"
    by blast

  from sD obtain a a' d
    where tD: "(ktc_state (f (Suc (2 * j))), a,
                ktc_state (f (Suc (Suc (2 * j)))), a', d) ∈ arm_D N D one"
    by (rule ktm_step_states)
  from tD obtain r p where srcD: "ktc_state (f (Suc (2 * j))) = CRun r p False"
    by (rule arm_D_src)
  from srcD tgtN have nacc: "ktc_state cN' ≠ t_ktm N" "ktc_state cN' ≠ r_ktm N"
    by (auto split: if_splits)
  with tgtN have tgtN': "ktc_state (f (Suc (2 * j)))
                           = CRun (ktc_state cN') (ktc_state cD) False" by simp

  have inv1: "clock_inv N D one (ktc_set_state (0::nat) (f (Suc (2 * j)))) cN' cD"
  proof (rule clock_inv_from_tapes)
    show "proj_config 0 (k_ktm N) (bl_ktm N)
            (ktc_set_state (ktc_state cN') (ktc_set_state (0::nat) (f (Suc (2 * j))))) = cN'"
      using pN by simp
    show "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
            (ktc_set_state (ktc_state cD) (ktc_set_state (0::nat) (f (Suc (2 * j))))) = cD"
      using pD by simp
    show "ktc_tapes_fit (clock_Gamma N D one) (bl_ktm N) (clock_tapes N D)
            (ktc_set_state (0::nat) (f (Suc (2 * j))))"
      using tapes [OF less_imp_le [OF lt2]] by simp
  qed

  have srcD': "ktc_set_state (CRun (ktc_state cN') (ktc_state cD) False) (f (Suc (2 * j)))
                 = f (Suc (2 * j))"
    unfolding tgtN' [symmetric] by simp
  have sD': "(ktc_set_state (CRun (ktc_state cN') (ktc_state cD) False)
                      (ktc_set_state (0::nat) (f (Suc (2 * j)))), f (Suc (Suc (2 * j))))
               ∈ ktm_step (arm_D N D one)"
    using sD by (simp add: srcD')
  from arm_D_rev [OF vD blD inv1 sD'] obtain cD'
    where stepD: "(cD, cD') ∈ ktm_step (delta_ktm D)"
      and tgtD: "ktc_state (f (Suc (Suc (2 * j))))
                   = (if ktc_state cD' = t_ktm D ∨ ktc_state cD' = r_ktm D then CRej
                      else CRun (ktc_state cN') (ktc_state cD') True)"
      and pD2: "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
                  (ktc_set_state (ktc_state cD') (f (Suc (Suc (2 * j))))) = cD'"
      and pN2: "proj_config 0 (k_ktm N) (bl_ktm N)
                  (ktc_set_state (ktc_state cN') (f (Suc (Suc (2 * j))))) = cN'"
    by blast

  from sN2 obtain a2 a2' d2
    where t2: "(ktc_state (f (Suc (Suc (2 * j)))), a2,
                ktc_state (f (Suc (Suc (Suc (2 * j))))), a2', d2) ∈ arm_N N D one"
    by (rule ktm_step_states)
  from t2 obtain r2 p2
    where srcN2: "ktc_state (f (Suc (Suc (2 * j)))) = CRun r2 p2 True"
    by (rule arm_N_src)
  from srcN2 tgtD have aliveD': "ktc_state cD' ≠ t_ktm D" "ktc_state cD' ≠ r_ktm D"
    by (auto split: if_splits)
  with tgtD have tgtD': "ktc_state (f (Suc (Suc (2 * j))))
                           = CRun (ktc_state cN') (ktc_state cD') True" by simp

  have inv2: "clock_inv N D one (ktc_set_state (0::nat) (f (Suc (Suc (2 * j))))) cN' cD'"
  proof (rule clock_inv_from_tapes)
    show "proj_config 0 (k_ktm N) (bl_ktm N)
            (ktc_set_state (ktc_state cN') (ktc_set_state (0::nat) (f (Suc (Suc (2 * j)))))) = cN'"
      using pN2 by simp
    show "proj_config (k_ktm N) (k_ktm D) (bl_ktm N)
            (ktc_set_state (ktc_state cD') (ktc_set_state (0::nat) (f (Suc (Suc (2 * j)))))) = cD'"
      using pD2 by simp
    show "ktc_tapes_fit (clock_Gamma N D one) (bl_ktm N) (clock_tapes N D)
            (ktc_set_state (0::nat) (f (Suc (Suc (2 * j)))))"
      using tapes [OF less_imp_le [OF lt3]] by simp
  qed

  have rN: "(cN0, cN') ∈ (ktm_step (delta_ktm N)) ^^ Suc j"
    using runN stepN by (rule relpow_Suc_I)
  have rD: "(cD0, cD') ∈ (ktm_step (delta_ktm D)) ^^ Suc j"
    using runD stepD by (rule relpow_Suc_I)
  show ?case using rN rD aliveD' tgtD' inv2 unfolding idx by blast
qed


lemma clock_accepts_rev:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D" and det: "det_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and blD: "bl_ktm D = bl_ktm N" and leD: "le_ktm D = le_ktm N"
      and startD: "s_ktm D ≠ t_ktm D" "s_ktm D ≠ r_ktm D"
      and alarm: "(init_config_ktm D (replicate (length w) one), cfg)
                     ∈ (ktm_step (delta_ktm D)) ^^ (g (length w))"
      and halt: "ktc_state cfg = t_ktm D"
      and w: "set w ⊆ Sigma_ktm N"
      and run: "(init_config_ktm (clock_product N D one) w, z)
                  ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ M"
      and accz: "ktc_state z = CAcc"
    shows "accepts_in_time_ktm N w (g (length w))"
proof -
  let ?n = "length w"
  let ?R = "ktm_step (delta_ktm (clock_product N D one))"
  let ?cN0 = "init_config_ktm N w"
  let ?cD0 = "init_config_ktm D (replicate ?n one)"
  let ?C0 = "KConfig (undefined :: nat)
                      (setup_tape N D one w 0) (setup_pos (k_ktm N) 0)"
  let ?H = "KConfig (CRun (s_ktm N) (s_ktm D) True)
                    (setup_tape N D one w 0) (setup_pos (k_ktm N) 0)"
  have cpv: "valid_ktm (clock_product N D one)"
    by (rule clock_product_valid [OF vN vD blle blD leD])

  from setup_forced_length [OF vN vD blle w run accz] have Mge: "2 * ?n + 3 ≤ M" .
  show ?thesis
  proof (cases "clock_start_state N D ∈ {CAcc, CRej}")
    case True
    from clock_setup_terminal_run [OF vN vD blle w run Mge True] accz
    have start: "s_ktm N = t_ktm N"
      by (auto simp: clock_start_state_def split: if_splits)
    show ?thesis
      unfolding accepts_in_time_ktm_def
      by (intro exI [where x = 0] exI [where x = "init_config_ktm N w"])
        (simp add: start)
  next
    case False
    have home: "clock_start_state N D = CRun (s_ktm N) (s_ktm D) True"
      using False by (auto simp: clock_start_state_def split: if_splits)
    from setup_forced_ge [OF vN vD blle w run Mge]
    have tail: "(?H, z) ∈ ?R ^^ (M - (2 * ?n + 3))" by (simp add: home)
    define K where "K = M - (2 * ?n + 3)"
    with tail have tailK: "(?H, z) ∈ ?R ^^ K" by simp

    have qW: "ktc_state ?H ≠ CWalk" and qB: "ktc_state ?H ≠ CBack"
     and turn: "cturn (ktc_state ?H)" by simp_all
    from clock_alternates [OF tailK qW qB turn] obtain f
      where f0H: "f 0 = ?H" and fK: "f K = z"
        and armN: "⋀i. i < K ⟹ even i
                     ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_N N D one)"
        and armD: "⋀i. i < K ⟹ odd i
                     ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_D N D one)"
      by blast

    have Kpos: "K ≠ 0"
    proof
      assume K0: "K = 0"
      have zH: "z = ?H" by (rule sym [OF trans [OF f0H [symmetric] fK [unfolded K0]]])
      from accz [unfolded zH] show False by simp
    qed
    then obtain K' where K: "K = Suc K'" by (cases K) auto

    have K'lt: "K' < K" by (simp add: K)
    have evK': "even K'"
    proof (rule ccontr)
      assume odd: "¬ even K'"
      from armD [OF K'lt] odd obtain a a' d
        where "(ktc_state (f K'), a, ktc_state (f (Suc K')), a', d) ∈ arm_D N D one"
        by (blast elim: ktm_step_states)
      from arm_D_acc [OF this] fK accz show False by (simp add: K)
    qed
    then obtain m where m: "K' = 2 * m" by blast
    have mlt: "2 * m < K" using K'lt m by simp

    have wsig: "set w ⊆ Sigma_ktm (clock_product N D one)" using w by simp
    have vinit: "valid_config_ktm (clock_product N D one)
                   (init_config_ktm (clock_product N D one) w)"
      by (rule valid_init_config_ktm [OF cpv wsig])
    have tapes: "ktc_tapes_fit (clock_Gamma N D one) (bl_ktm N) (clock_tapes N D) (f i)"
      if ile: "i ≤ K" for i
    proof -
      have setup_phase:
        "(init_config_ktm (clock_product N D one) w, f 0) ∈ ?R ^^ (2 * ?n + 3)"
        using setup_run [OF vN vD blle w] by (simp add: home f0H)
      have arm: "(f 0, f i) ∈ ?R ^^ i"
        by (rule clock_alternates_reach [where f = f and K = K, OF armN armD ile])
      from setup_phase arm
      have "(init_config_ktm (clock_product N D one) w, f i)
              ∈ ?R ^^ ((2 * ?n + 3) + i)"
        unfolding relpow_add by (rule relcompI)
      from valid_reach_relpow_ktm [OF cpv vinit this]
      show ?thesis using valid_config_tapes_fit by fastforce
    qed

    have inv0: "clock_inv N D one ?C0 ?cN0 ?cD0"
      by (rule clock_setup_inv [OF vN vD blD leD w])
    have f0: "f 0 = ktc_set_state (CRun (ktc_state ?cN0) (ktc_state ?cD0) True) ?C0"
      by (simp add: f0H ktc_state_init_config ktc_set_state_def)
    have aliveD0: "ktc_state ?cD0 ≠ t_ktm D" "ktc_state ?cD0 ≠ r_ktm D"
      using startD by (simp_all add: ktc_state_init_config)

    from clock_run_rev [OF vN vD blD inv0 aliveD0 f0 armN armD tapes mlt]
    obtain cN cD
      where runN: "(?cN0, cN) ∈ (ktm_step (delta_ktm N)) ^^ m"
        and runD: "(?cD0, cD) ∈ (ktm_step (delta_ktm D)) ^^ m"
        and aliveD: "ktc_state cD ≠ t_ktm D" "ktc_state cD ≠ r_ktm D"
        and stf: "ktc_state (f (2 * m)) = CRun (ktc_state cN) (ktc_state cD) True"
        and inv: "clock_inv N D one (ktc_set_state (0::nat) (f (2 * m))) cN cD"
      by blast

    have mg: "m < g ?n"
      by (rule alarm_running_lt [OF vD det alarm halt runD aliveD])

    have srcN: "ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True) (f (2 * m)) = f (2 * m)"
      unfolding stf [symmetric] by simp
    have sN': "(ktc_set_state (CRun (ktc_state cN) (ktc_state cD) True)
                        (ktc_set_state (0::nat) (f (2 * m))), f (Suc (2 * m)))
                 ∈ ktm_step (arm_N N D one)"
      using armN [OF mlt] by (simp add: srcN)
    from arm_N_rev [OF vN inv sN'] obtain cN'
      where stepN: "(cN, cN') ∈ ktm_step (delta_ktm N)"
        and tgtN: "ktc_state (f (Suc (2 * m)))
                     = (if ktc_state cN' = t_ktm N then CAcc
                        else if ktc_state cN' = r_ktm N then CRej
                        else CRun (ktc_state cN') (ktc_state cD) False)"
      by blast
    have accN: "ktc_state cN' = t_ktm N"
      using tgtN fK accz by (simp add: K m split: if_splits)

    have runN': "(?cN0, cN') ∈ (ktm_step (delta_ktm N)) ^^ Suc m"
      using runN stepN by (rule relpow_Suc_I)
    show ?thesis
      unfolding accepts_in_time_ktm_def
    proof (intro exI conjI)
      show "Suc m ≤ g ?n" using mg by simp
      show "(?cN0, cN') ∈ (ktm_step (delta_ktm N)) ^^ Suc m" by (rule runN')
      show "ktc_state cN' = t_ktm N" by (rule accN)
    qed
  qed
qed

text ‹Every path, not only the accepting ones, ends within
  ‹2 n + 3 + 2 g n› steps.  The argument is ‹clock_accepts_rev›'s without the
  acceptance: past the setup, a run whose arm phase holds term‹g n› full
  ticks would leave the constructor alive after term‹g n› steps, which the
  alarm forbids.  This is the bound of Hopcroft and Ullman's convention for
  nondeterministic time, where no sequence of choices may run longer than the
  bound.›

lemma clock_run_bounded:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D" and det: "det_ktm D"
      and blle: "bl_ktm N ≠ le_ktm N"
      and blD: "bl_ktm D = bl_ktm N" and leD: "le_ktm D = le_ktm N"
      and startD: "s_ktm D ≠ t_ktm D" "s_ktm D ≠ r_ktm D"
      and alarm: "(init_config_ktm D (replicate (length w) one), cfg)
                     ∈ (ktm_step (delta_ktm D)) ^^ (g (length w))"
      and halt: "ktc_state cfg = t_ktm D"
      and w: "set w ⊆ Sigma_ktm N"
      and run: "(init_config_ktm (clock_product N D one) w, z)
                  ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ M"
    shows "M ≤ 2 * length w + 3 + 2 * g (length w)"
proof (cases "2 * length w + 3 ≤ M")
  case False
  then show ?thesis by simp
next
  case Mge: True
  show ?thesis
  proof (cases "clock_start_state N D ∈ {CAcc, CRej}")
    case True
    from clock_setup_terminal_run [OF vN vD blle w run Mge True]
    show ?thesis by simp
  next
    case False
    have home: "clock_start_state N D = CRun (s_ktm N) (s_ktm D) True"
      using False by (auto simp: clock_start_state_def split: if_splits)
    let ?n = "length w"
    let ?R = "ktm_step (delta_ktm (clock_product N D one))"
    let ?cN0 = "init_config_ktm N w"
    let ?cD0 = "init_config_ktm D (replicate ?n one)"
    let ?C0 = "KConfig (undefined :: nat)
                        (setup_tape N D one w 0) (setup_pos (k_ktm N) 0)"
    let ?H = "KConfig (CRun (s_ktm N) (s_ktm D) True)
                      (setup_tape N D one w 0) (setup_pos (k_ktm N) 0)"
    have cpv: "valid_ktm (clock_product N D one)"
      by (rule clock_product_valid [OF vN vD blle blD leD])
    from setup_forced_ge [OF vN vD blle w run Mge]
    have tail: "(?H, z) ∈ ?R ^^ (M - (2 * ?n + 3))" by (simp add: home)
    define K where "K = M - (2 * ?n + 3)"
    with tail have tailK: "(?H, z) ∈ ?R ^^ K" by simp
    have qW: "ktc_state ?H ≠ CWalk" and qB: "ktc_state ?H ≠ CBack"
     and turn: "cturn (ktc_state ?H)" by simp_all
    from clock_alternates [OF tailK qW qB turn] obtain f
      where f0H: "f 0 = ?H"
        and armN: "⋀i. i < K ⟹ even i
                     ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_N N D one)"
        and armD: "⋀i. i < K ⟹ odd i
                     ⟹ (f i, f (Suc i)) ∈ ktm_step (arm_D N D one)"
      by blast
    have "K ≤ 2 * g ?n"
    proof (rule ccontr)
      assume "¬ K ≤ 2 * g ?n"
      then have glt: "2 * g ?n < K" by simp
      have wsig: "set w ⊆ Sigma_ktm (clock_product N D one)" using w by simp
      have vinit: "valid_config_ktm (clock_product N D one)
                     (init_config_ktm (clock_product N D one) w)"
        by (rule valid_init_config_ktm [OF cpv wsig])
      have tapes: "ktc_tapes_fit (clock_Gamma N D one) (bl_ktm N) (clock_tapes N D) (f i)"
        if ile: "i ≤ K" for i
      proof -
        have setup_phase:
          "(init_config_ktm (clock_product N D one) w, f 0) ∈ ?R ^^ (2 * ?n + 3)"
        using setup_run [OF vN vD blle w] by (simp add: home f0H)
        have arm: "(f 0, f i) ∈ ?R ^^ i"
          by (rule clock_alternates_reach [where f = f and K = K, OF armN armD ile])
        from setup_phase arm
        have "(init_config_ktm (clock_product N D one) w, f i)
                ∈ ?R ^^ ((2 * ?n + 3) + i)"
          unfolding relpow_add by (rule relcompI)
        from valid_reach_relpow_ktm [OF cpv vinit this]
        show ?thesis using valid_config_tapes_fit by fastforce
      qed
      have inv0: "clock_inv N D one ?C0 ?cN0 ?cD0"
        by (rule clock_setup_inv [OF vN vD blD leD w])
      have f0: "f 0 = ktc_set_state (CRun (ktc_state ?cN0) (ktc_state ?cD0) True) ?C0"
        by (simp add: f0H ktc_state_init_config ktc_set_state_def)
      have aliveD0: "ktc_state ?cD0 ≠ t_ktm D" "ktc_state ?cD0 ≠ r_ktm D"
        using startD by (simp_all add: ktc_state_init_config)
      from clock_run_rev [OF vN vD blD inv0 aliveD0 f0 armN armD tapes glt]
      obtain cD
        where runD: "(?cD0, cD) ∈ (ktm_step (delta_ktm D)) ^^ g ?n"
          and aliveD: "ktc_state cD ≠ t_ktm D" "ktc_state cD ≠ r_ktm D"
        by blast
      from alarm_running_lt [OF vD det alarm halt runD aliveD] show False by simp
    qed
    then show ?thesis unfolding K_def by simp
  qed
qed

lemma clock_lang:
  assumes vN: "valid_ktm N" and vD: "valid_ktm D" and det: "det_ktm D"
      and st: "s_ktm N ≠ t_ktm N"
      and blle: "bl_ktm N ≠ le_ktm N"
      and blD: "bl_ktm D = bl_ktm N" and leD: "le_ktm D = le_ktm N"
      and oneD: "one ∈ Sigma_ktm D"
      and gn: "⋀n. n ≤ g n"
      and alarm: "⋀n. ∃cfg. (init_config_ktm D (replicate n one), cfg)
                              ∈ (ktm_step (delta_ktm D)) ^^ (g n)
                           ∧ ktc_state cfg = t_ktm D"
    shows "Lang_ktm (clock_product N D one)
             = {w. set w ⊆ Sigma_ktm N
                 ∧ accepts_in_time_ktm N w (g (length w))}"
proof -
  from alarm [of 1] obtain cfg1
    where a1: "(init_config_ktm D (replicate 1 one), cfg1)
                 ∈ (ktm_step (delta_ktm D)) ^^ (g 1)" by blast
  have "0 < g 1" using gn [of 1] by simp
  from alarm_start_alive [OF vD a1 this]
  have startD: "s_ktm D ≠ t_ktm D" "s_ktm D ≠ r_ktm D" by simp_all

  show ?thesis
  proof (rule set_eqI, rule iffI)
    fix w assume "w ∈ Lang_ktm (clock_product N D one)"
    then have wsig: "set w ⊆ Sigma_ktm N"
      and ex: "∃n. accepts_in_time_ktm (clock_product N D one) w n"
      unfolding Lang_ktm_iff by simp_all
    from ex obtain M z
      where run: "(init_config_ktm (clock_product N D one) w, z)
                    ∈ (ktm_step (delta_ktm (clock_product N D one))) ^^ M"
        and accz: "ktc_state z = t_ktm (clock_product N D one)"
      unfolding accepts_in_time_ktm_def by blast
    from accz have accz': "ktc_state z = CAcc" by simp
    from alarm [of "length w"] obtain cfg
      where al: "(init_config_ktm D (replicate (length w) one), cfg)
                   ∈ (ktm_step (delta_ktm D)) ^^ (g (length w))"
        and hl: "ktc_state cfg = t_ktm D" by blast
    from clock_accepts_rev [where g = g and w = w,
                            OF vN vD det blle blD leD startD al hl wsig run accz']
    show "w ∈ {w. set w ⊆ Sigma_ktm N
                ∧ accepts_in_time_ktm N w (g (length w))}"
      using wsig by simp
  next
    fix w assume "w ∈ {w. set w ⊆ Sigma_ktm N
                        ∧ accepts_in_time_ktm N w (g (length w))}"
    then have wsig: "set w ⊆ Sigma_ktm N"
      and acc: "accepts_in_time_ktm N w (g (length w))" by simp_all
    have alarmw: "∃cfg. (init_config_ktm D (replicate (length w) one), cfg)
                          ∈ (ktm_step (delta_ktm D)) ^^ (g (length w))"
      using alarm [of "length w"] by blast
    from clock_accepts [where g = g and w = w,
                        OF vN vD st blle blD leD oneD gn [of "length w"]
                           alarmw wsig acc]
    show "w ∈ Lang_ktm (clock_product N D one)"
      unfolding Lang_ktm_iff using wsig by auto
  qed
qed

end