The dilated region hosts input and scratch
Definitionsgl_dilation_hostsThe dilated region hosts the input beside an empty tape — the semantic payoff of the dilation, and the fact eliminate_last_scratch_tape turns on.
Both tracks split at the first block, so a single SplitAtFlag serves both. Track A then projects to the input followed by one blank — PadEq to the input tape, the trailing blank being exactly the padding PadEq was designed to absorb. Track B projects to blanks throughout — PadEq to the empty tape.
hostsPair_encodeInputBlocks states it for every input, the empty case falling to the merge-initial block. So after dilation the physical host tape carries, as two interleaved tracks, precisely the last input tape and the scratch tape the simulated machine expects — which is what lets the merge stack run unchanged over an input-bearing host.
import Definitions.Def_sgl_dilation_spec
/-!
# The dilated region hosts the input beside an empty tape
Module G3: the semantic payoff of the dilation. Both tracks split at the
first block, so one split serves both; track A then projects to the input
followed by a single blank, and track B to blanks throughout — each `PadEq` to
the virtual tape it must carry.
-/
namespace SipserGacsLautemann
/-- **A dilated non-empty input is hosted correctly.** -/
theorem hostsPair_dilBlocks (x : Bool) (xs : List Bool) :
HostsPair (dilBlocks (x :: xs))
(fun sd => match sd with
| TrackSide.A => Tape.ofBits (x :: xs)
| TrackSide.B => ⟨[], TapeSymbol.blank, []⟩) := by
intro side
refine ⟨[], inputBlock x true,
(xs.map fun c => inputBlock c false) ++ [exitBlock],
dilBlocks_split side x xs, ?_⟩
cases side with
| A =>
refine ⟨[], [TapeSymbol.blank], AllBlank.nil, AllBlank.single, ?_⟩
show trackOfSplit TrackSide.A.pick [] (inputBlock x true) _ = _
rw [trackOfSplit, trackTape]
simp [trackSyms, TrackSide.pick, inputBlock, exitBlock, Tape.ofBits,
bitCells]
| B =>
refine ⟨[], List.replicate (xs.length + 1) TapeSymbol.blank,
AllBlank.nil, ?_, ?_⟩
· intro c hc
exact List.eq_of_mem_replicate hc
· show trackOfSplit TrackSide.B.pick [] (inputBlock x true) _ = _
rw [trackOfSplit, trackTape]
simp [trackSyms, TrackSide.pick, inputBlock, exitBlock]
induction xs with
| nil => rfl
| cons y ys ih => simp [List.replicate_succ, inputBlock, ih]
/-- **The general statement**: the region `encodeInputBlocks xs` hosts the
input tape beside the empty tape, for every input. -/
theorem hostsPair_encodeInputBlocks (xs : List Bool) :
HostsPair (encodeInputBlocks xs)
(fun sd => match sd with
| TrackSide.A => Tape.ofBits xs
| TrackSide.B => ⟨[], TapeSymbol.blank, []⟩) := by
cases xs with
| nil =>
refine hostsPair_initBlock _ ?_
intro sd
cases sd <;> rfl
| cons x xs' =>
have h := hostsPair_dilBlocks x xs'
rw [encodeInputBlocks_cons, dilSuffix_nonempty_eq]
exact h
end SipserGacsLautemann