The track update, ghost-uniform
Definitionsgl_step_uniformThe track update with its cost and output region fixed before the ghost.
updateTrack_step takes the simulation invariant — hence a fixed physical tape — and produces its cost existentially. The per-step composition needs the opposite order: a read phase hands its continuation an arbitrary ghost, so the continuation's cost must be one value valid for all of them, and the resulting region likewise.
This is the same restructuring the bounded specifications received one level down, applied one level up. Because those specifications already quantify the ghost inside their cost, the hoist is direct: the case analysis is redone with the ghost introduced after the cost and output region are named. 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 a single fact — cost bounded by , one output region, and MergeInv re-established with the updated track's virtual tape written and moved — usable at any ghost, which is exactly what a nested read phase's continuation hypothesis consumes.
import Definitions.Def_sgl_step_pieces
/-!
# The track update, ghost-uniform
Module E3b, second part.
`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 ∧
∀ (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, ?_⟩
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, ?_⟩
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, ?_⟩
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, ?_⟩
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, ?_⟩
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