The track update, ghost-uniform, with region bound
Definitionsgl_update_uniformThe track update with cost, output region, and region length fixed before the ghost.
Successor to sgl_step_uniform. That module fixed the cost and output region ahead of the ghost — necessary because a read phase hands its continuation an arbitrary one — but did not bound the output region's length. Without that bound the second of two chained updates has a cost expressed in terms of a region of unknown size, and the composed step is not visibly polynomial. Each of the five variants either preserves the region's length or extends it by the single materialised block, so ; it simply has to be stated.
IdentPart separates the non-host component of the invariant so it can be carried across an update without mentioning the host tape at all. The result is one fact — cost bounded by , region growth by at most one, and MergeInv re-established with the updated track's virtual tape written and moved — valid at any ghost.
import Definitions.Def_sgl_step_pieces
/-!
# The track update, ghost-uniform (with region bound)
Module E3b, second part. Successor to `sgl_step_uniform`, which lacked the
output-region length bound; that bound is needed to keep the *second* update's
cost expressible in terms of the *first* update's input, hence to keep the
composed step polynomial. Platform definitions being immutable, this is a new
module rather than an edit.
`updateTrack_step` takes the invariant — hence a *fixed* physical tape — and
produces its cost existentially. The per-step composition needs the opposite
order: the read phases hand their continuation an arbitrary ghost, so the cost
and the resulting region must be fixed **before** the ghost is chosen.
The bounded specifications already have that shape, so the hoist is direct:
this module redoes `updateTrack_step`'s case analysis with the ghost
introduced inside, yielding one cost and one output region valid for every
ghost.
-/
namespace SipserGacsLautemann
variable {states : Nat}
/-- The non-host component of the invariant, separated so it can be carried
across an update without mentioning the host tape. -/
def IdentPart (tapes' : Nat) (virt : Configuration (tapes' + 2) states)
(base : Fin (tapes' + 1) → Tape) : Prop :=
∀ j : Fin (tapes' + 1), j.val < tapes' → base j = virt.tape ⟨j.val, by omega⟩
theorem identPart_update {tapes' : Nat} {virt : Configuration (tapes' + 2) states}
{base : Fin (tapes' + 1) → Tape} (h : IdentPart tapes' virt base)
(side : TrackSide) (X : Tape) (Y : Tape) :
IdentPart tapes'
{ state := virt.state
tape := Function.update virt.tape (hostIdx tapes' side) X }
(Function.update base (Fin.last tapes') Y) := by
intro j hj
have hne : j ≠ Fin.last tapes' := by
intro hcon; rw [hcon] at hj; simp at hj
have hne2 : (⟨j.val, by omega⟩ : Fin (tapes' + 2)) ≠ hostIdx tapes' side := by
intro hcon
have := congrArg Fin.val hcon
cases side <;> simp [hostIdx] at this <;> omega
rw [Function.update_of_ne hne]
show base j = Function.update virt.tape (hostIdx tapes' side) X _
rw [Function.update_of_ne hne2]
exact h j hj
/-- **The update, with cost and output region fixed before the ghost.** -/
theorem updateTrack_step_u {tapes' : Nat}
(virt : Configuration (tapes' + 2) states)
(base : Fin (tapes' + 1) → Tape) (blocks : List Block)
(side : TrackSide) (s : TapeSymbol) (mv : HeadMove)
(hident : IdentPart tapes' virt base)
(hosts : HostsPair blocks (fun sd => virt.tape (hostIdx tapes' sd))) :
∃ (cost : Nat) (blocks' : List Block),
cost ≤ 100 * blocks.length + 300 ∧
blocks'.length ≤ blocks.length + 1 ∧
∀ (G : List TapeSymbol), AllBlank G →
HaltsExactly (updateTrack side (Fin.last tapes') s mv)
((updateTrack side (Fin.last tapes') s mv).startCfg
(Function.update base (Fin.last tapes')
(ParkedTape blocks G))) cost false ∧
∃ G', AllBlank G' ∧
(((updateTrack side (Fin.last tapes') s mv).step^[cost])
((updateTrack side (Fin.last tapes') s mv).startCfg
(Function.update base (Fin.last tapes')
(ParkedTape blocks G)))).tape =
Function.update base (Fin.last tapes')
(ParkedTape blocks' G') ∧
MergeInv tapes'
{ state := virt.state
tape := Function.update virt.tape (hostIdx tapes' side)
(Tape.move
(Tape.write (virt.tape (hostIdx tapes' side)) s) mv) }
(Function.update base (Fin.last tapes')
(ParkedTape blocks' G')) blocks' G' := by
classical
obtain ⟨pre, cur, post, hsplit, -⟩ := hosts side
have hblocks := hsplit.eq
subst hblocks
have hpk : ∀ (bl : List Block) (Gx : List TapeSymbol),
(Function.update base (Fin.last tapes') (ParkedTape bl Gx))
(Fin.last tapes') = ParkedTape bl Gx := by
intro bl Gx; simp
have hstart : ∀ (Gx : List TapeSymbol),
(Function.update base (Fin.last tapes') (ParkedTape (pre ++ cur :: post) Gx))
(Fin.last tapes') = ParkedTape (pre ++ cur :: post) Gx := fun Gx => hpk _ _
cases mv with
| stay =>
obtain ⟨cost, hbound, hrun⟩ := updateTrack_stay_bounded side
(Fin.last tapes') s pre cur post hsplit.preClear hsplit.curSet
refine ⟨cost, pre ++ setSymFlag side s true cur :: post, hbound,
by simp, ?_⟩
intro G hG
obtain ⟨G', hG', hhalt, htape⟩ := hrun G _ hG (hstart G)
rw [Function.update_idem] at htape
refine ⟨hhalt, G', hG', htape, identPart_update hident side _ _,
hpk _ _, hG', ?_⟩
have hp := hosts.update_stay side hsplit s
simp only [virtTape_update_apply]
exact hp
| right =>
cases post with
| cons nxt post' =>
obtain ⟨cost, hbound, hrun⟩ := updateTrack_right_cons_bounded side
(Fin.last tapes') s pre cur nxt post' hsplit.preClear hsplit.curSet
refine ⟨cost, pre ++ setSymFlag side s false cur ::
setFlag side true nxt :: post', hbound, by simp, ?_⟩
intro G hG
obtain ⟨G', hG', hhalt, htape⟩ := hrun G _ hG (hstart G)
rw [Function.update_idem] at htape
refine ⟨hhalt, G', hG', htape, identPart_update hident side _ _,
hpk _ _, hG', ?_⟩
have hp := hosts.update_right_mid side hsplit s
simp only [virtTape_update_apply]
exact hp
| nil =>
obtain ⟨cost, hbound, hrun⟩ := updateTrack_right_nil_bounded side
(Fin.last tapes') s pre cur hsplit.preClear hsplit.curSet
refine ⟨cost, pre ++ [setSymFlag side s false cur,
freshFlagged side], hbound, by simp, ?_⟩
intro G hG
obtain ⟨G', hG', hhalt, htape⟩ := hrun G _ hG (hstart G)
rw [Function.update_idem] at htape
refine ⟨hhalt, G', hG', htape, identPart_update hident side _ _,
hpk _ _, hG', ?_⟩
have hp := hosts.update_right_edge side hsplit s
simp only [virtTape_update_apply]
exact hp
| left =>
rcases List.eq_nil_or_concat pre with rfl | ⟨pre', prv, rfl⟩
· obtain ⟨cost, hbound, hrun⟩ := updateTrack_left_nil_bounded side
(Fin.last tapes') s cur post hsplit.curSet
refine ⟨cost, freshFlagged side ::
setSymFlag side s false cur :: post, hbound, by simp, ?_⟩
intro G hG
obtain ⟨G', hG', hhalt, htape⟩ := hrun G _ hG
(by have h := hstart G; simp only [List.nil_append] at h; exact h)
rw [Function.update_idem] at htape
refine ⟨by simpa using hhalt, G', hG', by simpa using htape,
identPart_update hident side _ _, hpk _ _, hG', ?_⟩
have hp := hosts.update_left_edge side (by simpa using hsplit) s
simp only [virtTape_update_apply]
exact hp
· simp only [List.concat_eq_append] at *
obtain ⟨cost, hbound, hrun⟩ := updateTrack_left_concat_bounded side
(Fin.last tapes') s pre' prv cur post hsplit.preClear hsplit.curSet
refine ⟨cost, pre' ++ setFlag side true prv ::
setSymFlag side s false cur :: post, hbound, by simp, ?_⟩
intro G hG
obtain ⟨G', hG', hhalt, htape⟩ := hrun G _ hG (hstart G)
rw [Function.update_idem] at htape
refine ⟨hhalt, G', hG', htape, identPart_update hident side _ _,
hpk _ _, hG', ?_⟩
have hp := hosts.update_left_mid side hsplit s
simp only [virtTape_update_apply]
exact hp
end SipserGacsLautemann