Theory Multitape_Substrate
theory Multitape_Substrate
imports Multitape_Substrate_Core
begin
section ‹Basic facts about machines and runs›
text ‹The substrate metatheory --- ∗‹our› additions over the
Dalvit--Thiemann definition surface isolated in ‹Multitape_Substrate_Core›:
relation-power and finiteness utilities, the ‹valid_ktm›
axiom-extraction toolkit, per-step and reachability validity
preservation, and the displacement / left-endmarker / no-write tape
tools. The core (‹Multitape_Substrate_Core›) carries the datatypes, accessors,
step relation, and the validity / language definitions.›
subsection ‹Relation powers and finiteness›
lemma finite_UNIV_move [simp, intro]: "finite (UNIV :: move set)"
proof -
have id: "UNIV = {MoveL, MoveR, MoveN}"
using move.exhaust by auto
show ?thesis unfolding id by auto
qed
text ‹Blank-tail finiteness: the set of total functions ‹nat ⇒ 'b›
ranging in a finite codomain ‹B› and ∗‹constant ‹c› beyond an
index ‹k›› is finite. This replaces the function-space finiteness
lemmas (‹fin_funcsetI› / ‹finite_UNIV_fun_dir›) that the AFP source
relied on: those are false at the value-level ‹nat› index, where
the domain is infinite. Finiteness is recovered from the support
bound — a blank-tail function is determined by its restriction to
‹{..<k}›, of which there are finitely many. Used to re-derive
‹finite δ› for constructed machines (‹valid_ktm_finite_delta›),
with codomain ‹Γ› (blank tail) for read/write tuples and ‹move›
(‹MoveN› tail) for the move tuples.›
lemma finite_tail_const_funcs:
fixes B :: "'b set" and k :: nat and c :: 'b
assumes finB: "finite B"
shows "finite {f :: nat ⇒ 'b. (∀j. f j ∈ B) ∧ (∀j ≥ k. f j = c)}"
proof -
let ?S = "{f :: nat ⇒ 'b. (∀j. f j ∈ B) ∧ (∀j ≥ k. f j = c)}"
have inj: "inj_on (λf. restrict f {..<k}) ?S"
proof (rule inj_onI)
fix f g
assume f: "f ∈ ?S" and g: "g ∈ ?S"
and eq: "restrict f {..<k} = restrict g {..<k}"
show "f = g"
proof
fix j
show "f j = g j"
proof (cases "j < k")
case True
have "restrict f {..<k} j = restrict g {..<k} j" using eq by simp
thus ?thesis using True by (simp add: restrict_def)
next
case False
hence "k ≤ j" by simp
with f g show ?thesis by simp
qed
qed
qed
have rng: "(λf. restrict f {..<k}) ` ?S ⊆ ({..<k} →⇩E B)"
proof
fix h assume "h ∈ (λf. restrict f {..<k}) ` ?S"
then obtain f where f: "f ∈ ?S" and h: "h = restrict f {..<k}" by blast
show "h ∈ {..<k} →⇩E B"
using f unfolding h by (simp add: restrict_PiE Pi_iff)
qed
have finPiE: "finite ({..<k} →⇩E B)" using finB by (simp add: finite_PiE)
have "finite ((λf. restrict f {..<k}) ` ?S)"
by (rule finite_subset[OF rng finPiE])
thus "finite ?S" using inj by (rule finite_imageD)
qed
text ‹Runs compose by HOL's ‹relpow_trans›. Monotonicity in the relation is
HOL's predicate lemma ‹relpowp_mono›, restated for relations as sets.›
lemma relpow_subset_mono: fixes R :: "'a rel"
shows "R ⊆ S ⟹ R^^n ⊆ S^^n"
by (induct n, auto)
text ‹Bounded-iteration combinator: given a single-step law that,
from any config satisfying an index-parameterised invariant
‹P i› with ‹i < n›, takes one ‹R›-step to a config satisfying
‹P (Suc i)›, iterate it: from ‹P 0 c⇩0› reach a ‹c'› with
‹(c⇩0, c') ∈ R⇗n⇖› and ‹P n c'›. A loop whose counter
starts at some ‹off > 0› instantiates ‹P› to re-index by that
offset. Proved by induction generalising ∗‹both› the start
config and the invariant, so the hypothesis applies to the shifted
predicate ‹λj. P (Suc j)› after peeling the first step
(prepended via ‹relpow_Suc_I2›).›
lemma relpow_invariant_chain:
fixes R :: "('s × 's) set"
and P :: "nat ⇒ 's ⇒ bool"
assumes step: "⋀i c. ⟦ i < n; P i c ⟧
⟹ ∃c'. (c, c') ∈ R ∧ P (Suc i) c'"
and base: "P 0 c0"
shows "∃c'. (c0, c') ∈ R ^^ n ∧ P n c'"
using assms
proof (induction n arbitrary: c0)
case 0
show ?case using "0.prems"(2) by auto
next
case (Suc m)
have step_m:
"⋀i c. ⟦ i < m; P i c ⟧
⟹ ∃c'. (c, c') ∈ R ∧ P (Suc i) c'"
proof -
fix i :: nat and c :: 's
assume "i < m" and "P i c"
thus "∃c'. (c, c') ∈ R ∧ P (Suc i) c'"
using Suc.prems(1)[of i c] by simp
qed
obtain c_m where chain_m: "(c0, c_m) ∈ R ^^ m" and Pcm: "P m c_m"
using Suc.IH[OF step_m Suc.prems(2)] by blast
obtain c' where last_step: "(c_m, c') ∈ R" and Pc': "P (Suc m) c'"
using Suc.prems(1)[of m c_m] Pcm by auto
have "(c0, c') ∈ R ^^ Suc m"
using chain_m last_step by (rule relpow_Suc_I)
thus ?case using Pc' by blast
qed
text ‹❙‹A step simulation is a run simulation.› A construction that
re-encodes configurations by a map ‹h› proves that each step of the
source is a step of the target on the images, and wants the same of a run
of any length. The step may assume its source was reached from the run's
start: the encodings that are steps only on reachable configurations (a
valid one, or one with its endmarkers in place) discharge that by the
relational-power forms of their invariants.›
lemma relpow_map:
assumes step: "⋀m x y. (a, x) ∈ R ^^ m ⟹ (x, y) ∈ R ⟹ (h x, h y) ∈ S"
and run: "(a, b) ∈ R ^^ n"
shows "(h a, h b) ∈ S ^^ n"
using run
proof (induction n arbitrary: b)
case 0
then show ?case by simp
next
case (Suc n)
from Suc.prems obtain x where ax: "(a, x) ∈ R ^^ n" and xb: "(x, b) ∈ R"
by (rule relpow_Suc_E)
from Suc.IH [OF ax] step [OF ax xb] show ?case by (rule relpow_Suc_I)
qed
subsection ‹Uniqueness on a deterministic region›
text ‹❙‹‹det_ktm_relpow_unique› (below) for a machine that is
deterministic only somewhere.› A nondeterministic machine can still have large regions in
which it branches nowhere, and a run that stays inside one of those is as
pinned as a deterministic machine's. What makes the statement usable is
that both hypotheses are about the ∗‹region› rather than about the
relation: ‹R› is closed under a step, and a step out of ‹R› is unique.
The induction cannot be traded for ⬚‹single_valued_relpow› the way
‹det_ktm_relpow_unique›'s was. Restricting the relation to ‹R› does make it
single-valued, but showing that an unrestricted run ∗‹is› a
restricted one is the same induction again --- the closure has to be
carried along the run, and that is precisely what the induction does.
Stated for a bare relation because nothing here is about machines.›
lemma relpow_unique_on:
assumes closed: "⋀x y. x ∈ R ⟹ (x, y) ∈ S ⟹ y ∈ R"
and fn: "⋀x y z. x ∈ R ⟹ (x, y) ∈ S ⟹ (x, z) ∈ S
⟹ y = z"
shows "x ∈ R ⟹ (x, y) ∈ S ^^ n ⟹ (x, z) ∈ S ^^ n ⟹ y = z"
proof (induct n arbitrary: x y z)
case 0
then show ?case by simp
next
case (Suc n)
from Suc.prems(2) obtain u where xu: "(x, u) ∈ S" and uy: "(u, y) ∈ S ^^ n"
by (blast dest: relpow_Suc_D2)
from Suc.prems(3) obtain v where xv: "(x, v) ∈ S" and vz: "(v, z) ∈ S ^^ n"
by (blast dest: relpow_Suc_D2)
from fn [OF Suc.prems(1) xu xv] have uv: "u = v" .
have uR: "u ∈ R" by (rule closed [OF Suc.prems(1) xu])
from vz uv have uz: "(u, z) ∈ S ^^ n" by simp
show ?case by (rule Suc.hyps [OF uR uy uz])
qed
text ‹❙‹What the region buys, stated the way a language argument wants
it.› The lemma above compares runs of the ∗‹same› length, which no
consumer ever has: one is given a path that halts and asked about another
path that halts, and the two lengths are unrelated. The bridge is that a
halting configuration has no successor, so the shorter run cannot be a
proper prefix of the longer one --- and by uniqueness it is a prefix or
nothing. So the two runs have the same length as well as the same end.
So a branch-free region admits ∗‹at most one› halting configuration
reachable from a given start, whatever the path and whatever its length.
That is the form soundness uses: exhibit the run that halts, and every
other halting run is that one. The length half is what pins a phase of a
simulation: two runs of a sub-relation that both end where it stops took
the same number of steps.›
lemma relpow_halted_le:
assumes closed: "⋀x y. x ∈ R ⟹ (x, y) ∈ S ⟹ y ∈ R"
and fn: "⋀x y z. x ∈ R ⟹ (x, y) ∈ S ⟹ (x, z) ∈ S
⟹ y = z"
and stuck: "⋀u v. u ∈ H ⟹ (u, v) ∈ S ⟹ False"
and x: "x ∈ R"
and r1: "(x, y) ∈ S ^^ m" and h1: "y ∈ H"
and r2: "(x, z) ∈ S ^^ n"
and mn: "m ≤ n"
shows "m = n ∧ y = z"
proof -
have "S ^^ (m + (n - m)) = S ^^ m O S ^^ (n - m)" by (rule relpow_add)
moreover from mn have "m + (n - m) = n" by simp
ultimately have "S ^^ n = S ^^ m O S ^^ (n - m)" by simp
with r2 have "(x, z) ∈ S ^^ m O S ^^ (n - m)" by simp
then obtain u where xu: "(x, u) ∈ S ^^ m" and uz: "(u, z) ∈ S ^^ (n - m)"
by auto
from relpow_unique_on [OF closed fn x r1 xu] have "y = u" .
with uz have yz: "(y, z) ∈ S ^^ (n - m)" by simp
show ?thesis
proof (cases "n - m")
case 0
with yz mn show ?thesis by simp
next
case (Suc k)
from yz Suc have "(y, z) ∈ S ^^ Suc k" by simp
then obtain v where "(y, v) ∈ S" by (blast dest: relpow_Suc_D2)
from stuck [OF h1 this] show ?thesis ..
qed
qed
lemma relpow_halted_same_run:
assumes closed: "⋀x y. x ∈ R ⟹ (x, y) ∈ S ⟹ y ∈ R"
and fn: "⋀x y z. x ∈ R ⟹ (x, y) ∈ S ⟹ (x, z) ∈ S
⟹ y = z"
and stuck: "⋀u v. u ∈ H ⟹ (u, v) ∈ S ⟹ False"
and x: "x ∈ R"
and r1: "(x, y) ∈ S ^^ m" and h1: "y ∈ H"
and r2: "(x, z) ∈ S ^^ n" and h2: "z ∈ H"
shows "m = n ∧ y = z"
using nat_le_linear [of m n]
proof
assume mn: "m ≤ n"
from relpow_halted_le [OF closed fn stuck x r1 h1 r2 mn] show ?thesis .
next
assume nm: "n ≤ m"
from relpow_halted_le [OF closed fn stuck x r2 h2 r1 nm] show ?thesis by simp
qed
lemmas relpow_halted_unique_on = relpow_halted_same_run [THEN conjunct2]
subsection ‹The conditions of validity, one at a time›
text ‹Convenience lemmas projecting the substrate's structural
axioms out of @{const valid_ktm} at the functional layer.
Each one is a one-shot ‹by (cases M) auto›: the case-decomposition
rewrites @{term M} into ‹KTM›-form, exposes the @{thm[source] valid_ktm.simps}
conjunction, and ‹auto› extracts the relevant conjunct.
These replace what used to be locale-routed retrievals of the
form ‹multitape_tm.X[OF loc]›.›
lemma valid_ktm_finite_Q:
assumes "valid_ktm M"
shows "finite (Q_ktm M)"
using assms by (cases M) auto
lemma valid_ktm_finite_Gamma:
assumes "valid_ktm M"
shows "finite (Γ_ktm M)"
using assms by (cases M) auto
lemma valid_ktm_Sigma_sub_Gamma:
assumes "valid_ktm M"
shows "Sigma_ktm M ⊆ Γ_ktm M"
using assms by (cases M) auto
lemma valid_ktm_s_in_Q:
assumes "valid_ktm M"
shows "s_ktm M ∈ Q_ktm M"
using assms by (cases M) auto
lemma valid_ktm_t_in_Q:
assumes "valid_ktm M"
shows "t_ktm M ∈ Q_ktm M"
using assms by (cases M) auto
lemma valid_ktm_r_in_Q:
assumes "valid_ktm M"
shows "r_ktm M ∈ Q_ktm M"
using assms by (cases M) auto
lemma valid_ktm_blank_in_Gamma:
assumes "valid_ktm M"
shows "bl_ktm M ∈ Γ_ktm M"
using assms by (cases M) auto
lemma valid_ktm_blank_not_Sigma:
assumes "valid_ktm M"
shows "bl_ktm M ∉ Sigma_ktm M"
using assms by (cases M) auto
lemma valid_ktm_LE_in_Gamma:
assumes "valid_ktm M"
shows "le_ktm M ∈ Γ_ktm M"
using assms by (cases M) auto
lemma valid_ktm_LE_not_Sigma:
assumes "valid_ktm M"
shows "le_ktm M ∉ Sigma_ktm M"
using assms by (cases M) auto
lemma valid_ktm_t_neq_r:
assumes "valid_ktm M"
shows "t_ktm M ≠ r_ktm M"
using assms by (cases M) auto
lemma valid_ktm_k_pos:
assumes "valid_ktm M"
shows "0 < k_ktm M"
using assms by (cases M) auto
lemma valid_ktm_delta_set:
assumes "valid_ktm M"
shows "delta_ktm M ⊆
(Q_ktm M - {t_ktm M, r_ktm M})
× (UNIV → Γ_ktm M)
× Q_ktm M
× (UNIV → Γ_ktm M)
× (UNIV → UNIV)"
using assms by (cases M) auto
text ‹Range typing for transition tuples: pulls the four
per-component facts from a single transition membership.›
lemma valid_ktm_delta:
assumes vM: "valid_ktm M"
and tr: "(q, a, q', b, d) ∈ delta_ktm M"
shows "q ∈ Q_ktm M" "a k ∈ Γ_ktm M" "q' ∈ Q_ktm M" "b k ∈ Γ_ktm M"
using valid_ktm_delta_set[OF vM] tr by auto
text ‹Left-endmarker discipline: transitions reading ‹le› must
rewrite ‹le› with itself and move only ‹N› or ‹R›.›
lemma valid_ktm_deltaLE:
assumes vM: "valid_ktm M"
and tr: "(q, a, q', a', d) ∈ delta_ktm M"
and LE: "a k = le_ktm M"
shows "a' k = le_ktm M ∧ d k ∈ {MoveN, MoveR}"
using vM tr LE by (cases M) auto
text ‹Left-endmarker write discipline: a transition writes ‹le› on
tape ‹k› only when it was reading ‹le› on the same tape. This is
exactly the content of @{const le_unique} specialised to one tape /
transition; it is the sole place that fact is extracted. Needed by
‹ae_coupled_run_aux› to preserve the "no LE in window" invariant
across an M-step. Takes @{const le_unique} (not @{const valid_ktm}):
it is the property a machine may forgo, so consumers thread it
explicitly rather than reading it off ‹valid_ktm›.›
lemma valid_ktm_deltaLE_no_write:
assumes lu: "le_unique M"
and tr: "(q, a, q', a', d) ∈ delta_ktm M"
and LE': "a' k = le_ktm M"
shows "a k = le_ktm M"
using lu[unfolded le_unique_def] tr LE' by blast
text ‹Support invariant: every transition of a valid machine is
blank on reads and writes, and stationary, at every tape index
‹j ≥ k_ktm M›. The value-level confinement of a ‹k›-tape machine's
action to tapes ‹0 … k - 1›.›
lemma valid_ktm_delta_support:
assumes vM: "valid_ktm M"
and tr: "(q, a, q', a', d) ∈ delta_ktm M"
and j: "j ≥ k_ktm M"
shows "a j = bl_ktm M ∧ a' j = bl_ktm M ∧ d j = MoveN"
proof -
obtain Q Σ Γ bl le δ s t r K where M_eq:
"M = KTM Q Σ Γ bl le δ s t r K"
by (cases M)
have supp:
"∀q a q' a' d. (q, a, q', a', d) ∈ δ ⟶
(∀j ≥ K. a j = bl ∧ a' j = bl ∧ d j = MoveN)"
using vM[unfolded M_eq valid_ktm.simps] by blast
from tr M_eq have tr_delta: "(q, a, q', a', d) ∈ δ" by simp
from j M_eq have jK: "j ≥ K" by simp
have bleq: "bl_ktm M = bl" using M_eq by simp
from supp tr_delta jK have "a j = bl ∧ a' j = bl ∧ d j = MoveN" by blast
thus ?thesis using bleq by simp
qed
text ‹Finiteness of ‹δ› from bounded support: a valid machine's
transition relation is finite. The value-level replacement for
the AFP source's function-space finiteness over a finite tape
type. Each transition's read / write tuples range in the finite
@{term Γ} and are blank beyond ‹k›, each move tuple is ‹N›
beyond ‹k›; by @{thm[source] finite_tail_const_funcs} there are
finitely many of each, so ‹δ› embeds in a finite product.›
lemma valid_ktm_finite_delta:
assumes vM: "valid_ktm M"
shows "finite (delta_ktm M)"
proof -
obtain Q Σ Γ bl le δ s t r K where M_eq:
"M = KTM Q Σ Γ bl le δ s t r K"
by (cases M)
have finQ: "finite Q" using valid_ktm_finite_Q[OF vM] M_eq by simp
have finG: "finite Γ" using valid_ktm_finite_Gamma[OF vM] M_eq by simp
let ?A = "{a. (∀j. a j ∈ Γ) ∧ (∀j ≥ K. a j = bl)}"
let ?D = "{d. (∀j. d j ∈ (UNIV :: move set)) ∧ (∀j ≥ K. d j = MoveN)}"
have finA: "finite ?A" by (rule finite_tail_const_funcs[OF finG, of K bl])
have finD: "finite ?D" by (rule finite_tail_const_funcs[OF finite_UNIV_move, of K MoveN])
have finprod: "finite ((Q - {t, r}) × ?A × Q × ?A × ?D)"
using finQ finA finD by (intro finite_cartesian_product) auto
have sub: "delta_ktm M ⊆ (Q - {t, r}) × ?A × Q × ?A × ?D"
proof
fix x assume xd: "x ∈ delta_ktm M"
obtain q a q' a' d where x: "x = (q, a, q', a', d)"
by (cases x)
from valid_ktm_delta_set[OF vM] xd x M_eq
have q_mem: "q ∈ Q - {t, r}" and a_pi: "a ∈ UNIV → Γ"
and q'_mem: "q' ∈ Q" and a'_pi: "a' ∈ UNIV → Γ"
by auto
from a_pi have aG: "∀j. a j ∈ Γ" by (auto simp: Pi_iff)
from a'_pi have a'G: "∀j. a' j ∈ Γ" by (auto simp: Pi_iff)
have trM: "(q, a, q', a', d) ∈ delta_ktm M" using xd x by simp
have supp: "∀j ≥ K. a j = bl ∧ a' j = bl ∧ d j = MoveN"
proof (intro allI impI)
fix j assume "K ≤ j"
hence "j ≥ k_ktm M" using M_eq by simp
thus "a j = bl ∧ a' j = bl ∧ d j = MoveN"
using valid_ktm_delta_support[OF vM trM] M_eq by simp
qed
have "a ∈ ?A" using aG supp by auto
moreover have "a' ∈ ?A" using a'G supp by auto
moreover have "d ∈ ?D" using supp by auto
ultimately show "x ∈ (Q - {t, r}) × ?A × Q × ?A × ?D"
using x q_mem q'_mem by auto
qed
show ?thesis using sub finprod by (rule finite_subset)
qed
text ‹State membership at the source of an ‹ktm_step›: the
source state is in ‹Q_ktm M› and is neither the accept nor
the reject state. Direct consequence of the ‹ktm_step›
introduction rule plus ‹valid_ktm_delta_set›'s range typing
(which excludes halting states from the source projection of
‹delta_ktm M›).
Used by the chunked-induction engine
‹ae_simulation_phase_chunked›: when the M-trace
‹(cM, cM_final) ∈ ktm_step (delta_ktm M) ^^ (Suc n)›
is non-empty, the first step exists and forces ‹cM›'s state
to be non-halt and in ‹Q›, which feeds
‹ae_simulates_forward_stage_general›'s ‹qM_in_Q› /
‹q_neq_t› / ‹q_neq_r› hypotheses.›
lemma ktm_step_src:
fixes M :: "('q, 'a) ktm"
assumes vM: "valid_ktm M"
and step: "(c, c') ∈ ktm_step (delta_ktm M)"
shows ktm_step_src_in_Q: "ktc_state c ∈ Q_ktm M"
and ktm_step_src_neq_t: "ktc_state c ≠ t_ktm M"
and ktm_step_src_neq_r: "ktc_state c ≠ r_ktm M"
proof -
from step obtain q ts n q' a move where
c_eq: "c = KConfig q ts n"
and tr: "(q, λk. ts k (n k), q', a, move) ∈ delta_ktm M"
by (auto elim: ktm_step.cases)
have q_eq: "ktc_state c = q" using c_eq by simp
have q_in_strict: "q ∈ Q_ktm M - {t_ktm M, r_ktm M}"
using valid_ktm_delta_set[OF vM] tr by auto
show "ktc_state c ∈ Q_ktm M" using q_eq q_in_strict by simp
show "ktc_state c ≠ t_ktm M" using q_eq q_in_strict by simp
show "ktc_state c ≠ r_ktm M" using q_eq q_in_strict by simp
qed
subsection ‹A step preserves valid configurations›
text ‹Per-step preservation of @{const valid_config_ktm}: a valid
configuration steps only to valid configurations. Re-derived
directly from @{thm[source] valid_ktm_delta} (range typing),
@{thm[source] valid_ktm_deltaLE} (left-endmarker discipline),
and @{thm[source] valid_ktm_delta_support} (the new inactive-tape
blank-tail case).›
lemma valid_step_ktm:
fixes M :: "('q, 'a) ktm"
assumes vM: "valid_ktm M"
and step: "(c, c') ∈ ktm_step (delta_ktm M)"
and val_c: "valid_config_ktm M c"
shows "valid_config_ktm M c'"
proof -
obtain Q Σ Γ bl le δ s t r K where M_eq:
"M = KTM Q Σ Γ bl le δ s t r K"
by (cases M)
obtain q ts n where c_eq: "c = KConfig q ts n"
by (cases c)
from step M_eq c_eq have step_delta:
"(KConfig q ts n, c') ∈ ktm_step δ"
by simp
obtain q' a move where c'_eq:
"c' = KConfig q' (λk. (ts k)(n k := a k))
(λk. go_move (move k) (n k))"
and tr: "(q, (λk. ts k (n k)), q', a, move) ∈ δ"
using step_delta by (auto elim: ktm_step.cases)
from val_c c_eq M_eq have q_in: "q ∈ Q"
and ts_Gamma: "⋀k. range (ts k) ⊆ Γ"
and ts_LE: "⋀k. k < K ⟹ ts k 0 = le"
and ts_blank: "⋀k p. k ≥ K ⟹ ts k p = bl"
by auto
from tr M_eq have tr_M: "(q, (λk. ts k (n k)), q', a, move) ∈ delta_ktm M"
by simp
have q'_in: "q' ∈ Q_ktm M" and a_Gamma: "⋀k. a k ∈ Γ_ktm M"
using valid_ktm_delta[OF vM tr_M] by auto
hence q'_in_Q: "q' ∈ Q" and a_Gamma_set: "⋀k. a k ∈ Γ"
using M_eq by auto
have new_ts_Gamma: "⋀k. range ((ts k)(n k := a k)) ⊆ Γ"
using ts_Gamma a_Gamma_set by auto
have new_LE: "⋀k. k < K ⟹ ((ts k)(n k := a k)) 0 = le"
proof -
fix k assume kK: "k < K"
show "((ts k)(n k := a k)) 0 = le"
proof (cases "n k = 0")
case True
have read_LE: "(λj. ts j (n j)) k = le"
using ts_LE[OF kK] True by simp
have read_LE_le: "(λj. ts j (n j)) k = le_ktm M"
using read_LE M_eq by simp
have "a k = le_ktm M"
using valid_ktm_deltaLE[OF vM tr_M read_LE_le] by simp
hence "a k = le" using M_eq by simp
with True show ?thesis by simp
next
case False
thus ?thesis using ts_LE[OF kK] by simp
qed
qed
have new_blank: "⋀k p. k ≥ K ⟹ ((ts k)(n k := a k)) p = bl"
proof -
fix k p assume kK: "k ≥ K"
have ak_bl: "a k = bl"
proof -
have "k ≥ k_ktm M" using kK M_eq by simp
hence "a k = bl_ktm M"
using valid_ktm_delta_support[OF vM tr_M] by simp
thus ?thesis using M_eq by simp
qed
show "((ts k)(n k := a k)) p = bl"
using ts_blank[OF kK] ak_bl by (cases "p = n k") auto
qed
show ?thesis
unfolding M_eq c'_eq valid_config_ktm.simps
proof (intro conjI allI impI)
show "q' ∈ Q" using q'_in_Q .
next
fix i
show "range ((λk. (ts k)(n k := a k)) i) ⊆ Γ"
using new_ts_Gamma by simp
next
fix i assume "i < K"
show "(λk. (ts k)(n k := a k)) i 0 = le"
using new_LE[OF ‹i < K›] by simp
next
fix i p assume "K ≤ i"
show "(λk. (ts k)(n k := a k)) i p = bl"
using new_blank[OF ‹K ≤ i›] by simp
qed
qed
text ‹Initial-configuration accessors, in terms of the machine's
structural projections. \<^const>‹init_config_ktm› is a ⬚‹fun› over
the ‹KTM› constructor, so without these a proof reads the start tape,
state or heads only after an inline ‹cases M›. The head positions are
a ⬚‹simp› rule, since every head starts at the origin.›
lemma ktc_tape_init_config:
"ktc_tape (init_config_ktm M w)
= (λk n. if k < k_ktm M
then (if n = 0 then le_ktm M
else if k = 0 ∧ n ≤ length w then w ! (n - 1)
else bl_ktm M)
else bl_ktm M)"
proof (cases M)
case (KTM Q Sg Gm bl le dl s tt rr kk)
then have lhs: "ktc_tape (init_config_ktm M w)
= (λk n. if k < kk
then (if n = 0 then le
else if k = 0 ∧ n ≤ length w then w ! (n - 1)
else bl)
else bl)"
and le': "le_ktm M = le" and bl': "bl_ktm M = bl" and kk': "k_ktm M = kk"
by simp_all
show ?thesis by (simp only: lhs le' bl' kk')
qed
lemma ktc_state_init_config [simp]:
"ktc_state (init_config_ktm M w) = s_ktm M"
proof (cases M)
case (KTM Q Sg Gm bl le dl s tt rr kk)
then have lhs: "ktc_state (init_config_ktm M w) = s" and s': "s_ktm M = s"
by simp_all
show ?thesis by (simp only: lhs s')
qed
lemma ktc_pos_init_config [simp]:
"ktc_pos (init_config_ktm M w) = (λ_. 0)"
by (cases M) simp
text ‹Initial-configuration validity: a valid ‹M›'s initial
configuration on a valid input is itself valid.›
lemma valid_init_config_ktm:
fixes M :: "('q, 'a) ktm"
assumes vM: "valid_ktm M"
and w: "set w ⊆ Sigma_ktm M"
shows "valid_config_ktm M (init_config_ktm M w)"
proof -
obtain Q Σ Γ bl le δ s t r K where M_eq:
"M = KTM Q Σ Γ bl le δ s t r K"
by (cases M)
have w_Sigma: "set w ⊆ Σ"
using w M_eq by simp
have s_in: "s ∈ Q" using valid_ktm_s_in_Q[OF vM] M_eq by simp
have Sigma_sub: "Σ ⊆ Γ" using valid_ktm_Sigma_sub_Gamma[OF vM] M_eq by simp
have bl_in: "bl ∈ Γ" using valid_ktm_blank_in_Gamma[OF vM] M_eq by simp
have le_in: "le ∈ Γ" using valid_ktm_LE_in_Gamma[OF vM] M_eq by simp
show ?thesis
unfolding M_eq init_config_ktm.simps valid_config_ktm.simps
proof (intro conjI allI impI)
show "s ∈ Q" using s_in .
next
fix i
show "range (λn. if i < K
then (if n = 0 then le
else if i = 0 ∧ n ≤ length w then w ! (n - 1)
else bl)
else bl) ⊆ Γ"
proof (cases "i < K")
case True
show ?thesis
using bl_in le_in Sigma_sub w_Sigma True
by (force simp: set_conv_nth)
next
case False
show ?thesis using bl_in False by simp
qed
next
fix i assume "i < K"
show "(if i < K
then (if (0::nat) = 0 then le
else if i = 0 ∧ 0 ≤ length w then w ! (0 - 1)
else bl)
else bl) = le"
using ‹i < K› by simp
next
fix i p assume "K ≤ i"
show "(if i < K
then (if p = 0 then le
else if i = 0 ∧ p ≤ length w then w ! (p - 1)
else bl)
else bl) = bl"
using ‹K ≤ i› by simp
qed
qed
text ‹Reachability lift: every configuration reachable from a
valid initial configuration is itself valid.›
lemma valid_reach_ktm:
fixes M :: "('q, 'a) ktm"
assumes vM: "valid_ktm M"
and w: "set w ⊆ Sigma_ktm M"
and reach: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M))⇧*"
shows "valid_config_ktm M c"
using reach
proof induction
case base
show ?case using valid_init_config_ktm[OF vM w] .
next
case (step y z)
show ?case using valid_step_ktm[OF vM step.hyps(2) step.IH] .
qed
text ‹Blank-tail accessor for a valid configuration: beyond the
machine's tape count ‹k_ktm M› every cell holds the blank
‹bl_ktm M›. Used on the reverse lift's padding tapes, where the
per-tape window invariant is unavailable (it constrains the LE
home cell, which is blank on padding) and the read-match must
instead come from the substrate blank-tail.›
lemma valid_config_ktm_blank_tail:
assumes valc: "valid_config_ktm M c"
and kge: "i ≥ k_ktm M"
shows "ktc_tape c i p = bl_ktm M"
proof -
obtain Q Σ Γ bl le δ s t r K where
M_eq: "M = KTM Q Σ Γ bl le δ s t r K"
by (cases M)
obtain q ts n where c_eq: "c = KConfig q ts n" by (cases c)
from valc kge show ?thesis
unfolding M_eq c_eq by auto
qed
text ‹Validity preservation along an ‹n›-step substrate trace
from an arbitrary valid configuration (generic relpow closure of
@{thm[source] valid_step_ktm}; @{thm[source] valid_reach_ktm}
anchors only at ‹init_config_ktm›). Threads the blank-tail
validity of the reverse lift's intermediate configs ‹cM_n'›
through the chain induction.›
lemma valid_reach_relpow_ktm:
assumes vM: "valid_ktm M"
and valc: "valid_config_ktm M c"
and reach: "(c, c') ∈ ktm_step (delta_ktm M) ^^ n"
shows "valid_config_ktm M c'"
using relpow_imp_rtrancl [OF reach]
by (induction rule: rtrancl_induct) (auto intro: valc valid_step_ktm [OF vM])
text ‹Per-tape LE-pinning corollary: along any reachable trace
from a valid initial configuration, every ∗‹active› tape
(index ‹k < k_ktm M›) carries ‹le_ktm M› at position 0.
Note: ‹valid_config_ktm› only encodes the position-0 = LE
constraint on active tapes, not the converse (positions ‹p ≠ 0›
may legally hold LE in an arbitrary valid config). The "LE only
at position 0" property is reach-specific and proved separately
in the companion lemma below.›
lemma valid_reach_LE_pos0_ktm:
fixes M :: "('q, 'a) ktm"
assumes vM: "valid_ktm M"
and w: "set w ⊆ Sigma_ktm M"
and reach: "(init_config_ktm M w, KConfig q ts n)
∈ (ktm_step (delta_ktm M))⇧*"
and kK: "k < k_ktm M"
shows "ts k 0 = le_ktm M"
proof -
have val: "valid_config_ktm M (KConfig q ts n)"
using valid_reach_ktm[OF vM w reach] .
obtain Q Σ Γ bl le δ sM t r K where M_eq:
"M = KTM Q Σ Γ bl le δ sM t r K"
by (cases M)
have "k < K" using kK M_eq by simp
thus ?thesis using val M_eq by simp
qed
text ‹Dual to @{thm[source] valid_reach_LE_pos0_ktm}: along any reachable
trace from a valid initial configuration whose blank symbol differs
from the left endmarker, every cell at a position ‹p ≠ 0› on any
tape is not the left endmarker. Proof: induction on the
reachability relation. Base: ‹init_config_ktm› places ‹le›
only at position 0 of active tapes (input cells are in ‹Σ› hence
‹≠ le›; other active cells and all inactive cells are ‹bl› which
by hypothesis ‹≠ le›). Step: cells away from the head are
preserved (substrate update is ‹(ts k)(n k := a k)›); at the head,
the substrate's ‹δLE›-no-write rule says the write equals ‹le›
only if the read did, which by IH is impossible since the read
sits at the head position ‹n k› (and if ‹n k = p ≠ 0› the IH
gives the read is not ‹le›; if ‹n k = 0› then ‹p ≠ n k› and the
off-head case fires).›
lemma valid_reach_LE_only_pos0_ktm:
fixes M :: "('q, 'a) ktm"
and c :: "('a, 'q) ktc_config"
and k :: nat
and p :: nat
assumes vM: "valid_ktm M"
and lu: "le_unique M"
and w: "set w ⊆ Sigma_ktm M"
and reach: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M))⇧*"
and p_ne_0: "p ≠ 0"
and bl_neq_le: "bl_ktm M ≠ le_ktm M"
shows "ktc_tape c k p ≠ le_ktm M"
proof -
obtain Q Σ Γ bl le δ sM tt rr K where M_eq:
"M = KTM Q Σ Γ bl le δ sM tt rr K"
by (cases M)
have le_eq: "le_ktm M = le" using M_eq by simp
have bl_eq: "bl_ktm M = bl" using M_eq by simp
have bl_ne_le: "bl ≠ le" using bl_neq_le le_eq bl_eq by simp
have le_not_Sigma: "le ∉ Σ"
using valid_ktm_LE_not_Sigma[OF vM] M_eq by simp
have w_Sigma: "set w ⊆ Σ" using w M_eq by simp
have main:
"∀c'. (init_config_ktm M w, c') ∈ (ktm_step (delta_ktm M))⇧*
⟶ ktc_tape c' k p ≠ le_ktm M"
proof (intro allI impI)
fix c'
assume r: "(init_config_ktm M w, c') ∈ (ktm_step (delta_ktm M))⇧*"
show "ktc_tape c' k p ≠ le_ktm M"
using r
proof induction
case base
have tape_p_init:
"ktc_tape (init_config_ktm M w) k p
= (if k < K
then (if p = 0 then le
else if k = 0 ∧ p ≤ length w then w ! (p - 1)
else bl)
else bl)"
unfolding M_eq init_config_ktm.simps by simp
show ?case
proof (cases "k = 0 ∧ p ≤ length w")
case True
have K_pos: "0 < K" using valid_ktm_k_pos[OF vM] M_eq by simp
have kK: "k < K" using True K_pos by simp
have p_ge_1: "p ≥ 1" using p_ne_0 by simp
have idx_lt: "p - 1 < length w" using True p_ge_1 by linarith
have in_w: "w ! (p - 1) ∈ set w"
using idx_lt by (auto simp: set_conv_nth)
with w_Sigma have "w ! (p - 1) ∈ Σ" by blast
with le_not_Sigma have "w ! (p - 1) ≠ le" by blast
thus ?thesis using tape_p_init True kK p_ne_0 le_eq by simp
next
case False
have "ktc_tape (init_config_ktm M w) k p = bl"
using tape_p_init False p_ne_0 by (cases "k < K") auto
thus ?thesis using bl_ne_le le_eq by simp
qed
next
case (step y z)
have ne_y: "ktc_tape y k p ≠ le_ktm M" using step.IH .
obtain qy ts n where y_eq: "y = KConfig qy ts n"
by (cases y)
from step.hyps(2) y_eq obtain q' a dr where
z_eq: "z = KConfig q'
(λkk. (ts kk)(n kk := a kk))
(λkk. go_move (dr kk) (n kk))"
and tr: "(qy, (λkk. ts kk (n kk)), q', a, dr) ∈ delta_ktm M"
by (auto elim: ktm_step.cases)
show ?case
proof (cases "n k = p")
case False
have "ktc_tape z k p = ((ts k)(n k := a k)) p" using z_eq by simp
also have "… = ts k p" using False by simp
also have "… = ktc_tape y k p" using y_eq by simp
finally have "ktc_tape z k p = ktc_tape y k p" .
thus ?thesis using ne_y by simp
next
case True
have read_at_p: "ts k (n k) = ktc_tape y k p"
using y_eq True by simp
have read_ne: "ts k (n k) ≠ le_ktm M"
using ne_y read_at_p by simp
have a_ne: "a k ≠ le_ktm M"
proof
assume a_le: "a k = le_ktm M"
have "(λkk. ts kk (n kk)) k = le_ktm M"
using valid_ktm_deltaLE_no_write[OF lu tr a_le] by simp
hence "ts k (n k) = le_ktm M" by simp
thus False using read_ne by simp
qed
have "ktc_tape z k p = ((ts k)(n k := a k)) p" using z_eq by simp
also have "… = a k" using True by simp
finally have "ktc_tape z k p = a k" .
thus ?thesis using a_ne by simp
qed
qed
qed
show ?thesis using main reach by blast
qed
subsection ‹Step locality: non-head cells preserved, head moves by ‹≤› 1›
text ‹Two structural facts about ‹ktm_step› that fall directly out
of the single rule's body ‹(ts k)(n k := a k)› and
‹go_move (move k) (n k)›: a single step modifies only the head
cell on each tape, and the head displaces by at most one position
per tape per step. These are generic over ‹δ› and used by
alphabet-enlargement / -reduction to argue that cells outside a
bounded window are unchanged after ‹n› steps.›
lemma ktm_step_tape_off_head:
assumes step: "(c, c') ∈ ktm_step δ"
and ne: "p ≠ ktc_pos c k"
shows "ktc_tape c' k p = ktc_tape c k p"
proof -
from step obtain q ts n q' a dr where
c_eq: "c = KConfig q ts n"
and c'_eq: "c' = KConfig q'
(λk. (ts k)(n k := a k))
(λk. go_move (dr k) (n k))"
by (auto elim: ktm_step.cases)
from ne c_eq have "p ≠ n k" by simp
thus ?thesis by (simp add: c_eq c'_eq)
qed
lemma ktm_step_pos_displacement:
assumes step: "(c, c') ∈ ktm_step δ"
shows "ktc_pos c' k ≤ ktc_pos c k + 1
∧ ktc_pos c k ≤ ktc_pos c' k + 1"
proof -
from step obtain q ts n q' a dr where
c_eq: "c = KConfig q ts n"
and c'_eq: "c' = KConfig q'
(λk. (ts k)(n k := a k))
(λk. go_move (dr k) (n k))"
by (auto elim: ktm_step.cases)
have pos: "ktc_pos c k = n k" by (simp add: c_eq)
have pos': "ktc_pos c' k = go_move (dr k) (n k)" by (simp add: c'_eq)
show ?thesis
unfolding pos pos' by (cases "dr k") auto
qed
text ‹‹n›-step lift: after ‹n› steps, head displacement on each
tape is at most ‹n›.›
lemma ktm_relpow_pos_displacement:
assumes "(c, c') ∈ ktm_step δ ^^ n"
shows "ktc_pos c' k ≤ ktc_pos c k + n
∧ ktc_pos c k ≤ ktc_pos c' k + n"
using assms
proof (induction n arbitrary: c')
case 0
thus ?case by simp
next
case (Suc n)
from Suc.prems obtain c'' where
ih: "(c, c'') ∈ ktm_step δ ^^ n"
and step: "(c'', c') ∈ ktm_step δ"
by (auto elim: relpow_Suc_E)
have h1: "ktc_pos c'' k ≤ ktc_pos c k + n
∧ ktc_pos c k ≤ ktc_pos c'' k + n"
using Suc.IH[OF ih] .
have h2: "ktc_pos c' k ≤ ktc_pos c'' k + 1
∧ ktc_pos c'' k ≤ ktc_pos c' k + 1"
using ktm_step_pos_displacement[OF step] .
from h1 h2 show ?case by linarith
qed
text ‹‹n›-step lift: cells more than ‹n› away from the start head
position are unchanged after ‹n› steps.›
lemma ktm_relpow_tape_off_window:
assumes "(c, c') ∈ ktm_step δ ^^ n"
and "p > ktc_pos c k + n ∨ p + n < ktc_pos c k"
shows "ktc_tape c' k p = ktc_tape c k p"
using assms
proof (induction n arbitrary: c')
case 0
thus ?case by simp
next
case (Suc n)
from Suc.prems(1) obtain c'' where
ih: "(c, c'') ∈ ktm_step δ ^^ n"
and step: "(c'', c') ∈ ktm_step δ"
by (auto elim: relpow_Suc_E)
have far: "p > ktc_pos c k + n ∨ p + n < ktc_pos c k"
using Suc.prems(2) by linarith
have eq_ih: "ktc_tape c'' k p = ktc_tape c k p"
using Suc.IH[OF ih far] .
have disp: "ktc_pos c'' k ≤ ktc_pos c k + n
∧ ktc_pos c k ≤ ktc_pos c'' k + n"
using ktm_relpow_pos_displacement[OF ih] .
have ne: "p ≠ ktc_pos c'' k"
using Suc.prems(2) disp by linarith
have eq_step: "ktc_tape c' k p = ktc_tape c'' k p"
using ktm_step_tape_off_head[OF step ne] .
show ?case using eq_step eq_ih by simp
qed
subsection ‹The left endmarker stays at cell 0›
text ‹Local LE-pinning: any step of a valid M from a config whose
tape ‹k› already has ‹le_ktm M› at position 0 ends with a config
whose tape ‹k› still has ‹le_ktm M› at position 0. Standalone
variant of ‹valid_step_ktm›'s position-0-= LE conjunct,
stripped of the ‹valid_config_ktm› precondition: only the
per-tape LE-at-0 fact is needed (not Q-membership or ‹Γ›-typing).
Case-split on whether the head is at position 0: at-head fires
‹δLE› (read LE forces write LE); off-head uses
‹ktm_step_tape_off_head› directly.›
lemma ktm_step_LE_pos0_preserve:
fixes M :: "('q, 'a) ktm"
assumes vM: "valid_ktm M"
and step: "(c, c') ∈ ktm_step (delta_ktm M)"
and LE_at0: "ktc_tape c k 0 = le_ktm M"
shows "ktc_tape c' k 0 = le_ktm M"
proof (cases "ktc_pos c k = 0")
case True
from step obtain q ts n q' a dr where
c_eq: "c = KConfig q ts n"
and c'_eq: "c' = KConfig q'
(λkk. (ts kk)(n kk := a kk))
(λkk. go_move (dr kk) (n kk))"
and tr: "(q, λkk. ts kk (n kk), q', a, dr) ∈ delta_ktm M"
by (auto elim: ktm_step.cases)
have nk_0: "n k = 0" using True c_eq by simp
have ts_k_0_le: "ts k 0 = le_ktm M" using LE_at0 c_eq by simp
have read_LE: "(λkk. ts kk (n kk)) k = le_ktm M"
using ts_k_0_le nk_0 by simp
have write_LE: "a k = le_ktm M"
using valid_ktm_deltaLE[OF vM tr read_LE] by simp
have "ktc_tape c' k 0 = ((ts k)(n k := a k)) 0"
using c'_eq by simp
also have "… = a k" using nk_0 by simp
also have "… = le_ktm M" using write_LE .
finally show ?thesis .
next
case False
have ne_0: "(0 :: nat) ≠ ktc_pos c k" using False by simp
have unchanged: "ktc_tape c' k 0 = ktc_tape c k 0"
using ktm_step_tape_off_head[OF step ne_0] .
show ?thesis using unchanged LE_at0 by simp
qed
text ‹‹n›-step lift of @{thm[source] ktm_step_LE_pos0_preserve}: along
any chain of M-steps, ‹le_ktm M› at position 0 is preserved
on every tape. Used in AE's LE-edge forward stage to derive
‹cM_k›'s position-0 = LE without recourse to reachability
from init.›
lemma ktm_relpow_LE_pos0_preserve:
fixes M :: "('q, 'a) ktm"
assumes vM: "valid_ktm M"
and chain: "(c, c') ∈ ktm_step (delta_ktm M) ^^ n"
and LE_at0: "ktc_tape c k 0 = le_ktm M"
shows "ktc_tape c' k 0 = le_ktm M"
using relpow_imp_rtrancl [OF chain]
by (induction rule: rtrancl_induct)
(auto intro: LE_at0 ktm_step_LE_pos0_preserve [OF vM])
subsection ‹Decomposing a step›
text ‹Packages ‹ktm_step.cases› with the post-state position +
tape equations on each tape: a single ‹obtains› rule that
yields all four useful facts (pre-state's state, post-state's
state, the per-tape position equation ‹go_move (dr k) (n k)›,
and the per-tape head-cell update). Chain proofs in
AE / AR / TR avoid re-doing the case-analysis at every
per-substep position-trajectory step.›
lemma ktm_step_obtain_action:
assumes step: "(c, c') ∈ ktm_step δ"
obtains q q' a dr where
"ktc_state c = q"
and "ktc_state c' = q'"
and "(q, λk. ktc_tape c k (ktc_pos c k), q', a, dr) ∈ δ"
and "⋀kk. ktc_pos c' kk = go_move (dr kk) (ktc_pos c kk)"
and "⋀kk p. p ≠ ktc_pos c kk
⟹ ktc_tape c' kk p = ktc_tape c kk p"
and "⋀kk. ktc_tape c' kk (ktc_pos c kk) = a kk"
proof -
from step obtain q ts n q' a dr where
c_eq: "c = KConfig q ts n"
and c'_eq: "c' = KConfig q'
(λk. (ts k)(n k := a k))
(λk. go_move (dr k) (n k))"
and tr: "(q, λk. ts k (n k), q', a, dr) ∈ δ"
by (auto elim: ktm_step.cases)
have st_c: "ktc_state c = q" using c_eq by simp
have st_c': "ktc_state c' = q'" using c'_eq by simp
have pos_c: "⋀kk. ktc_pos c kk = n kk" using c_eq by simp
have pos_c': "⋀kk. ktc_pos c' kk = go_move (dr kk) (n kk)"
using c'_eq by simp
have tape_c: "⋀kk. ktc_tape c kk = ts kk" using c_eq by simp
have tape_c': "⋀kk. ktc_tape c' kk = (ts kk)(n kk := a kk)"
using c'_eq by simp
have tr': "(q, λk. ktc_tape c k (ktc_pos c k), q', a, dr) ∈ δ"
using tr c_eq by simp
show thesis
proof (rule that[OF st_c st_c' tr'])
fix kk show "ktc_pos c' kk = go_move (dr kk) (ktc_pos c kk)"
using pos_c' pos_c by simp
next
fix kk p assume "p ≠ ktc_pos c kk"
thus "ktc_tape c' kk p = ktc_tape c kk p"
using tape_c' tape_c pos_c by simp
next
fix kk show "ktc_tape c' kk (ktc_pos c kk) = a kk"
using tape_c' pos_c by simp
qed
qed
subsection ‹Transitions that write nothing›
text ‹For a transition relation in which every tuple's
read-component equals its write-component, a single step
preserves the entire tape function (the substrate update
‹f(x := f x)› is the identity). Used by the alphabet-
enlargement chain proof for the read-only buffer-loading
substeps SS1‹→›SS2, SS2‹→›SS3, SS3‹→›SS4, SS4‹→›SS5.›
lemma ktm_step_no_write_tape:
assumes step: "(c, c') ∈ ktm_step δ"
and no_write: "⋀q a q' a' d. (q, a, q', a', d) ∈ δ ⟹ a' = a"
shows "ktc_tape c' = ktc_tape c"
proof -
from step obtain q ts n q' a dr where
c_eq: "c = KConfig q ts n"
and c'_eq: "c' = KConfig q'
(λk. (ts k)(n k := a k))
(λk. go_move (dr k) (n k))"
and tr: "(q, λk. ts k (n k), q', a, dr) ∈ δ"
by (auto elim: ktm_step.cases)
from no_write[OF tr] have "a = (λk. ts k (n k))" by simp
hence "(λk. (ts k)(n k := a k)) = ts" by auto
thus ?thesis by (simp add: c_eq c'_eq)
qed
subsection ‹Read-only steps and head walks›
text ‹The introduction direction of the same fact. A tuple that writes back
what it read leaves the tape function as it was, so its step is determined by
the state change and the moves alone. Repeated in one state with one move
vector, it is a ∗‹walk›: the commonest subroutine of a multi-pass machine,
which returns a head to its origin, skips a field, or seeks a marker.›
lemma ktm_step_read_only:
assumes "(q, λi. ts i (pos i), q', λi. ts i (pos i), mv) ∈ δ"
shows "(KConfig q ts pos, KConfig q' ts (λi. go_move (mv i) (pos i)))
∈ ktm_step δ"
proof -
have "(KConfig q ts pos,
KConfig q' (λi. (ts i)(pos i := ts i (pos i)))
(λi. go_move (mv i) (pos i))) ∈ ktm_step δ"
by (rule ktm_step.step) (rule assms)
then show ?thesis by simp
qed
text ‹The walk in its general form: the head positions after ‹m› steps are
‹pos m›, and every head moves by ‹mv› at every step. Several heads may
move at once, in different directions.›
lemma ktm_read_only_run:
assumes tr: "⋀m. m < n ⟹
(q, λi. ts i (pos m i), q, λi. ts i (pos m i), mv) ∈ δ"
and mv: "⋀m. m < n ⟹ pos (Suc m) = (λi. go_move (mv i) (pos m i))"
shows "(KConfig q ts (pos 0), KConfig q ts (pos n)) ∈ ktm_step δ ^^ n"
using tr mv
proof (induction n)
case 0
show ?case by simp
next
case (Suc n)
have run: "(KConfig q ts (pos 0), KConfig q ts (pos n)) ∈ ktm_step δ ^^ n"
by (rule Suc.IH) (simp_all add: Suc.prems)
have "(KConfig q ts (pos n), KConfig q ts (λi. go_move (mv i) (pos n i)))
∈ ktm_step δ"
by (rule ktm_step_read_only) (simp add: Suc.prems)
then have "(KConfig q ts (pos n), KConfig q ts (pos (Suc n))) ∈ ktm_step δ"
by (simp add: Suc.prems)
with run show ?case by (rule relpow_Suc_I)
qed
text ‹The usual case moves one head.›
definition move_one :: "nat ⇒ move ⇒ (nat ⇒ move)" where
"move_one tp d = (λj. if j = tp then d else MoveN)"
lemma move_one_same [simp]: "move_one tp d tp = d"
by (simp add: move_one_def)
lemma move_one_other [simp]: "j ≠ tp ⟹ move_one tp d j = MoveN"
by (simp add: move_one_def)
text ‹Two heads moving, possibly in different directions. The first tape
wins where the two coincide.›
definition move_pair :: "nat ⇒ move ⇒ nat ⇒ move ⇒ (nat ⇒ move)" where
"move_pair tp1 d1 tp2 d2 =
(λj. if j = tp1 then d1 else if j = tp2 then d2 else MoveN)"
lemma move_pair_fst [simp]: "move_pair tp1 d1 tp2 d2 tp1 = d1"
by (simp add: move_pair_def)
lemma move_pair_snd [simp]:
"tp2 ≠ tp1 ⟹ move_pair tp1 d1 tp2 d2 tp2 = d2"
by (simp add: move_pair_def)
lemma move_pair_other [simp]:
"j ≠ tp1 ⟹ j ≠ tp2 ⟹ move_pair tp1 d1 tp2 d2 j = MoveN"
by (simp add: move_pair_def)
text ‹On machines over \<^typ>‹nat› symbols with blank ‹0›, the read vector of
a one-tape arc: tape ‹0› reads ‹x›, and every other index reads the blank.›
definition one_tape_read :: "nat ⇒ nat ⇒ nat" where
"one_tape_read x = (λj. if j = 0 then x else 0)"
lemma one_tape_read_inj: "one_tape_read x = one_tape_read y ⟹ x = y"
by (drule fun_cong [of _ _ 0]) (simp add: one_tape_read_def)
text ‹A one-head walk, leftwards from cell ‹P + n› to cell ‹P› and rightwards
from ‹P› to ‹P + n›. The hypothesis names each cell the head reads, so a
caller states it as a property of a stretch of tape (``every cell here holds
an input symbol''). A walk that stops on a cell it recognises adds one exit
step, ‹ktm_step_read_only› again but into another state.›
lemma ktm_walk_left:
assumes tr: "⋀m. P < m ⟹ m ≤ P + n ⟹
(q, λi. ts i ((pos(tp := m)) i), q, λi. ts i ((pos(tp := m)) i),
move_one tp MoveL) ∈ δ"
shows "(KConfig q ts (pos(tp := P + n)), KConfig q ts (pos(tp := P)))
∈ ktm_step δ ^^ n"
proof -
have "(KConfig q ts (pos(tp := P + n - 0)), KConfig q ts (pos(tp := P + n - n)))
∈ ktm_step δ ^^ n"
proof (rule ktm_read_only_run [where pos = "λm. pos(tp := P + n - m)"
and mv = "move_one tp MoveL"])
fix m assume "m < n"
then show "(q, λi. ts i ((pos(tp := P + n - m)) i), q,
λi. ts i ((pos(tp := P + n - m)) i), move_one tp MoveL) ∈ δ"
using tr [of "P + n - m"] by simp
next
fix m assume "m < n"
then show "pos(tp := P + n - Suc m)
= (λi. go_move (move_one tp MoveL i) ((pos(tp := P + n - m)) i))"
by (simp add: fun_eq_iff move_one_def)
qed
then show ?thesis by simp
qed
lemma ktm_walk_right:
assumes tr: "⋀m. P ≤ m ⟹ m < P + n ⟹
(q, λi. ts i ((pos(tp := m)) i), q, λi. ts i ((pos(tp := m)) i),
move_one tp MoveR) ∈ δ"
shows "(KConfig q ts (pos(tp := P)), KConfig q ts (pos(tp := P + n)))
∈ ktm_step δ ^^ n"
proof -
have "(KConfig q ts (pos(tp := P + 0)), KConfig q ts (pos(tp := P + n)))
∈ ktm_step δ ^^ n"
proof (rule ktm_read_only_run [where pos = "λm. pos(tp := P + m)"
and mv = "move_one tp MoveR"])
fix m assume "m < n"
then show "(q, λi. ts i ((pos(tp := P + m)) i), q,
λi. ts i ((pos(tp := P + m)) i), move_one tp MoveR) ∈ δ"
using tr [of "P + m"] by simp
next
fix m assume "m < n"
then show "pos(tp := P + Suc m)
= (λi. go_move (move_one tp MoveR i) ((pos(tp := P + m)) i))"
by (simp add: fun_eq_iff move_one_def)
qed
then show ?thesis by simp
qed
subsection ‹What a composite needs from the step relation›
text ‹Facts about \<^const>‹ktm_step› that belong to the substrate rather
than to any construction.
❙‹The union laws are what make a turn-taking composite cheap.›
\<^const>‹ktm_step› is defined by a single introduction rule whose only premise
is that one tuple lies in ‹δ›, and nothing in the rule quantifies over ‹δ›
--- so the step relation of a union is the union of the step relations, on
the nose. A composite whose transition relation is a union of arms therefore
splits a step into "which arm took it" by rewriting, and each arm can then be
analysed on its own. There is no corresponding law for a ∗‹lockstep›
product, whose transition relation is a join of the two factors' sets rather
than a union; that asymmetry, not the running time, is why a clocked
composite takes turns.
‹ktm_step_state_rel› is the state-side counterpart of the tape-side
‹ktm_step_frozen_tape› (‹Multitape_Run_Facts›), and is much the weaker statement of the two:
the state is carried through a step untouched, so any relation holding
between the two ends of every tuple holds across the step. It is general in
‹R› because the composite needs two instances of it --- one frozen component
(the factor that is not moving keeps its state) and one that changes (the
turn flips). The tape lemma cannot be stated this way, because there the
tuple's read component has to be matched against what is actually under the
head.›
lemma ktm_step_mono:
assumes "δ⇩1 ⊆ δ⇩2"
shows "ktm_step δ⇩1 ⊆ ktm_step δ⇩2"
using assms by (auto elim!: ktm_step.cases intro: ktm_step.step)
lemma ktm_step_Un:
"ktm_step (δ⇩1 ∪ δ⇩2) = ktm_step δ⇩1 ∪ ktm_step δ⇩2"
by (auto elim!: ktm_step.cases intro: ktm_step.step)
lemma ktm_step_UN:
"ktm_step (⋃i∈I. δ i) = (⋃i∈I. ktm_step (δ i))"
by (auto elim!: ktm_step.cases intro: ktm_step.step)
text ‹‹ktm_step_mono› needs only the tuples the step can use, and those
are the ones out of the configuration's state. So a step of a union whose
source state is known lies in the part of the union that state can fire:
the routing fact for the tuples, ‹sub›, lifts to the step relation
without the client taking the step apart.
❙‹Apply it by ⬚‹rule›, not ⬚‹OF›.› Given the routing fact
by ⬚‹OF›, ‹P q› is matched against a condition on a ∗‹schematic›
source state, which is not a pattern, and ⬚‹OF› reports multiple
unifiers. Closing ‹sub› by ⬚‹erule› with the routing fact binds that
state to ‹q› first, after which ‹P› is fixed by pattern unification and
the state hypothesis closes the last goal.›
lemma ktm_step_restrict_src:
assumes step: "(C, C') ∈ ktm_step δ"
and sub: "⋀q a q' a' d. (q, a, q', a', d) ∈ δ ⟹ P q
⟹ (q, a, q', a', d) ∈ δ'"
and src: "P (ktc_state C)"
shows "(C, C') ∈ ktm_step δ'"
proof -
from step obtain q ts n q' a d where
C: "C = KConfig q ts n"
and C': "C' = KConfig q' (λk. (ts k)(n k := a k)) (λk. go_move (d k) (n k))"
and t: "(q, λk. ts k (n k), q', a, d) ∈ δ"
by (auto elim: ktm_step.cases)
from src C have "P q" by simp
with t have "(q, λk. ts k (n k), q', a, d) ∈ δ'" by (rule sub)
then show ?thesis
unfolding C C' by (rule ktm_step.step [where ts = ts and n = n])
qed
text ‹The run-level form of ‹ktm_step_mono›: a run of
one arm of a composite is a run of the composite.›
lemma ktm_run_mono:
assumes sub: "δ⇩1 ⊆ δ⇩2"
and run: "(c, c') ∈ (ktm_step δ⇩1) ^^ n"
shows "(c, c') ∈ (ktm_step δ⇩2) ^^ n"
using relpow_subset_mono [OF ktm_step_mono [OF sub]] run ..
text ‹Both ends of a step as one tuple, and nothing else. ‹ktm_step.cases›
exposes the whole anatomy --- tape frame, read, write, directions --- and a
∗‹routing› argument wants none of it: which part of a union a step came from
is settled by the source state alone. This is the projection that says so.
❙‹The read component stays existential.› It is determined ---
it is \<^term>‹λk. ktc_tape C k (ktc_pos C k)› --- but naming it would put the
tape frame back into every consumer, which is the thing being avoided. A
consumer that needs the read still has ‹ktm_step.cases›.›
lemma ktm_step_states:
assumes step: "(C, C') ∈ ktm_step δ"
obtains a a' d where "(ktc_state C, a, ktc_state C', a', d) ∈ δ"
proof -
from step obtain q ts n q' a dr where
c_eq: "C = KConfig q ts n"
and c'_eq: "C' = KConfig q'
(λk. (ts k)(n k := a k))
(λk. go_move (dr k) (n k))"
and tr: "(q, λk. ts k (n k), q', a, dr) ∈ δ"
by (auto elim: ktm_step.cases)
have "(ktc_state C, λk. ts k (n k), ktc_state C', a, dr) ∈ δ"
using tr by (simp add: c_eq c'_eq)
then show thesis by (rule that)
qed
lemma ktm_step_state_rel:
assumes step: "(c, c') ∈ ktm_step δ"
and rel: "∀q a q' a' d. (q, a, q', a', d) ∈ δ ⟶ R q q'"
shows "R (ktc_state c) (ktc_state c')"
proof -
from step obtain a a' d where "(ktc_state c, a, ktc_state c', a', d) ∈ δ"
by (rule ktm_step_states)
with rel show ?thesis by blast
qed
text ‹❙‹The halting states are dead ends, so a configuration that can still
move is not in one.› \<^const>‹valid_ktm› restricts ‹δ›'s source component to
\<^term>‹Q_ktm M - {t_ktm M, r_ktm M}›, which is usually read as a well-formedness
condition and is also a ∗‹tool›: it converts "there is a next step" into
"the state is neither halting state" (‹ktm_step_src›), and that is the only
way to learn anything about the ∗‹intermediate› configurations of a run
whose endpoints are all that is stated.
The run form below is the one a race wants. A run of ‹n› steps that ends
accepting says nothing directly about step ‹k < n›; but the remainder is
non-empty, so a step leaves that configuration, so it has not halted. This
is what lets a caller with only "the machine halts in exactly ‹g n›
steps" conclude that it is ∗‹still running› at any earlier time.›
lemma ktm_relpow_not_halted:
assumes vM: "valid_ktm M"
and run: "(C, C') ∈ (ktm_step (delta_ktm M)) ^^ n" and k: "k < n"
obtains D
where "(C, D) ∈ (ktm_step (delta_ktm M)) ^^ k"
and "ktc_state D ≠ t_ktm M" and "ktc_state D ≠ r_ktm M"
proof -
obtain c where n: "n = k + Suc c"
proof -
from k have "n = k + Suc (n - Suc k)" by simp
then show thesis by (rule that)
qed
from run [unfolded n relpow_add] obtain D
where CD: "(C, D) ∈ (ktm_step (delta_ktm M)) ^^ k"
and rest: "(D, C') ∈ (ktm_step (delta_ktm M)) ^^ Suc c" by auto
obtain E where "(D, E) ∈ ktm_step (delta_ktm M)"
using relpow_Suc_D2 [OF rest] by blast
from CD ktm_step_src_neq_t [OF vM this] ktm_step_src_neq_r [OF vM this]
show thesis by (rule that)
qed
text ‹Single-valuedness, transported from the tuples to the configurations.
\<^const>‹det_ktm› is stated of a whole machine, but a composite is
deterministic only in ∗‹parts› --- its setup phase is forced while its arms
are not --- so the useful form is generic in ‹δ› and the machine-level
reading is the corollary. A typical use is a converse walk: it peels a
step, instantiates a forward lemma about the same configuration, and pins
the two together, so the transformed tape content is never inverted.
The read component is what carries the argument. Two steps out of one
configuration read the same frame \<^term>‹λk. ts k (n k)›, so the tuple
hypothesis applies at a common ‹a› and the write and the direction come
back equal --- whereupon the two successors are equal as functions of the
∗‹same› ‹ts› and ‹n›.
The hypothesis is asked for ∗‹at the state the configuration is in›, not at
every state, because a phase-wise deterministic composite is exactly the case
this is for: the argument never leaves \<^term>‹ktc_state C›, so demanding more
would be demanding what the consumer cannot supply. The uniform reading is
‹ktm_step_functional› below, and ‹det_ktm_step› states it for a
deterministic machine.›
lemma ktm_step_det_at:
assumes det: "⋀a p⇩1 b⇩1 d⇩1 p⇩2 b⇩2 d⇩2.
(ktc_state C, a, p⇩1, b⇩1, d⇩1) ∈ δ
⟹ (ktc_state C, a, p⇩2, b⇩2, d⇩2) ∈ δ
⟹ (p⇩1, b⇩1, d⇩1) = (p⇩2, b⇩2, d⇩2)"
and s⇩1: "(C, C⇩1) ∈ ktm_step δ"
and s⇩2: "(C, C⇩2) ∈ ktm_step δ"
shows "C⇩1 = C⇩2"
proof -
from s⇩1 obtain q ts n q⇩1 a⇩1 d⇩1 where
C: "C = KConfig q ts n"
and C⇩1: "C⇩1 = KConfig q⇩1 (λk. (ts k)(n k := a⇩1 k))
(λk. go_move (d⇩1 k) (n k))"
and t⇩1: "(q, λk. ts k (n k), q⇩1, a⇩1, d⇩1) ∈ δ"
by (auto elim: ktm_step.cases)
from s⇩2 obtain q' ts' n' q⇩2 a⇩2 d⇩2 where
C': "C = KConfig q' ts' n'"
and C⇩2: "C⇩2 = KConfig q⇩2 (λk. (ts' k)(n' k := a⇩2 k))
(λk. go_move (d⇩2 k) (n' k))"
and t⇩2: "(q', λk. ts' k (n' k), q⇩2, a⇩2, d⇩2) ∈ δ"
by (auto elim: ktm_step.cases)
have "KConfig q ts n = KConfig q' ts' n'" using C C' by simp
then have qe: "q' = q" and te: "ts' = ts" and ne: "n' = n" by auto
from t⇩2 [unfolded qe te ne] have t⇩2': "(q, λk. ts k (n k), q⇩2, a⇩2, d⇩2) ∈ δ" .
from t⇩1 have u⇩1: "(ktc_state C, λk. ts k (n k), q⇩1, a⇩1, d⇩1) ∈ δ"
by (simp add: C)
from t⇩2' have u⇩2: "(ktc_state C, λk. ts k (n k), q⇩2, a⇩2, d⇩2) ∈ δ"
by (simp add: C)
have "(q⇩1, a⇩1, d⇩1) = (q⇩2, a⇩2, d⇩2)" by (rule det [OF u⇩1 u⇩2])
then show ?thesis by (simp add: C⇩1 C⇩2 te ne)
qed
lemma det_ktm_step:
assumes det: "det_ktm M"
and s⇩1: "(C, C⇩1) ∈ ktm_step (delta_ktm M)"
and s⇩2: "(C, C⇩2) ∈ ktm_step (delta_ktm M)"
shows "C⇩1 = C⇩2"
proof (rule ktm_step_det_at [OF _ s⇩1 s⇩2])
fix a p⇩1 b⇩1 d⇩1 p⇩2 b⇩2 d⇩2
assume "(ktc_state C, a, p⇩1, b⇩1, d⇩1) ∈ delta_ktm M"
and "(ktc_state C, a, p⇩2, b⇩2, d⇩2) ∈ delta_ktm M"
with det show "(p⇩1, b⇩1, d⇩1) = (p⇩2, b⇩2, d⇩2)" unfolding det_ktm_def by blast
qed
text ‹The same fact once more in the library's vocabulary, which is what
buys the run-level statement for nothing: ⬚‹single_valued_relpow› lifts
single-valuedness along ‹^^ n›, so a deterministic machine's runs of a
∗‹given› length are unique without an induction here. The step-level and
run-level readings are wanted in different places --- the step level pins a
converse walk, the run level pins an alarm --- so both names earn their
keep.›
lemma det_ktm_single_valued:
assumes det: "det_ktm M"
shows "single_valued (ktm_step (delta_ktm M))"
by (blast intro: single_valuedI det_ktm_step [OF det])
lemma det_ktm_relpow_unique:
assumes det: "det_ktm M"
and r⇩1: "(C, C⇩1) ∈ (ktm_step (delta_ktm M)) ^^ n"
and r⇩2: "(C, C⇩2) ∈ (ktm_step (delta_ktm M)) ^^ n"
shows "C⇩1 = C⇩2"
by (rule single_valuedD
[OF single_valued_relpow [OF det_ktm_single_valued [OF det]] r⇩1 r⇩2])
lemma det_ktm_dead_end_no_longer_run:
assumes det: "det_ktm M"
and stopped: "(initial, final) ∈ (ktm_step (delta_ktm M)) ^^ amount"
and dead_end: "∀following. (final, following) ∉ ktm_step (delta_ktm M)"
and longer_run: "(initial, other) ∈ (ktm_step (delta_ktm M)) ^^ longer"
and longer: "amount < longer"
shows False
proof -
have "amount = longer ∧ final = other"
by (rule relpow_halted_le [where R = UNIV and H = "{final}",
OF _ _ _ _ stopped _ longer_run])
(use dead_end longer det_ktm_step [OF det] in auto)
with longer show False by simp
qed
subsection ‹Step determinism and acceptance monotonicity›
text ‹Two general facts promoted from the finite-control layer: a step of
a functional transition relation is deterministic (a configuration has at
most one successor), which is ‹ktm_step_det_at› with the hypothesis asked
at every state, and weak time-bounded acceptance is monotone in the time
budget.›
lemma ktm_step_functional:
assumes fdet: "∀q a p⇩1 b⇩1 d⇩1 p⇩2 b⇩2 d⇩2.
(q, a, p⇩1, b⇩1, d⇩1) ∈ δ ⟶ (q, a, p⇩2, b⇩2, d⇩2) ∈ δ
⟶ (p⇩1, b⇩1, d⇩1) = (p⇩2, b⇩2, d⇩2)"
and step1: "(c, c1) ∈ ktm_step δ"
and step2: "(c, c2) ∈ ktm_step δ"
shows "c1 = c2"
using fdet by (blast intro: ktm_step_det_at [OF _ step1 step2])
text ‹Weak time-bounded acceptance is monotone in the time budget.›
lemma accepts_in_time_ktm_mono:
"accepts_in_time_ktm M w t ⟹ t ≤ t' ⟹ accepts_in_time_ktm M w t'"
unfolding accepts_in_time_ktm_def by (meson order_trans)
subsection ‹Reaching a given state within a time bound›
text ‹Bounded acceptance names the accept state. A simulation argument
usually never uses which halting state a run ends in, and a client that
bounds rejection as well as acceptance needs the same statement for the
reject state; so the bound is stated once for an arbitrary state, and
acceptance is its instance at @{term "t_ktm M"}.›
definition reaches_state_in_time_ktm ::
"('q, 'a) ktm ⇒ 'a list ⇒ 'q ⇒ nat ⇒ bool" where
"reaches_state_in_time_ktm M w q T ⟷
(∃n c. n ≤ T
∧ (init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n
∧ ktc_state c = q)"
lemma reaches_state_in_time_ktmI:
assumes "n ≤ T"
and "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n"
and "ktc_state c = q"
shows "reaches_state_in_time_ktm M w q T"
using assms unfolding reaches_state_in_time_ktm_def by blast
lemma reaches_state_in_time_ktmE:
assumes "reaches_state_in_time_ktm M w q T"
obtains n c where "n ≤ T"
and "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n"
and "ktc_state c = q"
using assms unfolding reaches_state_in_time_ktm_def by blast
lemma reaches_state_in_time_ktm_mono:
assumes "reaches_state_in_time_ktm M w q T" and "T ≤ T'"
shows "reaches_state_in_time_ktm M w q T'"
proof -
from assms(1) obtain n c where n: "n ≤ T"
and run: "(init_config_ktm M w, c) ∈ (ktm_step (delta_ktm M)) ^^ n"
and state: "ktc_state c = q"
by (rule reaches_state_in_time_ktmE)
from order_trans [OF n assms(2)] run state show ?thesis
by (rule reaches_state_in_time_ktmI)
qed
lemma accepts_in_time_ktm_iff_reaches:
"accepts_in_time_ktm M w T
⟷ reaches_state_in_time_ktm M w (t_ktm M) T"
unfolding accepts_in_time_ktm_def reaches_state_in_time_ktm_def by blast
end