Theory AlphabetEnlargement
theory AlphabetEnlargement
imports AlphabetEnlargement_Acceptance
begin
text ‹The three top-level theorems characterising
‹alphabet_enlarge›, at the end of the forward-simulation
chain that begins in
‹AlphabetEnlargement_ComputeCorrect›: the linear time
bound ‹alphabet_enlarge_time›, well-formedness
preservation ‹alphabet_enlarge_wf›, and forward language
preservation ‹alphabet_enlarge_language_forward›. The
reverse direction of the language biconditional
(‹alphabet_enlarge_language›) and the nondeterministic
corollary live in ‹AlphabetEnlargement_Reverse›.›
subsection ‹Top-level theorems›
text ‹Time bound, encoded form: ‹M' = alphabet_enlarge m M›
on input ‹encode_input m (bl_ktm M) w› runs in time
‹α ⋅ ⌈n/m⌉ + 8 ⋅ ⌈T(n) / m⌉ + f› for structural
additive constants ‹α, f› independent of ‹M›, where
‹m› is the block size and ‹n› is
‹M›'s input length ‹length w›. ‹M'›'s input is the
consolidated block-encoding ‹encode_input m (bl_ktm M) w› of
length ‹⌈n/m⌉›.
This is the linear-speedup theorem in ∗‹encoded form›:
the input bijection
‹encode_input› is exposed externally; ‹M'›'s job is to
validate the encoded input's shape and simulate ‹M›. The
classical same-alphabet statement (Hartmanis and Stearns
\<^cite>‹‹Theorem 2› in "Hartmanis1965:computational"›, modernised as
Hopcroft and Ullman \<^cite>‹‹Theorem 12.3› in "Hopcroft1979:introduction"›)
follows as a corollary by
composing this with a wrap combinator that runs an encoder pass
first.
Cost breakdown:
▪ ‹α ⋅ ⌈n/c⌉›: validation-phase pass over the
encoded input of length ‹⌈n/c⌉› (forward scan + return
scan; ‹α = 2›).
▪ ‹8 ⋅ ⌈T(n) / c⌉›: 8 ‹M'›-substeps per simulated
‹c›-fold ‹M›-step group; ‹⌈T(n)/c⌉› such groups suffice
to cover ‹M›'s ‹T(n)›-step accepting path.
▪ ‹f›: validation-phase setup additive (‹f_v›).
The ‹T(n)› argument (not ‹T(c ⋅ n)›) reflects that
‹M›'s and ‹M'›'s input represent the same problem instance
of size ‹n›; ‹M'›'s tape just compresses it by a factor
of ‹c›.
∗‹Existential acceptance.› Hypothesis and conclusion both at
‹accepts_in_time_ktm› (the existential accepting-path
predicate). The constants ‹α›, ‹f›
depend only on ‹M› and ‹m›, not
on ‹w›; the universal-‹w› form inside ‹obtains› encodes
this.
∗‹The same-alphabet form follows as a corollary› by composing with
the wrap combinator (‹encoding_wrap› in
‹Wrap_Defs.thy›). Theorem 12.3's setup-phase
cost ‹n + ⌈n/m⌉› appears in the wrapped form as the
inline encoder's cost (‹O(n)›) plus this lemma's
‹⌈n/c⌉› validation cost. Together with the speedup
factor ‹1/c› applied to ‹T(n)›, this gives the textbook
bound ‹c_0 ⋅ T(n)› for any ‹c_0 > 0› when
‹inf T(n)/n = ∞› (Theorem 12.3); the companion
\<^cite>‹‹Theorem 12.4› in "Hopcroft1979:introduction"› patches the
linear case ‹T(n) = Θ(n)› via a different choice of ‹c›.›
theorem alphabet_enlarge_terminal_time:
fixes M :: "('q, 'a) ktm"
and T :: "nat ⇒ nat"
assumes wf: "well_formed_ktm M"
and terminal: "q_stop ∈ {t_ktm M, r_ktm M}"
and m_pos: "0 < m"
shows "∀w. set w ⊆ Sigma_ktm M
⟶ reaches_state_in_time_ktm M w q_stop (T (length w))
⟶ reaches_state_in_time_ktm
(alphabet_enlarge m M
:: ('q × 'a ae_stage,
nat ⇒ 'a) ktm)
(encode_input m (bl_ktm M) w)
(q_stop, init_stage m (le_ktm M))
(2 * ((length w + m - 1)
div m)
+ 8 * ((T (length w) + m - 1)
div m)
+ 4)"
proof -
from wf have vM: "valid_ktm M"
and lu: "le_unique 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"
by auto
let ?c = "m"
let ?M' = "alphabet_enlarge m M
:: ('q × 'a ae_stage, nat ⇒ 'a) ktm"
show "∀w. set w ⊆ Sigma_ktm M
⟶ reaches_state_in_time_ktm M w q_stop (T (length w))
⟶ reaches_state_in_time_ktm ?M' (encode_input m (bl_ktm M) w)
(q_stop, init_stage m (le_ktm M))
(2 * ((length w + ?c - 1) div ?c)
+ 8 * ((T (length w) + ?c - 1) div ?c)
+ 4)"
proof (intro allI impI)
fix w :: "'a list"
assume w_sub: "set w ⊆ Sigma_ktm M"
assume m_acc: "reaches_state_in_time_ktm M w q_stop (T (length w))"
let ?ew = "encode_input m (bl_ktm M) w
:: (nat ⇒ 'a) list"
have ew_sub: "set ?ew ⊆ gamma_block m (Sigma_ktm M ∪ {bl_ktm M})"
by (rule encode_input_in_gamma_block[OF w_sub])
have ew_wf: "ae_input_well_formed m (bl_ktm M) ?ew"
by (rule encode_input_well_formed[OF vM w_sub])
have s_in_Q: "s_ktm M ∈ Q_ktm M"
by (rule valid_ktm_s_in_Q[OF vM])
let ?c1 = "KConfig (s_ktm M, init_offset,
init_buffer m (le_ktm M), init_dest, SS1)
(ktc_tape (ae_init_config m M ?ew))
(λ_ :: nat. 0)
:: (nat ⇒ 'a,
'q × 'a ae_stage) ktc_config"
have val_chain:
"(ae_init_config m M ?ew, ?c1)
∈ ktm_step (alphabet_enlarge_delta m M)
^^ (2 * length ?ew + 4)"
by (rule ae_validation_well_formed_to_SS1
[OF vM ew_sub ew_wf s_in_Q s_neq_t s_neq_r le_neq_bl m_pos])
have le_anchor: "∀kk<k_ktm M. ktc_tape ?c1 kk 0 = LE_block m (le_ktm M)"
proof (intro allI impI)
fix kk assume kk_lt: "kk < k_ktm M"
have "ktc_tape ?c1 kk 0 = ktc_tape (ae_init_config m M ?ew) kk 0"
by simp
also have "… = LE_block m (le_ktm M)"
by (rule ae_init_config_tape_le[OF kk_lt])
finally show "ktc_tape ?c1 kk 0 = LE_block m (le_ktm M)" .
qed
have buf_gamma: "ae_buffer_in_gamma_block m M ?c1"
unfolding ae_buffer_in_gamma_block_def init_buffer_def
using LE_block_in_gamma_block[OF valid_ktm_LE_in_Gamma[OF vM]] m_pos
by (simp add: init_offset_def)
have tape_corr:
"∀k<k_ktm M. ae_tape_correspondence m (le_ktm M)
(ktc_tape (init_config_ktm M w) k)
(ktc_tape (ae_init_config m M ?ew) k)"
by (rule ae_tape_correspondence_init[OF vM w_sub])
have subst_pos_zero:
"∀k. ktc_pos (init_config_ktm M w) k = 0"
by (cases M) simp
have c1_pos_zero: "∀k. ktc_pos ?c1 k = 0" by simp
have pos_corr_c1:
"∀k. ktc_pos (init_config_ktm M w) k
= ae_decode_pos m (ktc_pos ?c1 k)
((init_offset :: nat ⇒ nat) k)"
using c1_pos_zero subst_pos_zero
unfolding ae_decode_pos_def by simp
have qM_subst: "ktc_state (init_config_ktm M w) = s_ktm M"
by (cases M) simp
have c1_state:
"ktc_state ?c1 = (s_ktm M, init_offset,
init_buffer m (le_ktm M), init_dest, SS1)"
by simp
have gamma_block_c1: "ae_tape_in_gamma_block m M ?c1"
unfolding ae_tape_in_gamma_block_def
proof (intro conjI)
show "∀k p. ktc_tape ?c1 k p ∈ gamma_block m (Γ_ktm M)"
using ae_init_config_in_gamma_block[OF vM ew_sub] by simp
show "∀j≥k_ktm M. ∀p. ktc_tape ?c1 j p = bl_block m (bl_ktm M)"
by (simp add: ae_init_config_tape_blank_tail)
qed
have sim: "ae_simulates m M (init_config_ktm M w) ?c1"
unfolding ae_simulates_def Let_def c1_state
using qM_subst tape_corr pos_corr_c1 gamma_block_c1
s_neq_t s_neq_r by simp
obtain n_sim c'' where
n_sim_bd:
"n_sim ≤ 8 * ((T (length w) + ?c - 1) div ?c)"
and sim_chain:
"(?c1, c'') ∈ ktm_step (alphabet_enlarge_delta m M) ^^ n_sim"
and c''_state: "ktc_state c'' = (q_stop, init_stage m (le_ktm M))"
using ae_simulation_phase_step_count
[where M = M and T = T and u = w and c' = ?c1,
OF vM lu terminal m_acc w_sub sim buf_gamma le_anchor
s_neq_t s_neq_r le_neq_bl]
by metis
have chain_compose:
"(ae_init_config m M ?ew, c'')
∈ ktm_step (alphabet_enlarge_delta m M)
^^ ((2 * length ?ew + 4) + n_sim)"
using val_chain sim_chain by (auto simp: relpow_add)
have len_ew: "length ?ew = (length w + ?c - 1) div ?c"
by (rule length_encode_input)
let ?total = "(2 * length ?ew + 4) + n_sim"
let ?target = "2 * ((length w + ?c - 1) div ?c)
+ 8 * ((T (length w) + ?c - 1) div ?c)
+ 4"
have bound: "?total ≤ ?target"
using n_sim_bd len_ew by simp
have init_bridge:
"init_config_ktm ?M' ?ew = ae_init_config m M ?ew"
by (rule init_config_alphabet_enlarge)
have delta_bridge:
"delta_ktm ?M' = alphabet_enlarge_delta m M"
by (rule delta_ktm_alphabet_enlarge)
show "reaches_state_in_time_ktm ?M' ?ew (q_stop, init_stage m (le_ktm M)) ?target"
unfolding reaches_state_in_time_ktm_def
proof (intro exI conjI)
show "?total ≤ ?target" using bound .
show "(init_config_ktm ?M' ?ew, c'')
∈ (ktm_step (delta_ktm ?M')) ^^ ?total"
using chain_compose init_bridge delta_bridge by simp
show "ktc_state c'' = (q_stop, init_stage m (le_ktm M))"
by (rule c''_state)
qed
qed
qed
text ‹The accepting instance: the time bound above at the accept state.›
theorem alphabet_enlarge_time_explicit:
fixes M :: "('q, 'a) ktm"
and T :: "nat ⇒ nat"
assumes wf: "well_formed_ktm M"
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 M
:: ('q × 'a ae_stage,
nat ⇒ 'a) ktm)
(encode_input m (bl_ktm M) w)
(2 * ((length w + m - 1)
div m)
+ 8 * ((T (length w) + m - 1)
div m)
+ 4)"
unfolding accepts_in_time_ktm_iff_reaches t_ktm_alphabet_enlarge
by (rule alphabet_enlarge_terminal_time [OF wf _ m_pos]) simp
text ‹The classical HU-form of the linear-speedup time bound: the
additive constants ‹α›, ‹f› instantiated at ‹α = 2›, ‹f = 4›
from ‹alphabet_enlarge_time_explicit›. The per-block simulation
constant ‹8› and the speedup divisor ‹m› are already
explicit in the statement.›
theorem alphabet_enlarge_time:
fixes M :: "('q, 'a) ktm"
and T :: "nat ⇒ nat"
assumes wf: "well_formed_ktm M"
and m_pos: "0 < m"
obtains α f :: nat
where "∀w. set w ⊆ Sigma_ktm M
⟶ accepts_in_time_ktm M w (T (length w))
⟶ accepts_in_time_ktm
(alphabet_enlarge m M
:: ('q × 'a ae_stage,
nat ⇒ 'a) ktm)
(encode_input m (bl_ktm M) w)
(α * ((length w + m - 1)
div m)
+ 8 * ((T (length w) + m - 1)
div m)
+ f)"
proof (rule that[of 2 4])
show "∀w. set w ⊆ Sigma_ktm M
⟶ accepts_in_time_ktm M w (T (length w))
⟶ accepts_in_time_ktm
(alphabet_enlarge m M
:: ('q × 'a ae_stage,
nat ⇒ 'a) ktm)
(encode_input m (bl_ktm M) w)
(2 * ((length w + m - 1)
div m)
+ 8 * ((T (length w) + m - 1)
div m)
+ 4)"
by (rule alphabet_enlarge_time_explicit[OF wf m_pos])
qed
text ‹Forward language inclusion modulo input encoding: a word
‹w› with ‹set w ⊆ Σ_M› that is in
‹M›'s language has its canonical block-encoding (using
‹M›'s blank for padding) in
‹M' = alphabet_enlarge M›'s language. This is the
forward leg of the language-equivalence claim; the reverse leg
(‹encode_input w ∈ Lang_ktm M' ⟹ w ∈ Lang_ktm M›)
holds for every well-formed ‹M› --- with no determinism
hypothesis, the original ‹det_ktm M› dependency having been
removed in refactoring --- and lives in
‹AlphabetEnlargement_Reverse.thy› as the biconditional
‹alphabet_enlarge_language›.
Hypotheses align with ‹alphabet_enlarge_time›:
‹s ≠ t›, ‹s ≠ r›, ‹le ≠ bl›. The first
two would be redundant if we manually handled the degenerate
always-accept (‹s = t›) and always-reject (‹s = r›)
cases, but matching the ‹_time› signature keeps the call
sites uniform. ‹le ≠ bl› is genuinely necessary: the
simulation infrastructure requires it (compute substep's buffer-
write composition), and the ‹Sigma_ktm› containment for
encoded inputs uses it to exclude ‹LE_block›.
The ‹set w ⊆ Sigma_ktm M› antecedent inside the
‹∀w› is required: without it the inclusion fails for
‹w› containing blank symbols (such ‹w› are outside
‹Lang_ktm M› by the substrate's ‹Lang_ktm›
definition, but their encodings can still pass M'-validation
and be M'-accepted).
Strategy: extract an accepting M-path of length ‹n0›;
instantiate ‹alphabet_enlarge_time› with
‹T = (λ_. n0)› to obtain a bounded M'-witness; drop the
bound and conclude.›
theorem alphabet_enlarge_language_forward:
fixes M :: "('q, 'a) ktm"
assumes wf: "well_formed_ktm M"
and m_pos: "0 < m"
shows "∀w. set w ⊆ Sigma_ktm M
⟶ w ∈ Lang_ktm M
⟶ encode_input m (bl_ktm M) w ∈ Lang_ktm
(alphabet_enlarge m M
:: ('q × 'a ae_stage,
nat ⇒ 'a) ktm)"
proof -
from wf have vM: "valid_ktm M"
and lu: "le_unique 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"
by auto
let ?c = "m"
let ?M' = "alphabet_enlarge m M
:: ('q × 'a ae_stage, nat ⇒ 'a) ktm"
show ?thesis
proof (intro allI impI)
fix w :: "'a list"
assume w_sub: "set w ⊆ Sigma_ktm M"
assume w_in_M: "w ∈ Lang_ktm M"
have enc_in_gamma:
"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_sub])
have enc_no_bl:
"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_sub])
have enc_no_LE:
"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_sub])
have enc_sub:
"set (encode_input m (bl_ktm M) w :: (nat ⇒ 'a) list)
⊆ Sigma_ktm ?M'"
unfolding Sigma_ktm_alphabet_enlarge
using enc_in_gamma enc_no_bl enc_no_LE by blast
from w_in_M obtain wM' nM where
m_path: "(init_config_ktm M w,
KConfig (t_ktm M) wM' nM)
∈ (ktm_step (delta_ktm M))⇧*"
unfolding Lang_ktm_def by blast
obtain n0 where m_pow:
"(init_config_ktm M w, KConfig (t_ktm M) wM' nM)
∈ (ktm_step (delta_ktm M)) ^^ n0"
using m_path rtrancl_imp_relpow by metis
have m_acc: "accepts_in_time_ktm M w n0"
unfolding accepts_in_time_ktm_def
proof (intro exI conjI)
show "(n0 :: nat) ≤ n0" by simp
show "(init_config_ktm M w, KConfig (t_ktm M) wM' nM)
∈ ktm_step (delta_ktm M) ^^ n0"
using m_pow .
show "ktc_state (KConfig (t_ktm M) wM' nM) = t_ktm M"
by simp
qed
obtain α f :: nat where AE_time:
"∀w_arg. set w_arg ⊆ Sigma_ktm M
⟶ accepts_in_time_ktm M w_arg n0
⟶ accepts_in_time_ktm ?M'
(encode_input m (bl_ktm M) w_arg)
(α * ((length w_arg + ?c - 1) div ?c)
+ 8 * ((n0 + ?c - 1) div ?c) + f)"
by (rule alphabet_enlarge_time
[where T = "λ_. n0", OF wf m_pos])
from AE_time w_sub m_acc have m'_acc:
"accepts_in_time_ktm ?M' (encode_input m (bl_ktm M) w)
(α * ((length w + ?c - 1) div ?c)
+ 8 * ((n0 + ?c - 1) div ?c) + f)"
by blast
from m'_acc obtain n_m' c_acc where
run: "(init_config_ktm ?M' (encode_input m (bl_ktm M) w),
c_acc)
∈ (ktm_step (delta_ktm ?M')) ^^ n_m'"
and acc: "ktc_state c_acc = t_ktm ?M'"
unfolding accepts_in_time_ktm_def by blast
obtain wM_acc' nM_acc where c_acc_eq:
"c_acc = KConfig (t_ktm ?M') wM_acc' nM_acc"
using acc by (cases c_acc) simp
have run_star:
"(init_config_ktm ?M' (encode_input m (bl_ktm M) w),
KConfig (t_ktm ?M') wM_acc' nM_acc)
∈ (ktm_step (delta_ktm ?M'))⇧*"
using run c_acc_eq relpow_imp_rtrancl by metis
show "encode_input m (bl_ktm M) w ∈ Lang_ktm ?M'"
unfolding Lang_ktm_def
using enc_sub run_star by blast
qed
qed
end