Theory Multitape_Time_Convention

theory Multitape_Time_Convention
  imports Multitape_Finite_Patch
begin

section ‹Time bounds in the textbook convention, and the cleanup›

text ‹Shared vocabulary for the linear-speedup consumers.  An
  ∗‹eventual› bound holds for all long enough inputs in the language; a
  ∗‹convention› bound is the Hopcroft--Ullman
  cite‹‹p.~291› in "Hopcroft1979:introduction"› ‹max(n+1, ...)› form on
  the substrate, where the floor is ‹n + 2› (the substrate reads the
  left endmarker before the first input symbol).›

definition time_bounded_ev :: "('q, 'a) ktm ⇒ (nat ⇒ nat) ⇒ bool" where
  "time_bounded_ev M g ⟷
     (∃N. ∀w∈Lang_ktm M. N ≤ length w
             ⟶ accepts_in_time_ktm M w (g (length w)))"

definition time_bounded_conv :: "('q, 'a) ktm ⇒ (nat ⇒ nat) ⇒ bool" where
  "time_bounded_conv M g ⟷
     (∀w∈Lang_ktm M.
        accepts_in_time_ktm M w (max (length w + 2) (g (length w))))"

text ‹The cleanup corollary: an eventual bound is upgraded to a
  convention bound on ∗‹all› inputs, at the cost of the finite-control
  overhead ‹c0 = 2 * N + 4›, with language, tape count, and determinism
  preserved.  Instantiates @{const finite_patch} with the (finite, hence
  unconditionally available) table ‹w ∈ Lang_ktm M›.

  Hypotheses are the weakest the proof uses --- @{const valid_ktm} and
  ‹bl_ktm M ≠ le_ktm M›, matching the @{const finite_patch} contract
  lemmas it composes (‹finite_patch_language› / ‹_det› /
  ‹fp_short_time› / ‹fp_long_time›).  In particular it does ∗‹not›
  require @{const le_unique} or the state distinctness of
  @{const well_formed_ktm}, so it applies to machines (e.g. the
  encoding wrap) whose ‹le›-uniqueness is not separately established.›

theorem time_cleanup:
  assumes vM: "valid_ktm M" and blle: "bl_ktm M ≠ le_ktm M"
    and ev: "time_bounded_ev M g"
  obtains N where
    "Lang_ktm (finite_patch M (λw. w ∈ Lang_ktm M) N) = Lang_ktm M"
    and "k_ktm (finite_patch M (λw. w ∈ Lang_ktm M) N) = k_ktm M"
    and "det_ktm M ⟶ det_ktm (finite_patch M (λw. w ∈ Lang_ktm M) N)"
    and "time_bounded_conv (finite_patch M (λw. w ∈ Lang_ktm M) N)
           (λn. g n + (2 * N + 4))"
proof -
  from ev obtain N where evN: "∀w∈Lang_ktm M. N ≤ length w
                                 ⟶ accepts_in_time_ktm M w (g (length w))"
    unfolding time_bounded_ev_def by blast
  let ?M' = "finite_patch M (λw. w ∈ Lang_ktm M) N"
  have lang: "Lang_ktm ?M' = Lang_ktm M"
  proof -
    have "Lang_ktm ?M' = {w. set w ⊆ Sigma_ktm M
             ∧ (if length w ≤ N then w ∈ Lang_ktm M else w ∈ Lang_ktm M)}"
      by (rule finite_patch_language[OF vM blle])
    also have "… = {w. set w ⊆ Sigma_ktm M ∧ w ∈ Lang_ktm M}" by simp
    also have "… = Lang_ktm M" unfolding Lang_ktm_def by auto
    finally show ?thesis .
  qed
  have kpres: "k_ktm ?M' = k_ktm M" by (rule finite_patch_k_ktm)
  have detpres: "det_ktm M ⟶ det_ktm ?M'"
    using finite_patch_det[OF vM blle] by blast
  have conv: "time_bounded_conv ?M' (λn. g n + (2 * N + 4))"
    unfolding time_bounded_conv_def
  proof
    fix w assume "w ∈ Lang_ktm ?M'"
    hence wL: "w ∈ Lang_ktm M" using lang by simp
    have wSg: "set w ⊆ Sigma_ktm M" using wL unfolding Lang_ktm_def by simp
    show "accepts_in_time_ktm ?M' w
            (max (length w + 2) ((λn. g n + (2 * N + 4)) (length w)))"
    proof (cases "length w ≤ N")
      case True
      have "accepts_in_time_ktm ?M' w (length w + 2)"
        using vM wSg True wL by (rule fp_short_time)
      moreover have "length w + 2 ≤ max (length w + 2) (g (length w) + (2 * N + 4))"
        by simp
      ultimately show ?thesis by (auto elim: accepts_in_time_ktm_mono)
    next
      case False
      hence Nlt: "N < length w" by simp
      have "accepts_in_time_ktm M w (g (length w))" using evN wL Nlt by simp
      hence "accepts_in_time_ktm ?M' w (g (length w) + (2 * N + 4))"
        by (rule fp_long_time[OF vM wSg Nlt])
      moreover have "g (length w) + (2 * N + 4)
                       ≤ max (length w + 2) (g (length w) + (2 * N + 4))" by simp
      ultimately show ?thesis by (auto elim: accepts_in_time_ktm_mono)
    qed
  qed
  show thesis
  proof (rule that[of N])
    show "Lang_ktm ?M' = Lang_ktm M" by (rule lang)
    show "k_ktm ?M' = k_ktm M" by (rule kpres)
    show "det_ktm M ⟶ det_ktm ?M'" by (rule detpres)
    show "time_bounded_conv ?M' (λn. g n + (2 * N + 4))" by (rule conv)
  qed
qed


subsection ‹The clean convention form is unattainable in general›

text ‹Why the linear-‹T› speedup theorems are stated with a residual
  ‹+K› (all inputs) or an explicit threshold (eventual), never as the clean
  ‹time_bounded_conv M (λn. n + n div q)› on ∗‹all› inputs: that clean form
  is not attainable for a machine whose small-input computation exceeds the
  convention floor ‹n + 2›.  The minimal witness ‹conv_cex_ktm› below
  (the convention's counterexample) is a deterministic, valid machine over the
  empty input alphabet that accepts the empty input in exactly
  ∗‹three› steps (state chain ‹0 → 1 → 2 → 3›, reading and
  rewriting the left endmarker in place), one more than the floor
  ‹length [] + 2 = 2›.  So ‹[] ∈ Lang_ktm conv_cex_ktm› yet
  ‹¬ accepts_in_time_ktm conv_cex_ktm [] 2›, hence
  ‹time_bounded_conv conv_cex_ktm (λn. n + n div q)› fails at ‹[]› for
  every ‹q›.  ‹conv_cex_ktm› stands in for the encoding wrap, whose
  own setup phases (‹W_Init → W_Buf → W_Reset → W_Disp›) likewise exceed the
  floor on tiny inputs; closing the small-input band needs the non-effective
  finite-exceptions table (an existence-only object; see ‹time_cleanup›),
  which is exactly what the clean form would
  demand and what the speedup construction does not build.›

definition conv_cex_delta ::
  "(nat × (nat ⇒ nat) × nat × (nat ⇒ nat) × (nat ⇒ move)) set" where
  "conv_cex_delta = {(0, one_tape_read 1, 1, one_tape_read 1, λ_. MoveN),
                     (1, one_tape_read 1, 2, one_tape_read 1, λ_. MoveN),
                     (2, one_tape_read 1, 3, one_tape_read 1, λ_. MoveN)}"

definition conv_cex_ktm :: "(nat, nat) ktm" where
  "conv_cex_ktm = KTM {0,1,2,3,4} {} {0,1} 0 1 conv_cex_delta 0 3 4 1"

definition conv_cex_tape :: "nat ⇒ nat ⇒ nat" where
  "conv_cex_tape = (λi n. if i = 0 ∧ n = 0 then 1 else 0)"

abbreviation conv_cex_cfg :: "nat ⇒ (nat, nat) ktc_config" where
  "conv_cex_cfg q ≡ KConfig q conv_cex_tape (λ_. 0)"

lemma conv_cex_delta_ktm: "delta_ktm conv_cex_ktm = conv_cex_delta"
  by (simp add: conv_cex_ktm_def)
lemma conv_cex_t_ktm: "t_ktm conv_cex_ktm = 3" by (simp add: conv_cex_ktm_def)

lemma conv_cex_read_eq: "(λk. conv_cex_tape k ((λ_. 0::nat) k)) = one_tape_read 1"
  by (simp add: conv_cex_tape_def one_tape_read_def fun_eq_iff)

lemma conv_cex_valid: "valid_ktm conv_cex_ktm"
  by (auto simp: conv_cex_ktm_def conv_cex_delta_def one_tape_read_def Pi_iff)

lemma conv_cex_det: "det_ktm conv_cex_ktm"
  by (auto simp: det_ktm_def conv_cex_delta_ktm conv_cex_delta_def)

lemma conv_cex_init: "init_config_ktm conv_cex_ktm [] = conv_cex_cfg 0"
  by (auto simp: conv_cex_ktm_def conv_cex_tape_def fun_eq_iff)

text ‹Forward: each state ‹m ≤ 2› steps deterministically to ‹m + 1›, the
  tape and heads unchanged (the endmarker is re-read and re-written in place).›

lemma conv_cex_step_fwd:
  assumes "m ≤ 2"
  shows "(conv_cex_cfg m, conv_cex_cfg (Suc m)) ∈ ktm_step conv_cex_delta"
proof -
  have mem: "(m, one_tape_read 1, Suc m, one_tape_read 1, λ_. MoveN) ∈ conv_cex_delta"
    using assms unfolding conv_cex_delta_def by (cases m; simp; presburger)
  have upd: "(λk. (conv_cex_tape k)((λ_. 0::nat) k := one_tape_read 1 k)) = conv_cex_tape"
    by (simp add: conv_cex_tape_def one_tape_read_def fun_eq_iff)
  have mov: "(λk. go_move ((λ_. MoveN) k) ((λ_. 0::nat) k)) = (λ_. 0)"
    by simp
  have "(KConfig m conv_cex_tape (λ_. 0),
         KConfig (Suc m) (λk. (conv_cex_tape k)((λ_. 0) k := one_tape_read 1 k))
                          (λk. go_move ((λ_. MoveN) k) ((λ_. 0) k)))
          ∈ ktm_step conv_cex_delta"
    by (rule ktm_step.step) (use mem conv_cex_read_eq in simp)
  thus ?thesis using upd mov by simp
qed

text ‹Backward: from state ‹m› the ∗‹only› successor is state ‹m + 1› ---
  the single ‹conv_cex_delta› entry with source ‹m›, tape and heads fixed.›

lemma conv_cex_delta_inv:
  "(m, one_tape_read 1, q', a, move) ∈ conv_cex_delta ⟹ q' = Suc m ∧ a = one_tape_read 1 ∧ move = (λ_. MoveN)"
  by (auto simp: conv_cex_delta_def)

lemma conv_cex_step_unique:
  "(conv_cex_cfg m, cM) ∈ ktm_step conv_cex_delta ⟹ cM = conv_cex_cfg (Suc m)"
  by (auto elim!: ktm_step.cases
           simp: conv_cex_delta_def conv_cex_tape_def one_tape_read_def fun_eq_iff)

text ‹Reachability: in ‹n ≤ 2› steps from the start the machine is in state
  ‹n ≤ 2 ≠ 3› --- so it cannot have accepted.›

lemma conv_cex_reach:
  "(conv_cex_cfg 0, cM) ∈ (ktm_step conv_cex_delta) ^^ n ⟹ n ≤ 2 ⟹ cM = conv_cex_cfg n"
proof (induction n arbitrary: cM)
  case 0
  then show ?case by simp
next
  case (Suc m)
  from Suc.prems(1) obtain c where
    rm: "(conv_cex_cfg 0, c) ∈ (ktm_step conv_cex_delta) ^^ m" and
    st: "(c, cM) ∈ ktm_step conv_cex_delta"
    by (auto elim: relpow_Suc_E)
  have "m ≤ 2" using Suc.prems(2) by simp
  from Suc.IH[OF rm this] have "c = conv_cex_cfg m" .
  with st have "(conv_cex_cfg m, cM) ∈ ktm_step conv_cex_delta" by simp
  from conv_cex_step_unique[OF this] show ?case .
qed

lemma conv_cex_lang: "[] ∈ Lang_ktm conv_cex_ktm"
proof -
  have s0: "(conv_cex_cfg 0, conv_cex_cfg (Suc 0)) ∈ ktm_step conv_cex_delta"
    by (rule conv_cex_step_fwd) simp
  have s1: "(conv_cex_cfg (Suc 0), conv_cex_cfg (Suc (Suc 0))) ∈ ktm_step conv_cex_delta"
    by (rule conv_cex_step_fwd) simp
  have s2: "(conv_cex_cfg (Suc (Suc 0)), conv_cex_cfg (Suc (Suc (Suc 0)))) ∈ ktm_step conv_cex_delta"
    by (rule conv_cex_step_fwd) simp
  have "(conv_cex_cfg 0, conv_cex_cfg (Suc (Suc (Suc 0)))) ∈ (ktm_step conv_cex_delta) ^^ (Suc (Suc (Suc 0)))"
    by (rule relpow_Suc_I2[OF s0 relpow_Suc_I2[OF s1 relpow_Suc_I2[OF s2 relpow_0_I]]])
  hence "(conv_cex_cfg 0, conv_cex_cfg (Suc (Suc (Suc 0)))) ∈ (ktm_step conv_cex_delta)*"
    by (rule relpow_imp_rtrancl)
  hence "(init_config_ktm conv_cex_ktm [], KConfig (t_ktm conv_cex_ktm) conv_cex_tape (λ_. 0))
           ∈ (ktm_step (delta_ktm conv_cex_ktm))*"
    by (simp add: conv_cex_init conv_cex_delta_ktm conv_cex_t_ktm numeral_3_eq_3)
  thus ?thesis
    unfolding Lang_ktm_def by (auto simp: conv_cex_ktm_def)
qed

lemma conv_cex_not_accepts: "¬ accepts_in_time_ktm conv_cex_ktm [] 2"
proof
  assume "accepts_in_time_ktm conv_cex_ktm [] 2"
  then obtain n cM where nle: "n ≤ 2"
    and reach: "(init_config_ktm conv_cex_ktm [], cM) ∈ (ktm_step (delta_ktm conv_cex_ktm)) ^^ n"
    and acc: "ktc_state cM = t_ktm conv_cex_ktm"
    unfolding accepts_in_time_ktm_def by blast
  from reach have "(conv_cex_cfg 0, cM) ∈ (ktm_step conv_cex_delta) ^^ n"
    by (simp add: conv_cex_init conv_cex_delta_ktm)
  from conv_cex_reach[OF this nle] have "ktc_state cM = n" by simp
  with acc nle show False by (simp add: conv_cex_t_ktm)
qed

theorem clean_convention_unattainable:
  "¬ time_bounded_conv conv_cex_ktm (λn. n + n div q)"
proof
  assume "time_bounded_conv conv_cex_ktm (λn. n + n div q)"
  hence "∀w∈Lang_ktm conv_cex_ktm.
           accepts_in_time_ktm conv_cex_ktm w (max (length w + 2) (length w + length w div q))"
    by (simp add: time_bounded_conv_def)
  from bspec[OF this conv_cex_lang] have "accepts_in_time_ktm conv_cex_ktm [] 2"
    by (simp add: numeral_2_eq_2)
  with conv_cex_not_accepts show False by simp
qed

end