Theory Multitape_One_Tape_Clocks
theory Multitape_One_Tape_Clocks
imports Multitape_Clock_Interface
begin
section ‹Two one-tape clocks›
text ‹The unary walk and marking sweep supply exact linear and quadratic
clocks for the nondeterministic and deterministic hierarchy instances.
This theory builds them as plain one-tape machines over the symbols blank ‹0›, endmarker ‹1›, mark ‹2›
and input ‹3›, and proves their exact step counts on \<^term>‹unary_word n›.›
subsection ‹One-tape machines›
text ‹A transition reads and writes a whole vector of symbols, one per
tape index, and every index at or above the tape count must read and write
the blank and stay put. So a one-tape arc is determined by its state
change, the symbol it reads, the symbol it writes, and one direction:
\<^const>‹one_tape_read› and \<^const>‹move_one› at tape ‹0›.›
definition one_tape_arc :: "nat ⇒ nat ⇒ nat ⇒ nat ⇒ move
⇒ nat × (nat ⇒ nat) × nat × (nat ⇒ nat) × (nat ⇒ move)" where
"one_tape_arc q x q' y d = (q, one_tape_read x, q', one_tape_read y, move_one 0 d)"
text ‹States ‹0› to ‹4›, start ‹0›, accept ‹1›, reject ‹2›; input
symbol ‹3› alone.›
definition one_tape ::
"(nat × (nat ⇒ nat) × nat × (nat ⇒ nat) × (nat ⇒ move)) set ⇒ (nat, nat) ktm" where
"one_tape D = KTM {0..4} {3} {0..3} 0 1 D 0 1 2 1"
lemma one_tape_fields [simp]:
"k_ktm (one_tape D) = 1" "delta_ktm (one_tape D) = D"
"s_ktm (one_tape D) = 0" "t_ktm (one_tape D) = 1" "r_ktm (one_tape D) = 2"
"bl_ktm (one_tape D) = 0" "le_ktm (one_tape D) = 1"
"Sigma_ktm (one_tape D) = {3 :: nat}" "Γ_ktm (one_tape D) = {0 .. 3 :: nat}"
"Q_ktm (one_tape D) = {0 .. 4 :: nat}"
by (simp_all add: one_tape_def)
text ‹The configurations such a machine passes through: tape ‹0› holds ‹u›
with its head at ‹p›, and every other tape is blank with its head at the
origin.›
definition one_tape_config :: "nat ⇒ (nat ⇒ nat) ⇒ nat ⇒ (nat, nat) ktc_config" where
"one_tape_config q u p = KConfig q (λj. if j = 0 then u else (λ_. 0)) (λj. if j = 0 then p else 0)"
lemma one_tape_config_state [simp]: "ktc_state (one_tape_config q u p) = q"
by (simp add: one_tape_config_def)
lemma one_tape_config_step:
assumes a: "one_tape_arc q x q' y d ∈ D" and x: "u p = x"
shows "(one_tape_config q u p, one_tape_config q' (u(p := y)) (go_move d p)) ∈ ktm_step D"
proof -
let ?ts = "λj. if j = 0 then u else (λ_. 0 :: nat)"
let ?ps = "λj. if j = 0 then p else (0 :: nat)"
have rd: "(λk. ?ts k (?ps k)) = one_tape_read x" using x by (auto simp: one_tape_read_def)
have "(q, (λk. ?ts k (?ps k)), q', one_tape_read y, move_one 0 d) ∈ D"
using a unfolding rd by (simp add: one_tape_arc_def)
from ktm_step.step [where ts = ?ts and n = ?ps, OF this]
have "(KConfig q ?ts ?ps,
KConfig q' (λk. (?ts k)(?ps k := one_tape_read y k)) (λk. go_move (move_one 0 d k) (?ps k)))
∈ ktm_step D" .
moreover have "(λk. (?ts k)(?ps k := one_tape_read y k))
= (λj. if j = 0 then u(p := y) else (λ_. 0))"
by (auto simp: fun_eq_iff one_tape_read_def)
moreover have "(λk. go_move (move_one 0 d k) (?ps k)) = (λj. if j = 0 then go_move d p else 0)"
by (auto simp: fun_eq_iff move_one_def)
ultimately show ?thesis by (simp add: one_tape_config_def)
qed
text ‹The input as tape ‹0› sees it.›
definition one_tape_input :: "nat ⇒ nat ⇒ nat" where
"one_tape_input n = (λm. if m = 0 then 1 else if m ≤ n then 3 else 0)"
lemma one_tape_init: "init_config_ktm (one_tape D) (unary_word n) = one_tape_config 0 (one_tape_input n) 0"
by (auto simp: one_tape_def one_tape_config_def one_tape_input_def unary_word_def fun_eq_iff)
text ‹Walks: a state that loops on every symbol it meets, moving one way.›
lemma one_tape_run_right:
assumes a: "⋀i. i < m ⟹ one_tape_arc q (u (p + i)) q (u (p + i)) MoveR ∈ D"
shows "(one_tape_config q u p, one_tape_config q u (p + m)) ∈ ktm_step D ^^ m"
using a
proof (induction m)
case 0
then show ?case by simp
next
case (Suc m)
then have ih: "(one_tape_config q u p, one_tape_config q u (p + m)) ∈ ktm_step D ^^ m" by simp
have "(one_tape_config q u (p + m), one_tape_config q (u(p + m := u (p + m))) (go_move MoveR (p + m)))
∈ ktm_step D"
by (rule one_tape_config_step [OF Suc.prems]) simp_all
then have "(one_tape_config q u (p + m), one_tape_config q u (p + Suc m)) ∈ ktm_step D" by simp
with ih show ?case by (rule relpow_Suc_I)
qed
lemma one_tape_run_left:
assumes mp: "m ≤ p"
and a: "⋀i. i < m ⟹ one_tape_arc q (u (p - i)) q (u (p - i)) MoveL ∈ D"
shows "(one_tape_config q u p, one_tape_config q u (p - m)) ∈ ktm_step D ^^ m"
using mp a
proof (induction m)
case 0
then show ?case by simp
next
case (Suc m)
then have ih: "(one_tape_config q u p, one_tape_config q u (p - m)) ∈ ktm_step D ^^ m" by simp
have "(one_tape_config q u (p - m), one_tape_config q (u(p - m := u (p - m))) (go_move MoveL (p - m)))
∈ ktm_step D"
by (rule one_tape_config_step [OF Suc.prems(2)]) simp_all
moreover have "go_move MoveL (p - m) = p - Suc m" using Suc.prems(1) by simp
ultimately have "(one_tape_config q u (p - m), one_tape_config q u (p - Suc m)) ∈ ktm_step D" by simp
with ih show ?case by (rule relpow_Suc_I)
qed
subsection ‹Structure›
text ‹What an arc must satisfy for the machine to be well formed: it leaves
neither halting state, stays within the five states and four symbols, keeps
the endmarker where it is and steps off it only rightwards, and writes the
endmarker nowhere else.›
definition one_tape_arc_ok :: "nat ⇒ nat ⇒ nat ⇒ nat ⇒ move ⇒ bool" where
"one_tape_arc_ok q x q' y d ⟷ q ∈ {0, 3, 4} ∧ q' ≤ 4 ∧ x ≤ 3 ∧ y ≤ 3
∧ (x = 1 ⟶ y = 1 ∧ d ≠ MoveL) ∧ (y = 1 ⟶ x = 1)"
lemma one_tape_arc_eq [simp]:
"one_tape_arc q x q' y d = one_tape_arc q2 x2 q2' y2 d2 ⟷ q = q2 ∧ x = x2 ∧ q' = q2' ∧ y = y2 ∧ d = d2"
proof
assume e: "one_tape_arc q x q' y d = one_tape_arc q2 x2 q2' y2 d2"
then have "one_tape_read x = one_tape_read x2" "one_tape_read y = one_tape_read y2" "move_one 0 d = move_one 0 d2" "q = q2" "q' = q2'"
by (simp_all add: one_tape_arc_def)
moreover have "d = d2" using fun_cong [OF ‹move_one 0 d = move_one 0 d2›, of 0] by (simp add: move_one_def)
ultimately show "q = q2 ∧ x = x2 ∧ q' = q2' ∧ y = y2 ∧ d = d2"
by (auto dest: one_tape_read_inj)
qed simp
lemma one_tape_wf:
assumes arcs: "⋀e. e ∈ D ⟹ ∃q x q' y d. e = one_tape_arc q x q' y d ∧ one_tape_arc_ok q x q' y d"
shows "well_formed_ktm (one_tape D)"
proof -
have sub: "D ⊆ ({0..4} - {1, 2}) × (UNIV → {0..3}) × {0..4}
× (UNIV → {0..3}) × (UNIV → UNIV)"
proof
fix e assume "e ∈ D"
then obtain q x q' y d where e: "e = one_tape_arc q x q' y d" and ok: "one_tape_arc_ok q x q' y d"
using arcs by blast
show "e ∈ ({0..4} - {1, 2}) × (UNIV → {0..3}) × {0..4}
× (UNIV → {0..3}) × (UNIV → UNIV)"
using ok by (auto simp: e one_tape_arc_def one_tape_read_def one_tape_arc_ok_def)
qed
have le: "a' j = 1 ∧ dd j ∈ {MoveN, MoveR}"
if m: "(q, a, q', a', dd) ∈ D" and aj: "a j = 1" for q a q' a' dd j
proof -
obtain q0 x q0' y d where e: "(q, a, q', a', dd) = one_tape_arc q0 x q0' y d"
and ok: "one_tape_arc_ok q0 x q0' y d" using arcs [OF m] by blast
have aa: "a = one_tape_read x" "a' = one_tape_read y" "dd = move_one 0 d" using e by (simp_all add: one_tape_arc_def)
have j0: "j = 0" using aj aa(1) by (simp add: one_tape_read_def split: if_splits)
show ?thesis using ok aj aa j0 by (cases d) (auto simp: one_tape_arc_ok_def one_tape_read_def move_one_def)
qed
have hi: "a j = 0 ∧ a' j = 0 ∧ dd j = MoveN"
if m: "(q, a, q', a', dd) ∈ D" and j1: "1 ≤ j" for q a q' a' dd j
proof -
obtain q0 x q0' y d where e: "(q, a, q', a', dd) = one_tape_arc q0 x q0' y d"
using arcs [OF m] by blast
then show ?thesis using j1 by (simp add: one_tape_arc_def one_tape_read_def move_one_def)
qed
have lu: "a j = 1" if m: "(q, a, q', a', dd) ∈ D" and aj: "a' j = 1" for q a q' a' dd j
proof -
obtain q0 x q0' y d where e: "(q, a, q', a', dd) = one_tape_arc q0 x q0' y d"
and ok: "one_tape_arc_ok q0 x q0' y d" using arcs [OF m] by blast
have aa: "a = one_tape_read x" "a' = one_tape_read y" using e by (simp_all add: one_tape_arc_def)
show ?thesis using ok aj aa by (auto simp: one_tape_arc_ok_def one_tape_read_def split: if_splits)
qed
have "valid_ktm (one_tape D)"
unfolding one_tape_def valid_ktm.simps using sub le hi by auto
moreover have "le_unique (one_tape D)"
unfolding le_unique_def using lu by simp
ultimately show ?thesis by simp
qed
lemma one_tape_det:
assumes arcs: "⋀e. e ∈ D ⟹ ∃q x q' y d. e = one_tape_arc q x q' y d"
and key: "⋀q x q1 y1 d1 q2 y2 d2. one_tape_arc q x q1 y1 d1 ∈ D ⟹ one_tape_arc q x q2 y2 d2 ∈ D
⟹ (q1, y1, d1) = (q2, y2, d2)"
shows "det_ktm (one_tape D)"
unfolding det_ktm_def
proof (intro allI impI)
fix q a p1 b1 d1 p2 b2 d2
assume m1: "(q, a, p1, b1, d1) ∈ delta_ktm (one_tape D)"
and m2: "(q, a, p2, b2, d2) ∈ delta_ktm (one_tape D)"
obtain q0 x q1 y1 e1 where e1: "(q, a, p1, b1, d1) = one_tape_arc q0 x q1 y1 e1"
using arcs m1 by fastforce
obtain q0' x' q2 y2 e2 where e2: "(q, a, p2, b2, d2) = one_tape_arc q0' x' q2 y2 e2"
using arcs m2 by fastforce
have "q0 = q" "q0' = q" "a = one_tape_read x" "a = one_tape_read x'" using e1 e2 by (simp_all add: one_tape_arc_def)
then have xx: "x' = x" using one_tape_read_inj by metis
have "one_tape_arc q x q1 y1 e1 ∈ D" "one_tape_arc q x q2 y2 e2 ∈ D"
using m1 m2 e1 e2 ‹q0 = q› ‹q0' = q› xx by simp_all
from key [OF this] show "(p1, b1, d1) = (p2, b2, d2)"
using e1 e2 by (simp add: one_tape_arc_def)
qed
subsection ‹The walk: a clock for ‹n + 2››
text ‹One state: step off the endmarker, run over the input, and halt on
the blank above it.›
definition walk_delta where
"walk_delta = {one_tape_arc 0 1 0 1 MoveR, one_tape_arc 0 3 0 3 MoveR, one_tape_arc 0 0 1 0 MoveN}"
definition walk_clock :: "(nat, nat) ktm" where
"walk_clock = one_tape walk_delta"
lemma walk_clock_wf: "well_formed_ktm walk_clock"
unfolding walk_clock_def
by (rule one_tape_wf) (auto simp: walk_delta_def one_tape_arc_ok_def)
lemma walk_clock_det: "det_ktm walk_clock"
unfolding walk_clock_def
proof (rule one_tape_det)
show "∃q x q' y d. e = one_tape_arc q x q' y d" if "e ∈ walk_delta" for e
using that by (auto simp: walk_delta_def)
show "(q1, y1, d1) = (q2, y2, d2)"
if "one_tape_arc q x q1 y1 d1 ∈ walk_delta" "one_tape_arc q x q2 y2 d2 ∈ walk_delta"
for q x q1 y1 d1 q2 y2 d2
using that by (auto simp: walk_delta_def)
qed
lemma walk_run:
"(one_tape_config 0 (one_tape_input n) 0, one_tape_config 1 (one_tape_input n) (Suc n))
∈ ktm_step walk_delta ^^ (n + 2)"
proof -
let ?u = "one_tape_input n"
have s1: "(one_tape_config 0 ?u 0, one_tape_config 0 ?u 1) ∈ ktm_step walk_delta"
using one_tape_config_step [of 0 1 0 1 MoveR walk_delta ?u 0]
by (simp add: walk_delta_def one_tape_input_def fun_upd_idem)
have s2: "(one_tape_config 0 ?u 1, one_tape_config 0 ?u (1 + n)) ∈ ktm_step walk_delta ^^ n"
by (rule one_tape_run_right) (simp add: walk_delta_def one_tape_input_def)
have s3: "(one_tape_config 0 ?u (1 + n), one_tape_config 1 ?u (Suc n)) ∈ ktm_step walk_delta"
using one_tape_config_step [of 0 0 1 0 MoveN walk_delta ?u "1 + n"]
by (simp add: walk_delta_def one_tape_input_def fun_upd_idem)
from relpow_Suc_I [OF relpow_Suc_I2 [OF s1 s2] s3] show ?thesis by simp
qed
theorem time_constructible_walk: "time_constructible (λn. n + 2)"
proof -
have run: "∀n. ∃cfg. (init_config_ktm walk_clock (unary_word n), cfg)
∈ ktm_step (delta_ktm walk_clock) ^^ (n + 2)
∧ ktc_state cfg = t_ktm walk_clock"
proof (intro allI exI conjI)
fix n
show "(init_config_ktm walk_clock (unary_word n), one_tape_config 1 (one_tape_input n) (Suc n))
∈ ktm_step (delta_ktm walk_clock) ^^ (n + 2)"
unfolding walk_clock_def one_tape_init one_tape_fields(2) by (rule walk_run)
show "ktc_state (one_tape_config 1 (one_tape_input n) (Suc n)) = t_ktm walk_clock"
by (simp add: walk_clock_def)
qed
have sig: "3 ∈ Sigma_ktm walk_clock" by (simp add: walk_clock_def)
show ?thesis unfolding time_constructible_def
using walk_clock_wf walk_clock_det sig run by blast
qed
subsection ‹The sweep: a clock for ‹2 n⇧2 + 3 n + 2››
text ‹Each pass marks the first unmarked input cell, runs to the blank above
the input, and returns to the endmarker; the pass that finds no unmarked
cell halts. State ‹0› seeks, ‹3› runs right, ‹4› runs left. A pass
costs ‹2 n + 2› however many marks it finds, which is what makes the count
a polynomial rather than a sum.›
definition sweep_delta where
"sweep_delta =
{one_tape_arc 0 1 0 1 MoveR, one_tape_arc 0 2 0 2 MoveR, one_tape_arc 0 3 3 2 MoveR, one_tape_arc 0 0 1 0 MoveN,
one_tape_arc 3 2 3 2 MoveR, one_tape_arc 3 3 3 3 MoveR, one_tape_arc 3 0 4 0 MoveL,
one_tape_arc 4 2 4 2 MoveL, one_tape_arc 4 3 4 3 MoveL, one_tape_arc 4 1 0 1 MoveR}"
definition sweep_clock :: "(nat, nat) ktm" where
"sweep_clock = one_tape sweep_delta"
lemma sweep_clock_wf: "well_formed_ktm sweep_clock"
unfolding sweep_clock_def
by (rule one_tape_wf) (auto simp: sweep_delta_def one_tape_arc_ok_def)
lemma sweep_clock_det: "det_ktm sweep_clock"
unfolding sweep_clock_def
proof (rule one_tape_det)
show "∃q x q' y d. e = one_tape_arc q x q' y d" if "e ∈ sweep_delta" for e
using that by (auto simp: sweep_delta_def)
show "(q1, y1, d1) = (q2, y2, d2)"
if "one_tape_arc q x q1 y1 d1 ∈ sweep_delta" "one_tape_arc q x q2 y2 d2 ∈ sweep_delta"
for q x q1 y1 d1 q2 y2 d2
using that by (auto simp: sweep_delta_def)
qed
text ‹The tape after ‹k› passes.›
definition sweep_tape :: "nat ⇒ nat ⇒ nat ⇒ nat" where
"sweep_tape n k = (λm. if m = 0 then 1 else if m ≤ k then 2 else if m ≤ n then 3 else 0)"
lemma sweep_tape_0: "sweep_tape n 0 = one_tape_input n"
by (simp add: sweep_tape_def one_tape_input_def fun_eq_iff)
lemma sweep_pass:
assumes k: "k < n"
shows "(one_tape_config 0 (sweep_tape n k) 1, one_tape_config 0 (sweep_tape n (Suc k)) 1) ∈ ktm_step sweep_delta ^^ (2 * n + 2)"
proof -
let ?R = "ktm_step sweep_delta"
let ?u = "sweep_tape n k" and ?v = "sweep_tape n (Suc k)"
have r1: "(one_tape_config 0 ?u 1, one_tape_config 0 ?u (1 + k)) ∈ ?R ^^ k"
by (rule one_tape_run_right) (simp add: sweep_delta_def sweep_tape_def)
have vu: "?u(1 + k := 2) = ?v" using k by (auto simp: sweep_tape_def fun_eq_iff)
have s2': "(one_tape_config 0 ?u (1 + k), one_tape_config 3 (?u(1 + k := 2)) (2 + k)) ∈ ?R"
using one_tape_config_step [of 0 3 3 2 MoveR sweep_delta ?u "1 + k"] k
by (simp add: sweep_delta_def sweep_tape_def)
note s2 = s2' [unfolded vu]
have r3: "(one_tape_config 3 ?v (2 + k), one_tape_config 3 ?v (2 + k + (n - k - 1))) ∈ ?R ^^ (n - k - 1)"
by (rule one_tape_run_right) (use k in ‹auto simp: sweep_delta_def sweep_tape_def›)
have e3: "2 + k + (n - k - 1) = Suc n" using k by simp
have s4: "(one_tape_config 3 ?v (Suc n), one_tape_config 4 ?v n) ∈ ?R"
using one_tape_config_step [of 3 0 4 0 MoveL sweep_delta ?v "Suc n"] k
by (simp add: sweep_delta_def sweep_tape_def fun_upd_idem)
have r5: "(one_tape_config 4 ?v n, one_tape_config 4 ?v (n - n)) ∈ ?R ^^ n"
by (rule one_tape_run_left) (auto simp: sweep_delta_def sweep_tape_def)
have s6: "(one_tape_config 4 ?v 0, one_tape_config 0 ?v 1) ∈ ?R"
using one_tape_config_step [of 4 1 0 1 MoveR sweep_delta ?v 0]
by (simp add: sweep_delta_def sweep_tape_def fun_upd_idem)
have r5': "(one_tape_config 4 ?v n, one_tape_config 4 ?v 0) ∈ ?R ^^ n" using r5 by simp
from relpow_Suc_I [OF relpow_trans [OF r1 relpow_Suc_I2 [OF s2
relpow_trans [OF r3 [unfolded e3] relpow_Suc_I2 [OF s4 r5']]]] s6]
have "(one_tape_config 0 ?u 1, one_tape_config 0 ?v 1) ∈ ?R ^^ Suc (k + Suc (n - k - 1 + Suc n))" .
moreover have "Suc (k + Suc (n - k - 1 + Suc n)) = 2 * n + 2" using k by simp
ultimately show ?thesis by (simp only:)
qed
lemma sweep_passes:
"k ≤ n ⟹ (one_tape_config 0 (sweep_tape n 0) 1, one_tape_config 0 (sweep_tape n k) 1) ∈ ktm_step sweep_delta ^^ (k * (2 * n + 2))"
proof (induction k)
case 0
then show ?case by simp
next
case (Suc k)
then have "(one_tape_config 0 (sweep_tape n 0) 1, one_tape_config 0 (sweep_tape n k) 1) ∈ ktm_step sweep_delta ^^ (k * (2 * n + 2))"
by simp
from relpow_trans [OF this sweep_pass [of k n]] Suc.prems
have "(one_tape_config 0 (sweep_tape n 0) 1, one_tape_config 0 (sweep_tape n (Suc k)) 1)
∈ ktm_step sweep_delta ^^ (k * (2 * n + 2) + (2 * n + 2))" by simp
moreover have "k * (2 * n + 2) + (2 * n + 2) = Suc k * (2 * n + 2)" by simp
ultimately show ?case by (simp only:)
qed
lemma sweep_run:
"(one_tape_config 0 (one_tape_input n) 0, one_tape_config 1 (sweep_tape n n) (Suc n))
∈ ktm_step sweep_delta ^^ (2 * n * n + 3 * n + 2)"
proof -
let ?R = "ktm_step sweep_delta"
have s1: "(one_tape_config 0 (sweep_tape n 0) 0, one_tape_config 0 (sweep_tape n 0) 1) ∈ ?R"
using one_tape_config_step [of 0 1 0 1 MoveR sweep_delta "sweep_tape n 0" 0]
by (simp add: sweep_delta_def sweep_tape_def fun_upd_idem)
have r2: "(one_tape_config 0 (sweep_tape n 0) 1, one_tape_config 0 (sweep_tape n n) 1) ∈ ?R ^^ (n * (2 * n + 2))"
by (rule sweep_passes) simp
have r3: "(one_tape_config 0 (sweep_tape n n) 1, one_tape_config 0 (sweep_tape n n) (1 + n)) ∈ ?R ^^ n"
by (rule one_tape_run_right) (simp add: sweep_delta_def sweep_tape_def)
have s4: "(one_tape_config 0 (sweep_tape n n) (1 + n), one_tape_config 1 (sweep_tape n n) (Suc n)) ∈ ?R"
using one_tape_config_step [of 0 0 1 0 MoveN sweep_delta "sweep_tape n n" "1 + n"]
by (simp add: sweep_delta_def sweep_tape_def fun_upd_idem)
from relpow_Suc_I2 [OF s1 relpow_trans [OF r2 relpow_Suc_I [OF r3 s4]]]
have "(one_tape_config 0 (sweep_tape n 0) 0, one_tape_config 1 (sweep_tape n n) (Suc n)) ∈ ?R ^^ Suc (n * (2 * n + 2) + Suc n)" .
moreover have "Suc (n * (2 * n + 2) + Suc n) = 2 * n * n + 3 * n + 2"
by (simp add: algebra_simps)
ultimately show ?thesis by (simp only: sweep_tape_0)
qed
theorem time_constructible_sweep: "time_constructible (λn. 2 * n * n + 3 * n + 2)"
proof -
have run: "∀n. ∃cfg. (init_config_ktm sweep_clock (unary_word n), cfg)
∈ ktm_step (delta_ktm sweep_clock) ^^ (2 * n * n + 3 * n + 2)
∧ ktc_state cfg = t_ktm sweep_clock"
proof (intro allI exI conjI)
fix n
show "(init_config_ktm sweep_clock (unary_word n), one_tape_config 1 (sweep_tape n n) (Suc n))
∈ ktm_step (delta_ktm sweep_clock) ^^ (2 * n * n + 3 * n + 2)"
unfolding sweep_clock_def one_tape_init one_tape_fields(2) by (rule sweep_run)
show "ktc_state (one_tape_config 1 (sweep_tape n n) (Suc n)) = t_ktm sweep_clock"
by (simp add: sweep_clock_def)
qed
have sig: "3 ∈ Sigma_ktm sweep_clock" by (simp add: sweep_clock_def)
show ?thesis unfolding time_constructible_def
using sweep_clock_wf sweep_clock_det sig run by blast
qed
end