Theory Multitape_Time_Convention
theory Multitape_Time_Convention
imports Multitape_Finite_Patch
begin
section ‹Time bounds in the textbook convention, and the cleanup›
text ‹Shared vocabulary for the linear-speedup consumers. An
∗‹eventual› bound holds for all long enough inputs in the language; a
∗‹convention› bound is the Hopcroft--Ullman
\<^cite>‹‹p.~291› in "Hopcroft1979:introduction"› ‹max(n+1, ...)› form on
the substrate, where the floor is ‹n + 2› (the substrate reads the
left endmarker before the first input symbol).›
definition time_bounded_ev :: "('q, 'a) ktm ⇒ (nat ⇒ nat) ⇒ bool" where
"time_bounded_ev M g ⟷
(∃N. ∀w∈Lang_ktm M. N ≤ length w
⟶ accepts_in_time_ktm M w (g (length w)))"
definition time_bounded_conv :: "('q, 'a) ktm ⇒ (nat ⇒ nat) ⇒ bool" where
"time_bounded_conv M g ⟷
(∀w∈Lang_ktm M.
accepts_in_time_ktm M w (max (length w + 2) (g (length w))))"
text ‹The cleanup corollary: an eventual bound is upgraded to a
convention bound on ∗‹all› inputs, at the cost of the finite-control
overhead ‹c0 = 2 * N + 4›, with language, tape count, and determinism
preserved. Instantiates @{const finite_patch} with the (finite, hence
unconditionally available) table ‹w ∈ Lang_ktm M›.
Hypotheses are the weakest the proof uses --- @{const valid_ktm} and
‹bl_ktm M ≠ le_ktm M›, matching the @{const finite_patch} contract
lemmas it composes (‹finite_patch_language› / ‹_det› /
‹fp_short_time› / ‹fp_long_time›). In particular it does ∗‹not›
require @{const le_unique} or the state distinctness of
@{const well_formed_ktm}, so it applies to machines (e.g. the
encoding wrap) whose ‹le›-uniqueness is not separately established.›
theorem time_cleanup:
assumes vM: "valid_ktm M" and blle: "bl_ktm M ≠ le_ktm M"
and ev: "time_bounded_ev M g"
obtains N where
"Lang_ktm (finite_patch M (λw. w ∈ Lang_ktm M) N) = Lang_ktm M"
and "k_ktm (finite_patch M (λw. w ∈ Lang_ktm M) N) = k_ktm M"
and "det_ktm M ⟶ det_ktm (finite_patch M (λw. w ∈ Lang_ktm M) N)"
and "time_bounded_conv (finite_patch M (λw. w ∈ Lang_ktm M) N)
(λn. g n + (2 * N + 4))"
proof -
from ev obtain N where evN: "∀w∈Lang_ktm M. N ≤ length w
⟶ accepts_in_time_ktm M w (g (length w))"
unfolding time_bounded_ev_def by blast
let ?M' = "finite_patch M (λw. w ∈ Lang_ktm M) N"
have lang: "Lang_ktm ?M' = Lang_ktm M"
proof -
have "Lang_ktm ?M' = {w. set w ⊆ Sigma_ktm M
∧ (if length w ≤ N then w ∈ Lang_ktm M else w ∈ Lang_ktm M)}"
by (rule finite_patch_language[OF vM blle])
also have "… = {w. set w ⊆ Sigma_ktm M ∧ w ∈ Lang_ktm M}" by simp
also have "… = Lang_ktm M" unfolding Lang_ktm_def by auto
finally show ?thesis .
qed
have kpres: "k_ktm ?M' = k_ktm M" by (rule finite_patch_k_ktm)
have detpres: "det_ktm M ⟶ det_ktm ?M'"
using finite_patch_det[OF vM blle] by blast
have conv: "time_bounded_conv ?M' (λn. g n + (2 * N + 4))"
unfolding time_bounded_conv_def
proof
fix w assume "w ∈ Lang_ktm ?M'"
hence wL: "w ∈ Lang_ktm M" using lang by simp
have wSg: "set w ⊆ Sigma_ktm M" using wL unfolding Lang_ktm_def by simp
show "accepts_in_time_ktm ?M' w
(max (length w + 2) ((λn. g n + (2 * N + 4)) (length w)))"
proof (cases "length w ≤ N")
case True
have "accepts_in_time_ktm ?M' w (length w + 2)"
using vM wSg True wL by (rule fp_short_time)
moreover have "length w + 2 ≤ max (length w + 2) (g (length w) + (2 * N + 4))"
by simp
ultimately show ?thesis by (auto elim: accepts_in_time_ktm_mono)
next
case False
hence Nlt: "N < length w" by simp
have "accepts_in_time_ktm M w (g (length w))" using evN wL Nlt by simp
hence "accepts_in_time_ktm ?M' w (g (length w) + (2 * N + 4))"
by (rule fp_long_time[OF vM wSg Nlt])
moreover have "g (length w) + (2 * N + 4)
≤ max (length w + 2) (g (length w) + (2 * N + 4))" by simp
ultimately show ?thesis by (auto elim: accepts_in_time_ktm_mono)
qed
qed
show thesis
proof (rule that[of N])
show "Lang_ktm ?M' = Lang_ktm M" by (rule lang)
show "k_ktm ?M' = k_ktm M" by (rule kpres)
show "det_ktm M ⟶ det_ktm ?M'" by (rule detpres)
show "time_bounded_conv ?M' (λn. g n + (2 * N + 4))" by (rule conv)
qed
qed
subsection ‹The clean convention form is unattainable in general›
text ‹Why the linear-‹T› speedup theorems are stated with a residual
‹+K› (all inputs) or an explicit threshold (eventual), never as the clean
‹time_bounded_conv M (λn. n + n div q)› on ∗‹all› inputs: that clean form
is not attainable for a machine whose small-input computation exceeds the
convention floor ‹n + 2›. The minimal witness ‹conv_cex_ktm› below
(the convention's counterexample) is a deterministic, valid machine over the
empty input alphabet that accepts the empty input in exactly
∗‹three› steps (state chain ‹0 → 1 → 2 → 3›, reading and
rewriting the left endmarker in place), one more than the floor
‹length [] + 2 = 2›. So ‹[] ∈ Lang_ktm conv_cex_ktm› yet
‹¬ accepts_in_time_ktm conv_cex_ktm [] 2›, hence
‹time_bounded_conv conv_cex_ktm (λn. n + n div q)› fails at ‹[]› for
every ‹q›. ‹conv_cex_ktm› stands in for the encoding wrap, whose
own setup phases (‹W_Init → W_Buf → W_Reset → W_Disp›) likewise exceed the
floor on tiny inputs; closing the small-input band needs the non-effective
finite-exceptions table (an existence-only object; see ‹time_cleanup›),
which is exactly what the clean form would
demand and what the speedup construction does not build.›
definition conv_cex_delta ::
"(nat × (nat ⇒ nat) × nat × (nat ⇒ nat) × (nat ⇒ move)) set" where
"conv_cex_delta = {(0, one_tape_read 1, 1, one_tape_read 1, λ_. MoveN),
(1, one_tape_read 1, 2, one_tape_read 1, λ_. MoveN),
(2, one_tape_read 1, 3, one_tape_read 1, λ_. MoveN)}"
definition conv_cex_ktm :: "(nat, nat) ktm" where
"conv_cex_ktm = KTM {0,1,2,3,4} {} {0,1} 0 1 conv_cex_delta 0 3 4 1"
definition conv_cex_tape :: "nat ⇒ nat ⇒ nat" where
"conv_cex_tape = (λi n. if i = 0 ∧ n = 0 then 1 else 0)"
abbreviation conv_cex_cfg :: "nat ⇒ (nat, nat) ktc_config" where
"conv_cex_cfg q ≡ KConfig q conv_cex_tape (λ_. 0)"
lemma conv_cex_delta_ktm: "delta_ktm conv_cex_ktm = conv_cex_delta"
by (simp add: conv_cex_ktm_def)
lemma conv_cex_t_ktm: "t_ktm conv_cex_ktm = 3" by (simp add: conv_cex_ktm_def)
lemma conv_cex_read_eq: "(λk. conv_cex_tape k ((λ_. 0::nat) k)) = one_tape_read 1"
by (simp add: conv_cex_tape_def one_tape_read_def fun_eq_iff)
lemma conv_cex_valid: "valid_ktm conv_cex_ktm"
by (auto simp: conv_cex_ktm_def conv_cex_delta_def one_tape_read_def Pi_iff)
lemma conv_cex_det: "det_ktm conv_cex_ktm"
by (auto simp: det_ktm_def conv_cex_delta_ktm conv_cex_delta_def)
lemma conv_cex_init: "init_config_ktm conv_cex_ktm [] = conv_cex_cfg 0"
by (auto simp: conv_cex_ktm_def conv_cex_tape_def fun_eq_iff)
text ‹Forward: each state ‹m ≤ 2› steps deterministically to ‹m + 1›, the
tape and heads unchanged (the endmarker is re-read and re-written in place).›
lemma conv_cex_step_fwd:
assumes "m ≤ 2"
shows "(conv_cex_cfg m, conv_cex_cfg (Suc m)) ∈ ktm_step conv_cex_delta"
proof -
have mem: "(m, one_tape_read 1, Suc m, one_tape_read 1, λ_. MoveN) ∈ conv_cex_delta"
using assms unfolding conv_cex_delta_def by (cases m; simp; presburger)
have upd: "(λk. (conv_cex_tape k)((λ_. 0::nat) k := one_tape_read 1 k)) = conv_cex_tape"
by (simp add: conv_cex_tape_def one_tape_read_def fun_eq_iff)
have mov: "(λk. go_move ((λ_. MoveN) k) ((λ_. 0::nat) k)) = (λ_. 0)"
by simp
have "(KConfig m conv_cex_tape (λ_. 0),
KConfig (Suc m) (λk. (conv_cex_tape k)((λ_. 0) k := one_tape_read 1 k))
(λk. go_move ((λ_. MoveN) k) ((λ_. 0) k)))
∈ ktm_step conv_cex_delta"
by (rule ktm_step.step) (use mem conv_cex_read_eq in simp)
thus ?thesis using upd mov by simp
qed
text ‹Backward: from state ‹m› the ∗‹only› successor is state ‹m + 1› ---
the single ‹conv_cex_delta› entry with source ‹m›, tape and heads fixed.›
lemma conv_cex_delta_inv:
"(m, one_tape_read 1, q', a, move) ∈ conv_cex_delta ⟹ q' = Suc m ∧ a = one_tape_read 1 ∧ move = (λ_. MoveN)"
by (auto simp: conv_cex_delta_def)
lemma conv_cex_step_unique:
"(conv_cex_cfg m, cM) ∈ ktm_step conv_cex_delta ⟹ cM = conv_cex_cfg (Suc m)"
by (auto elim!: ktm_step.cases
simp: conv_cex_delta_def conv_cex_tape_def one_tape_read_def fun_eq_iff)
text ‹Reachability: in ‹n ≤ 2› steps from the start the machine is in state
‹n ≤ 2 ≠ 3› --- so it cannot have accepted.›
lemma conv_cex_reach:
"(conv_cex_cfg 0, cM) ∈ (ktm_step conv_cex_delta) ^^ n ⟹ n ≤ 2 ⟹ cM = conv_cex_cfg n"
proof (induction n arbitrary: cM)
case 0
then show ?case by simp
next
case (Suc m)
from Suc.prems(1) obtain c where
rm: "(conv_cex_cfg 0, c) ∈ (ktm_step conv_cex_delta) ^^ m" and
st: "(c, cM) ∈ ktm_step conv_cex_delta"
by (auto elim: relpow_Suc_E)
have "m ≤ 2" using Suc.prems(2) by simp
from Suc.IH[OF rm this] have "c = conv_cex_cfg m" .
with st have "(conv_cex_cfg m, cM) ∈ ktm_step conv_cex_delta" by simp
from conv_cex_step_unique[OF this] show ?case .
qed
lemma conv_cex_lang: "[] ∈ Lang_ktm conv_cex_ktm"
proof -
have s0: "(conv_cex_cfg 0, conv_cex_cfg (Suc 0)) ∈ ktm_step conv_cex_delta"
by (rule conv_cex_step_fwd) simp
have s1: "(conv_cex_cfg (Suc 0), conv_cex_cfg (Suc (Suc 0))) ∈ ktm_step conv_cex_delta"
by (rule conv_cex_step_fwd) simp
have s2: "(conv_cex_cfg (Suc (Suc 0)), conv_cex_cfg (Suc (Suc (Suc 0)))) ∈ ktm_step conv_cex_delta"
by (rule conv_cex_step_fwd) simp
have "(conv_cex_cfg 0, conv_cex_cfg (Suc (Suc (Suc 0)))) ∈ (ktm_step conv_cex_delta) ^^ (Suc (Suc (Suc 0)))"
by (rule relpow_Suc_I2[OF s0 relpow_Suc_I2[OF s1 relpow_Suc_I2[OF s2 relpow_0_I]]])
hence "(conv_cex_cfg 0, conv_cex_cfg (Suc (Suc (Suc 0)))) ∈ (ktm_step conv_cex_delta)⇧*"
by (rule relpow_imp_rtrancl)
hence "(init_config_ktm conv_cex_ktm [], KConfig (t_ktm conv_cex_ktm) conv_cex_tape (λ_. 0))
∈ (ktm_step (delta_ktm conv_cex_ktm))⇧*"
by (simp add: conv_cex_init conv_cex_delta_ktm conv_cex_t_ktm numeral_3_eq_3)
thus ?thesis
unfolding Lang_ktm_def by (auto simp: conv_cex_ktm_def)
qed
lemma conv_cex_not_accepts: "¬ accepts_in_time_ktm conv_cex_ktm [] 2"
proof
assume "accepts_in_time_ktm conv_cex_ktm [] 2"
then obtain n cM where nle: "n ≤ 2"
and reach: "(init_config_ktm conv_cex_ktm [], cM) ∈ (ktm_step (delta_ktm conv_cex_ktm)) ^^ n"
and acc: "ktc_state cM = t_ktm conv_cex_ktm"
unfolding accepts_in_time_ktm_def by blast
from reach have "(conv_cex_cfg 0, cM) ∈ (ktm_step conv_cex_delta) ^^ n"
by (simp add: conv_cex_init conv_cex_delta_ktm)
from conv_cex_reach[OF this nle] have "ktc_state cM = n" by simp
with acc nle show False by (simp add: conv_cex_t_ktm)
qed
theorem clean_convention_unattainable:
"¬ time_bounded_conv conv_cex_ktm (λn. n + n div q)"
proof
assume "time_bounded_conv conv_cex_ktm (λn. n + n div q)"
hence "∀w∈Lang_ktm conv_cex_ktm.
accepts_in_time_ktm conv_cex_ktm w (max (length w + 2) (length w + length w div q))"
by (simp add: time_bounded_conv_def)
from bspec[OF this conv_cex_lang] have "accepts_in_time_ktm conv_cex_ktm [] 2"
by (simp add: numeral_2_eq_2)
with conv_cex_not_accepts show False by simp
qed
end