Theory Multitape_Alphabet_Enlargement.AlphabetEnlargement_Acceptance
theory AlphabetEnlargement_Acceptance
imports AlphabetEnlargement_ForwardStage
begin
subsection ‹Halting correspondence and step counts›
subsubsection ‹Halting correspondence and initial setup›
text ‹Halting correspondence: when ‹M› is in a halting state ‹q› (accept
or reject), ‹M'› is in the canonical halt config
‹(q, init_stage le_M)›. Direct from ‹ae_simulates_def›'s halt-arm
disjunct, which pins down ‹(off, buf, dest, idx) = init_stage le_M›
exactly when ‹qM' ∈ {t_ktm M, r_ktm M}›, plus the
‹q›-correspondence conjunct. Stated for either halting state, so that
the step-count engine below transports rejecting runs as well as
accepting ones.›
lemma ae_simulates_terminal_state:
assumes sim: "ae_simulates m M c d"
and terminal: "q ∈ {t_ktm M, r_ktm M}"
and state: "ktc_state c = q"
shows "ktc_state d = (q, init_stage m (le_ktm M))"
proof -
obtain p off buf dest idx where shape:
"ktc_state d = (p, off, buf, dest, idx)" by (cases "ktc_state d")
have paired: "ktc_state c = p" and phase:
"(idx = SS1 ∧ p ∉ {t_ktm M, r_ktm M}) ∨
(p ∈ {t_ktm M, r_ktm M} ∧ (off, buf, dest, idx) = init_stage m (le_ktm M))"
using sim unfolding ae_simulates_def Let_def shape by simp_all
have p: "p = q" using paired state by simp
have canonical: "(off, buf, dest, idx) = init_stage m (le_ktm M)"
using phase terminal p by blast
show ?thesis using shape p canonical by simp
qed
subsubsection ‹Step counts, and the induction over simulated stages›
text ‹Step-counting lemmas: the simulation phase is bounded by
‹8 ⋅ ⌈T(c ⋅ n) / c⌉›. The validation phase's bound,
‹2 ⋅ n + f⇩v›, is ‹ae_validation_steps_bound› of theory
‹AlphabetEnlargement_ValidationBound›.›
text ‹Chunked-induction engine for the simulation-phase
step count. Given a specific (finite) accepting ‹M›-path
of length ‹n› from a reachable ‹cM› with a paired SS1
M'-config ‹c'› satisfying the invariants ‹buf_gamma›,
‹le_anchor›, exhibit a corresponding accepting ‹M'›-path
of length at most ‹8 ⋅ ⌈n / c⌉›.
Proof structure (when discharged): induction on the M-path
length ‹n›, taking the next chunk of up to
‹m› M-steps per stage and
invoking ‹ae_simulates_forward_stage_general›. The
invariant ‹buf_gamma c'_j ∧ le_anchor c'_j› is
preserved by ‹forward_stage_general›'s output
conjuncts (just strengthened in the previous commit). The
M-side ‹no_le_per_tape› hypothesis for the per-tape
unified forward stage is discharged from
‹valid_reach_LE_only_pos0_ktm› on the substrate,
threaded through ‹reach_M›.
Wrapped by ‹ae_simulation_phase_step_count› below to
produce the named-bound ‹obtains›-form.›
lemma ae_simulation_phase_chunked:
fixes M :: "('q, 'a) ktm"
and w :: "'a list"
and cM cM_final :: "('a, 'q) ktc_config"
and c' :: "(nat ⇒ 'a,
'q × 'a ae_stage) ktc_config"
and n :: nat
assumes vM: "valid_ktm M"
and lu: "le_unique M"
and w_sub: "set w ⊆ Sigma_ktm M"
and le_neq_bl: "le_ktm M ≠ bl_ktm M"
and s_neq_t: "s_ktm M ≠ t_ktm M"
and s_neq_r: "s_ktm M ≠ r_ktm M"
and terminal: "q_stop ∈ {t_ktm M, r_ktm M}"
and reach_M: "(init_config_ktm M w, cM)
∈ (ktm_step (delta_ktm M))⇧*"
and trace: "(cM, cM_final) ∈ (ktm_step (delta_ktm M))^^n"
and accept: "ktc_state cM_final = q_stop"
and sim: "ae_simulates m M cM c'"
and buf_gamma: "ae_buffer_in_gamma_block m M c'"
and le_anchor: "∀kk<k_ktm M. ktc_tape c' kk 0 = LE_block m (le_ktm M)"
shows "∃nm c''. nm ≤ 8 * ((n + m - 1)
div m)
∧ (c', c'') ∈ (ktm_step (alphabet_enlarge_delta m M))^^nm
∧ ktc_state c'' = (q_stop, init_stage m (le_ktm M))"
using reach_M trace accept sim buf_gamma le_anchor
proof (induction n arbitrary: cM cM_final c' rule: less_induct)
case (less n)
show ?case
proof (cases n)
case 0
have trace_zero: "(cM, cM_final) ∈ (ktm_step (delta_ktm M))^^0"
using less.prems(2) ‹n = 0› by simp
have cM_eq: "cM_final = cM"
using trace_zero by simp
have ktc_cM: "ktc_state cM = q_stop"
using less.prems(3) cM_eq by simp
have state_c': "ktc_state c' = (q_stop, init_stage m (le_ktm M))"
by (rule ae_simulates_terminal_state[OF less.prems(4) terminal ktc_cM])
have run_zero:
"(c', c') ∈ (ktm_step (alphabet_enlarge_delta m M))^^0"
by simp
have bound_zero:
"(0 :: nat) ≤ 8 * ((n + m - 1)
div m)"
by simp
show ?thesis
using bound_zero run_zero state_c' by blast
next
case (Suc n_minus_1)
have trace_Suc: "(cM, cM_final)
∈ ktm_step (delta_ktm M) ^^ Suc n_minus_1"
using less.prems(2) Suc by simp
obtain cM_1 where
step_first: "(cM, cM_1) ∈ ktm_step (delta_ktm M)"
and rest_trace: "(cM_1, cM_final)
∈ ktm_step (delta_ktm M) ^^ n_minus_1"
using relpow_Suc_D2[OF trace_Suc] by blast
have cM_in_Q: "ktc_state cM ∈ Q_ktm M"
using ktm_step_src_in_Q[OF vM step_first] .
have cM_neq_t: "ktc_state cM ≠ t_ktm M"
using ktm_step_src_neq_t[OF vM step_first] .
have cM_neq_r: "ktc_state cM ≠ r_ktm M"
using ktm_step_src_neq_r[OF vM step_first] .
define c where "c ≡ m"
have c_pos: "0 < c"
unfolding c_def by (rule ae_buffer_in_gamma_block_width_pos[OF buf_gamma])
define k_chunk where "k_chunk ≡ min n c"
have k_chunk_pos: "0 < k_chunk"
using c_pos Suc unfolding k_chunk_def by simp
have k_chunk_le_n: "k_chunk ≤ n"
unfolding k_chunk_def by simp
have k_chunk_le_c: "k_chunk ≤ c"
unfolding k_chunk_def by simp
have trace_split_rel:
"(cM, cM_final) ∈ (ktm_step (delta_ktm M) ^^ k_chunk)
O (ktm_step (delta_ktm M) ^^ (n - k_chunk))"
proof -
have sum_eq: "k_chunk + (n - k_chunk) = n"
using k_chunk_le_n by simp
have "(cM, cM_final) ∈ ktm_step (delta_ktm M)
^^ (k_chunk + (n - k_chunk))"
using less.prems(2) sum_eq by simp
thus ?thesis by (simp add: relpow_add)
qed
obtain cM_k where
chunk_trace: "(cM, cM_k) ∈ ktm_step (delta_ktm M) ^^ k_chunk"
and rest_after_chunk:
"(cM_k, cM_final) ∈ ktm_step (delta_ktm M) ^^ (n - k_chunk)"
using trace_split_rel by auto
have end_or_halt:
"k_chunk = c ∨ ktc_state cM_k ∈ {t_ktm M, r_ktm M}"
proof (cases "k_chunk = n")
case True
hence "n - k_chunk = 0" by simp
hence "cM_k = cM_final"
using rest_after_chunk by simp
hence "ktc_state cM_k = q_stop"
using less.prems(3) by simp
thus ?thesis using terminal by simp
next
case False
hence "k_chunk < n" using k_chunk_le_n by linarith
hence "min n c < n" unfolding k_chunk_def by simp
hence "c < n" by linarith
hence "min n c = c" by simp
hence "k_chunk = c" unfolding k_chunk_def by simp
thus ?thesis by simp
qed
have reach_cM: "(init_config_ktm M w, cM)
∈ (ktm_step (delta_ktm M))⇧*"
using less.prems(1) .
have no_le_per_tape:
"∀kk. (ktc_pos c' kk ≥ 2
⟶ (∀i. i < 3 * c
⟶ ktc_tape cM kk
((ktc_pos c' kk - 2) * c + 1 + i)
≠ le_ktm M))
∧ (ktc_pos c' kk = 1
⟶ (∀i. i < 2 * c
⟶ ktc_tape cM kk (Suc i) ≠ le_ktm M))
∧ (ktc_pos c' kk = 0
⟶ (∀i. i < c
⟶ ktc_tape cM kk (Suc i) ≠ le_ktm M))"
proof (intro allI conjI impI allI impI)
fix kk :: nat and i :: nat
assume "2 ≤ ktc_pos c' kk" and "i < 3 * c"
have idx_nz: "(ktc_pos c' kk - 2) * c + 1 + i ≠ 0" by simp
show "ktc_tape cM kk ((ktc_pos c' kk - 2) * c + 1 + i) ≠ le_ktm M"
using valid_reach_LE_only_pos0_ktm
[OF vM lu w_sub reach_cM idx_nz le_neq_bl[symmetric]] .
next
fix kk :: nat and i :: nat
assume "ktc_pos c' kk = 1" and "i < 2 * c"
have idx_nz: "Suc i ≠ 0" by simp
show "ktc_tape cM kk (Suc i) ≠ le_ktm M"
using valid_reach_LE_only_pos0_ktm
[OF vM lu w_sub reach_cM idx_nz le_neq_bl[symmetric]] .
next
fix kk :: nat and i :: nat
assume "ktc_pos c' kk = 0" and "i < c"
have idx_nz: "Suc i ≠ 0" by simp
show "ktc_tape cM kk (Suc i) ≠ le_ktm M"
using valid_reach_LE_only_pos0_ktm
[OF vM lu w_sub reach_cM idx_nz le_neq_bl[symmetric]] .
qed
have k_chunk_le_card: "k_chunk ≤ m"
using k_chunk_le_c unfolding c_def .
have end_or_halt_card:
"k_chunk = m
∨ ktc_state cM_k ∈ {t_ktm M, r_ktm M}"
using end_or_halt unfolding c_def .
have no_le_per_tape_card:
"∀kk. (ktc_pos c' kk ≥ 2
⟶ (∀i. i < 3 * m
⟶ ktc_tape cM kk
((ktc_pos c' kk - 2) * m + 1 + i)
≠ le_ktm M))
∧ (ktc_pos c' kk = 1
⟶ (∀i. i < 2 * m
⟶ ktc_tape cM kk (Suc i) ≠ le_ktm M))
∧ (ktc_pos c' kk = 0
⟶ (∀i. i < m
⟶ ktc_tape cM kk (Suc i) ≠ le_ktm M))"
using no_le_per_tape unfolding c_def .
obtain c8 where
chain8: "(c', c8) ∈ ktm_step (alphabet_enlarge_delta m M) ^^ 8"
and sim_c8: "ae_simulates m M cM_k c8"
and buf_gamma_c8: "ae_buffer_in_gamma_block m M c8"
and le_anchor_c8: "∀kk<k_ktm M. ktc_tape c8 kk 0 = LE_block m (le_ktm M)"
by (rule ae_simulates_forward_stage_general
[OF vM lu less.prems(4) cM_in_Q cM_neq_t cM_neq_r
less.prems(5) k_chunk_le_card chunk_trace
end_or_halt_card less.prems(6) le_neq_bl
no_le_per_tape_card])
have chunk_in_rtrancl: "(cM, cM_k) ∈ (ktm_step (delta_ktm M))⇧*"
using chunk_trace by (rule relpow_imp_rtrancl)
have reach_cM_k: "(init_config_ktm M w, cM_k)
∈ (ktm_step (delta_ktm M))⇧*"
using reach_cM chunk_in_rtrancl by (rule rtrancl_trans)
have n_minus_lt_n: "n - k_chunk < n"
using k_chunk_pos Suc by linarith
obtain m_rec c'' where
bound_rec: "m_rec ≤ 8 * ((n - k_chunk + m - 1)
div m)"
and chain_rec: "(c8, c'') ∈ (ktm_step (alphabet_enlarge_delta m M))^^m_rec"
and state_c'': "ktc_state c'' = (q_stop, init_stage m (le_ktm M))"
using less.IH[OF n_minus_lt_n reach_cM_k rest_after_chunk
less.prems(3) sim_c8 buf_gamma_c8 le_anchor_c8]
by blast
have chain_compose:
"(c', c'') ∈ (ktm_step (alphabet_enlarge_delta m M))^^(8 + m_rec)"
using chain8 chain_rec by (auto simp: relpow_add)
have n_pos: "0 < n" using Suc by simp
have bound_compose:
"8 + m_rec
≤ 8 * ((n + m - 1)
div m)"
proof (cases "k_chunk = n")
case True
have m_rec_zero: "m_rec = 0"
proof -
have "n - k_chunk = 0" using True by simp
hence "(n - k_chunk + m - 1)
div m = 0"
using c_pos[unfolded c_def] by simp
thus ?thesis using bound_rec by simp
qed
have one_le_ceil:
"1 ≤ (n + m - 1)
div m"
proof -
have "m ≤ n + m - 1"
using n_pos by simp
hence "m div m
≤ (n + m - 1)
div m"
using div_le_mono by blast
thus ?thesis using c_pos[unfolded c_def] by simp
qed
show ?thesis using m_rec_zero one_le_ceil by simp
next
case False
have k_chunk_eq_c: "k_chunk = c"
proof -
have "k_chunk < n" using k_chunk_le_n False by linarith
hence "min n c < n" unfolding k_chunk_def by simp
hence "c < n" by linarith
hence "min n c = c" by simp
thus ?thesis unfolding k_chunk_def by simp
qed
have n_gt_c: "c < n"
using False k_chunk_le_n k_chunk_eq_c by linarith
have n_minus_eq: "n - k_chunk + c - 1 = n - 1"
using k_chunk_eq_c n_gt_c by simp
have rec_bound:
"m_rec ≤ 8 * ((n - 1) div m)"
using bound_rec n_minus_eq unfolding c_def by simp
have ceil_step:
"(n + m - 1)
div m
= (n - 1) div m + 1"
proof -
have c_nz: "m ≠ 0"
using c_pos unfolding c_def by simp
have sum_eq: "n + m - 1
= (n - 1) + m"
using n_pos by simp
have div_step:
"((n - 1) + m)
div m
= (n - 1) div m + 1"
using div_add_self2[OF c_nz] .
show ?thesis using sum_eq div_step by simp
qed
have "8 + m_rec
≤ 8 + 8 * ((n - 1) div m)"
using rec_bound by simp
also have "… = 8 * ((n - 1) div m + 1)"
by simp
also have "… = 8 * ((n + m - 1)
div m)"
using ceil_step by simp
finally show ?thesis .
qed
show ?thesis
using bound_compose chain_compose state_c'' by blast
qed
qed
text ‹Simulation-phase step count under weak acceptance. If
‹M› accepts ‹u› within time ‹T (length u)› (an accepting
‹M›-path of length at most ‹T (length u)› from
‹init_config_ktm M u› to a config in state ‹t_ktm M›),
then from any simulation-paired SS1 config ‹c'› there is an
accepting ‹M'›-path of length at most ‹8 * ⌈T(length u) / c⌉›
ending at ‹(t_ktm M, init_stage (le_ktm M))›.
Under the weak time-bounded acceptance convention
(‹accepts_in_time_ktm›). Hypothesis
‹accepts_in_time_ktm M u (T (length u))› replaces the
universal-path-bound ‹upperb_time_ktm M T›; conclusion drops
the ‹r_ktm›-arm (under weak acceptance, "reject" just means
"no accepting path"; no canonical ‹r_ktm› config is tracked
explicitly). Thin
wrapper around ‹ae_simulation_phase_chunked›: unpacks
the weak-acceptance witness, lifts the tight bound
‹(n0 + c - 1) div c› to the ‹T (length u)› bound
via monotonicity of division, and adapts to the
‹obtains›-form.›
lemma ae_simulation_phase_step_count:
fixes M :: "('q, 'a) ktm"
and T :: "nat ⇒ nat"
and u :: "'a list"
and c' :: "(nat ⇒ 'a,
'q × 'a ae_stage) ktc_config"
assumes vM: "valid_ktm M"
and lu: "le_unique M"
and terminal: "q_stop ∈ {t_ktm M, r_ktm M}"
and m_accepts: "reaches_state_in_time_ktm M u q_stop (T (length u))"
and u_sub: "set u ⊆ Sigma_ktm M"
and sim: "ae_simulates m M (init_config_ktm M u) c'"
and buf_gamma_c': "ae_buffer_in_gamma_block m M c'"
and le_anchor_c': "∀kk<k_ktm M. ktc_tape c' kk 0 = LE_block m (le_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"
obtains n_steps :: nat and c'' where
"n_steps ≤ 8 * ((T (length u) + m - 1)
div m)"
and "(c', c'') ∈ ktm_step (alphabet_enlarge_delta m M) ^^ n_steps"
and "ktc_state c'' = (q_stop, init_stage m (le_ktm M))"
proof -
from m_accepts obtain n0 cM_n0 where
n0_bd: "n0 ≤ T (length u)"
and n0_run: "(init_config_ktm M u, cM_n0)
∈ ktm_step (delta_ktm M) ^^ n0"
and n0_acc: "ktc_state cM_n0 = q_stop"
unfolding reaches_state_in_time_ktm_def by blast
have init_reach:
"(init_config_ktm M u, init_config_ktm M u)
∈ (ktm_step (delta_ktm M))⇧*"
by simp
obtain n_steps c'' where
tight_bound: "n_steps ≤ 8 * ((n0 + m - 1)
div m)"
and run: "(c', c'') ∈ ktm_step (alphabet_enlarge_delta m M) ^^ n_steps"
and halt: "ktc_state c'' = (q_stop, init_stage m (le_ktm M))"
using ae_simulation_phase_chunked[OF vM lu u_sub le_neq_bl s_neq_t s_neq_r terminal
init_reach n0_run n0_acc sim
buf_gamma_c' le_anchor_c']
by blast
have div_mono:
"(n0 + m - 1) div m
≤ (T (length u) + m - 1)
div m"
using n0_bd by (intro div_le_mono add_le_mono) auto
have loose_bound:
"n_steps ≤ 8 * ((T (length u) + m - 1)
div m)"
using tight_bound div_mono by linarith
show ?thesis
proof (rule that)
show "n_steps ≤ 8 * ((T (length u) + m - 1)
div m)"
using loose_bound .
show "(c', c'') ∈ ktm_step (alphabet_enlarge_delta m M) ^^ n_steps"
using run .
show "ktc_state c'' = (q_stop, init_stage m (le_ktm M))"
using halt .
qed
qed
end