Theory AlphabetRoundtrip

theory AlphabetRoundtrip
  imports
    "Multitape_Alphabet_Enlargement.AlphabetEnlargement_Reverse"
    "Multitape_Alphabet_Reduction.AlphabetReduction_Reverse"
begin

section ‹Round-trip composition of the alphabet transformations›

text ‹The two alphabet transformations compose ∗‹as machines› in both
  orders on the shared substrate.  This theory states, for each order,
  language preservation and a composed linear-time slowdown bound.  Nothing
  is re-proved: each headline chains the language / time theorems of
  const‹alphabet_enlarge› and const‹alphabet_reduce› already established
  in the two sibling sessions.

  Two directions:
  ▪ ❙‹reduce after enlarge›: term‹alphabet_reduce (alphabet_enlarge m M)›.
    The enlarged machine feeds const‹alphabet_reduce›; the four-symbol lower
    bound its hypotheses require follows from the constant-cell embedding of
    the source alphabet into the block alphabet (‹card_gamma_block_ge_card›).
  ▪ ❙‹enlarge after reduce›: term‹alphabet_enlarge m (alphabet_reduce M)›.
    The reduced machine is well-formed for ∗‹any› valid source with a
    four-symbol alphabet (‹alphabet_reduce_well_formed›), which discharges the
    const‹well_formed_ktm› hypothesis const‹alphabet_enlarge› requires of its
    input -- the cut-tolerance payoff.›

subsection ‹The enlarged alphabet has at least as many symbols as the source›

text ‹The block alphabet term‹gamma_block m Γ› contains the constant
  block term‹restrict (λ_. a) {..<m}› for every term‹a ∈ Γ›, and the
  embedding sending ‹a› to that block is injective when a block has a cell
  (term‹0 < m›).  Hence the enlarged alphabet is at least as large as the
  source, so a source with term‹4 ≤ card Γ› enlarges to a machine whose
  alphabet still meets the reduction combinator's minimal-alphabet bound.›

lemma card_gamma_block_ge_card:
  fixes Γ :: "'a set"
  assumes finG: "finite Γ" and m_pos: "0 < m"
  shows "card Γ ≤ card (gamma_block m Γ :: (nat ⇒ 'a) set)"
proof -
  have inj: "inj_on (λa. restrict (λ_::nat. a) {..<m}) Γ"
  proof (rule inj_onI)
    fix a b
    assume "restrict (λ_::nat. a) {..<m} = restrict (λ_::nat. b) {..<m}"
    then have "restrict (λ_::nat. a) {..<m} 0 = restrict (λ_::nat. b) {..<m} 0"
      by simp
    then show "a = b" using m_pos by simp
  qed
  have img: "(λa. restrict (λ_::nat. a) {..<m}) ` Γ ⊆ gamma_block m Γ"
    by (auto simp: gamma_block_def)
  have "card Γ = card ((λa. restrict (λ_::nat. a) {..<m}) ` Γ)"
    by (simp add: card_image[OF inj])
  also have "… ≤ card (gamma_block m Γ :: (nat ⇒ 'a) set)"
    by (rule card_mono[OF finite_gamma_block[OF finG] img])
  finally show ?thesis .
qed

subsection ‹Time-composition preliminaries›

text ‹A small fact used when composing the running-time bounds: the block
  count ‹(n + c - 1) div c› (rounding ‹n / c› up) that the enlargement
  bound divides by never exceeds ‹n› for a nonempty index (‹0 < c›).
  Monotonicity of acceptance in the time bound is the substrate's
  ‹accepts_in_time_ktm_mono›.›

lemma ceil_div_le:
  fixes n c :: nat
  assumes cpos: "0 < c"
  shows "(n + c - 1) div c ≤ n"
proof (cases "n = 0")
  case True
  from cpos obtain m where cm: "c = Suc m" using gr0_implies_Suc by blast
  have "c - 1 < c" using cm by simp
  hence "(c - 1) div c = 0" by (rule div_less)
  thus ?thesis using True by simp
next
  case False
  then have n1: "1 ≤ n" by simp
  have cnz: "c ≠ 0" using cpos by simp
  have eq: "n + c - 1 = (n - 1) + c" using n1 by simp
  have "(n + c - 1) div c = (n - 1) div c + 1"
    unfolding eq by (rule div_add_self2[OF cnz])
  also have "… ≤ (n - 1) + 1"
    using div_le_dividend[of "n - 1" c] by simp
  also have "… = n" using n1 by simp
  finally show ?thesis .
qed

subsection ‹Enlarge after reduce›

text ‹Reduce ‹M› to the four-symbol machine term‹alphabet_reduce M›, then
  enlarge that.  Language preservation chains the two headline biconditionals:
  ‹alphabet_reduce_language› (from ‹M› to the reduced machine, under the
  per-symbol encoding const‹encode_input_ar›) and ‹alphabet_enlarge_language›
  (from the reduced machine to its enlargement, under the block encoding
  const‹encode_input›).  Two seams are discharged locally: the reduced machine
  is well-formed for any valid four-symbol source
  (‹alphabet_reduce_well_formed›, the input hypothesis
  const‹alphabet_enlarge› requires), and the encoded intermediate word lies in
  the reduced machine's input alphabet term‹{BIT0, BIT1}›
  (‹set_encode_input_ar›).›

theorem alphabet_reduce_enlarge_language:
  fixes M :: "('q, 'a) ktm"
  assumes vM: "valid_ktm M"
      and s_neq_t: "s_ktm M ≠ t_ktm M"
      and s_neq_r: "s_ktm M ≠ r_ktm M"
      and le_neq_bl: "le_ktm M ≠ bl_ktm M"
      and card_ge: "card (Γ_ktm M) ≥ 4"
      and m_pos: "0 < m"
  shows "∀w. set w ⊆ Sigma_ktm M ⟶
           (encode_input m (bl_ktm (alphabet_reduce M))
                (encode_input_ar (Γ_ktm M) (bl_ktm M) w)
              ∈ Lang_ktm (alphabet_enlarge m (alphabet_reduce M)
                   :: ((('q × 'a ar_stage) × sym4 ae_stage),
                       nat ⇒ sym4) ktm))
           = (w ∈ Lang_ktm M)"
proof (intro allI impI)
  fix w assume w: "set w ⊆ Sigma_ktm M"
  let ?Mr = "alphabet_reduce M :: ('q × 'a ar_stage, sym4) ktm"
  let ?enc = "encode_input_ar (Γ_ktm M) (bl_ktm M) w"
  have wfr: "well_formed_ktm ?Mr"
    by (rule alphabet_reduce_well_formed[OF vM card_ge])
  have red: "(?enc ∈ Lang_ktm ?Mr) = (w ∈ Lang_ktm M)"
    using alphabet_reduce_language[OF vM s_neq_t s_neq_r le_neq_bl card_ge] w
    by blast
  have guard: "set ?enc ⊆ Sigma_ktm ?Mr"
    using set_encode_input_ar[of "Γ_ktm M" "bl_ktm M" w]
    by (simp add: alphabet_reduce_Sigma)
  have enl: "(encode_input m (bl_ktm ?Mr) ?enc
                ∈ Lang_ktm (alphabet_enlarge m ?Mr
                     :: ((('q × 'a ar_stage) × sym4 ae_stage),
                         nat ⇒ sym4) ktm))
             = (?enc ∈ Lang_ktm ?Mr)"
    using alphabet_enlarge_language[OF wfr m_pos] guard by blast
  show "(encode_input m (bl_ktm ?Mr) ?enc
            ∈ Lang_ktm (alphabet_enlarge m ?Mr
                 :: ((('q × 'a ar_stage) × sym4 ae_stage),
                     nat ⇒ sym4) ktm))
        = (w ∈ Lang_ktm M)"
    using enl red by simp
qed

text ‹The composed slowdown, with explicit constants.  Reducing then
  enlarging is linear-time, with the affine bound
  ‹8 ⋅ (6 ⋅ k_ktm M + 1) ⋅ b ⋅ T(|w|) + 2 ⋅ b ⋅ |w| + 4›, where
  ‹b = block_width (Γ_ktm M)› is the per-symbol binary width and ‹k_ktm M› the tape
  count.  It routes the explicit reduction bound
  (‹(6 ⋅ k_ktm M + 1) ⋅ b ⋅ T›, ‹alphabet_reduce_time_explicit›) in as the
  enlargement's per-input running-time function ‹Tr›; on the encoded
  intermediate word (length ‹b ⋅ |w|›) the enlargement hypothesis holds
  ∗‹exactly› (‹Tr (b ⋅ |w|) = (6 ⋅ k_ktm M + 1) ⋅ b ⋅ T(|w|)›), and the
  enlargement's ceiling divisions are relaxed by ‹ceil_div_le› and
  ‹accepts_in_time_ktm_mono›.  The enlargement's block-speedup divisor
  ‹m› ∗‹cancels›: it divides the intermediate length
  and running time, but ‹ceil_div_le› discards it in the relaxation, so it
  does not appear in the bound --- the block speedup buys nothing once the
  reduction has fixed the alphabet.  The classical existential form is
  ‹alphabet_reduce_enlarge_time› below.›

theorem alphabet_reduce_enlarge_time_explicit:
  fixes M :: "('q, 'a) ktm" and T :: "nat ⇒ nat"
  assumes vM: "valid_ktm M"
      and s_neq_t: "s_ktm M ≠ t_ktm M"
      and s_neq_r: "s_ktm M ≠ r_ktm M"
      and le_neq_bl: "le_ktm M ≠ bl_ktm M"
      and card_ge: "card (Γ_ktm M) ≥ 4"
      and m_pos: "0 < m"
  shows "∀w. set w ⊆ Sigma_ktm M ⟶
           accepts_in_time_ktm M w (T (length w)) ⟶
           accepts_in_time_ktm
             (alphabet_enlarge m (alphabet_reduce M)
                :: ((('q × 'a ar_stage) × sym4 ae_stage),
                    nat ⇒ sym4) ktm)
             (encode_input m (bl_ktm (alphabet_reduce M))
                (encode_input_ar (Γ_ktm M) (bl_ktm M) w))
             (8 * (6 * k_ktm M + 1) * block_width (Γ_ktm M) * T (length w)
               + 2 * block_width (Γ_ktm M) * length w + 4)"
proof -
  let ?Mr = "alphabet_reduce M :: ('q × 'a ar_stage, sym4) ktm"
  let ?Me = "alphabet_enlarge m ?Mr
               :: ((('q × 'a ar_stage) × sym4 ae_stage),
                   nat ⇒ sym4) ktm"
  let ?kf = "block_width (Γ_ktm M)"
  let ?c = "m"
  let ?d = "6 * k_ktm M + 1"
  have wfr: "well_formed_ktm ?Mr" by (rule alphabet_reduce_well_formed[OF vM card_ge])
  have kfpos: "0 < ?kf" using block_width_pos[of "Γ_ktm M"] by simp
  have cpos: "0 < ?c" by (rule m_pos)
  have ar: "∀w. set w ⊆ Sigma_ktm M ⟶
               accepts_in_time_ktm M w (T (length w)) ⟶
               accepts_in_time_ktm ?Mr (encode_input_ar (Γ_ktm M) (bl_ktm M) w)
                 (?d * ?kf * T (length w))"
    by (rule alphabet_reduce_time_explicit[OF vM s_neq_t s_neq_r le_neq_bl card_ge])
  ― ‹route the reduction bound in as the enlargement's per-input time function›
  define Tr :: "nat ⇒ nat" where "Tr = (λn. ?d * ?kf * T (n div ?kf))"
  have ae: "∀v. set v ⊆ Sigma_ktm ?Mr ⟶
        accepts_in_time_ktm ?Mr v (Tr (length v)) ⟶
        accepts_in_time_ktm ?Me (encode_input m (bl_ktm ?Mr) v)
          (2 * ((length v + ?c - 1) div ?c)
            + 8 * ((Tr (length v) + ?c - 1) div ?c) + 4)"
    by (rule alphabet_enlarge_time_explicit[OF wfr m_pos, where T = Tr])
  show "∀w. set w ⊆ Sigma_ktm M ⟶
        accepts_in_time_ktm M w (T (length w)) ⟶
        accepts_in_time_ktm ?Me
          (encode_input m (bl_ktm ?Mr) (encode_input_ar (Γ_ktm M) (bl_ktm M) w))
          (8 * (6 * k_ktm M + 1) * block_width (Γ_ktm M) * T (length w)
            + 2 * block_width (Γ_ktm M) * length w + 4)"
  proof (intro allI impI)
    fix w assume w: "set w ⊆ Sigma_ktm M"
      and accM: "accepts_in_time_ktm M w (T (length w))"
    let ?v = "encode_input_ar (Γ_ktm M) (bl_ktm M) w"
    have lenv: "length ?v = ?kf * length w"
      by (simp add: length_encode_input_ar)
    have div_w: "length ?v div ?kf = length w"
      using lenv kfpos by simp
    have Tr_v: "Tr (length ?v) = ?d * ?kf * T (length w)"
      using div_w by (simp add: Tr_def)
    have accr: "accepts_in_time_ktm ?Mr ?v (Tr (length ?v))"
      using ar w accM Tr_v by simp
    have guard: "set ?v ⊆ Sigma_ktm ?Mr"
      using set_encode_input_ar[of "Γ_ktm M" "bl_ktm M" w]
      by (simp add: alphabet_reduce_Sigma)
    have ae_acc: "accepts_in_time_ktm ?Me (encode_input m (bl_ktm ?Mr) ?v)
                    (2 * ((length ?v + ?c - 1) div ?c)
                      + 8 * ((Tr (length ?v) + ?c - 1) div ?c) + 4)"
      using ae guard accr by blast
    have bound_le:
      "2 * ((length ?v + ?c - 1) div ?c)
         + 8 * ((Tr (length ?v) + ?c - 1) div ?c) + 4
       ≤ 8 * ?d * ?kf * T (length w) + 2 * ?kf * length w + 4"
    proof -
      have h1: "(length ?v + ?c - 1) div ?c ≤ length ?v" by (rule ceil_div_le[OF cpos])
      have h2: "(Tr (length ?v) + ?c - 1) div ?c ≤ Tr (length ?v)" by (rule ceil_div_le[OF cpos])
      have "2 * ((length ?v + ?c - 1) div ?c)
              + 8 * ((Tr (length ?v) + ?c - 1) div ?c) + 4
            ≤ 2 * length ?v + 8 * Tr (length ?v) + 4"
        using h1 h2 by (simp add: add_mono mult_le_mono2)
      also have "… = 2 * (?kf * length w) + 8 * (?d * ?kf * T (length w)) + 4"
        using lenv Tr_v by simp
      also have "… = 8 * ?d * ?kf * T (length w) + 2 * ?kf * length w + 4"
        by (simp add: algebra_simps)
      finally show ?thesis .
    qed
    show "accepts_in_time_ktm ?Me
            (encode_input m (bl_ktm ?Mr) ?v)
            (8 * (6 * k_ktm M + 1) * block_width (Γ_ktm M) * T (length w)
              + 2 * block_width (Γ_ktm M) * length w + 4)"
      by (rule accepts_in_time_ktm_mono[OF ae_acc bound_le])
  qed
qed

text ‹The classical existential form ‹A ⋅ T(|w|) + B ⋅ |w| + C›, with
  ‹A = 8 ⋅ (6 ⋅ k_ktm M + 1) ⋅ b›,
  ‹B = 2 ⋅ b›, and ‹C = 4› from
  ‹alphabet_reduce_enlarge_time_explicit›.›

theorem alphabet_reduce_enlarge_time:
  fixes M :: "('q, 'a) ktm" and T :: "nat ⇒ nat"
  assumes vM: "valid_ktm M"
      and s_neq_t: "s_ktm M ≠ t_ktm M"
      and s_neq_r: "s_ktm M ≠ r_ktm M"
      and le_neq_bl: "le_ktm M ≠ bl_ktm M"
      and card_ge: "card (Γ_ktm M) ≥ 4"
      and m_pos: "0 < m"
  obtains A B C :: nat
  where "∀w. set w ⊆ Sigma_ktm M ⟶
           accepts_in_time_ktm M w (T (length w)) ⟶
           accepts_in_time_ktm
             (alphabet_enlarge m (alphabet_reduce M)
                :: ((('q × 'a ar_stage) × sym4 ae_stage),
                    nat ⇒ sym4) ktm)
             (encode_input m (bl_ktm (alphabet_reduce M))
                (encode_input_ar (Γ_ktm M) (bl_ktm M) w))
             (A * T (length w) + B * length w + C)"
proof (rule that[of "8 * (6 * k_ktm M + 1) * block_width (Γ_ktm M)"
                    "2 * block_width (Γ_ktm M)" 4])
  show "∀w. set w ⊆ Sigma_ktm M ⟶
           accepts_in_time_ktm M w (T (length w)) ⟶
           accepts_in_time_ktm
             (alphabet_enlarge m (alphabet_reduce M)
                :: ((('q × 'a ar_stage) × sym4 ae_stage),
                    nat ⇒ sym4) ktm)
             (encode_input m (bl_ktm (alphabet_reduce M))
                (encode_input_ar (Γ_ktm M) (bl_ktm M) w))
             (8 * (6 * k_ktm M + 1) * block_width (Γ_ktm M) * T (length w)
               + 2 * block_width (Γ_ktm M) * length w + 4)"
    by (rule alphabet_reduce_enlarge_time_explicit[OF vM s_neq_t s_neq_r le_neq_bl card_ge m_pos])
qed

subsection ‹Reduce after enlarge›

text ‹Enlarge ‹M› to the block machine term‹alphabet_enlarge m M›, then reduce
  that back to four symbols.  This is the direction whose seams need the
  enlarged machine's own well-formedness data: its start / accept / reject
  states, blank and endmarker are the source ones tagged / block-encoded (the
  field accessors ‹s_ktm_alphabet_enlarge› etc.), and its tape alphabet is the
  block alphabet term‹gamma_block m (Γ_ktm M)›, whose cardinality is at least
  the source's (‹card_gamma_block_ge_card›) --- so a four-symbol source stays
  above the reduction's minimal-alphabet bound.›

lemma Gamma_ktm_alphabet_enlarge:
  fixes M :: "('q, 'a) ktm"
  shows "Γ_ktm (alphabet_enlarge m M
                  :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
          = gamma_block m (Γ_ktm M)"
  by (cases M) (simp add: alphabet_enlarge_def)

text ‹Enlargement preserves the tape count (the last ‹ktm› field is
  copied unchanged): the block transformation is purely alphabet-level, so the
  reduction's tape-count factor ‹6 ⋅ k_ktm M + 1› is the ∗‹source› tape count
  even when the reduction is applied to the enlarged machine.  Mirrors
  ‹alphabet_reduce_preserves_tape_count›.›

lemma k_ktm_alphabet_enlarge:
  fixes M :: "('q, 'a) ktm"
  shows "k_ktm (alphabet_enlarge m M
                  :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
          = k_ktm M"
  by (cases M) (simp add: alphabet_enlarge_def)

text ‹Discharge of the reduction's input hypotheses on the enlarged machine
  (validity, the three non-degeneracy conditions, and the four-symbol lower
  bound), packaged for reuse by both the language and the time theorem.›

lemma alphabet_enlarge_reduce_hyps:
  fixes M :: "('q, 'a) ktm"
  assumes vM: "valid_ktm M"
      and s_neq_t: "s_ktm M ≠ t_ktm M"
      and s_neq_r: "s_ktm M ≠ r_ktm M"
      and le_neq_bl: "le_ktm M ≠ bl_ktm M"
      and card_ge: "card (Γ_ktm M) ≥ 4"
      and m_pos: "0 < m"
  shows "valid_ktm (alphabet_enlarge m M
            :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)"
    and "s_ktm (alphabet_enlarge m M
            :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
          ≠ t_ktm (alphabet_enlarge m M)"
    and "s_ktm (alphabet_enlarge m M
            :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
          ≠ r_ktm (alphabet_enlarge m M)"
    and "le_ktm (alphabet_enlarge m M
            :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)
          ≠ bl_ktm (alphabet_enlarge m M)"
    and "card (Γ_ktm (alphabet_enlarge m M
            :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)) ≥ 4"
proof -
  let ?M' = "alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm"
  have finG: "finite (Γ_ktm M)" by (rule valid_ktm_finite_Gamma[OF vM])
  show "valid_ktm ?M'" by (rule alphabet_enlarge_wf[OF vM m_pos])
  show "s_ktm ?M' ≠ t_ktm ?M'"
    using s_neq_t by (simp add: s_ktm_alphabet_enlarge t_ktm_alphabet_enlarge)
  show "s_ktm ?M' ≠ r_ktm ?M'"
    using s_neq_r by (simp add: s_ktm_alphabet_enlarge r_ktm_alphabet_enlarge)
  show "le_ktm ?M' ≠ bl_ktm ?M'"
  proof
    assume "le_ktm ?M' = bl_ktm ?M'"
    hence "(LE_block m (le_ktm M) :: nat ⇒ 'a) = bl_block m (bl_ktm M)"
      by (simp add: le_ktm_alphabet_enlarge bl_ktm_alphabet_enlarge)
    hence "le_ktm M = bl_ktm M" by (rule LE_block_eq_bl_block_imp_eq[OF _ m_pos])
    with le_neq_bl show False by simp
  qed
  have "card (Γ_ktm M) ≤ card (gamma_block m (Γ_ktm M) :: (nat ⇒ 'a) set)"
    by (rule card_gamma_block_ge_card[OF finG m_pos])
  hence "4 ≤ card (gamma_block m (Γ_ktm M) :: (nat ⇒ 'a) set)"
    using card_ge by linarith
  thus "card (Γ_ktm ?M') ≥ 4" by (simp add: Gamma_ktm_alphabet_enlarge)
qed

text ‹The intermediate-word guard: the block encoding of a genuine input
  word lands in the enlarged machine's input alphabet (it is a block
  over the source, and avoids the two reserved blocks).  Shared by the
  language and time theorems of this direction.›

lemma encode_input_in_Sigma_alphabet_enlarge:
  fixes M :: "('q, 'a) ktm"
  assumes vM: "valid_ktm M" and w: "set w ⊆ Sigma_ktm M"
  shows "set (encode_input m (bl_ktm M) w :: (nat ⇒ 'a) list)
           ⊆ Sigma_ktm (alphabet_enlarge m M
                :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)"
proof -
  have "set (encode_input m (bl_ktm M) w :: (nat ⇒ 'a) list)
          ⊆ gamma_block m (Sigma_ktm M ∪ {bl_ktm M})"
    by (rule encode_input_in_gamma_block[OF w])
  moreover have "bl_block m (bl_ktm M)
          ∉ set (encode_input m (bl_ktm M) w :: (nat ⇒ 'a) list)"
    by (rule encode_input_no_bl_block[OF vM w])
  moreover have "LE_block m (le_ktm M)
          ∉ set (encode_input m (bl_ktm M) w :: (nat ⇒ 'a) list)"
    by (rule encode_input_no_LE_block[OF vM w])
  ultimately show ?thesis by (auto simp: Sigma_ktm_alphabet_enlarge)
qed

theorem alphabet_enlarge_reduce_language:
  fixes M :: "('q, 'a) ktm"
  assumes wfM: "well_formed_ktm M"
      and card_ge: "card (Γ_ktm M) ≥ 4"
      and m_pos: "0 < m"
  shows "∀w. set w ⊆ Sigma_ktm M ⟶
           (encode_input_ar
               (Γ_ktm (alphabet_enlarge m M
                        :: ('q × 'a ae_stage, nat ⇒ 'a) ktm))
               (bl_ktm (alphabet_enlarge m M))
               (encode_input m (bl_ktm M) w)
             ∈ Lang_ktm (alphabet_reduce (alphabet_enlarge m M)
                  :: ((('q × 'a ae_stage) × (nat ⇒ 'a) ar_stage), sym4) ktm))
           = (w ∈ Lang_ktm M)"
proof (intro allI impI)
  fix w assume w: "set w ⊆ Sigma_ktm M"
  let ?M' = "alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm"
  have vM: "valid_ktm M"
    and s_neq_t: "s_ktm M ≠ t_ktm M"
    and s_neq_r: "s_ktm M ≠ r_ktm M"
    and le_neq_bl: "le_ktm M ≠ bl_ktm M"
    using wfM by auto
  note hyps = alphabet_enlarge_reduce_hyps[OF vM s_neq_t s_neq_r le_neq_bl card_ge m_pos]
  have enl: "(encode_input m (bl_ktm M) w ∈ Lang_ktm ?M') = (w ∈ Lang_ktm M)"
    using alphabet_enlarge_language[OF wfM m_pos] w by blast
  have guard: "set (encode_input m (bl_ktm M) w :: (nat ⇒ 'a) list) ⊆ Sigma_ktm ?M'"
    by (rule encode_input_in_Sigma_alphabet_enlarge[OF vM w])
  have red: "(encode_input_ar (Γ_ktm ?M') (bl_ktm ?M') (encode_input m (bl_ktm M) w)
                ∈ Lang_ktm (alphabet_reduce ?M'
                     :: ((('q × 'a ae_stage) × (nat ⇒ 'a) ar_stage), sym4) ktm))
             = (encode_input m (bl_ktm M) w ∈ Lang_ktm ?M')"
    using alphabet_reduce_language[OF hyps(1) hyps(2) hyps(3) hyps(4) hyps(5)] guard
    by blast
  show "(encode_input_ar (Γ_ktm ?M') (bl_ktm ?M') (encode_input m (bl_ktm M) w)
            ∈ Lang_ktm (alphabet_reduce ?M'
                 :: ((('q × 'a ae_stage) × (nat ⇒ 'a) ar_stage), sym4) ktm))
        = (w ∈ Lang_ktm M)"
    using red enl by simp
qed

text ‹The composed slowdown for reduce-after-enlarge, with explicit
  constants.  Unlike the other order, the inner transformation (enlargement)
  ∗‹speeds up› by the block size ‹m›, so the
  intermediate word has length ‹⌈|w| / m⌉› --- a lossy function of ‹|w|›,
  not an exact multiple --- and the enlarged machine's running time cannot be
  routed into the reduction's time function exactly.  Two mild ingredients
  close the gap: ‹T› is assumed non-decreasing (‹mono T›), and the outer
  bound is stated at ‹T(|w| + c - 1)› --- ‹T› at the input length rounded up
  to the next block boundary.  The bound is
  ‹8 ⋅ D ⋅ b' ⋅ T(|w| + c - 1) + 2 ⋅ D ⋅ b' ⋅ |w| + 4 ⋅ D ⋅ b'›, where
  ‹D = 6 ⋅ k_ktm M + 1› (the tape count is preserved by enlargement,
  ‹k_ktm_alphabet_enlarge›) and
  ‹b' = block_width (Γ_ktm (alphabet_enlarge m M)) = block_width (gamma_block m (Γ_ktm M))› is
  the per-symbol width of the ∗‹block› alphabet, i.e.
  ‹⌈c ⋅ log2 (card ΓM)⌉›.  Because ‹b'› grows with ‹c›, the block-speedup
  factor ∗‹does not› cancel here: ‹c› survives both in the time argument
  ‹T(|w| + c - 1)› and, through ‹b'›, in every coefficient.  The classical
  existential form is ‹alphabet_enlarge_reduce_time› below.›

theorem alphabet_enlarge_reduce_time_explicit:
  fixes M :: "('q, 'a) ktm" and T :: "nat ⇒ nat"
  assumes wfM: "well_formed_ktm M"
      and card_ge: "card (Γ_ktm M) ≥ 4"
      and Tmono: "mono T"
      and m_pos: "0 < m"
  shows "∀w. set w ⊆ Sigma_ktm M ⟶
           accepts_in_time_ktm M w (T (length w)) ⟶
           accepts_in_time_ktm
             (alphabet_reduce (alphabet_enlarge m M)
                :: ((('q × 'a ae_stage) × (nat ⇒ 'a) ar_stage), sym4) ktm)
             (encode_input_ar
                 (Γ_ktm (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm))
                 (bl_ktm (alphabet_enlarge m M))
                 (encode_input m (bl_ktm M) w))
             (8 * (6 * k_ktm M + 1)
                   * block_width (Γ_ktm (alphabet_enlarge m M
                        :: ('q × 'a ae_stage, nat ⇒ 'a) ktm))
                   * T (length w + m - 1)
               + 2 * (6 * k_ktm M + 1)
                   * block_width (Γ_ktm (alphabet_enlarge m M
                        :: ('q × 'a ae_stage, nat ⇒ 'a) ktm))
                   * length w
               + 4 * (6 * k_ktm M + 1)
                   * block_width (Γ_ktm (alphabet_enlarge m M
                        :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)))"
proof -
  let ?M' = "alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm"
  let ?c = "m"
  let ?ke = "block_width (Γ_ktm ?M')"
  let ?d = "6 * k_ktm M + 1"
  have vM: "valid_ktm M"
    and s_neq_t: "s_ktm M ≠ t_ktm M"
    and s_neq_r: "s_ktm M ≠ r_ktm M"
    and le_neq_bl: "le_ktm M ≠ bl_ktm M"
    using wfM by auto
  have cpos: "0 < ?c" by (rule m_pos)
  have ktm: "k_ktm ?M' = k_ktm M" by (rule k_ktm_alphabet_enlarge)
  note hyps = alphabet_enlarge_reduce_hyps[OF vM s_neq_t s_neq_r le_neq_bl card_ge m_pos]
  ― ‹enlargement time constants (explicit: ‹al = 2›, ‹fe = 4›)›
  have ae: "∀w. set w ⊆ Sigma_ktm M ⟶
        accepts_in_time_ktm M w (T (length w)) ⟶
        accepts_in_time_ktm ?M' (encode_input m (bl_ktm M) w)
          (2 * ((length w + ?c - 1) div ?c)
            + 8 * ((T (length w) + ?c - 1) div ?c) + 4)"
    by (rule alphabet_enlarge_time_explicit[OF wfM m_pos])
  ― ‹route the enlarged machine's running time in as the reduction's time function›
  define Te :: "nat ⇒ nat" where "Te = (λn. 8 * T (?c * n) + 2 * n + 4)"
  ― ‹reduction on the enlarged machine (explicit: ‹e = fr = 0›,
      ‹d = 6 ⋅ k_ktm M + 1› by tape preservation, ‹b› the block-alphabet width)›
  have ar0: "∀v. set v ⊆ Sigma_ktm ?M' ⟶
        accepts_in_time_ktm ?M' v (Te (length v)) ⟶
        accepts_in_time_ktm (alphabet_reduce ?M'
            :: ((('q × 'a ae_stage) × (nat ⇒ 'a) ar_stage), sym4) ktm)
          (encode_input_ar (Γ_ktm ?M') (bl_ktm ?M') v)
          ((6 * k_ktm ?M' + 1) * ?ke * Te (length v))"
    by (rule alphabet_reduce_time_explicit[OF hyps(1) hyps(2) hyps(3) hyps(4) hyps(5)])
  have ar: "∀v. set v ⊆ Sigma_ktm ?M' ⟶
        accepts_in_time_ktm ?M' v (Te (length v)) ⟶
        accepts_in_time_ktm (alphabet_reduce ?M'
            :: ((('q × 'a ae_stage) × (nat ⇒ 'a) ar_stage), sym4) ktm)
          (encode_input_ar (Γ_ktm ?M') (bl_ktm ?M') v)
          (?d * ?ke * Te (length v))"
    using ar0 by (simp add: ktm)
  show "∀w. set w ⊆ Sigma_ktm M ⟶
        accepts_in_time_ktm M w (T (length w)) ⟶
        accepts_in_time_ktm (alphabet_reduce ?M'
            :: ((('q × 'a ae_stage) × (nat ⇒ 'a) ar_stage), sym4) ktm)
          (encode_input_ar (Γ_ktm ?M') (bl_ktm ?M') (encode_input m (bl_ktm M) w))
          (8 * ?d * ?ke * T (length w + ?c - 1)
            + 2 * ?d * ?ke * length w + 4 * ?d * ?ke)"
  proof (intro allI impI)
    fix w assume w: "set w ⊆ Sigma_ktm M"
      and accM: "accepts_in_time_ktm M w (T (length w))"
    let ?v = "encode_input m (bl_ktm M) w :: (nat ⇒ 'a) list"
    have lenv: "length ?v = (length w + ?c - 1) div ?c"
      by (rule length_encode_input)
    have lv_le: "length ?v ≤ length w"
      using lenv ceil_div_le[OF cpos] by simp
    have cge: "length w ≤ ?c * length ?v"
    proof -
      have eq: "?c * ((length w + ?c - 1) div ?c) + (length w + ?c - 1) mod ?c
              = length w + ?c - 1"
        by (rule mult_div_mod_eq)
      have ml: "(length w + ?c - 1) mod ?c < ?c"
        using cpos by (rule mod_less_divisor)
      have "length w ≤ ?c * ((length w + ?c - 1) div ?c)"
        using eq ml cpos by linarith
      thus ?thesis by (simp add: lenv)
    qed
    have mcle: "?c * length ?v ≤ length w + ?c - 1"
    proof -
      have "?c * ((length w + ?c - 1) div ?c) ≤ length w + ?c - 1"
        by (metis mult_div_mod_eq le_add1)
      thus ?thesis using lenv by simp
    qed
    ― ‹enlargement: the enlarged machine accepts the block encoding›
    have accAE: "accepts_in_time_ktm ?M' ?v
                   (2 * ((length w + ?c - 1) div ?c)
                     + 8 * ((T (length w) + ?c - 1) div ?c) + 4)"
      using ae w accM by blast
    ― ‹its bound is dominated by ‹Te› at the intermediate length›
    have le1: "2 * ((length w + ?c - 1) div ?c)
                 + 8 * ((T (length w) + ?c - 1) div ?c) + 4
               ≤ Te (length ?v)"
    proof -
      have alv: "2 * ((length w + ?c - 1) div ?c) = 2 * length ?v"
        by (simp add: lenv)
      have tb: "8 * ((T (length w) + ?c - 1) div ?c) ≤ 8 * T (?c * length ?v)"
      proof -
        have "(T (length w) + ?c - 1) div ?c ≤ T (length w)"
          by (rule ceil_div_le[OF cpos])
        also have "… ≤ T (?c * length ?v)" using Tmono cge by (rule monoD)
        finally show ?thesis by (rule mult_le_mono2)
      qed
      have "2 * ((length w + ?c - 1) div ?c)
              + 8 * ((T (length w) + ?c - 1) div ?c) + 4
            = 2 * length ?v + 8 * ((T (length w) + ?c - 1) div ?c) + 4"
        by (simp only: alv)
      also have "… ≤ 2 * length ?v + 8 * T (?c * length ?v) + 4"
        using tb by simp
      also have "… = Te (length ?v)" by (simp add: Te_def)
      finally show ?thesis .
    qed
    have accr_hyp: "accepts_in_time_ktm ?M' ?v (Te (length ?v))"
      by (rule accepts_in_time_ktm_mono[OF accAE le1])
    have guard: "set ?v ⊆ Sigma_ktm ?M'"
      by (rule encode_input_in_Sigma_alphabet_enlarge[OF vM w])
    have accAR: "accepts_in_time_ktm (alphabet_reduce ?M'
                    :: ((('q × 'a ae_stage) × (nat ⇒ 'a) ar_stage), sym4) ktm)
                    (encode_input_ar (Γ_ktm ?M') (bl_ktm ?M') ?v)
                    (?d * ?ke * Te (length ?v))"
      using ar guard accr_hyp by blast
    have le2: "?d * ?ke * Te (length ?v)
                 ≤ 8 * ?d * ?ke * T (length w + ?c - 1)
                     + 2 * ?d * ?ke * length w + 4 * ?d * ?ke"
    proof -
      have T_le: "T (?c * length ?v) ≤ T (length w + ?c - 1)"
        using Tmono mcle by (simp add: monoD)
      have TeB: "Te (length ?v) ≤ 8 * T (length w + ?c - 1) + 2 * length w + 4"
        unfolding Te_def using T_le lv_le
        by (auto intro: add_mono mult_le_mono2)
      have "?d * ?ke * Te (length ?v)
              ≤ ?d * ?ke * (8 * T (length w + ?c - 1) + 2 * length w + 4)"
        using TeB by (rule mult_le_mono2)
      also have "… = 8 * ?d * ?ke * T (length w + ?c - 1)
                        + 2 * ?d * ?ke * length w + 4 * ?d * ?ke"
        by (simp add: algebra_simps)
      finally show ?thesis .
    qed
    show "accepts_in_time_ktm (alphabet_reduce ?M'
              :: ((('q × 'a ae_stage) × (nat ⇒ 'a) ar_stage), sym4) ktm)
            (encode_input_ar (Γ_ktm ?M') (bl_ktm ?M') ?v)
            (8 * ?d * ?ke * T (length w + ?c - 1)
              + 2 * ?d * ?ke * length w + 4 * ?d * ?ke)"
      by (rule accepts_in_time_ktm_mono[OF accAR le2])
  qed
qed

text ‹The classical existential form ‹A ⋅ T(|w| + c - 1) + B ⋅ |w| + C›,
  with ‹A = 8 ⋅ D ⋅ b'›, ‹B = 2 ⋅ D ⋅ b'›, ‹C = 4 ⋅ D ⋅ b'› for
  ‹D = 6 ⋅ k_ktm M + 1› and ‹b' = block_width (Γ_ktm (alphabet_enlarge M))›, from
  ‹alphabet_enlarge_reduce_time_explicit›.›

theorem alphabet_enlarge_reduce_time:
  fixes M :: "('q, 'a) ktm" and T :: "nat ⇒ nat"
  assumes wfM: "well_formed_ktm M"
      and card_ge: "card (Γ_ktm M) ≥ 4"
      and Tmono: "mono T"
      and m_pos: "0 < m"
  obtains A B C :: nat
  where "∀w. set w ⊆ Sigma_ktm M ⟶
           accepts_in_time_ktm M w (T (length w)) ⟶
           accepts_in_time_ktm
             (alphabet_reduce (alphabet_enlarge m M)
                :: ((('q × 'a ae_stage) × (nat ⇒ 'a) ar_stage), sym4) ktm)
             (encode_input_ar
                 (Γ_ktm (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm))
                 (bl_ktm (alphabet_enlarge m M))
                 (encode_input m (bl_ktm M) w))
             (A * T (length w + m - 1) + B * length w + C)"
proof (rule that[of "8 * (6 * k_ktm M + 1)
                       * block_width (Γ_ktm (alphabet_enlarge m M
                            :: ('q × 'a ae_stage, nat ⇒ 'a) ktm))"
                    "2 * (6 * k_ktm M + 1)
                       * block_width (Γ_ktm (alphabet_enlarge m M
                            :: ('q × 'a ae_stage, nat ⇒ 'a) ktm))"
                    "4 * (6 * k_ktm M + 1)
                       * block_width (Γ_ktm (alphabet_enlarge m M
                            :: ('q × 'a ae_stage, nat ⇒ 'a) ktm))"])
  show "∀w. set w ⊆ Sigma_ktm M ⟶
           accepts_in_time_ktm M w (T (length w)) ⟶
           accepts_in_time_ktm
             (alphabet_reduce (alphabet_enlarge m M)
                :: ((('q × 'a ae_stage) × (nat ⇒ 'a) ar_stage), sym4) ktm)
             (encode_input_ar
                 (Γ_ktm (alphabet_enlarge m M :: ('q × 'a ae_stage, nat ⇒ 'a) ktm))
                 (bl_ktm (alphabet_enlarge m M))
                 (encode_input m (bl_ktm M) w))
             (8 * (6 * k_ktm M + 1)
                   * block_width (Γ_ktm (alphabet_enlarge m M
                        :: ('q × 'a ae_stage, nat ⇒ 'a) ktm))
                   * T (length w + m - 1)
               + 2 * (6 * k_ktm M + 1)
                   * block_width (Γ_ktm (alphabet_enlarge m M
                        :: ('q × 'a ae_stage, nat ⇒ 'a) ktm))
                   * length w
               + 4 * (6 * k_ktm M + 1)
                   * block_width (Γ_ktm (alphabet_enlarge m M
                        :: ('q × 'a ae_stage, nat ⇒ 'a) ktm)))"
    by (rule alphabet_enlarge_reduce_time_explicit[OF wfM card_ge Tmono m_pos])
qed

end