Theory Wrap_Defs
theory Wrap_Defs
imports Wrap_Base "Multitape_TM_Substrate.Multitape_Origin_Float"
begin
section ‹The wrap, ending its reset with a fresh endmarker›
text ‹Keeping M's ‹k› tapes means reusing the input tape, and
∗‹rewinding› it after the encoder has read it costs about ‹2n› steps.
Under a super-linear time bound, as in Theorem 12.3
\<^cite>‹‹Theorem 12.3› in "Hopcroft1979:introduction"›, that cost is
absorbed, but Theorem 12.4's ‹(1+ε)n› bound cannot absorb it. So this
wrap does not rewind the input tape: it writes a fresh ‹le› at the input
head's final position, ∗‹floating› the origin (the spent raw input to
its left becomes unreachable, since a head reading ‹le› may not move
left, clause 1 of @{const valid_ktm}).
The storage tape (physical @{text 1}, carrying M's tape 0, the encoded
input) is still rewound to its ‹le›, but that is only ‹⌈n/c⌉› cells
(the encoded length), the ‹ε⋅n› term; it uses the generic single-tape
rewind @{const wrap_rewind_loop_delta_gen}. The input tape (physical
@{text 0}, becoming M's tape 1) is ∗‹not› rewound: the step that ends
the rewind writes ‹le› on it and hands over to @{text W_Disp}. The
encoder families, the transposed run and the dispatch are those of
@{theory Multitape_Alphabet_Enlargement.Wrap_Base}.
The fresh ‹le› makes the wrap ∗‹not› @{const le_unique} (it writes
‹le› where it did not read ‹le›); it remains @{const valid_ktm}, since
clause 1 constrains only transitions that ∗‹read› ‹le›. The engine
is then run from a floated-origin init config, bridged back to the
proper @{const init_config_ktm} by the origin-float lemmas of
@{theory Multitape_TM_Substrate.Multitape_Origin_Float}.›
subsection ‹The step that ends the reset›
text ‹The step that ends the reset (called ∗‹plant-done› in the names
below, for the ‹le› it plants): it fires when the storage tape
(index @{text "Suc 0"}) reads ‹le› (its cell 0, reached by the generic
rewind loop), and in the same transition writes ‹le› on the input tape
(index @{text 0}) under its head, handing over to @{text W_Disp}. No
head moves. This is the only reset family specific to this wrap; the
loop is the generic @{const wrap_rewind_loop_delta_gen}.›
definition wrap_plant_done_delta ::
"('q, 'b) ktm ⇒ 'a set
⇒ (('q, 'a, 'b) wrap_state
× (nat ⇒ ('a, 'b) wrap_alphabet)
× ('q, 'a, 'b) wrap_state
× (nat ⇒ ('a, 'b) wrap_alphabet)
× (nat ⇒ move)) set"
where
"wrap_plant_done_delta M Σu =
{ (W_Reset, sym, W_Disp,
(λt. if t = 0 then Enc (le_ktm M) else sym t),
λ_. MoveN)
| sym.
sym (Suc 0) = Enc (le_ktm M)
∧ (∀i≥k_ktm M. sym i = Enc (bl_ktm M))
∧ sym ∈ UNIV → Raw ` Σu ∪ Enc ` Γ_ktm M }"
subsection ‹The combinator›
text ‹The wrap's transition relation: the six encoder families at
@{term "K = k_ktm M"}, the transposed run and dispatch, and --- for the
reset --- the generic single-tape storage rewind (loop) plus the
plant-done step.›
definition wrap_delta ::
"('q, 'b) ktm ⇒ ('a list ⇒ 'b) ⇒ nat ⇒ 'a set
⇒ (('q, 'a, 'b) wrap_state
× (nat ⇒ ('a, 'b) wrap_alphabet)
× ('q, 'a, 'b) wrap_state
× (nat ⇒ ('a, 'b) wrap_alphabet)
× (nat ⇒ move)) set"
where
"wrap_delta M pack c Σu =
wrap_init_delta_gen (k_ktm M) M
∪ wrap_buf_extend_delta_gen (k_ktm M) M c Σu
∪ wrap_buf_close_delta_gen (k_ktm M) M pack c Σu
∪ wrap_buf_empty_end_delta_gen (k_ktm M) M Σu
∪ wrap_buf_nonempty_end_delta_gen (k_ktm M) M pack c Σu
∪ wrap_rewind_loop_delta_gen W_Reset (Suc 0) (k_ktm M) M Σu
∪ wrap_plant_done_delta M Σu
∪ wrap_disp_delta_gen (k_ktm M) M Σu
∪ wrap_run_delta M Σu"
text ‹The encoding wrap: transition relation @{const wrap_delta} at M's tape
count @{term "k_ktm M"}, over the wrap state set (no new state: writing
the fresh ‹le› is part of the step that ends the reset). It is proved
valid below for @{term "k_ktm M ≥ 2"}, since the input tape must serve
as one of M's tapes other than tape @{text 0}.›
fun encoding_wrap ::
"('q, 'b) ktm ⇒ ('a list ⇒ 'b) ⇒ nat ⇒ 'a set
⇒ (('q, 'a, 'b) wrap_state, ('a, 'b) wrap_alphabet) ktm"
where
"encoding_wrap M pack c Σu =
KTM
(wrap_state_set M c Σu)
(Raw ` Σu)
(Raw ` Σu ∪ Enc ` Γ_ktm M)
(Enc (bl_ktm M))
(Enc (le_ktm M))
(wrap_delta M pack c Σu)
W_Init
(W_Run (t_ktm M))
(W_Run (r_ktm M))
(k_ktm M)"
subsection ‹Validity of the wrap›
text ‹Phase-family case split for @{const wrap_delta}: a transition
belongs to exactly one of the nine builders --- the six
boundary-parameterised encoder families at @{term "k_ktm M"}, the generic
single-tape storage rewind loop, the plant-done step, the dispatch, and the
transposed run.›
lemma wrap_delta_cases:
assumes "(q, a, q', a', d) ∈ wrap_delta M pack c Σu"
obtains
(init) "(q, a, q', a', d) ∈ wrap_init_delta_gen (k_ktm M) M"
| (ext) "(q, a, q', a', d) ∈ wrap_buf_extend_delta_gen (k_ktm M) M c Σu"
| (close) "(q, a, q', a', d) ∈ wrap_buf_close_delta_gen (k_ktm M) M pack c Σu"
| (eend) "(q, a, q', a', d) ∈ wrap_buf_empty_end_delta_gen (k_ktm M) M Σu"
| (nend) "(q, a, q', a', d) ∈ wrap_buf_nonempty_end_delta_gen (k_ktm M) M pack c Σu"
| (rloop) "(q, a, q', a', d)
∈ wrap_rewind_loop_delta_gen W_Reset (Suc 0) (k_ktm M) M Σu"
| (rdone) "(q, a, q', a', d) ∈ wrap_plant_done_delta M Σu"
| (disp) "(q, a, q', a', d) ∈ wrap_disp_delta_gen (k_ktm M) M Σu"
| (run) "(q, a, q', a', d) ∈ wrap_run_delta M Σu"
using assms unfolding wrap_delta_def by blast
text ‹Validity of the wrap at tape count @{term "k_ktm M"}. Hypotheses:
@{term "2 ≤ k_ktm M"}, @{term "valid_ktm M"}, and
@{term "le_ktm M ≠ bl_ktm M"} (the storage rewind passes @{text bl}
through unchanged, and the plant-done step writes @{text le}, so the
obligations against a spurious @{text le} need them distinct). It does
∗‹not› require @{const le_unique} of the input, and the resulting wrap
is itself ∗‹not› @{const le_unique}: the plant-done step writes @{text le}
on physical tape @{text 0} without reading it there. That is allowed by
@{const valid_ktm}, whose endmarker clause (obligation 14 below)
constrains only transitions that ∗‹read› @{text le}; forbidding a fresh
@{text le} is the separate predicate @{const le_unique}.›
lemma wrap_wf:
assumes valM: "valid_ktm M"
and le_ne_bl: "le_ktm M ≠ bl_ktm M"
and finSu: "finite Σu"
and c_pos: "0 < c"
and k2: "2 ≤ k_ktm M"
shows "valid_ktm (encoding_wrap M pack c Σu)"
proof -
have eq:
"encoding_wrap M pack c Σu =
KTM (wrap_state_set M c Σu)
(Raw ` Σu)
(Raw ` Σu ∪ Enc ` Γ_ktm M)
(Enc (bl_ktm M))
(Enc (le_ktm M))
(wrap_delta M pack c Σu)
W_Init
(W_Run (t_ktm M))
(W_Run (r_ktm M))
(k_ktm M)"
by simp
show ?thesis
unfolding eq valid_ktm.simps
proof (intro conjI)
show "finite (wrap_state_set M c Σu)"
by (rule finite_wrap_state_set[OF valM finSu])
show "finite (Raw ` Σu ∪ Enc ` Γ_ktm M)"
using finSu valid_ktm_finite_Gamma[OF valM] by simp
show "Raw ` Σu ⊆ Raw ` Σu ∪ Enc ` Γ_ktm M"
by blast
show "W_Init ∈ wrap_state_set M c Σu"
unfolding wrap_state_set_def by simp
show "W_Run (t_ktm M) ∈ wrap_state_set M c Σu"
using valid_ktm_t_in_Q[OF valM]
unfolding wrap_state_set_def by simp
show "W_Run (r_ktm M) ∈ wrap_state_set M c Σu"
using valid_ktm_r_in_Q[OF valM]
unfolding wrap_state_set_def by simp
show "Enc (bl_ktm M) ∈ Raw ` Σu ∪ Enc ` Γ_ktm M"
using valid_ktm_blank_in_Gamma[OF valM] by blast
show "Enc (bl_ktm M) ∉ Raw ` Σu"
by auto
show "Enc (le_ktm M) ∈ Raw ` Σu ∪ Enc ` Γ_ktm M"
using valid_ktm_LE_in_Gamma[OF valM] by blast
show "Enc (le_ktm M) ∉ Raw ` Σu"
by auto
show "W_Run (t_ktm M) ≠ W_Run (r_ktm M)"
using valM by (cases M) simp
show "0 < k_ktm M"
using valid_ktm_k_pos[OF valM] by simp
show "wrap_delta M pack c Σu
⊆ (wrap_state_set M c Σu - {W_Run (t_ktm M), W_Run (r_ktm M)})
× (UNIV → Raw ` Σu ∪ Enc ` Γ_ktm M)
× wrap_state_set M c Σu
× (UNIV → Raw ` Σu ∪ Enc ` Γ_ktm M)
× (UNIV → UNIV)"
unfolding wrap_delta_def
wrap_init_delta_gen_def wrap_buf_extend_delta_gen_def
wrap_buf_close_delta_gen_def wrap_buf_empty_end_delta_gen_def
wrap_buf_nonempty_end_delta_gen_def
wrap_rewind_loop_delta_gen_def
wrap_plant_done_delta_def
wrap_disp_delta_gen_def wrap_run_delta_def
wrap_state_set_def
using c_pos valid_ktm_t_in_Q[OF valM] valid_ktm_s_in_Q[OF valM]
valid_ktm_LE_in_Gamma[OF valM] valid_ktm_blank_in_Gamma[OF valM]
valid_ktm_delta_set[OF valM]
valid_ktm_Sigma_sub_Gamma[OF valM]
by (fastforce split: nat.split if_splits)
show "∀q a q' a' d k.
(q, a, q', a', d) ∈ wrap_delta M pack c Σu ⟶
a k = Enc (le_ktm M) ⟶
a' k = Enc (le_ktm M) ∧ d k ∈ {MoveN, MoveR}"
proof (intro allI impI)
fix q a q' a' d k
assume in_δ: "(q, a, q', a', d) ∈ wrap_delta M pack c Σu"
and LE: "a k = Enc (le_ktm M)"
from in_δ show "a' k = Enc (le_ktm M) ∧ d k ∈ {MoveN, MoveR}"
proof (cases rule: wrap_delta_cases)
case init
thus ?thesis using LE unfolding wrap_init_delta_gen_def
by (auto split: nat.splits if_splits)
next
case ext
thus ?thesis using LE unfolding wrap_buf_extend_delta_gen_def
by (auto split: nat.splits)
next
case close
thus ?thesis using LE unfolding wrap_buf_close_delta_gen_def
by (fastforce split: nat.splits if_splits)
next
case eend
thus ?thesis using LE unfolding wrap_buf_empty_end_delta_gen_def
by (auto split: nat.splits)
next
case nend
thus ?thesis using LE unfolding wrap_buf_nonempty_end_delta_gen_def
by (fastforce split: nat.splits if_splits)
next
case rloop
thus ?thesis using LE unfolding wrap_rewind_loop_delta_gen_def
by (auto split: if_splits)
next
case rdone
thus ?thesis using LE unfolding wrap_plant_done_delta_def
by (auto split: if_splits)
next
case disp
thus ?thesis using LE unfolding wrap_disp_delta_gen_def
by (auto split: nat.splits)
next
case run
then obtain qq σ q'' σ' dd sym where
aeq: "a = sym"
and a'eq: "a' = (λp. Enc (σ' (wrap_tau p)))"
and deq: "d = (λp. dd (wrap_tau p))"
and trM: "(qq, σ, q'', σ', dd) ∈ delta_ktm M"
and symc: "∀p. sym p = Enc (σ (wrap_tau p))"
unfolding wrap_run_delta_def by auto
have "sym k = Enc (le_ktm M)" using LE aeq by simp
moreover have "sym k = Enc (σ (wrap_tau k))" using symc by simp
ultimately have "σ (wrap_tau k) = le_ktm M" by simp
from valid_ktm_deltaLE[OF valM trM this]
have "σ' (wrap_tau k) = le_ktm M ∧ dd (wrap_tau k) ∈ {MoveN, MoveR}" .
with a'eq deq show ?thesis by simp
qed
qed
show "∀q a q' a' d.
(q, a, q', a', d) ∈ wrap_delta M pack c Σu ⟶
(∀j ≥ k_ktm M.
a j = Enc (bl_ktm M) ∧ a' j = Enc (bl_ktm M) ∧ d j = MoveN)"
proof (intro allI impI)
fix q a q' a' d j
assume in_δ: "(q, a, q', a', d) ∈ wrap_delta M pack c Σu"
and jge: "k_ktm M ≤ j"
from k2 jge have j2: "2 ≤ j" by simp
from in_δ
show "a j = Enc (bl_ktm M) ∧ a' j = Enc (bl_ktm M) ∧ d j = MoveN"
proof (cases rule: wrap_delta_cases)
case init
thus ?thesis using jge j2 unfolding wrap_init_delta_gen_def
by (auto split: nat.splits if_splits)
next
case ext
thus ?thesis using jge j2 unfolding wrap_buf_extend_delta_gen_def
by (auto split: nat.splits)
next
case close
thus ?thesis using jge j2 unfolding wrap_buf_close_delta_gen_def
by (auto split: nat.splits if_splits)
next
case eend
thus ?thesis using jge j2 unfolding wrap_buf_empty_end_delta_gen_def
by (auto split: nat.splits)
next
case nend
thus ?thesis using jge j2 unfolding wrap_buf_nonempty_end_delta_gen_def
by (auto split: nat.splits if_splits)
next
case rloop
thus ?thesis using jge j2 unfolding wrap_rewind_loop_delta_gen_def
by (auto split: if_splits)
next
case rdone
thus ?thesis using jge j2 unfolding wrap_plant_done_delta_def
by (auto split: if_splits)
next
case disp
thus ?thesis using jge j2 unfolding wrap_disp_delta_gen_def
by (auto split: nat.splits)
next
case run
then obtain qq σ q'' σ' dd sym where
aeq: "a = sym"
and a'eq: "a' = (λp. Enc (σ' (wrap_tau p)))"
and deq: "d = (λp. dd (wrap_tau p))"
and trM: "(qq, σ, q'', σ', dd) ∈ delta_ktm M"
and symc: "∀p. sym p = Enc (σ (wrap_tau p))"
unfolding wrap_run_delta_def by auto
have tauj: "wrap_tau j = j" using j2 by (rule wrap_tau_ge2_id)
from valid_ktm_delta_support[OF valM trM jge]
have supp: "σ j = bl_ktm M ∧ σ' j = bl_ktm M ∧ dd j = MoveN" .
have "a j = Enc (bl_ktm M)" using aeq symc tauj supp by simp
moreover have "a' j = Enc (bl_ktm M)" using a'eq tauj supp by simp
moreover have "d j = MoveN" using deq tauj supp by simp
ultimately show ?thesis by simp
qed
qed
qed
qed
subsection ‹Determinism of the wrap›
text ‹Obligation 4 --- determinism preservation, conditional on
@{term "det_ktm M"}. The encoder families and
dispatch are functional per read pattern, and the transposed run inherits
M-determinism through @{const wrap_tau}. In the @{text W_Reset} case two
families can fire, and they are told apart, the generic storage rewind
loop from the plant-done step, by their
@{text le}-guards on the storage tape (index @{text "Suc 0"}) --- the loop
reads a non-@{text le} there, the plant-done reads @{text le} --- each
functional in the read.›
lemma wrap_det:
assumes valM: "valid_ktm M"
and detM: "det_ktm M"
and finSu: "finite Σu"
and c_pos: "0 < c"
shows "det_ktm (encoding_wrap M pack c Σu)"
unfolding det_ktm_def
proof (intro allI impI)
fix q a p1 b1 d1 p2 b2 d2
assume t1: "(q, a, p1, b1, d1) ∈ delta_ktm (encoding_wrap M pack c Σu)"
and t2: "(q, a, p2, b2, d2) ∈ delta_ktm (encoding_wrap M pack c Σu)"
hence t1w: "(q, a, p1, b1, d1) ∈ wrap_delta M pack c Σu"
and t2w: "(q, a, p2, b2, d2) ∈ wrap_delta M pack c Σu"
by simp_all
show "(p1, b1, d1) = (p2, b2, d2)"
proof (cases q)
case W_Init
with t1w t2w show ?thesis
unfolding wrap_delta_def
wrap_init_delta_gen_def wrap_buf_extend_delta_gen_def
wrap_buf_close_delta_gen_def wrap_buf_empty_end_delta_gen_def
wrap_buf_nonempty_end_delta_gen_def
wrap_rewind_loop_delta_gen_def
wrap_plant_done_delta_def
wrap_disp_delta_gen_def wrap_run_delta_def
by auto
next
case (W_Buf ws)
with t1w t2w show ?thesis
unfolding wrap_delta_def
wrap_init_delta_gen_def wrap_buf_extend_delta_gen_def
wrap_buf_close_delta_gen_def wrap_buf_empty_end_delta_gen_def
wrap_buf_nonempty_end_delta_gen_def
wrap_rewind_loop_delta_gen_def
wrap_plant_done_delta_def
wrap_disp_delta_gen_def wrap_run_delta_def
by auto
next
case W_Reset
with t1w t2w show ?thesis
unfolding wrap_delta_def
wrap_init_delta_gen_def wrap_buf_extend_delta_gen_def
wrap_buf_close_delta_gen_def wrap_buf_empty_end_delta_gen_def
wrap_buf_nonempty_end_delta_gen_def
wrap_rewind_loop_delta_gen_def
wrap_plant_done_delta_def
wrap_disp_delta_gen_def wrap_run_delta_def
by (auto split: if_splits)
next
case W_Disp
with t1w t2w show ?thesis
unfolding wrap_delta_def
wrap_init_delta_gen_def wrap_buf_extend_delta_gen_def
wrap_buf_close_delta_gen_def wrap_buf_empty_end_delta_gen_def
wrap_buf_nonempty_end_delta_gen_def
wrap_rewind_loop_delta_gen_def
wrap_plant_done_delta_def
wrap_disp_delta_gen_def wrap_run_delta_def
by auto
next
case (W_Run qM)
from t1w W_Run obtain sig1 q1' sig1' dd1 where
m1: "(qM, sig1, q1', sig1', dd1) ∈ delta_ktm M"
and sym1: "∀p. a p = Enc (sig1 (wrap_tau p))"
and p1_eq: "p1 = W_Run q1'"
and b1_eq: "b1 = (λp. Enc (sig1' (wrap_tau p)))"
and d1_eq: "d1 = (λp. dd1 (wrap_tau p))"
unfolding wrap_delta_def
wrap_init_delta_gen_def wrap_buf_extend_delta_gen_def
wrap_buf_close_delta_gen_def wrap_buf_empty_end_delta_gen_def
wrap_buf_nonempty_end_delta_gen_def
wrap_rewind_loop_delta_gen_def
wrap_plant_done_delta_def
wrap_disp_delta_gen_def wrap_run_delta_def
by auto
from t2w W_Run obtain sig2 q2' sig2' dd2 where
m2: "(qM, sig2, q2', sig2', dd2) ∈ delta_ktm M"
and sym2: "∀p. a p = Enc (sig2 (wrap_tau p))"
and p2_eq: "p2 = W_Run q2'"
and b2_eq: "b2 = (λp. Enc (sig2' (wrap_tau p)))"
and d2_eq: "d2 = (λp. dd2 (wrap_tau p))"
unfolding wrap_delta_def
wrap_init_delta_gen_def wrap_buf_extend_delta_gen_def
wrap_buf_close_delta_gen_def wrap_buf_empty_end_delta_gen_def
wrap_buf_nonempty_end_delta_gen_def
wrap_rewind_loop_delta_gen_def
wrap_plant_done_delta_def
wrap_disp_delta_gen_def wrap_run_delta_def
by auto
have sigma_eq: "sig1 = sig2"
proof (rule ext)
fix x
have e1: "a (wrap_tau x) = Enc (sig1 (wrap_tau (wrap_tau x)))"
using sym1 by blast
have e2: "a (wrap_tau x) = Enc (sig2 (wrap_tau (wrap_tau x)))"
using sym2 by blast
from e1 e2 have "sig1 (wrap_tau (wrap_tau x)) = sig2 (wrap_tau (wrap_tau x))"
by simp
thus "sig1 x = sig2 x" by (simp add: wrap_tau_invol)
qed
have M_det: "(q1', sig1', dd1) = (q2', sig2', dd2)"
using m1 m2 sigma_eq detM[unfolded det_ktm_def] by blast
hence q'_eq: "q1' = q2'" and sig'_eq: "sig1' = sig2'" and dd_eq: "dd1 = dd2"
by simp_all
show ?thesis
using p1_eq p2_eq b1_eq b2_eq d1_eq d2_eq q'_eq sig'_eq dd_eq
by metis
qed
qed
end