Theory Multitape_Clock_Interface
theory Multitape_Clock_Interface
imports Multitape_Run_Facts
begin
section ‹Exact unary clocks›
text ‹A small, construction-independent interface for clocks, as time
hierarchy proofs use them. A clock is tested on unary input, which a
machine can write without first decoding a binary number. The symbol ‹3›
is part of the interface: a caller must establish that it belongs to the
clock's input alphabet before using its initial configuration.
The run is required to have exactly the displayed length and to end in the
accepting state. This is deliberately stronger than
\<^const>‹accepts_in_time_ktm›, which only asks for an accepting run of at
most a given length and would therefore be satisfied by an immediately
accepting machine for every budget. Sink states supplied by
\<^const>‹valid_ktm› make the exact run a genuine alarm: it cannot have
entered a terminal state early and then continued.
This is the exact form of time constructibility, in which the clock's
running time is the function itself. It is close to what Hopcroft and
Ullman \<^cite>‹"Hopcroft1979:introduction"› call ∗‹fully›
time-constructible, except that only one input of each length, the unary
word, has to take exactly ‹g n› steps.
The predicate says nothing about a value produced on a work tape. That is
intentional: what a hierarchy proof needs from it is an elapsed-time alarm.
A contract for a clock that also writes its value has to state a tape layout
and belongs with the development that uses it.›
definition unary_word :: "nat ⇒ nat list" where
"unary_word n = replicate n 3"
definition time_constructible :: "(nat ⇒ nat) ⇒ bool" where
"time_constructible g ⟷
(∃D :: (nat, nat) ktm.
well_formed_ktm D ∧ det_ktm D ∧
3 ∈ Sigma_ktm D ∧
(∀n. ∃cfg. (init_config_ktm D (unary_word n), cfg)
∈ (ktm_step (delta_ktm D)) ^^ (g n)
∧ ktc_state cfg = t_ktm D))"
lemma unary_word_length [simp]: "length (unary_word n) = n"
by (simp add: unary_word_def)
lemma unary_word_set [simp]: "set (unary_word n) = (if n = 0 then {} else {3})"
proof (induct n)
case 0
then show ?case by (simp add: unary_word_def)
next
case (Suc n)
then show ?case by (simp add: unary_word_def)
qed
lemma unary_word_subset:
assumes "3 ∈ Sigma_ktm M"
shows "set (unary_word n) ⊆ Sigma_ktm M"
using assms by (auto simp: unary_word_def)
subsection ‹Halting states are sinks›
text ‹The exact-alarm interface is useful only when its terminal run cannot
pass through a halting state early. Validity supplies that sink property
for every multitape machine, and the following lemmas package the generic
consequences that a clocked construction uses. The first is the
contrapositive of the substrate's ‹ktm_step_src›, in the form these
proofs consume it. They mention no particular
construction.›
lemma halt_state_sink:
assumes vM: "valid_ktm M" and halt: "ktc_state c ∈ {t_ktm M, r_ktm M}"
shows "(c, c') ∉ ktm_step (delta_ktm M)"
using halt ktm_step_src_neq_t [OF vM] ktm_step_src_neq_r [OF vM] by blast
lemma halt_no_further:
assumes vM: "valid_ktm M"
and halt: "ktc_state c ∈ {t_ktm M, r_ktm M}"
and pos: "0 < N"
shows "(c, c') ∉ (ktm_step (delta_ktm M)) ^^ N"
proof
assume run: "(c, c') ∈ (ktm_step (delta_ktm M)) ^^ N"
from pos obtain m where m: "N = Suc m" by (cases N) auto
from run [unfolded m] obtain d where "(c, d) ∈ ktm_step (delta_ktm M)"
by (blast dest: relpow_Suc_D2)
with halt_state_sink [OF vM halt] show False by simp
qed
lemma alarm_running_lt:
assumes vM: "valid_ktm M" and det: "det_ktm M"
and alarm: "(c⇩0, cfg) ∈ (ktm_step (delta_ktm M)) ^^ G"
and halt: "ktc_state cfg = t_ktm M"
and run: "(c⇩0, c) ∈ (ktm_step (delta_ktm M)) ^^ m"
and alive: "ktc_state c ≠ t_ktm M" "ktc_state c ≠ r_ktm M"
shows "m < G"
proof (rule ccontr)
let ?R = "ktm_step (delta_ktm M)"
assume "¬ m < G"
then have "m = G + (m - G)" by simp
with run have "(c⇩0, c) ∈ ?R ^^ G O ?R ^^ (m - G)" by (metis relpow_add)
then obtain y where ay: "(c⇩0, y) ∈ ?R ^^ G" and yc: "(y, c) ∈ ?R ^^ (m - G)"
by auto
from det_ktm_relpow_unique [OF det ay alarm] have y: "y = cfg" .
with halt have yhalt: "ktc_state y ∈ {t_ktm M, r_ktm M}" by simp
show False
proof (cases "m - G")
case 0
with yc have "c = y" by simp
with yhalt alive show False by simp
next
case (Suc r)
then have "0 < m - G" by simp
from halt_no_further [OF vM yhalt this] yc show False by simp
qed
qed
lemma alarm_start_alive:
assumes vM: "valid_ktm M"
and run: "(init_config_ktm M v, cfg) ∈ (ktm_step (delta_ktm M)) ^^ G"
and G: "0 < G"
shows "s_ktm M ≠ t_ktm M ∧ s_ktm M ≠ r_ktm M"
proof (rule ccontr)
assume "¬ (s_ktm M ≠ t_ktm M ∧ s_ktm M ≠ r_ktm M)"
then have "ktc_state (init_config_ktm M v) ∈ {t_ktm M, r_ktm M}"
by (cases M) simp
from halt_no_further [OF vM this G] run show False by simp
qed
end