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])
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 ⋅ log⇩2 (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]
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])
define Te :: "nat ⇒ nat" where "Te = (λn. 8 * T (?c * n) + 2 * n + 4)"
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
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
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