Theory Multitape_Substrate_Core

theory Multitape_Substrate_Core
  imports "HOL-Library.FuncSet"
begin

section ‹Machines, configurations and runs (after Dalvit and Thiemann)›

text ‹The ∗‹definition surface› of the substrate, deliberately isolated
  in this theory: the datatypes, selectors, step relation, and the validity /
  configuration / language definitions --- and no proofs.  This is the part
  of the development that corresponds to the Dalvit--Thiemann AFP entry
  ‹Multitape_To_Singletape_TM› (its files ‹Multitape_TM› and
  ‹TM_Common›, about 180 lines), kept small so a reader can diff it
  directly against that source.  Every lemma --- the ‹valid_ktm›
  axiom-extraction toolkit, the validity-preservation and reachability
  results, and the displacement / left-endmarker tape tools, all
  ∗‹our› additions --- lives in the parent theory ‹Multitape_Substrate›,
  which imports this one.

  The datatypes (‹ktm›, ‹ktc_config›, ‹move›) and the step
  relation are adapted from that entry cite‹"Dalvit2022:verified"›;
  ‹valid_ktm› is a direct conjunction of the substrate's structural
  axioms (no locale wrapping), tightened beyond the AFP entry's
  ‹δLE› axiom by an additional LE-write conjunct (see the
  validity predicate below).

  The names are not the source's: its ‹mttm›, ‹mt_config›, ‹dir›,
  the selectors ‹Q_tm›, ‹Γ_tm› and the predicates ‹valid_mttm›,
  ‹Lang_mttm›, ‹det_mttm› are ‹ktm› (a ‹k›-tape machine),
  ‹ktc_config›, ‹move›, ‹Q_ktm›, ‹Γ_ktm›, ‹valid_ktm›, ‹Lang_ktm› and
  ‹det_ktm› here, so that a theory can import both developments.

  The number of tapes is a ∗‹value›: a machine carries its tape count
  as a ‹nat› field ‹k›, and head contents are a total function
  ‹nat ⇒ 'a› with a ∗‹blank tail› beyond ‹k› (the
  support invariant).  This departs from the AFP source, where the
  tape count is trapped in a finite type parameter ‹'k›; the value
  form is what makes ‹∃ M› / ‹∀ M› over machines of all
  arities a single HOL proposition.›


subsection ‹Head movements (adapted from ‹TM_Common›)›

text ‹Three-valued TM head movement: right (‹MoveR›), left (‹MoveL›), or
  neutral / stay (‹MoveN›).  Used positionally as the fifth component
  of every transition tuple; functions ‹nat ⇒ move› encode the
  per-tape head movement.  The source's type ‹dir› has constructors
  ‹R›, ‹L› and ‹N›; the names here differ so that both can be imported
  together.›

datatype move = MoveR | MoveL | MoveN

fun go_move :: "move ⇒ nat ⇒ nat" where
  "go_move MoveR n = Suc n"
| "go_move MoveL n = n - 1"
| "go_move MoveN n = n"


subsection ‹Machines and configurations (adapted from ‹Multitape_TM›)›

text ‹Multi-tape Turing-machine descriptor.  Ten components: state
  set ‹Q›, input alphabet ‹Σ›, tape alphabet ‹Γ›, blank symbol,
  left endmarker, transition relation ‹δ›, start state, accept
  state, reject state, and tape count ‹k›.  The shape mirrors the
  AFP source (the ‹ktm› type abbreviations are a conscious
  near-copy), except the tape count, trapped in the AFP source's
  finite type parameter ‹'k›, is here the value-level ‹nat› field
  ‹k›; transition tuples index the tapes by ‹nat›, blank beyond ‹k›.
  Only the ‹Q_ktm› and ‹Γ_ktm› accessors are record-style — the
  others are positional with custom selectors below.›

datatype ('q, 'a) ktm = KTM
  (Q_ktm: "'q set")        ― ‹Q — states›
  "'a set"                ― ‹‹Σ› — input alphabet›
  (Γ_ktm: "'a set")        ― ‹‹Γ› — tape alphabet›
  'a                      ― ‹blank›
  'a                      ― ‹left endmarker›
  "('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set"
                          ― ‹transitions ‹δ››
  'q                      ― ‹start state›
  'q                      ― ‹accept state›
  'q                      ― ‹reject state›
  nat                     ― ‹‹k› — tape count›

text ‹Multitape-TM configuration: state, per-tape contents (each a
  function ‹nat ⇒ 'a› of cell positions), per-tape head positions.
  Tapes and heads are indexed by ‹nat›; tapes beyond the machine's
  count ‹k› are all-blank in a valid configuration.›

datatype ('a, 'q) ktc_config = KConfig
  (ktc_state: 'q)
  (ktc_tape: "nat ⇒ nat ⇒ 'a")
  (ktc_pos: "nat ⇒ nat")


subsection ‹Component selectors›

text ‹Positional selectors for the @{type ktm} datatype's
  components.  The datatype declares record-style accessors for
  @{const Q_ktm} and @{const Γ_ktm} only; the others
  (‹Σ›, ‹blank›, ‹LE›, ‹δ›, ‹s›, ‹t›, ‹r›, ‹k›) are positional.
  These selectors are simple positional pattern matches, named
  on the ‹*_ktm› convention to match @{const Q_ktm} / @{const Γ_ktm}.›

fun bl_ktm :: "('q, 'a) ktm ⇒ 'a" where
  "bl_ktm (KTM _ _ _ bl _ _ _ _ _ _) = bl"

fun le_ktm :: "('q, 'a) ktm ⇒ 'a" where
  "le_ktm (KTM _ _ _ _ le _ _ _ _ _) = le"

fun delta_ktm ::
  "('q, 'a) ktm
    ⇒ ('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set" where
  "delta_ktm (KTM _ _ _ _ _ δ _ _ _ _) = δ"

fun s_ktm :: "('q, 'a) ktm ⇒ 'q" where
  "s_ktm (KTM _ _ _ _ _ _ s _ _ _) = s"

fun t_ktm :: "('q, 'a) ktm ⇒ 'q" where
  "t_ktm (KTM _ _ _ _ _ _ _ t _ _) = t"

fun r_ktm :: "('q, 'a) ktm ⇒ 'q" where
  "r_ktm (KTM _ _ _ _ _ _ _ _ r _) = r"

fun Sigma_ktm :: "('q, 'a) ktm ⇒ 'a set" where
  "Sigma_ktm (KTM _ Σ _ _ _ _ _ _ _ _) = Σ"

fun k_ktm :: "('q, 'a) ktm ⇒ nat" where
  "k_ktm (KTM _ _ _ _ _ _ _ _ _ k) = k"


subsection ‹Step relation›

text ‹Inductive characterisation of the multitape-TM step
  relation, parametrised by the transition relation ‹δ› alone.
  Body verbatim equivalent to the AFP source (only the tape index
  moves from the type ‹'k› to ‹nat›); functional layer, so
  downstream Hoare-triple proofs invoke
  ‹ktm_step.intros› directly without any locale routing.›

inductive_set ktm_step ::
  "('q × (nat ⇒ 'a) × 'q × (nat ⇒ 'a) × (nat ⇒ move)) set
    ⇒ ('a, 'q) ktc_config rel"
  for δ
where
  step: "(q, (λk. ts k (n k)), q', a, move) ∈ δ ⟹
   (KConfig q ts n,
    KConfig q' (λk. (ts k)(n k := a k)) (λk. go_move (move k) (n k)))
     ∈ ktm_step δ"


subsection ‹Machine validity›

text ‹Functional bundle of the substrate's structural axioms.  This
  predicate enumerates the standard well-formedness conditions of
  Hopcroft and Ullman cite‹‹\S7.3› in "Hopcroft1979:introduction"›:
  finiteness of @{term Q} and @{term Γ}, alphabet inclusion, state
  membership for the start, accept, and reject states, blank /
  left-endmarker tape-alphabet membership (with @{term Σ}
  disjointness), accept @{text "≠"} reject, a positive tape count
  (the input tape ‹0› must exist), the range typing of the
  transition relation, the LE read-discipline, and the
  ∗‹support invariant›.

  The LE-discipline kept here is the read direction only: every
  ‹δ›-transition reading the left endmarker on tape ‹j› rewrites the
  LE position with itself and moves only ‹N› or ‹R› (boundary
  preservation).  The converse write direction — a transition writes
  the left endmarker on tape ‹j› only where it was already reading
  it — is ∗‹not› a validity requirement: it is factored out as the
  separate predicate ‹le_unique› (below), which well-formed machines
  carry but a machine that deliberately writes a fresh ‹le› may forgo
  while staying valid.  The machine for the Hopcroft--Ullman speed-up
  bound cite‹‹Theorem 12.4› in "Hopcroft1979:introduction"› in the
  alphabet-enlargement entry is one: it writes a fresh ‹le› past the
  input it has consumed instead of rewinding over it, and keeping the
  write direction out of validity is what makes it a legal machine.

  The support invariant — every transition is blank on reads and
  writes and stationary (‹N›) on moves at every tape index ‹j ≥ k›
  — is the value-level replacement for the AFP source's finite tape
  type: it confines a ‹k›-tape machine's transitions to tapes
  ‹0 … k - 1› and, with @{term Γ} finite, makes ‹δ› finite
  (@{text "valid_ktm_finite_delta"}).›

fun valid_ktm :: "('q, 'a) ktm ⇒ bool" where
  "valid_ktm (KTM Q Σ Γ bl le δ s t r k) =
     (finite Q ∧
      finite Γ ∧
      Σ ⊆ Γ ∧
      s ∈ Q ∧
      t ∈ Q ∧
      r ∈ Q ∧
      bl ∈ Γ ∧
      bl ∉ Σ ∧
      le ∈ Γ ∧
      le ∉ Σ ∧
      t ≠ r ∧
      0 < k ∧
      δ ⊆ (Q - {t, r}) × (UNIV → Γ) × Q × (UNIV → Γ) × (UNIV → UNIV) ∧
      (∀q a q' a' d j. (q, a, q', a', d) ∈ δ ⟶ a j = le ⟶
                         a' j = le ∧ d j ∈ {MoveN, MoveR}) ∧
      (∀q a q' a' d. (q, a, q', a', d) ∈ δ ⟶
                       (∀j ≥ k. a j = bl ∧ a' j = bl ∧ d j = MoveN)))"

text ‹The left-endmarker write discipline, as a standalone predicate:
  a transition writes the left endmarker @{term "le_ktm M"} on a tape
  only where it was already reading it — the endmarker is never freshly
  planted.  It is kept out of @{const valid_ktm} so that a machine that
  ∗‹does› write a fresh ‹le›, such as the Theorem 12.4 speed-up machine,
  is still @{const valid_ktm}, while the alphabet transformations, which
  need the property of the machine they simulate, carry it explicitly
  (folded into ‹well_formed_ktm› and threaded to the simulation
  lemmas through ‹valid_ktm_deltaLE_no_write›).›

definition le_unique :: "('q, 'a) ktm ⇒ bool" where
  "le_unique M =
     (∀q a q' a' d j. (q, a, q', a', d) ∈ delta_ktm M ⟶
                        a' j = le_ktm M ⟶ a j = le_ktm M)"

text ‹Strengthening of @{const valid_ktm} with the three
  non-degeneracy conditions used by every linear-speedup-style
  theorem — distinct start / accept / reject states and distinct
  left-endmarker / blank tape symbols — plus the left-endmarker
  write discipline @{const le_unique}.  Bundles
  @{term "valid_ktm M"}, @{term "s_ktm M ≠ t_ktm M"},
  @{term "s_ktm M ≠ r_ktm M"}, @{term "le_ktm M ≠ bl_ktm M"}, and
  @{term "le_unique M"} into a single predicate so downstream
  statements need only one assumption clause instead of five.  Since
  @{const valid_ktm} does not imply @{const le_unique}, this is where
  the alphabet transformations get it from: ‹well_formed_ktm› is
  the hypothesis through which they learn that the machine they
  simulate never writes a fresh ‹le›.›

abbreviation well_formed_ktm
  :: "('q, 'a) ktm ⇒ bool"
where
  "well_formed_ktm M ≡
     valid_ktm M
     ∧ s_ktm M ≠ t_ktm M
     ∧ s_ktm M ≠ r_ktm M
     ∧ le_ktm M ≠ bl_ktm M
     ∧ le_unique M"


subsection ‹Configuration validity›

text ‹Functional re-exposition of the substrate's per-configuration
  validity invariant: state in @{term Q}, every tape's contents
  drawn from @{term Γ}, every ∗‹active› tape (index ‹i < k›)
  carries the left endmarker at position 0, and every ∗‹inactive›
  tape (index ‹i ≥ k›) is all-blank (the configuration-level support
  invariant — inactive tapes carry the blank symbol everywhere, not
  the left endmarker, since ‹bl ≠ le›).›

fun valid_config_ktm ::
  "('q, 'a) ktm ⇒ ('a, 'q) ktc_config ⇒ bool"
where
  "valid_config_ktm (KTM Q _ Γ bl le _ _ _ _ k) (KConfig q ts _) =
     (q ∈ Q
      ∧ (∀i. range (ts i) ⊆ Γ)
      ∧ (∀i<k. ts i 0 = le)
      ∧ (∀i≥k. ∀p. ts i p = bl))"

text ‹Functional initial configuration: take ‹M› as parameter,
  pull start state, blank, left endmarker, and tape count
  positionally.  Active tapes (index ‹i < k›) carry the left
  endmarker at position 0 and, on the input tape ‹0›, the input
  ‹w›; inactive tapes (index ‹i ≥ k›) are all-blank.›

fun init_config_ktm ::
  "('q, 'a) ktm ⇒ 'a list ⇒ ('a, 'q) ktc_config"
where
  "init_config_ktm (KTM _ _ _ bl le _ s _ _ k) w =
     KConfig s
       (λi 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)
       (λ_. 0)"


subsection ‹Language and time-bound predicates›

text ‹Functional analogues of the AFP's @{text "Lang_ktm"}
  and @{text "det_ktm"} top-level wrappers, plus the
  weak-acceptance predicate @{text "accepts_in_time_ktm"}.
  @{text "Lang_ktm"} is the set of inputs over @{term "Sigma_ktm M"}
  that drive @{term M} from its initial configuration to the accept
  state @{term "t_ktm M"}.  @{text "det_ktm"} says the transition
  relation is single-valued: each source state together with the
  symbols read admits at most one outcome — one next state, one
  written-symbol tuple, one head-move tuple — so a configuration has
  at most one successor.  This is the determinism hypothesis on
  which the alphabet-enlargement reverse direction turns.  Bodies
  routed through the functional @{const init_config_ktm} and
  @{const ktm_step} rather than through locale-internal
  definitions.  Used by the AE / AR language- and time-preservation
  theorems.›

definition Lang_ktm :: "('q, 'a) ktm ⇒ 'a list set" where
  "Lang_ktm M =
     {w. set w ⊆ Sigma_ktm M ∧
         (∃w' n. (init_config_ktm M w, KConfig (t_ktm M) w' n)
                    ∈ (ktm_step (delta_ktm M))*)}"

definition det_ktm :: "('q, 'a) ktm ⇒ bool" where
  "det_ktm M =
     (∀q a p1 b1 d1 p2 b2 d2.
        (q, a, p1, b1, d1) ∈ delta_ktm M ⟶
        (q, a, p2, b2, d2) ∈ delta_ktm M ⟶
        (p1, b1, d1) = (p2, b2, d2))"

text ‹Weak time-bounded acceptance: M accepts input @{term w} in
  time at most @{term t} iff some accepting path of length @{term
  "n ≤ t"} exists from @{const init_config_ktm} to a config in
  state @{term "t_ktm M"}.  This matches the existential
  accepting-path shape that the alphabet-enlargement top-level
  theorems preserve.  Non-accepting paths are not constrained,
  in contrast to a universal worst-case bound that would
  constrain every path regardless of acceptance.

  Used by @{text "alphabet_enlarge_language"} and
  @{text "alphabet_enlarge_time"}.›

definition accepts_in_time_ktm ::
  "('q, 'a) ktm ⇒ 'a list ⇒ nat ⇒ bool" where
  "accepts_in_time_ktm M w t =
     (∃n cM_n. n ≤ t
                ∧ (init_config_ktm M w, cM_n) ∈ (ktm_step (delta_ktm M))^^n
                ∧ ktc_state cM_n = t_ktm M)"

end