Theory Multitape_Run_Facts

theory Multitape_Run_Facts
  imports Multitape_Time_Convention
begin

section ‹Facts about runs›

text ‹Everything here is about const‹ktm_step›, const‹Lang_ktm› or
  const‹valid_ktm› and mentions no machine construction at all.  These
  are the facts that constructions over the substrate kept re-proving: the
  theories after this one (relabelling, embedding, endmarker normalisation
  and clocks) all build on them.  Nothing here depends on any of those
  theories, which is the property to preserve --- if a lemma added here starts
  needing a combinator, it belongs in the theory that defines the combinator
  instead.

  The groups are unrelated to each other and are together only because
  they share that entry condition: acceptance and parked heads, the
  frozen-tape fact, and where the heads start and how far they get.  The
  step-relation algebra and the determinism facts are not here but in
  ‹Multitape_Substrate›, because the alphabet transformations and the tape
  reductions need them and import only that.›

subsection ‹Acceptance and parked heads›

text ‹const‹Lang_ktm› is defined by a reflexive-transitive closure reaching
  a configuration whose ∗‹shape› names the accepting state, while
  const‹accepts_in_time_ktm› is defined by a bounded power reaching a
  configuration whose ∗‹state› is accepting.  They say the same thing once
  the bound is existentially closed, and saying so once is what lets a
  language theorem be read off a timing theorem instead of repeating its
  induction.›

lemma Lang_ktm_iff:
  "w ∈ Lang_ktm M
     ⟷ set w ⊆ Sigma_ktm M ∧ (∃n. accepts_in_time_ktm M w n)"
proof
  assume "w ∈ Lang_ktm M"
  then obtain w' p where wS: "set w ⊆ Sigma_ktm M"
    and r: "(init_config_ktm M w, KConfig (t_ktm M) w' p)
              ∈ (ktm_step (delta_ktm M))*"
    by (auto simp: Lang_ktm_def)
  from r obtain n where "(init_config_ktm M w, KConfig (t_ktm M) w' p)
                           ∈ (ktm_step (delta_ktm M)) ^^ n"
    by (auto simp: rtrancl_power)
  then have "accepts_in_time_ktm M w n"
    unfolding accepts_in_time_ktm_def by force
  with wS show "set w ⊆ Sigma_ktm M ∧ (∃n. accepts_in_time_ktm M w n)"
    by blast
next
  assume "set w ⊆ Sigma_ktm M ∧ (∃n. accepts_in_time_ktm M w n)"
  then obtain n where wS: "set w ⊆ Sigma_ktm M"
    and acc: "accepts_in_time_ktm M w n" by blast
  from acc obtain m c
    where r: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ m"
      and tc: "ktc_state c = t_ktm M"
    by (auto simp: accepts_in_time_ktm_def)
  from r have "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M))*"
    by (auto simp: rtrancl_power)
  with tc wS show "w ∈ Lang_ktm M"
    by (cases c) (auto simp: Lang_ktm_def)
qed

text ‹The introduction and elimination rules for both predicates, phrased
  with a run of a given length ending in the accepting state.  A proof that
  holds such a run concludes either predicate without unfolding a definition,
  and one that holds either predicate gets the run back.›

lemma Lang_ktm_run:
  assumes "w ∈ Lang_ktm M"
  obtains n c where "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n"
    and "ktc_state c = t_ktm M"
proof -
  from assms obtain w' p
    where "(init_config_ktm M w, KConfig (t_ktm M) w' p)
             ∈ (ktm_step (delta_ktm M))*"
    by (auto simp: Lang_ktm_def)
  then obtain n
    where run: "(init_config_ktm M w, KConfig (t_ktm M) w' p)
                  ∈ (ktm_step (delta_ktm M)) ^^ n"
    by (auto simp: rtrancl_power)
  have st: "ktc_state (KConfig (t_ktm M) w' p) = t_ktm M" by simp
  from run st show ?thesis by (rule that)
qed

lemma accepts_in_timeI:
  assumes "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n"
      and "ktc_state c = t_ktm M" and "n ≤ T"
  shows "accepts_in_time_ktm M w T"
  using assms by (auto simp: accepts_in_time_ktm_def)

lemma accepts_in_timeE:
  assumes "accepts_in_time_ktm M w T"
  obtains n c where "n ≤ T"
    and "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n"
    and "ktc_state c = t_ktm M"
  using assms by (auto simp: accepts_in_time_ktm_def)

lemma Lang_ktmI:
  assumes w: "set w ⊆ Sigma_ktm M"
      and run: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n"
      and st: "ktc_state c = t_ktm M"
  shows "w ∈ Lang_ktm M"
proof -
  from run have r: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M))*"
    by (auto simp: rtrancl_power)
  obtain p ts n' where cc: "c = KConfig p ts n'" by (cases c) auto
  with st have "c = KConfig (t_ktm M) ts n'" by simp
  with r w show ?thesis by (auto simp: Lang_ktm_def)
qed

text ‹❙‹The heads beyond the tape count stay at the origin.›
  const‹valid_config_ktm› records that those tapes are blank but says
  nothing about where their heads are, and the widening needs to know ---
  its new tapes carry an endmarker in cell 0, so the machine reads that
  endmarker only if the head is there.  It is true for the same reason the
  tapes stay blank: const‹valid_ktm›'s support invariant makes every
  transition stationary beyond the count, and the initial configuration parks
  every head at 0.  Kept as a separate predicate rather than folded into
  const‹valid_config_ktm›, which is the substrate's and not ours.›

definition heads_parked :: "nat ⇒ ('a, 'q) ktc_config ⇒ bool" where
  "heads_parked k c ⟷ (∀j. k ≤ j ⟶ ktc_pos c j = 0)"

lemma heads_parked_init: "heads_parked k (init_config_ktm M w)"
  by (cases M) (simp add: heads_parked_def)

lemma heads_parked_step:
  assumes vM: "valid_ktm M"
      and hp: "heads_parked (k_ktm M) c"
      and step: "(c, c') ∈ ktm_step (delta_ktm M)"
  shows "heads_parked (k_ktm M) c'"
proof -
  from step obtain q ts n q' a d
    where c: "c = KConfig q ts n"
      and c': "c' = KConfig q' (λj. (ts j)(n j := a j))
                              (λj. go_move (d j) (n j))"
      and tr: "(q, λj. ts j (n j), q', a, d) ∈ delta_ktm M"
    by (auto elim!: ktm_step.cases)
  show ?thesis
    unfolding heads_parked_def
  proof (intro allI impI)
    fix j assume j: "k_ktm M ≤ j"
    from valid_ktm_delta_support [OF vM tr j] have "d j = MoveN" by simp
    moreover from hp j c have "n j = 0" by (simp add: heads_parked_def)
    ultimately show "ktc_pos c' j = 0" using c' by simp
  qed
qed

lemma heads_parked_run:
  assumes vM: "valid_ktm M"
      and hp: "heads_parked (k_ktm M) c"
      and run: "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ n"
  shows "heads_parked (k_ktm M) c'"
  using relpow_imp_rtrancl [OF run]
  by (induction rule: rtrancl_induct) (auto intro: hp heads_parked_step [OF vM])


subsection ‹Freezing a tape›

text ‹The half of a two-machine composite that is ∗‹not› moving.  When two
  machines run side by side on disjoint tapes --- in lockstep or by turns ---
  every transition of the composite is an action of one factor extended over
  the other factor's tapes, and the extension has to be inert: read what is
  there, write it back, stay put.  The lemma says that such a tuple does
  exactly nothing to that tape.

  ‹ktm_step_no_write_tape› is the all-tapes version and is not usable here,
  because the moving factor does write.  The relativisation is stated
  ∗‹per index› rather than per set, which is the weaker hypothesis and the one
  a composite actually supplies: its arms are inert on a range of indices, and
  a range is just a conjunction of indices.

  ❙‹The head is part of the claim, and is the half that does not come for
  free.›  ‹ktm_step_tape_off_head› already gives cell preservation away from
  the head, so the tape contents would follow from the write component alone.
  The head position would not --- and a frozen tape must keep its head where it
  was, or the factor's next turn resumes in the wrong place.  It is the
  direction component that carries that, which is why the hypothesis names
  both.›

lemma ktm_step_frozen_tape:
  assumes step: "(c, c') ∈ ktm_step δ"
    and frozen: "∀q a q' a' d. (q, a, q', a', d) ∈ δ
                    ⟶ a' j = a j ∧ d j = MoveN"
  shows "ktc_tape c' j = ktc_tape c j ∧ ktc_pos c' j = ktc_pos c j"
proof -
  from step obtain q ts n q' a dr where
      c_eq:  "c = KConfig q ts n"
    and c'_eq: "c' = KConfig q'
                       (λk. (ts k)(n k := a k))
                       (λk. go_move (dr k) (n k))"
    and tr: "(q, λk. ts k (n k), q', a, dr) ∈ δ"
    by (auto elim: ktm_step.cases)
  from frozen [rule_format, OF tr] have aj: "a j = ts j (n j)"
    and dj: "dr j = MoveN"
    by simp_all
  from aj have "(ts j)(n j := a j) = ts j" by auto
  moreover from dj have "go_move (dr j) (n j) = n j" by simp
  ultimately show ?thesis by (simp add: c_eq c'_eq)
qed


subsection ‹Every head starts at the origin›

text ‹❙‹‹ktc_pos_init_config› paired with
  ‹ktm_relpow_pos_displacement›, because the caller should not have to
  write the step count twice.›  The pairing is what turns a step count into a
  head bound --- the reason a run lemma need not report a head it never
  promised.  A head that starts at the origin and moves at most
  one cell a step is bounded by ∗‹any› bound on the step count, so a phase
  that already reports its cost reports every head it never mentioned.  Stated
  over an abstract term‹n› and term‹B› rather than inline at the call site:
  the counts this composes with are twenty-line terms, and quoting one to
  instantiate ‹ktm_relpow_pos_displacement› and again to bound it invites
  the two copies to be spelled differently.›

lemma ktm_relpow_pos_bound:
  assumes run: "(init_config_ktm M w, Z) ∈ (ktm_step (delta_ktm M)) ^^ n"
      and nB: "n ≤ B"
  shows "ktc_pos Z k ≤ B"
proof -
  have "ktc_pos Z k ≤ ktc_pos (init_config_ktm M w) k + n"
    using ktm_relpow_pos_displacement [OF run, of k] by blast
  then have "ktc_pos Z k ≤ n" by simp
  with nB show ?thesis by simp
qed


end