Parking and the dilated region's split
Definitionsgl_dilation_specParking and the dilated region's structure.
dilPark: from the round layout with no input left, retreating over the region's cells plus the home blank lands exactly on ParkedTape — the form the merge invariant and the whole simulation stack consume. The five separator blanks the last round left behind are simply absorbed into the ghost, which is what the ghost was introduced for.
dilBlocks_split: on either track, a dilated region splits at its first block. Only the first block carries flags — both virtual heads start at position zero — so SplitAtFlag holds for track A and track B with the same three-way split, the tail being flag-clear on both tracks (input blocks written flag-false, and the exit block flag-clear by construction). This is the fact the HostsPair for the dilated region rests on: track A will project to the input followed by blanks, track B to blanks throughout.
import Definitions.Def_sgl_dilation_pre
/-!
# The dilation, specified
Module G2's conclusion: `dilation i` turns a tape holding raw input bits into
the parked region hosting that input beside an empty track.
The three stages compose — pre-pass, loop, park — and the top-level read
dispatches the empty input to `initRegion` through `either`.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-- Parking: from the round invariant with no input left, retreat over the
region's cells to home. -/
theorem dilPark (blocks : List Block) (G : List TapeSymbol) :
((moveDir HeadMove.left)^[(encodeBlocks blocks).length + 1])
(dilTape blocks [] G) =
ParkedTape blocks (List.replicate 5 TapeSymbol.blank ++ G) := by
rw [dilTape, ParkedTape]
have hbc : bitCells [] = [] := rfl
rw [hbc, List.append_nil]
have h := cellsTape_retreat (encodeBlocks blocks).reverse [TapeSymbol.blank]
(List.replicate 4 TapeSymbol.blank ++ G) TapeSymbol.blank
rw [List.length_reverse] at h
rw [show List.replicate 5 TapeSymbol.blank ++ G =
TapeSymbol.blank :: (List.replicate 4 TapeSymbol.blank ++ G) from rfl]
rw [Function.iterate_succ_apply', h, List.reverse_reverse]
obtain ⟨r, R, hcons⟩ : ∃ r R,
encodeBlocks blocks ++ TapeSymbol.blank ::
(List.replicate 4 TapeSymbol.blank ++ G) = r :: R := by
cases hx : encodeBlocks blocks with
| nil => exact ⟨TapeSymbol.blank, List.replicate 4 TapeSymbol.blank ++ G,
by simp [hx]⟩
| cons a as => exact ⟨a, as ++ TapeSymbol.blank ::
(List.replicate 4 TapeSymbol.blank ++ G), by simp [hx]⟩
rw [hcons, cellsTape_moveLeft, ← hcons]
/-! ## The blocks a full dilation writes -/
theorem dilSuffix_all (xs : List Bool) :
dilSuffix xs true = encodeInputBlocks xs ∨ xs = [] := by
cases xs with
| nil => exact Or.inr rfl
| cons x xs' =>
refine Or.inl ?_
rw [dilSuffix_nonempty_eq]
rfl
/-- The region a non-empty input dilates to, with its cells. -/
theorem encodeInputBlocks_cons (x : Bool) (xs : List Bool) :
encodeInputBlocks (x :: xs) = dilSuffix (x :: xs) true := by
rw [dilSuffix_nonempty_eq]
rfl
/-! ## Track projections of the dilated region
Both tracks are flagged only on the first block, so both split there. Track A
then projects to the input followed by blanks — `PadEq` to the input tape —
and track B to blanks throughout. -/
theorem dilBlocks_flagA_first (x : Bool) (xs : List Bool) :
TrackSide.A.getFlag (inputBlock x true) = true := rfl
theorem dilBlocks_flagB_first (x : Bool) (xs : List Bool) :
TrackSide.B.getFlag (inputBlock x true) = true := rfl
theorem inputBlock_flagA_false (b : Bool) :
TrackSide.A.getFlag (inputBlock b false) = false := rfl
theorem inputBlock_flagB_false (b : Bool) :
TrackSide.B.getFlag (inputBlock b false) = false := rfl
@[simp] theorem exitBlock_flagA : TrackSide.A.getFlag exitBlock = false := rfl
@[simp] theorem exitBlock_flagB : TrackSide.B.getFlag exitBlock = false := rfl
/-- The tail of a dilated region carries no flags on either track. -/
theorem dilTail_clear (side : TrackSide) (xs : List Bool) :
∀ b ∈ (xs.map fun c => inputBlock c false) ++ [exitBlock],
side.getFlag b = false := by
intro b hb
rcases List.mem_append.mp hb with h | h
· obtain ⟨c, -, rfl⟩ := List.mem_map.mp h
cases side <;> rfl
· rw [List.mem_singleton.mp h]
cases side <;> rfl
/-- **The split of a dilated region**, on either track: at the first block. -/
theorem dilBlocks_split (side : TrackSide) (x : Bool) (xs : List Bool) :
SplitAtFlag side (dilBlocks (x :: xs)) [] (inputBlock x true)
((xs.map fun c => inputBlock c false) ++ [exitBlock]) :=
⟨rfl, by intro b hb; simp at hb, by cases side <;> rfl,
dilTail_clear side xs⟩
end SipserGacsLautemann