The dilation loop
Definitionsgl_dilation_loopThe loop consuming the remaining input, proved by induction over it. dilLoop_run: from any round configuration — head at the separator start, blocks so far to the left, remaining input compact to the right — the loop consumes the whole remainder and halts with every block appended, exit block last, at cost at most : quadratic in the input, as in-place dilation must be.
The induction chains rounds through the loop algebra's single-round lemmas rather than the round-indexed trajectory apparatus, which needs one small general fact: HaltsExactly.of_advance — a halting fact composes across a configuration advance whose prefix is fresh. That is the whole bridge, and it is worth having separately: any loop proved by direct induction rather than through a LoopRound family will want it.
Also here: dilSuffix, the blocks a round-sequence writes from a given remainder, and its identification with the region dilBlocks for non-empty input.
import Definitions.Def_sgl_dilation_body
/-!
# The dilation loop
The loop consuming the remaining input, by induction over it.
`HaltsExactly.of_advance` is the small general bridge the induction needs: a
halting fact composes across a configuration advance whose prefix is fresh.
Any loop proved by direct induction rather than through a `LoopRound` family
will want it.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## The loop -/
/-- Advancing a machine to a later configuration composes halting facts. -/
theorem HaltsExactly.of_advance {S : Type} {M : TypedMachine tapes S}
{c₀ c₁ : TypedConfiguration tapes S} {k t : Nat} {v : Bool}
(hadv : (M.step^[k]) c₀ = c₁)
(hpre : ∀ j, j < k → M.result ((M.step^[j]) c₀).state = none)
(h : HaltsExactly M c₁ t v) :
HaltsExactly M c₀ (k + t) v := by
constructor
· rw [Nat.add_comm, Function.iterate_add_apply, hadv]
exact h.halts
· intro j hj
rcases Nat.lt_or_ge j k with hlt | hge
· exact hpre j hlt
· obtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le hge
rw [Nat.add_comm k d, Function.iterate_add_apply, hadv]
exact h.fresh d (by omega)
/-- The blocks the loop writes from the remaining input, given the current
first-round flag. -/
def dilSuffix : List Bool → Bool → List Block
| [], c => [blockFor (some TapeSymbol.blank) c]
| x :: xs, c => inputBlock x c :: dilSuffix xs false
theorem dilSuffix_nonempty_eq (x : Bool) (xs : List Bool) :
dilSuffix (x :: xs) true = dilBlocks (x :: xs) := by
rw [dilBlocks]
show inputBlock x true :: dilSuffix xs false = _
congr 1
induction xs with
| nil => rfl
| cons y ys ih =>
show inputBlock y false :: dilSuffix ys false = _
rw [ih]
rfl
set_option maxHeartbeats 1000000 in
/-- **The dilation loop consumes the remaining input.** From any round
configuration it halts with the remaining blocks (and the exit block)
appended, at quadratic cost. -/
theorem dilLoop_run (i : Fin tapes) :
∀ (xs : List Bool) (c : Bool) (done : List Block) (G : List TapeSymbol)
(T : Fin tapes → Tape), AllBlank G → T i = dilTape done xs G →
∃ (cost : Nat) (G' : List TapeSymbol), AllBlank G' ∧
cost ≤ (xs.length + 1) * (15 * xs.length + 49) ∧
HaltsExactly (dilLoop i)
(TypedConfiguration.inLoop c ⟨(dilBody i c).start, T⟩) cost false ∧
((((dilLoop i).step^[cost])
(TypedConfiguration.inLoop c ⟨(dilBody i c).start, T⟩)).tape) =
Function.update T i (dilTape (done ++ dilSuffix xs c) [] G') := by
intro xs
induction xs with
| nil =>
intro c done G T hG hT
obtain ⟨cb, G', hG', hcb, hhalt, hread, htape⟩ :=
dilBody_spec_blank i c done G T hG hT
have hstop : (fun _ b => !(isBitO (stateRead b))) c
(((dilBody i c).step^[cb])
((dilBody i c).startCfg T)).state = true := by
simp only [hread]
rfl
have hmain := TypedMachine.loopState_spec_v
(fun first => dilBody i first) (fun _ _ => false)
(fun _ b => !(isBitO (stateRead b))) (fun _ _ => false)
true (fun _ => c)
(fun _ => (dilBody i c).startCfg T) (fun _ => 0) 0 cb true
(by intro j hj; omega) hhalt hstop
have hmain' : HaltsExactly (dilLoop i)
(TypedConfiguration.inLoop c ⟨(dilBody i c).start, T⟩) cb false := by
simpa [loopCost] using hmain
refine ⟨cb, G', hG', by simp; omega, hmain', ?_⟩
· have hiter := TypedMachine.loopState_iterate_body
(fun first => dilBody i first) (fun _ _ => false)
(fun _ b => !(isBitO (stateRead b))) (fun _ _ => false)
true c ((dilBody i c).startCfg T) cb hhalt.fresh
show (((dilLoop i).step^[cb])
(TypedConfiguration.inLoop c ((dilBody i c).startCfg T))).tape = _
rw [dilLoop, hiter]
show (((dilBody i c).step^[cb]) ((dilBody i c).startCfg T)).tape = _
rw [htape]
rfl
| cons x rest ih =>
intro c done G T hG hT
obtain ⟨cb, G', hG', hcb, hhalt, hread, htape⟩ :=
dilBody_spec_bit i c x done rest G T hG hT
have hkeep : (fun _ b => !(isBitO (stateRead b))) c
(((dilBody i c).step^[cb])
((dilBody i c).startCfg T)).state = false := by
simp only [hread]
rfl
set T' := Function.update T i
(dilTape (done ++ [inputBlock x c]) rest G') with hT'
have hT'i : T' i = dilTape (done ++ [inputBlock x c]) rest G' := by
rw [hT']; simp
obtain ⟨ct, G'', hG'', hct, hhalt', htape'⟩ :=
ih false (done ++ [inputBlock x c]) G' T' hG' hT'i
-- one round advances the loop
have hround := TypedMachine.loopState_round
(fun first => dilBody i first) (fun _ _ => false)
(fun _ b => !(isBitO (stateRead b))) (fun _ _ => false)
true (fun n => if n = 0 then c else false)
(fun n => if n = 0 then (dilBody i c).startCfg T
else (dilBody i false).startCfg T')
(fun _ => cb) 0
⟨⟨true, by simpa using hhalt⟩, by simpa using hkeep, by simp,
by
simp only [if_pos rfl, if_neg (Nat.zero_ne_one ∘ Eq.symm)]
show ((dilBody i false).startCfg T' :
TypedConfiguration tapes _) =
⟨(dilBody i false).start,
(((dilBody i c).step^[cb]) ((dilBody i c).startCfg T)).tape⟩
rw [htape]
rfl⟩
have hfresh := TypedMachine.loopState_round_fresh
(fun first => dilBody i first) (fun _ _ => false)
(fun _ b => !(isBitO (stateRead b))) (fun _ _ => false)
true c ((dilBody i c).startCfg T) cb true hhalt hkeep
have hadv : ((dilLoop i).step^[cb + 1])
(TypedConfiguration.inLoop c ⟨(dilBody i c).start, T⟩) =
TypedConfiguration.inLoop false ⟨(dilBody i false).start, T'⟩ := by
have := hround
simpa using this
refine ⟨cb + 1 + ct, G'', hG'', ?_, ?_, ?_⟩
· have h1 : cb + 1 ≤ 15 * rest.length + 49 := by omega
have h2 : ct ≤ (rest.length + 1) * (15 * rest.length + 49) := hct
have h3 : (rest.length + 1) * (15 * rest.length + 49) ≤
(rest.length + 1) * (15 * (rest.length + 1) + 49) :=
Nat.mul_le_mul_left _ (by omega)
have h4 : ((x :: rest).length + 1) * (15 * (x :: rest).length + 49) =
(rest.length + 2) * (15 * (rest.length + 1) + 49) := by
simp [List.length_cons]
rw [h4]
have h5 : (rest.length + 2) * (15 * (rest.length + 1) + 49) =
(rest.length + 1) * (15 * (rest.length + 1) + 49) +
(15 * (rest.length + 1) + 49) := by
rw [Nat.succ_mul]
omega
· exact HaltsExactly.of_advance hadv
(fun j hj => hfresh j hj) hhalt'
· rw [show cb + 1 + ct = ct + (cb + 1) by omega,
Function.iterate_add_apply, hadv, htape', hT']
simp only [Function.update_idem]
rw [show done ++ dilSuffix (x :: rest) c =
(done ++ [inputBlock x c]) ++ dilSuffix rest false by
rw [List.append_assoc]
rfl]
end SipserGacsLautemann