Theory Wrap_Convention

theory Wrap_Convention
  imports Wrap_Speedup Wrap_Prefix_Runs "Multitape_TM_Substrate.Multitape_Time_Convention"
begin

section ‹The linear-speedup headlines in Hopcroft--Ullman's
  time-complexity convention›

text ‹The @{theory Multitape_Alphabet_Enlargement.Wrap_Speedup} headlines
  ‹linear_speedup_HU_12_3› / ‹linear_speedup_HU_12_4› prove a ∗‹raw›
  bound: a per-run additive constant ‹K› (and for 12.3 a bare length
  threshold ‹N0›), gated on the input run itself completing within
  ‹T›.  Hopcroft and Ullman state 12.3 / 12.4 in a ∗‹time-complexity
  convention› cite‹‹p.~291› in "Hopcroft1979:introduction"›: a machine
  ``runs in time ‹cT(n)›'' means it accepts every
  word of its language within @{text ‹max(n + 1, ceil(cT(n)))›} steps, the
  @{text ‹n + 1›} floor being the cost of reading the input.  On our
  substrate the floor is @{text ‹n + 2›} (the left endmarker is read
  before the first input symbol); this is exactly the
  @{const time_bounded_conv} predicate of
  @{theory Multitape_TM_Substrate.Multitape_Time_Convention}.

  This theory restates the two headlines in that convention.  The
  wrapped machine is a genuine @{type ktm}, and its user-facing
  language / timing (@{const Lang_user_wrap} / @{const
  accepts_in_time_user_wrap}) are the @{const Lang_ktm} / @{const
  accepts_in_time_ktm} of the wrap read through @{const Raw}, so
  @{const time_bounded_conv} applied to the wrap ∗‹is› the user-level
  convention statement (‹Lang_ktm_encoding_wrap_ex_Raw› below is the
  bridge).  The two cases diverge:

  ▪ ❙‹12.4 (linear ‹T›).›  The raw bound @{text ‹|w| + |w| div q + K›}
    holds for all lengths, so the convention statement is the max-floored
    restatement, provided ‹M› runs in time ‹T› on its language.  There are
    three forms, for different uses:
    ▪ ∗‹with ‹K›› (‹_conv›): every input, the wrap itself, and every
      number explicit.  This is the form to compose with other constructions.
    ▪ ∗‹eventual› (‹_eventual›): the wrap itself runs in ‹n + n div q›
      exactly past the explicit threshold ‹q⋅(q+1)⋅K›, where ‹K› is
      absorbed.  Still effective, with no constant, but only for long inputs.
    ▪ ∗‹with a table› (‹_conv_table›): ‹n + n div q› on every input, for
      the wrap with a first-block table of the short words of ‹L(M)›.  The
      table is finite, so the machine exists, but the theorem does not
      compute it; and the alphabet must be wide enough to hold the threshold
      in the first block.  This is the form for class equalities, where only
      existence matters.
    The table cannot be avoided for a constant-free bound on every input: a
    valid machine can accept its language yet exceed the floor ‹n + 2› on
    its shortest inputs (the counterexample ‹clean_convention_unattainable›
    in @{theory Multitape_TM_Substrate.Multitape_Time_Convention}), and an
    outer @{const finite_patch} cleanup would rescan, at a cost proportional
    to its cutoff.  Hopcroft and Ullman decide the short words in the finite
    control while the input is read; the first-block patch of
    @{theory Multitape_Alphabet_Enlargement.Wrap_Prefix_Patch} does the same
    on the encoder's own end-of-input transition, within the floor.

  ▪ ❙‹12.3 (superlinear ‹T›).›  Here superlinear growth dominates any
    linear-in-cutoff cost, so the @{const finite_patch} small-input
    cleanup (‹time_cleanup› on the table @{term ‹λw. w ∈ Lang_ktm M›})
    and the additive constant both wash out into a slightly larger
    multiplicative constant --- a clean @{text ‹ceil(c T(n))›} convention
    bound with no residual constant.

  The raw @{text ‹+ K›} theorems remain the explicit-constant corollaries
  (nothing is lost).›

subsection ‹An accepted word of the wrap is @{const Raw}-encoded›

text ‹Every word of @{const Lang_ktm} of an @{const encoding_wrap} is
  @{term ‹map Raw w›} for a user word ‹w›, because the wrap's input
  alphabet is @{term ‹Raw ` Σu›}.  This lets a @{const time_bounded_conv}
  goal over the wrap's @{const Lang_ktm} be discharged through the
  user-level @{const accepts_in_time_user_wrap} bound the raw headlines
  supply, and conversely.›

lemma Lang_ktm_encoding_wrap_ex_Raw:
  assumes "v ∈ Lang_ktm (encoding_wrap M pack c Σu)"
  shows "∃w. v = map Raw w ∧ w ∈ Lang_user_wrap (encoding_wrap M pack c Σu)"
proof -
  let ?W = "encoding_wrap M pack c Σu"
  have sv: "set v ⊆ Raw ` Σu"
    using assms unfolding Lang_ktm_def by simp
  have "∀x∈set v. ∃y. x = Raw y" using sv by auto
  then obtain w where vw: "v = map Raw w" by (metis ex_map_conv)
  have "map Raw w ∈ Lang_ktm ?W" using assms vw by simp
  hence "w ∈ Lang_user_wrap ?W" unfolding Lang_user_wrap_def by simp
  thus ?thesis using vw by blast
qed

subsection ‹Arithmetic for the superlinear case›

text ‹The one inequality behind both constant-free forms: a
  constant ‹C› is absorbed by dropping the speedup denominator from
  ‹q + 1› to ‹q›, provided the numerator ‹a› is at least
  ‹q (q + 1) C›.  In use ‹a = T n›, and the superlinear growth of ‹T›
  makes the premise hold for all large ‹n› --- including ‹C = K + 2 N1
  + 4› where ‹N1› is the finite-control cutoff, because the numerator
  grows superlinearly in ‹n› while ‹C› grows only linearly in ‹N1›.›

lemma div_absorb_step:
  fixes a q C :: nat
  assumes q_pos: "0 < q" and big: "q * (q + 1) * C ≤ a"
  shows "a div (q + 1) + C ≤ a div q"
proof -
  have qne: "q ≠ 0" using q_pos by simp
  have q1ne: "q + 1 ≠ 0" by simp
  have qC: "q * C ≤ a div (q + 1)"
  proof -
    have "(q + 1) * (q * C) ≤ a" using big by (simp add: algebra_simps)
    hence "((q + 1) * (q * C)) div (q + 1) ≤ a div (q + 1)" by (rule div_le_mono)
    moreover have "((q + 1) * (q * C)) div (q + 1) = q * C"
      by (metis nonzero_mult_div_cancel_left q1ne)
    ultimately show ?thesis by simp
  qed
  have "q * (a div (q + 1) + C) = q * (a div (q + 1)) + q * C"
    by (simp add: algebra_simps)
  also have "… ≤ q * (a div (q + 1)) + a div (q + 1)" using qC by simp
  also have "… = (q + 1) * (a div (q + 1))" by (simp add: algebra_simps)
  also have "… ≤ a" by (metis mult.commute div_times_less_eq_dividend)
  finally have le_a: "q * (a div (q + 1) + C) ≤ a" .
  hence "(q * (a div (q + 1) + C)) div q ≤ a div q" by (rule div_le_mono)
  moreover have "(q * (a div (q + 1) + C)) div q = a div (q + 1) + C"
    by (metis nonzero_mult_div_cancel_left qne)
  ultimately show ?thesis by simp
qed

subsection ‹HU 12.4 in the convention (linear ‹T›)›

text ‹The nondeterministic linear-‹T› headline, restated as a
  @{const time_bounded_conv} bound.  The extra hypothesis over the raw
  @{thm[source] linear_speedup_HU_12_4_nae} is ‹Mtime›: ‹M› accepts every
  word of its language within ‹T› --- i.e. ‹L(M)› ∗‹is› a ‹T›-time
  language, the textbook premise.  The bound @{term ‹λn. n + n div q + K›}
  is the raw @{text ‹+ K›} constant read in the @{text ‹max(n + 2, ...)›}
  convention, with ‹K› the literal ‹28 + 8 d_0 + 8 b›: every number in the
  statement is explicit, and the machine is the wrap itself.›

theorem linear_speedup_HU_12_4_nae_conv:
  fixes M :: "('q, 'a) ktm"
    and T :: "nat ⇒ nat"
    and d_0 b q :: nat
  assumes wf:        "well_formed_ktm M"
      and Mtime:     "⋀w. w ∈ Lang_ktm M ⟹ accepts_in_time_ktm M w (T (length w))"
      and T_linear:  "∀n. T n ≤ d_0 * n + b"
      and q_pos:     "0 < q"
      and k2:        "2 ≤ k_ktm M"
      and m_pos: "0 < m"
  shows "valid_ktm
          (encoding_wrap
             (alphabet_enlarge m M
                :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))"
    and "Lang_user_wrap
          (encoding_wrap
             (alphabet_enlarge m M
                :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
         = Lang_ktm M"
    and "q * (3 + 8 * d_0) ≤ m
         ⟶ time_bounded_conv
               (encoding_wrap
                  (alphabet_enlarge m M
                     :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
                  (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
                  (m)
                  (Sigma_ktm M))
               (λn. n + n div q + (28 + 8 * d_0 + 8 * b))"
proof -
  let ?W = "encoding_wrap
              (alphabet_enlarge m M
                 :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
              (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
              (m)
              (Sigma_ktm M)"
  let ?K = "28 + 8 * d_0 + 8 * b"
  have V: "valid_ktm ?W"
    and L: "Lang_user_wrap ?W = Lang_ktm M"
    and Tb: "q * (3 + 8 * d_0) ≤ m
          ⟶ (∀w. set w ⊆ Sigma_ktm M
                    ⟶ accepts_in_time_ktm M w (T (length w))
                    ⟶ accepts_in_time_user_wrap ?W w (length w + length w div q + ?K))"
    by (rule linear_speedup_HU_12_4_nae[OF wf T_linear q_pos k2 m_pos])+
  show "valid_ktm ?W" by (rule V)
  show "Lang_user_wrap ?W = Lang_ktm M" by (rule L)
  show "q * (3 + 8 * d_0) ≤ m
         ⟶ time_bounded_conv ?W (λn. n + n div q + ?K)"
  proof
    assume cL: "q * (3 + 8 * d_0) ≤ m"
    show "time_bounded_conv ?W (λn. n + n div q + ?K)"
      unfolding time_bounded_conv_def
    proof
      fix v assume vW: "v ∈ Lang_ktm ?W"
      then obtain w where vmap: "v = map Raw w" and wU: "w ∈ Lang_user_wrap ?W"
        using Lang_ktm_encoding_wrap_ex_Raw by blast
      from wU L have wM: "w ∈ Lang_ktm M" by simp
      hence wSg: "set w ⊆ Sigma_ktm M" unfolding Lang_ktm_def by simp
      from wM have accM: "accepts_in_time_ktm M w (T (length w))" by (rule Mtime)
      have "accepts_in_time_user_wrap ?W w (length w + length w div q + ?K)"
        using Tb cL wSg accM by blast
      hence "accepts_in_time_ktm ?W v (length v + length v div q + ?K)"
        using vmap unfolding accepts_in_time_user_wrap_def by simp
      thus "accepts_in_time_ktm ?W v
              (max (length v + 2) ((λn. n + n div q + ?K) (length v)))"
        by (auto elim: accepts_in_time_ktm_mono)
    qed
  qed
qed

text ‹The deterministic specialisation: adds the ‹det› hypothesis on
  ‹M› and the determinism-preservation conjunct on the wrap, on top of
  @{thm[source] linear_speedup_HU_12_4_nae_conv}.›

theorem linear_speedup_HU_12_4_dae_conv:
  fixes M :: "('q, 'a) ktm"
    and T :: "nat ⇒ nat"
    and d_0 b q :: nat
  assumes wf:        "well_formed_ktm M"
      and det:       "det_ktm M"
      and Mtime:     "⋀w. w ∈ Lang_ktm M ⟹ accepts_in_time_ktm M w (T (length w))"
      and T_linear:  "∀n. T n ≤ d_0 * n + b"
      and q_pos:     "0 < q"
      and k2:        "2 ≤ k_ktm M"
      and m_pos: "0 < m"
  shows "valid_ktm
          (encoding_wrap
             (alphabet_enlarge m M
                :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))"
    and "det_ktm
          (encoding_wrap
             (alphabet_enlarge m M
                :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))"
    and "Lang_user_wrap
          (encoding_wrap
             (alphabet_enlarge m M
                :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
         = Lang_ktm M"
    and "q * (3 + 8 * d_0) ≤ m
         ⟶ time_bounded_conv
               (encoding_wrap
                  (alphabet_enlarge m M
                     :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
                  (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
                  (m)
                  (Sigma_ktm M))
               (λn. n + n div q + (28 + 8 * d_0 + 8 * b))"
  using linear_speedup_HU_12_4_nae_conv[OF wf Mtime T_linear q_pos k2 m_pos]
    linear_speedup_HU_12_4_dae(2)[OF wf det T_linear q_pos k2 m_pos]
  by blast+

text ‹The nondeterministic linear-‹T› headline in the ∗‹eventual›
  form, for the wrap itself: past an explicit input-length threshold the wrap
  runs in ‹n + n div q› exactly --- the additive ‹K› of
  @{thm[source] linear_speedup_HU_12_4_nae_conv} is gone, with no table, so
  the construction stays effective, but only for long enough inputs.  The
  table form below covers the short inputs as well, with the first-block
  table of @{theory Multitape_Alphabet_Enlargement.Wrap_Prefix_Patch}, at the
  price of effectiveness.
  Proof: run @{thm[source] linear_speedup_HU_12_4_nae} one denominator tighter
  (at ‹q+1›), then absorb its additive ‹K› into the extra ‹div›-slack via
  @{thm[source] div_absorb_step} once ‹q⋅(q+1)⋅K ≤ length v› ---
  the same inequality that makes the superlinear 12.3 constant-free, here read
  in the linear regime as an explicit threshold rather than an absorbed
  constant.  With ‹K› the literal ‹28 + 8 d_0 + 8 b›, the crossover
  threshold is the closed formula ‹q⋅(q+1)⋅(28 + 8 d_0 + 8 b)› ---
  quadratic in ‹q› (i.e. ‹O(1/ε2)›), and linear in the input
  machine's time-bound constants ‹d_0, b›.›

theorem linear_speedup_HU_12_4_nae_eventual:
  fixes M :: "('q, 'a) ktm"
    and T :: "nat ⇒ nat"
    and d_0 b q :: nat
  assumes wf:        "well_formed_ktm M"
      and Mtime:     "⋀w. w ∈ Lang_ktm M ⟹ accepts_in_time_ktm M w (T (length w))"
      and T_linear:  "∀n. T n ≤ d_0 * n + b"
      and q_pos:     "0 < q"
      and k2:        "2 ≤ k_ktm M"
      and m_pos: "0 < m"
  shows "valid_ktm
          (encoding_wrap
             (alphabet_enlarge m M
                :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))"
    and "Lang_user_wrap
          (encoding_wrap
             (alphabet_enlarge m M
                :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
         = Lang_ktm M"
    and "(q + 1) * (3 + 8 * d_0) ≤ m
         ⟶ (∀v ∈ Lang_ktm
                     (encoding_wrap
                        (alphabet_enlarge m M
                           :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
                        (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
                        (m)
                        (Sigma_ktm M)).
                q * (q + 1) * (28 + 8 * d_0 + 8 * b) ≤ length v
                ⟶ accepts_in_time_ktm
                      (encoding_wrap
                         (alphabet_enlarge m M
                            :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
                         (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
                         (m)
                         (Sigma_ktm M))
                      v
                      (length v + length v div q))"
proof -
  let ?W = "encoding_wrap
              (alphabet_enlarge m M
                 :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
              (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
              (m)
              (Sigma_ktm M)"
  have q1_pos: "0 < q + 1" by simp
  obtain α K :: nat where alpha2: "α = (2::nat)"
    and Kdef: "K = 28 + 8 * d_0 + 8 * b" by blast
  have V: "valid_ktm ?W"
    and L: "Lang_user_wrap ?W = Lang_ktm M"
    and Tb': "(q + 1) * (3 + 8 * d_0) ≤ m
          ⟶ (∀w. set w ⊆ Sigma_ktm M
                    ⟶ accepts_in_time_ktm M w (T (length w))
                    ⟶ accepts_in_time_user_wrap ?W w
                          (length w + length w div (q + 1) + (28 + 8 * d_0 + 8 * b)))"
    by (rule linear_speedup_HU_12_4_nae[where q = "q + 1", OF wf T_linear q1_pos k2 m_pos])+
  have e: "(1::nat) + α + 8 * d_0 = 3 + 8 * d_0" using alpha2 by simp
  have Tb: "(q + 1) * (1 + α + 8 * d_0) ≤ m
          ⟶ (∀w. set w ⊆ Sigma_ktm M
                    ⟶ accepts_in_time_ktm M w (T (length w))
                    ⟶ accepts_in_time_user_wrap ?W w
                          (length w + length w div (q + 1) + K))"
    unfolding e Kdef by (rule Tb')
  have ev: "(q + 1) * (1 + α + 8 * d_0) ≤ m
             ⟶ (∀v ∈ Lang_ktm ?W. q * (q + 1) * K ≤ length v
                    ⟶ accepts_in_time_ktm ?W v (length v + length v div q))"
  proof
    assume cL: "(q + 1) * (1 + α + 8 * d_0) ≤ m"
    show "∀v ∈ Lang_ktm ?W. q * (q + 1) * K ≤ length v
            ⟶ accepts_in_time_ktm ?W v (length v + length v div q)"
    proof
      fix v assume vW: "v ∈ Lang_ktm ?W"
      show "q * (q + 1) * K ≤ length v
              ⟶ accepts_in_time_ktm ?W v (length v + length v div q)"
      proof
        assume lv: "q * (q + 1) * K ≤ length v"
        from vW obtain w where vmap: "v = map Raw w"
          and wU: "w ∈ Lang_user_wrap ?W"
          using Lang_ktm_encoding_wrap_ex_Raw by blast
        from wU L have wM: "w ∈ Lang_ktm M" by simp
        hence wSg: "set w ⊆ Sigma_ktm M" unfolding Lang_ktm_def by simp
        from wM have accM: "accepts_in_time_ktm M w (T (length w))" by (rule Mtime)
        have lenwv: "length w = length v" using vmap by simp
        have raw: "accepts_in_time_user_wrap ?W w
                     (length w + length w div (q + 1) + K)"
          using Tb cL wSg accM by blast
        have absorb: "length w div (q + 1) + K ≤ length w div q"
          by (rule div_absorb_step[OF q_pos]) (use lv lenwv in simp)
        hence le: "length w + length w div (q + 1) + K
                     ≤ length w + length w div q" by simp
        have "accepts_in_time_ktm ?W (map Raw w)
                (length w + length w div (q + 1) + K)"
          using raw unfolding accepts_in_time_user_wrap_def by simp
        hence "accepts_in_time_ktm ?W (map Raw w) (length w + length w div q)"
          using le by (auto elim: accepts_in_time_ktm_mono)
        thus "accepts_in_time_ktm ?W v (length v + length v div q)"
          by (simp only: vmap length_map)
      qed
    qed
  qed
  show "valid_ktm ?W" by (rule V)
  show "Lang_user_wrap ?W = Lang_ktm M" by (rule L)
  show "(q + 1) * (3 + 8 * d_0) ≤ m
         ⟶ (∀v ∈ Lang_ktm ?W. q * (q + 1) * (28 + 8 * d_0 + 8 * b) ≤ length v
                ⟶ accepts_in_time_ktm ?W v (length v + length v div q))"
  proof -
    have s0: "(3::nat) + 8 * d_0 = 1 + α + 8 * d_0" using alpha2 by simp
    show ?thesis unfolding s0 Kdef[symmetric] by (rule ev)
  qed
qed

text ‹The determinism-preserving eventual form: @{thm[source]
  linear_speedup_HU_12_4_nae_eventual} with the ‹det› hypothesis and the
  determinism-preservation conjunct, over @{thm[source]
  linear_speedup_HU_12_4_dae}.›

theorem linear_speedup_HU_12_4_dae_eventual:
  fixes M :: "('q, 'a) ktm"
    and T :: "nat ⇒ nat"
    and d_0 b q :: nat
  assumes wf:        "well_formed_ktm M"
      and det:       "det_ktm M"
      and Mtime:     "⋀w. w ∈ Lang_ktm M ⟹ accepts_in_time_ktm M w (T (length w))"
      and T_linear:  "∀n. T n ≤ d_0 * n + b"
      and q_pos:     "0 < q"
      and k2:        "2 ≤ k_ktm M"
      and m_pos: "0 < m"
  shows "valid_ktm
          (encoding_wrap
             (alphabet_enlarge m M
                :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))"
    and "det_ktm
          (encoding_wrap
             (alphabet_enlarge m M
                :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))"
    and "Lang_user_wrap
          (encoding_wrap
             (alphabet_enlarge m M
                :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
         = Lang_ktm M"
    and "(q + 1) * (3 + 8 * d_0) ≤ m
         ⟶ (∀v ∈ Lang_ktm
                     (encoding_wrap
                        (alphabet_enlarge m M
                           :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
                        (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
                        (m)
                        (Sigma_ktm M)).
                q * (q + 1) * (28 + 8 * d_0 + 8 * b) ≤ length v
                ⟶ accepts_in_time_ktm
                      (encoding_wrap
                         (alphabet_enlarge m M
                            :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
                         (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
                         (m)
                         (Sigma_ktm M))
                      v
                      (length v + length v div q))"
proof -
  let ?W = "encoding_wrap
              (alphabet_enlarge m M
                 :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
              (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
              (m)
              (Sigma_ktm M)"
  have q1_pos: "0 < q + 1" by simp
  obtain α K :: nat where alpha2: "α = (2::nat)"
    and Kdef: "K = 28 + 8 * d_0 + 8 * b" by blast
  have V: "valid_ktm ?W"
    and D: "det_ktm ?W"
    and L: "Lang_user_wrap ?W = Lang_ktm M"
    and Tb': "(q + 1) * (3 + 8 * d_0) ≤ m
          ⟶ (∀w. set w ⊆ Sigma_ktm M
                    ⟶ accepts_in_time_ktm M w (T (length w))
                    ⟶ accepts_in_time_user_wrap ?W w
                          (length w + length w div (q + 1) + (28 + 8 * d_0 + 8 * b)))"
    by (rule linear_speedup_HU_12_4_dae[where q = "q + 1", OF wf det T_linear q1_pos k2 m_pos])+
  have e: "(1::nat) + α + 8 * d_0 = 3 + 8 * d_0" using alpha2 by simp
  have Tb: "(q + 1) * (1 + α + 8 * d_0) ≤ m
          ⟶ (∀w. set w ⊆ Sigma_ktm M
                    ⟶ accepts_in_time_ktm M w (T (length w))
                    ⟶ accepts_in_time_user_wrap ?W w
                          (length w + length w div (q + 1) + K))"
    unfolding e Kdef by (rule Tb')
  have ev: "(q + 1) * (1 + α + 8 * d_0) ≤ m
             ⟶ (∀v ∈ Lang_ktm ?W. q * (q + 1) * K ≤ length v
                    ⟶ accepts_in_time_ktm ?W v (length v + length v div q))"
  proof
    assume cL: "(q + 1) * (1 + α + 8 * d_0) ≤ m"
    show "∀v ∈ Lang_ktm ?W. q * (q + 1) * K ≤ length v
            ⟶ accepts_in_time_ktm ?W v (length v + length v div q)"
    proof
      fix v assume vW: "v ∈ Lang_ktm ?W"
      show "q * (q + 1) * K ≤ length v
              ⟶ accepts_in_time_ktm ?W v (length v + length v div q)"
      proof
        assume lv: "q * (q + 1) * K ≤ length v"
        from vW obtain w where vmap: "v = map Raw w"
          and wU: "w ∈ Lang_user_wrap ?W"
          using Lang_ktm_encoding_wrap_ex_Raw by blast
        from wU L have wM: "w ∈ Lang_ktm M" by simp
        hence wSg: "set w ⊆ Sigma_ktm M" unfolding Lang_ktm_def by simp
        from wM have accM: "accepts_in_time_ktm M w (T (length w))" by (rule Mtime)
        have lenwv: "length w = length v" using vmap by simp
        have raw: "accepts_in_time_user_wrap ?W w
                     (length w + length w div (q + 1) + K)"
          using Tb cL wSg accM by blast
        have absorb: "length w div (q + 1) + K ≤ length w div q"
          by (rule div_absorb_step[OF q_pos]) (use lv lenwv in simp)
        hence le: "length w + length w div (q + 1) + K
                     ≤ length w + length w div q" by simp
        have "accepts_in_time_ktm ?W (map Raw w)
                (length w + length w div (q + 1) + K)"
          using raw unfolding accepts_in_time_user_wrap_def by simp
        hence "accepts_in_time_ktm ?W (map Raw w) (length w + length w div q)"
          using le by (auto elim: accepts_in_time_ktm_mono)
        thus "accepts_in_time_ktm ?W v (length v + length v div q)"
          by (simp only: vmap length_map)
      qed
    qed
  qed
  show "valid_ktm ?W" by (rule V)
  show "det_ktm ?W" by (rule D)
  show "Lang_user_wrap ?W = Lang_ktm M" by (rule L)
  show "(q + 1) * (3 + 8 * d_0) ≤ m
         ⟶ (∀v ∈ Lang_ktm ?W. q * (q + 1) * (28 + 8 * d_0 + 8 * b) ≤ length v
                ⟶ accepts_in_time_ktm ?W v (length v + length v div q))"
  proof -
    have s0: "(3::nat) + 8 * d_0 = 1 + α + 8 * d_0" using alpha2 by simp
    show ?thesis unfolding s0 Kdef[symmetric] by (rule ev)
  qed
qed

text ‹HU 12.4 in the convention, constant-free: the patched wrap accepts
  every word of ‹L(M)› within @{text ‹max(n + 2, n + n div q)›}, for
  every length.  Long inputs run as the wrap does, by
  @{thm[source] linear_speedup_HU_12_4_nae_eventual}; inputs up to the
  threshold are decided by the first-block table, in ‹n + 2› steps.  The
  table is ‹L(M)› restricted to short words, a finite set, so the theorem
  asserts existence of the machine rather than an effective construction;
  @{thm[source] linear_speedup_HU_12_4_nae_conv} and the eventual forms are
  the effective statements.  The alphabet must be wide enough to hold the
  threshold inside the first block.›

theorem linear_speedup_HU_12_4_nae_conv_table:
  fixes M :: "('q, 'a) ktm"
    and T :: "nat ⇒ nat"
    and d_0 b q :: nat
  assumes wf:        "well_formed_ktm M"
      and Mtime:     "⋀w. w ∈ Lang_ktm M ⟹ accepts_in_time_ktm M w (T (length w))"
      and T_linear:  "∀n. T n ≤ d_0 * n + b"
      and q_pos:     "0 < q"
      and width:     "q * (q + 1) * (28 + 8 * d_0 + 8 * b) < m"
      and k2:        "2 ≤ k_ktm M"
      and m_pos: "0 < m"
  shows "valid_ktm
          (wrap_prefix_patch
          (encoding_wrap
             (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
          (λu. u ∈ Lang_ktm M) (q * (q + 1) * (28 + 8 * d_0 + 8 * b)))"
    and "Lang_user_wrap
          (wrap_prefix_patch
          (encoding_wrap
             (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
          (λu. u ∈ Lang_ktm M) (q * (q + 1) * (28 + 8 * d_0 + 8 * b)))
         = Lang_ktm M"
    and "time_bounded_conv
          (wrap_prefix_patch
          (encoding_wrap
             (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
          (λu. u ∈ Lang_ktm M) (q * (q + 1) * (28 + 8 * d_0 + 8 * b)))
          (λn. n + n div q)"
proof -
  let ?A = "(alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)"
  let ?pack = "(ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))"
  let ?m = "m"
  let ?W = "encoding_wrap ?A ?pack ?m (Sigma_ktm M)"
  let ?N = "(q * (q + 1) * (28 + 8 * d_0 + 8 * b))"
  let ?P = "wrap_prefix_patch ?W (λu. u ∈ Lang_ktm M) ?N"
  have c_pos: "0 < ?m" by (rule m_pos)
  note E = linear_speedup_HU_12_4_nae_eventual[OF wf Mtime T_linear q_pos k2 m_pos]
  have vM: "valid_ktm M" and le_bl: "le_ktm M ≠ bl_ktm M" using wf by auto
  have vA: "valid_ktm ?A" by (rule alphabet_enlarge_wf[OF vM m_pos])
  have blleA: "bl_ktm ?A ≠ le_ktm ?A"
    unfolding bl_ktm_alphabet_enlarge le_ktm_alphabet_enlarge
    using LE_block_neq_bl_block[OF m_pos le_bl] by metis
  have k2A: "2 ≤ k_ktm ?A" using k2 by (cases M) (simp add: alphabet_enlarge_def)
  have enc: "set (wrap_enc ?pack ?m w) ⊆ Sigma_ktm ?A" if "set w ⊆ Sigma_ktm M" for w
    by (rule ae_wrap_enc_in_Sigma[OF vM that m_pos])
  have Km: "(3 + 8 * d_0) ≤ 28 + 8 * d_0 + 8 * b" by simp
  have wide: "(q + 1) * (3 + 8 * d_0) ≤ ?m"
  proof -
    have "(q + 1) * (3 + 8 * d_0) ≤ (q + 1) * (28 + 8 * d_0 + 8 * b)"
      using Km by (rule mult_le_mono2)
    also have "… ≤ q * ((q + 1) * (28 + 8 * d_0 + 8 * b))"
      using q_pos by (cases q) simp_all
    also have "… = q * (q + 1) * (28 + 8 * d_0 + 8 * b)" by (simp only: mult.assoc)
    finally have chain: "(q + 1) * (3 + 8 * d_0) ≤ q * (q + 1) * (28 + 8 * d_0 + 8 * b)" .
    show ?thesis by (rule less_imp_le[OF le_less_trans[OF chain width]])
  qed
  have table: "(λu. u ∈ Lang_ktm M) = (λu. u ∈ Lang_user_wrap ?W)"
    using E(2) by simp
  show validP: "valid_ktm ?P" by (rule wrap_prefix_patch_valid[OF E(1)])
  have langP: "Lang_user_wrap ?P = Lang_user_wrap ?W"
    unfolding table
    by (rule wrap_prefix_language[OF vA c_pos blleA k2A width enc])
  show "Lang_user_wrap ?P = Lang_ktm M" using langP E(2) by simp
  have tP: "t_ktm ?P = (False, W_Run (t_ktm M, init_stage m (le_ktm M)))"
    by (simp add: t_ktm_alphabet_enlarge)
  show "time_bounded_conv ?P (λn. n + n div q)"
    unfolding time_bounded_conv_def
  proof
    fix v assume vP: "v ∈ Lang_ktm ?P"
    have "set v ⊆ Raw ` Sigma_ktm M" using vP by (simp add: Lang_ktm_iff)
    then have "v ∈ lists (Raw ` Sigma_ktm M)" by (auto simp: in_lists_conv_set)
    then obtain w where v: "v = map Raw w" and word: "set w ⊆ Sigma_ktm M"
      by (auto simp: lists_image)
    have "w ∈ Lang_user_wrap ?P"
      unfolding Lang_user_wrap_def mem_Collect_eq using vP unfolding v .
    then have wM: "w ∈ Lang_ktm M" using langP E(2) by blast
    have packw: "?pack (take ?m (drop (i * ?m) w)) ∈ Sigma_ktm ?A" if "i * ?m < length w" for i
      using enc[OF word] pack_take_in_set_wrap_enc[OF c_pos that, where pack="?pack"] by blast
    show "accepts_in_time_ktm ?P v (max (length v + 2) (length v + length v div q))"
    proof (cases "length w ≤ ?N")
      case short: True
      have shortm: "length w < ?m" using short width by simp
      have "reaches_state_in_time_ktm ?P (map Raw w)
          (False, if w ∈ Lang_ktm M then t_ktm ?W else r_ktm ?W) (length w + 2)"
        by (rule wrap_prefix_short_reaches[where A="?A" and pack="?pack" and m="?m"
            and S="Sigma_ktm M" and w=w and table="λu. u ∈ Lang_ktm M" and N="?N",
            OF vA c_pos word blleA k2A packw shortm short])
      then have "accepts_in_time_ktm ?P v (length v + 2)"
        using wM unfolding accepts_in_time_ktm_iff_reaches by (simp add: v)
      then show ?thesis by (rule accepts_in_time_ktm_mono) simp
    next
      case long: False
      have longN: "?N < length w" using long by simp
      have "w ∈ Lang_user_wrap ?W" using wM E(2) by blast
      then have vW: "v ∈ Lang_ktm ?W" unfolding v Lang_user_wrap_def by blast
      have thr: "?N ≤ length v" using longN by (simp add: v)
      have "accepts_in_time_ktm ?W v (length v + length v div q)"
        using E(3) wide vW thr by blast
      then have reach: "reaches_state_in_time_ktm ?W (map Raw w)
          (W_Run (t_ktm M, init_stage m (le_ktm M))) (length v + length v div q)"
        unfolding accepts_in_time_ktm_iff_reaches by (simp add: v t_ktm_alphabet_enlarge)
      have "reaches_state_in_time_ktm ?P (map Raw w)
          (False, W_Run (t_ktm M, init_stage m (le_ktm M))) (length v + length v div q)"
        by (rule wrap_prefix_transport[where A="?A" and pack="?pack" and m="?m"
            and S="Sigma_ktm M" and w=w and table="λu. u ∈ Lang_ktm M" and N="?N",
            OF vA c_pos word blleA k2A packw longN reach])
      then have "accepts_in_time_ktm ?P v (length v + length v div q)"
        unfolding accepts_in_time_ktm_iff_reaches tP by (simp add: v)
      then show ?thesis by (rule accepts_in_time_ktm_mono) simp
    qed
  qed
qed

text ‹The deterministic specialisation: the patch preserves determinism, so
  a deterministic ‹M› gives a deterministic machine with the same bound.›

theorem linear_speedup_HU_12_4_dae_conv_table:
  fixes M :: "('q, 'a) ktm"
    and T :: "nat ⇒ nat"
    and d_0 b q :: nat
  assumes wf:        "well_formed_ktm M"
      and det:       "det_ktm M"
      and Mtime:     "⋀w. w ∈ Lang_ktm M ⟹ accepts_in_time_ktm M w (T (length w))"
      and T_linear:  "∀n. T n ≤ d_0 * n + b"
      and q_pos:     "0 < q"
      and width:     "q * (q + 1) * (28 + 8 * d_0 + 8 * b) < m"
      and k2:        "2 ≤ k_ktm M"
      and m_pos: "0 < m"
  shows "valid_ktm
          (wrap_prefix_patch
          (encoding_wrap
             (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
          (λu. u ∈ Lang_ktm M) (q * (q + 1) * (28 + 8 * d_0 + 8 * b)))"
    and "det_ktm
          (wrap_prefix_patch
          (encoding_wrap
             (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
          (λu. u ∈ Lang_ktm M) (q * (q + 1) * (28 + 8 * d_0 + 8 * b)))"
    and "Lang_user_wrap
          (wrap_prefix_patch
          (encoding_wrap
             (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
          (λu. u ∈ Lang_ktm M) (q * (q + 1) * (28 + 8 * d_0 + 8 * b)))
         = Lang_ktm M"
    and "time_bounded_conv
          (wrap_prefix_patch
          (encoding_wrap
             (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
          (λu. u ∈ Lang_ktm M) (q * (q + 1) * (28 + 8 * d_0 + 8 * b)))
          (λn. n + n div q)"
proof -
  note C = linear_speedup_HU_12_4_nae_conv_table[OF wf Mtime T_linear q_pos width k2 m_pos]
  note D = linear_speedup_HU_12_4_dae_eventual[OF wf det Mtime T_linear q_pos k2 m_pos]
  show "valid_ktm (wrap_prefix_patch
          (encoding_wrap
             (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
          (λu. u ∈ Lang_ktm M) (q * (q + 1) * (28 + 8 * d_0 + 8 * b)))" by (rule C(1))
  show "det_ktm (wrap_prefix_patch
          (encoding_wrap
             (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
          (λu. u ∈ Lang_ktm M) (q * (q + 1) * (28 + 8 * d_0 + 8 * b)))" by (rule wrap_prefix_patch_det[OF D(2)])
  show "Lang_user_wrap (wrap_prefix_patch
          (encoding_wrap
             (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
          (λu. u ∈ Lang_ktm M) (q * (q + 1) * (28 + 8 * d_0 + 8 * b))) = Lang_ktm M" by (rule C(2))
  show "time_bounded_conv (wrap_prefix_patch
          (encoding_wrap
             (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
             (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
             (m)
             (Sigma_ktm M))
          (λu. u ∈ Lang_ktm M) (q * (q + 1) * (28 + 8 * d_0 + 8 * b))) (λn. n + n div q)" by (rule C(3))
qed

subsection ‹HU 12.3 in the convention (superlinear ‹T›)›

text ‹The nondeterministic superlinear-‹T› headline, restated as a
  ∗‹constant-free› @{const time_bounded_conv} bound @{term ‹λn. T n div q›}.
  Unlike 12.4, no additive constant survives: the raw simulation
  constant ‹K› ∗‹and› the finite-control overhead ‹2 N1 + 4› are both
  absorbed into a slightly smaller speedup denominator (the raw
  construction is run at ‹q + 1›, the headline states ‹q›), because
  superlinear ‹T› makes @{thm[source] div_absorb_step}'s premise
  ‹q (q + 1) C ≤ T n› hold for all long ‹n› with ‹C = K + 2 N1 + 4›.

  The machine is @{const finite_patch} of the wrap under the table
  ‹u ∈ Lang_ktm› of the wrap --- the wrap with the finite-control
  small-input cleanup planted on top (short inputs decided by table
  lookup in ‹n + 2›, long inputs run the wrap after the O(1) rewind).
  The extra hypothesis over the raw
  @{thm[source] linear_speedup_HU_12_3_nae} is again ‹Mtime›, and the
  cardinality side condition tightens from ‹16 q› to ‹16 (q + 1)› (the
  faster inner run).›

theorem linear_speedup_HU_12_3_nae_conv:
  fixes M :: "('q, 'a) ktm"
    and T :: "nat ⇒ nat"
    and q :: nat
  assumes wf:      "well_formed_ktm M"
      and Mtime:   "⋀w. w ∈ Lang_ktm M ⟹ accepts_in_time_ktm M w (T (length w))"
      and growth:  "∀d. ∃N. ∀n. N ≤ n ⟶ d * n ≤ T n"
      and q_pos:   "0 < q"
      and c_large: "16 * (q + 1) ≤ m"
      and k2:      "2 ≤ k_ktm M"
  obtains W' :: "((('q × 'a ae_stage, 'a, nat ⇒ 'a) wrap_state,
                   ('a, nat ⇒ 'a) wrap_alphabet) fp_state,
                  ('a, nat ⇒ 'a) wrap_alphabet) ktm"
  where "valid_ktm W'"
    and "Lang_user_wrap W' = Lang_ktm M"
    and "time_bounded_conv W' (λn. T n div q)"
proof -
  have m_pos: "0 < m" using c_large by (cases m) auto
  let ?W = "encoding_wrap
              (alphabet_enlarge m M
                 :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
              (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
              (m)
              (Sigma_ktm M)"
  have q1pos: "0 < q + 1" by simp
  obtain K N0 where
    Vraw: "valid_ktm ?W" and
    Lraw: "Lang_user_wrap ?W = Lang_ktm M" and
    Traw: "∀w. set w ⊆ Sigma_ktm M
                ⟶ N0 ≤ length w
                ⟶ accepts_in_time_ktm M w (T (length w))
                ⟶ accepts_in_time_user_wrap ?W w (T (length w) div (q + 1) + K)"
    by (rule linear_speedup_HU_12_3_nae[OF wf growth q1pos c_large k2])
  have blle: "bl_ktm ?W ≠ le_ktm ?W"
  proof -
    have le_neq_bl: "le_ktm M ≠ bl_ktm M" using wf by auto
    have "bl_ktm (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
            ≠ le_ktm (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)"
      unfolding bl_ktm_alphabet_enlarge le_ktm_alphabet_enlarge
      using LE_block_neq_bl_block[OF m_pos le_neq_bl] by metis
    thus ?thesis by simp
  qed
  from growth obtain Nd where
    growthN: "∀n. Nd ≤ n ⟶ 3 * q * (q + 1) * n ≤ T n" by blast
  define N1 where "N1 = max N0 (max Nd (K + 4))"
  have N1_N0: "N0 ≤ N1" and N1_Nd: "Nd ≤ N1" and N1_K: "K + 4 ≤ N1"
    unfolding N1_def by auto
  let ?W' = "finite_patch ?W (λu. u ∈ Lang_ktm ?W) N1"
  have lang': "Lang_ktm ?W' = Lang_ktm ?W"
  proof -
    have "Lang_ktm ?W' = {u. set u ⊆ Sigma_ktm ?W ∧ u ∈ Lang_ktm ?W}"
      using finite_patch_language[OF Vraw blle] by simp
    also have "… = Lang_ktm ?W" unfolding Lang_ktm_def by auto
    finally show ?thesis .
  qed
  have valid': "valid_ktm ?W'" by (rule finite_patch_valid[OF Vraw])
  have Luser': "Lang_user_wrap ?W' = Lang_ktm M"
    using lang' Lraw unfolding Lang_user_wrap_def by simp
  have conv': "time_bounded_conv ?W' (λn. T n div q)"
    unfolding time_bounded_conv_def
  proof
    fix v assume vW': "v ∈ Lang_ktm ?W'"
    hence vW: "v ∈ Lang_ktm ?W" using lang' by simp
    hence vSg: "set v ⊆ Sigma_ktm ?W" unfolding Lang_ktm_def by simp
    show "accepts_in_time_ktm ?W' v (max (length v + 2) ((λn. T n div q) (length v)))"
    proof (cases "length v ≤ N1")
      case True
      have "accepts_in_time_ktm ?W' v (length v + 2)"
        using Vraw vSg True vW by (rule fp_short_time)
      thus ?thesis by (auto elim: accepts_in_time_ktm_mono)
    next
      case False
      hence N1lt: "N1 < length v" by simp
      obtain w where vmap: "v = map Raw w" and wU: "w ∈ Lang_user_wrap ?W"
        using vW Lang_ktm_encoding_wrap_ex_Raw by blast
      from wU Lraw have wM: "w ∈ Lang_ktm M" by simp
      hence wSgM: "set w ⊆ Sigma_ktm M" unfolding Lang_ktm_def by simp
      from wM have accM: "accepts_in_time_ktm M w (T (length w))" by (rule Mtime)
      have lenwv: "length w = length v" using vmap by simp
      have N0w: "N0 ≤ length w" using N1lt lenwv N1_N0 by simp
      have "accepts_in_time_user_wrap ?W w (T (length w) div (q + 1) + K)"
        using Traw wSgM N0w accM by blast
      hence accW: "accepts_in_time_ktm ?W v (T (length v) div (q + 1) + K)"
        by (simp only: accepts_in_time_user_wrap_def vmap[symmetric] lenwv)
      have "accepts_in_time_ktm ?W' v ((T (length v) div (q + 1) + K) + (2 * N1 + 4))"
        using Vraw vSg N1lt accW by (rule fp_long_time)
      moreover have "(T (length v) div (q + 1) + K) + (2 * N1 + 4) ≤ T (length v) div q"
      proof -
        have Ndlv: "Nd ≤ length v" using N1_Nd N1lt by simp
        have TN: "3 * q * (q + 1) * length v ≤ T (length v)"
          using growthN Ndlv by blast
        have "K + 2 * N1 + 4 ≤ 3 * length v"
        proof -
          have "K + 2 * N1 + 4 ≤ 3 * N1" using N1_K by linarith
          also have "… ≤ 3 * length v" using N1lt by linarith
          finally show ?thesis .
        qed
        hence "q * (q + 1) * (K + 2 * N1 + 4) ≤ q * (q + 1) * (3 * length v)"
          by (rule mult_le_mono2)
        also have "q * (q + 1) * (3 * length v) = 3 * q * (q + 1) * length v"
          by (simp add: algebra_simps)
        also note TN
        finally have big: "q * (q + 1) * (K + 2 * N1 + 4) ≤ T (length v)" .
        have "T (length v) div (q + 1) + (K + 2 * N1 + 4) ≤ T (length v) div q"
          using q_pos big by (rule div_absorb_step)
        thus ?thesis by simp
      qed
      ultimately have "accepts_in_time_ktm ?W' v (T (length v) div q)"
        by (auto elim: accepts_in_time_ktm_mono)
      thus ?thesis by (auto elim: accepts_in_time_ktm_mono)
    qed
  qed
  show thesis
  proof (rule that[of ?W'])
    show "valid_ktm ?W'" by (rule valid')
    show "Lang_user_wrap ?W' = Lang_ktm M" by (rule Luser')
    show "time_bounded_conv ?W' (λn. T n div q)" by (rule conv')
  qed
qed

text ‹The deterministic specialisation of
  @{thm[source] linear_speedup_HU_12_3_nae_conv}: adds the ‹det›
  hypothesis on ‹M› and the determinism-preservation conjunct on the
  cleaned machine (via @{thm[source] finite_patch_det}).›

theorem linear_speedup_HU_12_3_dae_conv:
  fixes M :: "('q, 'a) ktm"
    and T :: "nat ⇒ nat"
    and q :: nat
  assumes wf:      "well_formed_ktm M"
      and det:     "det_ktm M"
      and Mtime:   "⋀w. w ∈ Lang_ktm M ⟹ accepts_in_time_ktm M w (T (length w))"
      and growth:  "∀d. ∃N. ∀n. N ≤ n ⟶ d * n ≤ T n"
      and q_pos:   "0 < q"
      and c_large: "16 * (q + 1) ≤ m"
      and k2:      "2 ≤ k_ktm M"
  obtains W' :: "((('q × 'a ae_stage, 'a, nat ⇒ 'a) wrap_state,
                   ('a, nat ⇒ 'a) wrap_alphabet) fp_state,
                  ('a, nat ⇒ 'a) wrap_alphabet) ktm"
  where "valid_ktm W'"
    and "det_ktm W'"
    and "Lang_user_wrap W' = Lang_ktm M"
    and "time_bounded_conv W' (λn. T n div q)"
proof -
  have m_pos: "0 < m" using c_large by (cases m) auto
  let ?W = "encoding_wrap
              (alphabet_enlarge m M
                 :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
              (ae_pack m (bl_ktm M) :: 'a list ⇒ (nat ⇒ 'a))
              (m)
              (Sigma_ktm M)"
  have q1pos: "0 < q + 1" by simp
  obtain K N0 where
    Vraw: "valid_ktm ?W" and
    Draw: "det_ktm ?W" and
    Lraw: "Lang_user_wrap ?W = Lang_ktm M" and
    Traw: "∀w. set w ⊆ Sigma_ktm M
                ⟶ N0 ≤ length w
                ⟶ accepts_in_time_ktm M w (T (length w))
                ⟶ accepts_in_time_user_wrap ?W w (T (length w) div (q + 1) + K)"
    by (rule linear_speedup_HU_12_3_dae[OF wf det growth q1pos c_large k2])
  have blle: "bl_ktm ?W ≠ le_ktm ?W"
  proof -
    have le_neq_bl: "le_ktm M ≠ bl_ktm M" using wf by auto
    have "bl_ktm (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
            ≠ le_ktm (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)"
      unfolding bl_ktm_alphabet_enlarge le_ktm_alphabet_enlarge
      using LE_block_neq_bl_block[OF m_pos le_neq_bl] by metis
    thus ?thesis by simp
  qed
  from growth obtain Nd where
    growthN: "∀n. Nd ≤ n ⟶ 3 * q * (q + 1) * n ≤ T n" by blast
  define N1 where "N1 = max N0 (max Nd (K + 4))"
  have N1_N0: "N0 ≤ N1" and N1_Nd: "Nd ≤ N1" and N1_K: "K + 4 ≤ N1"
    unfolding N1_def by auto
  let ?W' = "finite_patch ?W (λu. u ∈ Lang_ktm ?W) N1"
  have lang': "Lang_ktm ?W' = Lang_ktm ?W"
  proof -
    have "Lang_ktm ?W' = {u. set u ⊆ Sigma_ktm ?W ∧ u ∈ Lang_ktm ?W}"
      using finite_patch_language[OF Vraw blle] by simp
    also have "… = Lang_ktm ?W" unfolding Lang_ktm_def by auto
    finally show ?thesis .
  qed
  have valid': "valid_ktm ?W'" by (rule finite_patch_valid[OF Vraw])
  have det': "det_ktm ?W'" by (rule finite_patch_det[OF Vraw blle Draw])
  have Luser': "Lang_user_wrap ?W' = Lang_ktm M"
    using lang' Lraw unfolding Lang_user_wrap_def by simp
  have conv': "time_bounded_conv ?W' (λn. T n div q)"
    unfolding time_bounded_conv_def
  proof
    fix v assume vW': "v ∈ Lang_ktm ?W'"
    hence vW: "v ∈ Lang_ktm ?W" using lang' by simp
    hence vSg: "set v ⊆ Sigma_ktm ?W" unfolding Lang_ktm_def by simp
    show "accepts_in_time_ktm ?W' v (max (length v + 2) ((λn. T n div q) (length v)))"
    proof (cases "length v ≤ N1")
      case True
      have "accepts_in_time_ktm ?W' v (length v + 2)"
        using Vraw vSg True vW by (rule fp_short_time)
      thus ?thesis by (auto elim: accepts_in_time_ktm_mono)
    next
      case False
      hence N1lt: "N1 < length v" by simp
      obtain w where vmap: "v = map Raw w" and wU: "w ∈ Lang_user_wrap ?W"
        using vW Lang_ktm_encoding_wrap_ex_Raw by blast
      from wU Lraw have wM: "w ∈ Lang_ktm M" by simp
      hence wSgM: "set w ⊆ Sigma_ktm M" unfolding Lang_ktm_def by simp
      from wM have accM: "accepts_in_time_ktm M w (T (length w))" by (rule Mtime)
      have lenwv: "length w = length v" using vmap by simp
      have N0w: "N0 ≤ length w" using N1lt lenwv N1_N0 by simp
      have "accepts_in_time_user_wrap ?W w (T (length w) div (q + 1) + K)"
        using Traw wSgM N0w accM by blast
      hence accW: "accepts_in_time_ktm ?W v (T (length v) div (q + 1) + K)"
        by (simp only: accepts_in_time_user_wrap_def vmap[symmetric] lenwv)
      have "accepts_in_time_ktm ?W' v ((T (length v) div (q + 1) + K) + (2 * N1 + 4))"
        using Vraw vSg N1lt accW by (rule fp_long_time)
      moreover have "(T (length v) div (q + 1) + K) + (2 * N1 + 4) ≤ T (length v) div q"
      proof -
        have Ndlv: "Nd ≤ length v" using N1_Nd N1lt by simp
        have TN: "3 * q * (q + 1) * length v ≤ T (length v)"
          using growthN Ndlv by blast
        have "K + 2 * N1 + 4 ≤ 3 * length v"
        proof -
          have "K + 2 * N1 + 4 ≤ 3 * N1" using N1_K by linarith
          also have "… ≤ 3 * length v" using N1lt by linarith
          finally show ?thesis .
        qed
        hence "q * (q + 1) * (K + 2 * N1 + 4) ≤ q * (q + 1) * (3 * length v)"
          by (rule mult_le_mono2)
        also have "q * (q + 1) * (3 * length v) = 3 * q * (q + 1) * length v"
          by (simp add: algebra_simps)
        also note TN
        finally have big: "q * (q + 1) * (K + 2 * N1 + 4) ≤ T (length v)" .
        have "T (length v) div (q + 1) + (K + 2 * N1 + 4) ≤ T (length v) div q"
          using q_pos big by (rule div_absorb_step)
        thus ?thesis by simp
      qed
      ultimately have "accepts_in_time_ktm ?W' v (T (length v) div q)"
        by (auto elim: accepts_in_time_ktm_mono)
      thus ?thesis by (auto elim: accepts_in_time_ktm_mono)
    qed
  qed
  show thesis
  proof (rule that[of ?W'])
    show "valid_ktm ?W'" by (rule valid')
    show "det_ktm ?W'" by (rule det')
    show "Lang_user_wrap ?W' = Lang_ktm M" by (rule Luser')
    show "time_bounded_conv ?W' (λn. T n div q)" by (rule conv')
  qed
qed

end