Theory Multitape_Alphabet_Enlargement.AlphabetEnlargement_Defs

theory AlphabetEnlargement_Defs
  imports "Multitape_TM_Substrate.Multitape_Substrate"
begin

section ‹Alphabet enlargement›

text ‹Setup for the ‹alphabet_enlarge› combinator:
  substrate selectors, stage-bookkeeping types, offset and
  block helpers, encoder / decoder, encoder-canonicity
  predicates, per-substep transition relations, the
  ‹alphabet_enlarge› combinator itself, the
  ‹ae_simulates› relation, and the eight mid-stage
  invariants ‹ae_inv_ss1› through ‹ae_inv_ss8›,
  plus the upstream structural lemmas, the encoder-roundtrip
  chain, and the validation-phase chain culminating in
  ‹ae_validation_steps_bound›.

  The forward-simulation chain that consumes the validation
  result, and the top-level theorems
  ‹alphabet_enlarge_wf›,
  ‹alphabet_enlarge_language›, and
  ‹alphabet_enlarge_time›, follow further on in this
  chapter.›

text ‹Substrate selectors (‹bl_ktm›, ‹le_ktm›, ‹delta_ktm›,
  ‹s_ktm›, ‹t_ktm›, ‹r_ktm›, ‹Sigma_ktm›, ‹ktc_tape›) live in
  the ‹Multitape_Substrate› theory alongside the functional substrate
  layer; they're imported transitively.›

subsection ‹Stage bookkeeping types›

text ‹Substep counter / phase indicator for ‹M'›'s state machine.

  Constructors ‹VFwd› / ‹VFwdPad› / ‹VRet› mark the
  validation phase: forward scan (no padded block seen yet),
  forward scan after a trailing-padded block has been
  observed, and return scan back to the first input block.

  Constructors ‹SS1› … ‹SS8› mark the 8-substep simulation
  stage of Hopcroft--Ullman
  cite‹‹Theorem 12.3› in "Hopcroft1979:introduction"›; ‹SSn›
  corresponds to the spec's "substep ‹n›".›

datatype substep_idx =
    VFwd | VFwdPad | VRet
  | SS1 | SS2 | SS3 | SS4 | SS5 | SS6 | SS7 | SS8

instance substep_idx :: finite
proof (intro_classes)
  have "(UNIV :: substep_idx set) ⊆
          {VFwd, VFwdPad, VRet,
           SS1, SS2, SS3, SS4, SS5, SS6, SS7, SS8}"
    using substep_idx.exhaust by blast
  thus "finite (UNIV :: substep_idx set)"
    using finite_subset by auto
qed

text ‹Per-tape destination indicator: which buffer slot now holds
  the home block of ‹M›'s simulated head, after the compute
  substep (the 4th component of ‹stage›).
  The compute substep sets this; the write-back phase consumes it
  to choose between move-sequence variants
  (`L,R,R,N` / `L,R,R,L` / `R,L,L,N` for steady-state stages).›

datatype ae_dest = AE_Left | AE_Home | AE_Right

instance ae_dest :: finite
proof (intro_classes)
  have "(UNIV :: ae_dest set) ⊆ {AE_Left, AE_Home, AE_Right}"
    using ae_dest.exhaust by blast
  thus "finite (UNIV :: ae_dest set)"
    using finite_subset by auto
qed

text ‹Stage bookkeeping carried in the output machine's state set:
  per-tape within-block offset (‹nat ⇒ nat›), per-tape three-block
  buffer (left, home, right), per-tape destination indicator
  (‹AE_Left› / ‹AE_Home› / ‹AE_Right›), and the substep counter
  within the current 8-substep stage.›

type_synonym 'a ae_stage =
  "(nat ⇒ nat)
   × (nat ⇒ (nat ⇒ 'a) × (nat ⇒ 'a) × (nat ⇒ 'a))
   × (nat ⇒ ae_dest)
   × substep_idx"

subsection ‹Offsets within a block›

text ‹A block holds ‹m› cells of ‹M›'s tape, at the offsets
  ‹0› to ‹m - 1›; ‹m› is Hopcroft and Ullman's compression factor.
  The compute substep tracks a simulated head position by an offset
  within a 3-block buffer; advancing by ‹L› / ‹R› needs a partial
  successor and predecessor on offsets.›

definition c_last :: "nat ⇒ nat" where
  "c_last m = m - 1"

definition c_succ :: "nat ⇒ nat ⇒ nat option" where
  "c_succ m x = (if Suc x < m then Some (Suc x) else None)"

definition c_pred :: "nat ⇒ nat option" where
  "c_pred x = (if x = 0 then None else Some (x - 1))"

subsection ‹Block-encoding helpers›

text ‹The constant LE-block: a block whose every cell holds
  ‹M›'s left-endmarker symbol.  Used as ‹M'›'s left endmarker.
  Compatible with the substrate's ‹δLE› invariant: any read of
  this block tests ‹le› at every cell, so the
  ‹a k = LE ⟹ a' k = LE ∧ d k ∈ {N, R}› obligation lifts
  pointwise from ‹M›'s.

  A block is a function on offsets, ∗‹extensional› on ‹{..<m}›:
  past the last offset it is ‹undefined›, so that the blocks over a
  finite alphabet form a finite set (‹gamma_block›).›

definition LE_block :: "nat ⇒ 'a ⇒ (nat ⇒ 'a)" where
  "LE_block m le = restrict (λ_. le) {..<m}"

text ‹The constant blank-block: a block whose every cell holds
  ‹M›'s blank symbol.  Used as ‹M'›'s blank, and also as the
  semantic placeholder for ‹buf.left› in LE-stages.›

definition bl_block :: "nat ⇒ 'a ⇒ (nat ⇒ 'a)" where
  "bl_block m bl = restrict (λ_. bl) {..<m}"

subsection ‹Encoder›

text ‹Encoding an input word as a list of ‹m›-cell blocks,
  padding the final block with the substrate's blank symbol if the
  input length is not a multiple of ‹m›.  Block ‹i› (for
  ‹i < ⌈length w / m⌉›) holds ‹w ! (i ⋅ m + x)› at offset
  ‹x›, or the blank past the end of ‹w›; the output list has
  length ‹⌈length w / m⌉›, computed in nat arithmetic as
  ‹(length w + m - 1) div m›.›

definition encode_input ::
  "nat ⇒ 'a ⇒ 'a list ⇒ (nat ⇒ 'a) list" where
  "encode_input m bl w =
     (let c = m in
        map (λi. restrict (λx. let j = i * c + x in
                          if j < length w then w ! j else bl) {..<m})
            [0 ..< (length w + c - 1) div c])"

subsection ‹Decoder›

text ‹Decoder: extract ‹M›-symbols from a list of blocks by
  taking each block's ‹bl›-free prefix in offset
  order.  For pure blocks this yields all ‹m›
  cells; for trailing-padded blocks it yields the non-blank
  prefix; for non-canonical blocks (blank-then-non-blank
  pattern) it yields the leading non-blank prefix only — but
  the validation phase rejects these before decoding is invoked.
  Inverse to ‹encode_input› on the encoder image; cited by the
  forward direction of
  ‹ae_validation_canonical_iff_encoder_image›.›

definition ae_decode_block :: "nat ⇒ 'a ⇒ (nat ⇒ 'a) ⇒ 'a list" where
  "ae_decode_block m bl f =
     takeWhile (λa. a ≠ bl) (map f [0..<m])"

definition ae_decode_input :: "nat ⇒ 'a ⇒ (nat ⇒ 'a) list ⇒ 'a list" where
  "ae_decode_input m bl w = concat (map (ae_decode_block m bl) w)"

subsection ‹Initial stage›

text ‹Initial within-block offset: ‹0› on every tape (treated as
  the within-block position of ‹M›'s left endmarker on each tape).›

definition init_offset :: "nat ⇒ nat" where
  "init_offset = (λ_. 0)"

text ‹Initial buffer.  Every tape starts with three constant
  ‹LE›-blocks: at ‹M'›'s position 0 the home block is the
  left-endmarker block, and the buffer phase has not yet executed
  on the surrounding cells; the SS1‹→›SS4 buffer phase
  refills the slots from actual tape contents at the start of
  every stage.›

definition init_buffer ::
  "nat ⇒ 'a ⇒ (nat ⇒ ((nat ⇒ 'a)
                  × (nat ⇒ 'a)
                  × (nat ⇒ 'a)))" where
  "init_buffer m le = (λ_. (LE_block m le, LE_block m le, LE_block m le))"

text ‹Initial destination indicator: every tape starts with
  ‹AE_Home› (the indicator is meaningful only after the compute
  substep sets it; the initial value is canonical).›

definition init_dest :: "nat ⇒ ae_dest" where
  "init_dest = (λ_. AE_Home)"

text ‹Initial stage: zero offset, all-‹LE› buffers, dest = home,
  substep counter ‹SS1›.›

definition init_stage ::
  "nat ⇒ 'a ⇒ 'a ae_stage" where
  "init_stage m le = (init_offset, init_buffer m le, init_dest, VFwd)"

subsection ‹Encoder-canonicity predicates›

text ‹A block is ‹pure› if every cell is non-blank.  In the
  encoder image, every block except possibly the last has
  this form (every cell is from the original input).›

definition is_pure_block ::
  "nat ⇒ 'a ⇒ (nat ⇒ 'a) ⇒ bool" where
  "is_pure_block m bl f = (∀x<m. f x ≠ bl)"

text ‹A block is ‹trailing-padded› if there is a non-empty,
  proper prefix (in offset order) of
  non-blank cells, and the remaining cells are all blank.  In the
  encoder image, the last block has this form when the
  input length is not a multiple of ‹c›.›

definition is_padded_block ::
  "nat ⇒ 'a ⇒ (nat ⇒ 'a) ⇒ bool" where
  "is_padded_block m bl f =
     (∃k. k ≥ 1 ∧ k < length [0..<m]
       ∧ (∀x<m. x < k ⟶ f x ≠ bl)
       ∧ (∀x<m. x ≥ k ⟶ f x = bl))"

text ‹Encoder-canonical block: pure or trailing-padded.  The
  validation phase accepts only blocks satisfying this
  predicate; non-canonical blocks (blanks scattered in
  non-trailing positions) route the input to ‹r_M'›.›

definition is_canonical_block ::
  "nat ⇒ 'a ⇒ (nat ⇒ 'a) ⇒ bool" where
  "is_canonical_block m bl f = (is_pure_block m bl f ∨ is_padded_block m bl f)"

text ‹Sequence-level encoder-canonicity: the input ‹w› is
  well-formed (= in the encoder image) iff every block is
  pure, ∗‹except possibly the last› which may also be padded.
  Per block encoder-canonicity (‹is_canonical_block›) is
  necessary but not sufficient — a sequence with a padded
  block followed by anything else is per-cell canonical but
  not in the encoder image.

  The validation phase enforces exactly this distinction: VFwd
  reject fires on non-canonical cells; VFwdPad reject fires on
  any non-‹bl_block› cell after a padded block.›

definition ae_input_well_formed ::
  "nat ⇒ 'a ⇒ (nat ⇒ 'a) list ⇒ bool" where
  "ae_input_well_formed m bl w ⟷
     (∀s. s < length w ⟶
        (is_pure_block m bl (w ! s)
         ∨ (s = length w - 1 ∧ is_padded_block m bl (w ! s))))"

end