The eliminate-last composite
Definitionsgl_elim_compositecomplexity-theoryinfrastructuretheoretical-computer-scienceturing-machines
The eliminate-last composite: dilate the host tape's input into the two-track region, then run the merge simulation.
elimComposite_specB carries both costs — the dilation's quadratic bound and the simulation loop's — because the final theorem needs a time bound and a halting cost cannot be bounded after the fact. Given the identity-mapping, the two hosted virtual tapes (the last input tape and the empty scratch tape), and the host physical tape holding that same input, it halts with the simulated machine's answer inside .
encodeInputBlocks_length bounds the region by one block per input cell plus the exit block — which is what keeps the whole composite polynomial.
Definition code
import Definitions.Def_sgl_dilation_cost
import Definitions.Def_sgl_merge_compose
/-!
# The eliminate-last composite
Module G4, first part: dilate the host tape's input into the two-track
region, then run the merge simulation. Both costs are threaded — the
dilation's quadratic bound and the loop's — because the final theorem needs a
time bound, and a halting cost cannot be bounded after the fact.
-/
namespace SipserGacsLautemann
set_option synthInstance.maxSize 4000
set_option synthInstance.maxHeartbeats 2000000
variable {states : Nat}
/-- Dilate, then simulate. -/
noncomputable def elimComposite (tapes' : Nat)
(M : Machine (tapes' + 2) states) (q₀ : Fin states) :=
(dilation (Fin.last tapes')).andThen fun _ =>
mergeMachine tapes' M q₀
set_option maxHeartbeats 4000000 in
/-- **The composite decides what the simulated machine decides**, with the
region built from the input the host tape already carries. -/
theorem elimComposite_specB {tapes' : Nat} (M : Machine (tapes' + 2) states)
(virt : Configuration (tapes' + 2) states)
(base : Fin (tapes' + 1) → Tape) (xs : List Bool)
(rounds : Nat) (ans : Bool)
(hident : IdentPart tapes' virt base)
(hhostA : virt.tape (hostIdx tapes' TrackSide.A) = Tape.ofBits xs)
(hhostB : virt.tape (hostIdx tapes' TrackSide.B) =
⟨[], TapeSymbol.blank, []⟩)
(hbase : base (Fin.last tapes') = Tape.ofBits xs)
(hlive : ∀ i, i ≤ rounds → M.result ((M.step^[i]) virt).state = none)
(hhalt : M.result ((M.step^[rounds + 1]) virt).state = some ans) :
∃ total : Nat,
total ≤ 250 * (xs.length + 1) * (xs.length + 1) + 17 +
(rounds + 1) *
(500 * ((encodeInputBlocks xs).length + 2 * rounds) + 1501) ∧
HaltsExactly (elimComposite tapes' M virt.state)
((elimComposite tapes' M virt.state).startCfg base) total ans := by
classical
-- the dilation
obtain ⟨cd, G, hG, hcd, hD, hDt⟩ :=
dilation_specB (Fin.last tapes') xs base hbase
set blocks := encodeInputBlocks xs with hblocks
set base' := Function.update base (Fin.last tapes') (ParkedTape blocks G)
with hbase'
-- the round record
have hhosts : HostsPair blocks
(fun sd => virt.tape (hostIdx tapes' sd)) := by
have h := hostsPair_encodeInputBlocks xs
have hfun : (fun sd => virt.tape (hostIdx tapes' sd)) =
(fun sd => match sd with
| TrackSide.A => Tape.ofBits xs
| TrackSide.B => (⟨[], TapeSymbol.blank, []⟩ : Tape)) := by
funext sd
cases sd with
| A => exact hhostA
| B => exact hhostB
rw [hfun]
exact h
set R₀ : MergeRound tapes' M :=
{ virt := virt, base := base, blocks := blocks, ghost := G,
hg := hG, hident := hident, hosts := hhosts } with hR₀
obtain ⟨loopTotal, hloopBound, hloop⟩ :=
mergeMachine_spec R₀ rounds ans (by simpa [hR₀] using hlive)
(by simpa [hR₀] using hhalt)
have hloop' : HaltsExactly (mergeMachine tapes' M virt.state)
((mergeMachine tapes' M virt.state).startCfg base') loopTotal ans := by
rw [show base' = R₀.park from rfl]
exact hloop
refine ⟨cd + 1 + loopTotal, ?_, (chainStepC hD hDt hloop').1⟩
have hRb : R₀.blocks = encodeInputBlocks xs := rfl
rw [hRb] at hloopBound
set B := (encodeInputBlocks xs).length with hB
set Q := 250 * (xs.length + 1) * (xs.length + 1) with hQ
have hstep : (rounds + 1) * (500 * (B + 2 * rounds) + 1500 + 1) =
(rounds + 1) * (500 * (B + 2 * rounds) + 1501) := by
congr 1
rw [hstep] at hloopBound
omega
/-- The dilated region is one block per input cell, plus the exit block. -/
theorem encodeInputBlocks_length (xs : List Bool) :
(encodeInputBlocks xs).length ≤ xs.length + 1 := by
cases xs with
| nil => simp [encodeInputBlocks]
| cons x xs' =>
rw [encodeInputBlocks_cons, dilSuffix_nonempty_eq, dilBlocks]
simp
end SipserGacsLautemann
Source
Composite for eliminate_last_scratch_tape; builds on Def_sgl_dilation_cost and Def_sgl_merge_compose.