The dilation's cost
Definitionsgl_dilation_costThe dilation's cost: .
dilMain_specB and dilation_specB restate the end-to-end dilation with an explicit bound — at most steps on an input of length . The proofs are those of sgl_dilation_main with the arithmetic carried through: the pre-pass is linear, the loop is quadratic (each of rounds shifts a remainder of length at most ), and the parking scan is linear in the region, which is cells.
The earlier statements left the cost existential, which suffices for correctness but not for a time bound — and a time bound is exactly what the polynomial-time bookkeeping of eliminate_last_scratch_tape consumes. Since a halting cost is existentially quantified, it cannot be bounded after the fact; the bound has to be threaded through the same chain, which is why these are restatements rather than corollaries.
import Definitions.Def_sgl_dilation_main
/-!
# The dilation's cost
Bounded restatements: the dilation runs in $O(n^2)$, which is what the
polynomial-time bookkeeping of `eliminate_last_scratch_tape` consumes. The
proofs are those of `sgl_dilation_main` with the arithmetic carried through —
the earlier statements left the cost existential, which is enough for
correctness but not for a time bound.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
set_option maxHeartbeats 4000000 in
/-- **The dilation's main path**: from the raw input tape to the parked
region hosting it. -/
theorem dilMain_specB (i : Fin tapes) (x : Bool) (rest : List Bool)
(T : Fin tapes → Tape) (hT : T i = Tape.ofBits (x :: rest)) :
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
cost ≤ 250 * ((x :: rest).length + 1) * ((x :: rest).length + 1) ∧
HaltsExactly (dilMain i) ((dilMain i).startCfg T) cost false ∧
(((dilMain i).step^[cost]) ((dilMain i).startCfg T)).tape =
Function.update T i (ParkedTape (dilBlocks (x :: rest)) G') := by
classical
-- pre-pass
obtain ⟨cp, G₁, hG₁, hcp, hP, hPt⟩ := prePass_spec i x rest [] T AllBlank.nil
(by rw [hT, ofBits_eq_cellsTape]; simp)
set T1 := Function.update T i (dilTape [] (x :: rest) G₁) with hT1
have hT1i : T1 i = dilTape [] (x :: rest) G₁ := by rw [hT1]; simp
-- loop
obtain ⟨cl, G₂, hG₂, hcl, hL, hLt⟩ :=
dilLoop_run i (x :: rest) true [] G₁ T1 hG₁ hT1i
have hLstart : (dilLoop i).startCfg T1 =
TypedConfiguration.inLoop true ⟨(dilBody i true).start, T1⟩ := rfl
have hL' : HaltsExactly (dilLoop i) ((dilLoop i).startCfg T1) cl false := by
rw [hLstart]; exact hL
have hLt' : (((dilLoop i).step^[cl]) ((dilLoop i).startCfg T1)).tape =
Function.update T1 i (dilTape ([] ++ dilSuffix (x :: rest) true) []
G₂) := by
rw [hLstart]; exact hLt
set T2 := Function.update T i (dilTape (dilBlocks (x :: rest)) [] G₂)
with hT2
have hLt'' : (((dilLoop i).step^[cl]) ((dilLoop i).startCfg T1)).tape = T2 := by
rw [hLt', hT1, hT2]
simp only [Function.update_idem]
rw [List.nil_append, dilSuffix_nonempty_eq]
have hT2i : T2 i = dilTape (dilBlocks (x :: rest)) [] G₂ := by rw [hT2]; simp
-- park
obtain ⟨hK, hKt⟩ := dilPark_spec i (dilBlocks (x :: rest)) G₂ T2 hT2i
-- assemble
have c2 := chainStepC hL' hLt'' hK
have c1 := chainStepC hP hPt c2.1
refine ⟨cp + 1 + (cl + 1 + ((encodeBlocks (dilBlocks (x :: rest))).length
* 4 + 3)), List.replicate 5 TapeSymbol.blank ++ G₂, ?_, ?_, c1.1, ?_⟩
· intro c hc
rcases List.mem_append.mp hc with h | h
· exact List.eq_of_mem_replicate h
· exact hG₂ c h
· -- the cost bound
have hlen : (encodeBlocks (dilBlocks (x :: rest))).length =
6 * (rest.length + 2) := by
rw [encodeBlocks_length]
show 6 * (dilBlocks (x :: rest)).length = _
rw [dilBlocks]
simp
rw [hlen]
have hn : (x :: rest).length = rest.length + 1 := by simp
rw [hn]
have hq : 250 * (rest.length + 1 + 1) * (rest.length + 1 + 1) =
250 * ((rest.length + 2) * (rest.length + 2)) := by ring
rw [hq]
have hexp : (rest.length + 2) * (rest.length + 2) =
rest.length * rest.length + 4 * rest.length + 4 := by ring
have hcl' : cl ≤ (rest.length + 1 + 1) * (15 * (rest.length + 1) + 49) := by
have := hcl
simpa using this
have hclx : (rest.length + 1 + 1) * (15 * (rest.length + 1) + 49) =
15 * (rest.length * rest.length) + 94 * rest.length + 128 := by ring
rw [hclx] at hcl'
rw [hexp]
omega
· have hfin := c1.2
rw [c2.2] at hfin
have hfin' : ((dilMain i).step^[cp + 1 + (cl + 1 +
((encodeBlocks (dilBlocks (x :: rest))).length * 4 + 3))])
((dilMain i).startCfg T) = _ := hfin
rw [hfin']
show (((scanToBlank i HeadMove.left).step^[_])
((scanToBlank i HeadMove.left).startCfg T2)).tape = _
rw [hKt, hT2]
simp only [Function.update_idem]
set_option maxHeartbeats 4000000 in
/-- **The dilation, specified.** For every input, the machine parks the host
tape on the region hosting that input beside an empty scratch track. -/
theorem dilation_specB (i : Fin tapes) (xs : List Bool)
(T : Fin tapes → Tape) (hT : T i = Tape.ofBits xs) :
∃ (cost : Nat) (G : List TapeSymbol), AllBlank G ∧
cost ≤ 250 * (xs.length + 1) * (xs.length + 1) + 16 ∧
HaltsExactly (dilation i) ((dilation i).startCfg T) cost
(match xs with | [] => true | _ => false) ∧
(((dilation i).step^[cost]) ((dilation i).startCfg T)).tape =
Function.update T i (ParkedTape (encodeInputBlocks xs) G) := by
classical
set prog := (fun syms : Fin tapes → TapeSymbol =>
(syms i, fun j => (syms j, HeadMove.stay))) with hprog
have hfires := TypedMachine.readAct_fires prog T
have hrun1 := TypedMachine.readAct_run_one prog T
have hst : (((TypedMachine.readAct prog).step^[1])
((TypedMachine.readAct prog).startCfg T)).state =
some ((T i).head) := by
rw [hrun1]
have htp : (((TypedMachine.readAct prog).step^[1])
((TypedMachine.readAct prog).startCfg T)).tape = T := by
rw [hrun1]
show applyAction T (fun syms => (prog syms).2) = T
funext j
simp [applyAction, hprog, Tape.write_head_self, Tape.move]
cases xs with
| nil =>
-- the read finds blank: the initial-region branch
have hhead : (T i).head = TapeSymbol.blank := by rw [hT]; rfl
have hbit : isBitO (some ((T i).head)) = false := by rw [hhead]; rfl
obtain ⟨hI, hIt⟩ := initRegion_spec i T (by rw [hT]; rfl)
have hbranch : HaltsExactly
((dilMain i).either (initRegion i) (isBitO (some ((T i).head))))
(((dilMain i).either (initRegion i)
(isBitO (some ((T i).head)))).startCfg T) 14 true := by
rw [hbit]
exact HaltsExactly.either_inr (dilMain i) false hI
have hmain := chainStepS
(M₂ := fun rec => (dilMain i).either (initRegion i) (isBitO rec))
hfires.fires hfires.fresh hst htp hbranch
refine ⟨1 + 1 + 14, [TapeSymbol.blank], AllBlank.single, by simp,
hmain.1, ?_⟩
have hfin := hmain.2
have hfin' : ((dilation i).step^[1 + 1 + 14])
((dilation i).startCfg T) = _ := hfin
rw [hfin']
show (((((dilMain i).either (initRegion i)
(isBitO (some ((T i).head))))).step^[14])
((((dilMain i).either (initRegion i)
(isBitO (some ((T i).head))))).startCfg T)).tape = _
rw [hbit, either_run_tape_inr, hIt]
rfl
| cons x rest =>
-- the read finds a bit: the main path
have hhead : (T i).head = TapeSymbol.bit x := by rw [hT]; rfl
have hbit : isBitO (some ((T i).head)) = true := by rw [hhead]; rfl
obtain ⟨cm, G, hG, hcm, hM, hMt⟩ := dilMain_specB i x rest T hT
have hbranch : HaltsExactly
((dilMain i).either (initRegion i) (isBitO (some ((T i).head))))
(((dilMain i).either (initRegion i)
(isBitO (some ((T i).head)))).startCfg T) cm false := by
rw [hbit]
exact HaltsExactly.either_inl (initRegion i) true hM
have hmain := chainStepS
(M₂ := fun rec => (dilMain i).either (initRegion i) (isBitO rec))
hfires.fires hfires.fresh hst htp hbranch
refine ⟨1 + 1 + cm, G, hG, by simp at hcm ⊢; omega, hmain.1, ?_⟩
have hfin := hmain.2
have hfin' : ((dilation i).step^[1 + 1 + cm])
((dilation i).startCfg T) = _ := hfin
rw [hfin']
show (((((dilMain i).either (initRegion i)
(isBitO (some ((T i).head))))).step^[cm])
((((dilMain i).either (initRegion i)
(isBitO (some ((T i).head))))).startCfg T)).tape = _
rw [hbit, either_run_tape_inl, hMt, encodeInputBlocks_cons,
dilSuffix_nonempty_eq]
end SipserGacsLautemann