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