Bounded, ghost-uniform update and read specifications
Definitionsgl_bounded_specsBounded, ghost-uniform specifications: the repair that unblocks the final assembly.
The published update and read-phase specifications hide their costs behind an existential quantified after the ghost. Two consumers break on that, and both breaks are fatal rather than cosmetic:
Polynomial accounting. DecidesInPolynomialTime demands a uniform polynomial time bound, and the simulation's total is plus a final round. An opaque per-round cost cannot be summed, and the value is not recoverable after the fact: the halting time of a HaltsExactly is unique, but proving requires a firing-at- fact that only a re-derivation supplies.
Nested phases. A read phase's continuation hypothesis needs one fixed cost for every ghost. With the ghost quantified outside the cost, each ghost instantiation produces its own opaque cost and no uniform value exists — even though the underlying costs are visibly ghost-independent.
This module restates all six specifications in the corrected shape: cost first with an affine bound in the region size, ghost and tape introduced inside. The four update variants become separate theorems — stay, right_cons, right_nil, left_concat, left_nil — so each names its own result region rather than hiding an edge case behind a match, and readPhase_bounded gains the ∀-tape form its own nesting requires. Every cost is bounded by (plus the continuation's for the read phase); the constants are deliberately generous, since only polynomiality is at stake.
Formalization note. The proofs are the original chain constructions with the cost expression supplied up front — the exact nested sum the chain accumulates, written in statement-level terms — and the bound discharged by loopCost_const together with length facts and omega. This works because set folds the goal's occurrences into the same names the chain produces, so the pre-supplied expression unifies with what the junctions build.
import Definitions.Def_sgl_step_program
/-!
# Bounded, ghost-uniform specifications
Module E3a of the merge_empty plan (`DESIGN_E3_F.md` §1.1).
The published update and read-phase specifications hide their costs behind an
existential, quantified *after* the ghost. Two consumers break on that: the
final polynomial accounting cannot bound an opaque per-round cost, and a
nested phase's `hcont` needs one fixed cost **for every ghost**. The costs
are in fact ghost-independent and affinely bounded — the statements just
failed to say so.
This module restates them in the corrected shape
```
∃ cost, cost ≤ ⟨affine in the region size⟩ ∧
∀ G tape, AllBlank G → tape i = ParkedTape … G → ⟨the original conclusion⟩
```
— cost first, bound alongside, ghost and tape inside. The proofs are the
original chain constructions with the cost supplied up front; the edge cases
become separate theorems (`right_cons`/`right_nil`, `left_concat`/`left_nil`)
so each statement names its own result region.
-/
namespace SipserGacsLautemann
set_option maxHeartbeats 4000000
variable {tapes : Nat}
/-- `blockReadSteps` is twelve. -/
theorem blockReadSteps_eq : blockReadSteps = 12 := rfl
/-! ## The stay variant, bounded -/
theorem updateTrack_stay_bounded (side : TrackSide) (i : Fin tapes)
(s : TapeSymbol) (mid : List Block) (cur : Block) (post : List Block)
(hmid : ∀ b ∈ mid, side.getFlag b = false)
(hcur : side.getFlag cur = true) :
∃ cost, cost ≤ 100 * (mid ++ cur :: post).length + 300 ∧
∀ (G : List TapeSymbol) (tape : Fin tapes → Tape),
AllBlank G → tape i = ParkedTape (mid ++ cur :: post) G →
∃ G', AllBlank G' ∧
HaltsExactly (updateTrack side i s HeadMove.stay)
((updateTrack side i s HeadMove.stay).startCfg tape) cost false ∧
(((updateTrack side i s HeadMove.stay).step^[cost])
((updateTrack side i s HeadMove.stay).startCfg tape)).tape =
Function.update tape i
(ParkedTape (mid ++ setSymFlag side s true cur :: post) G') := by
classical
refine ⟨1 + 1 + ((loopCost (fun _ => blockReadSteps) mid.length +
blockReadSteps) + 1 + (6 + 1 + (6 + 1 + (6 + 1 + (6 + 1 +
((((Block.toCells (setSymFlag side s true cur)).reverse ++
(encodeBlocks mid).reverse).length) * 4 + 3)))))), ?_, ?_⟩
· rw [loopCost_const, blockReadSteps_eq]
simp only [List.length_append, List.length_reverse,
Block.toCells_length, encodeBlocks_length, List.length_cons]
omega
intro G tape hG hi
have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
set newCur := setSymFlag side s true cur with hnewCur
-- junction 1: enter
set T1 : Fin tapes → Tape := Function.update tape i
(cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: post) ++ G)) with hT1
have htp1 : (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg tape)).tape = T1 := by
rw [moveUpTo_tape i 1 HeadMove.right (by omega) tape, hT1]
congr 1
rw [Function.iterate_one, hi, ParkedTape]
exact cellsTape_moveRight _ _ _
have hT1i : T1 i = cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: post) ++ G) := by
rw [hT1]; simp
-- junction 2: walk
obtain ⟨hw, -, hwt⟩ := walkToFlag_spec side i T1 [TapeSymbol.blank] G
mid cur post hmid hcur hT1i
set T2 := scanTapesDir T1 i HeadMove.right (6 * (mid.length + 1)) with hT2
have hsplit : encodeBlocks (mid ++ cur :: post) =
encodeBlocks (mid ++ [cur]) ++ encodeBlocks post := by
rw [← encodeBlocks_append]
congr 1
simp
have hT2i : T2 i =
cellsTape ((encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank])
(encodeBlocks post ++ G) := by
rw [hT2, scanTapesDir_self, hT1i, hsplit, List.append_assoc,
show 6 * (mid.length + 1) = (encodeBlocks (mid ++ [cur])).length by
rw [encodeBlocks_length]; simp,
cellsTape_advance]
-- junction 3: back onto the flagged block
obtain ⟨G₃, hG₃, hret3⟩ := retreat_block (Block.toCells cur).reverse
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G hG
set T3 := Function.update T2 i
(cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃))) with hT3
have htp3 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T2)).tape = T3 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T2, hT3]
congr 1
rw [hT2i,
show (encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank] =
(Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) by
rw [encodeBlocks_append]
simp [List.reverse_append, encodeBlocks_cons],
show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
rw [hret3, List.reverse_reverse]
have hT3i : T3 i = cellsTape
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃)) := by
rw [hT3]; simp
-- junction 4: rewrite the flagged block
set T4 := Function.update T3 i
(cellsTape ((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃)) with hT4
have htp4 : (((patchRun6 i (symWindow side s true)).step^[6])
((patchRun6 i (symWindow side s true)).startCfg T3)).tape = T4 := by
rw [patchRun6_tape i _ T3 _ _ hT3i, hT4]
congr 1
rw [patchCellsN_symWindow, ← hnewCur,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
List.drop_left]
have hT4i : T4 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃) := by
rw [hT4]; simp
-- junction 5: retreat again
obtain ⟨G₅, hG₅, hret5⟩ := retreat_block (Block.toCells newCur).reverse
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G₃ hG₃
set T5 := Function.update T4 i
(cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells newCur ++ (encodeBlocks post ++ G₅))) with hT5
have htp5 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T4)).tape = T5 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T4, hT5]
congr 1
rw [hT4i,
show (6 : Nat) = ((Block.toCells newCur).reverse).length by
simp [Block.toCells_length]]
rw [hret5, List.reverse_reverse]
have hT5i : T5 i = cellsTape
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
rw [hT5]; simp
-- junction 6: identity window
set T6 := Function.update T5 i
(cellsTape ((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₅)) with hT6
have htp6 : (((patchRun6 i allNormWindow).step^[6])
((patchRun6 i allNormWindow).startCfg T5)).tape = T6 := by
rw [patchRun6_tape i _ T5 _ _ hT5i, hT6]
congr 1
rw [patchCellsN_allNorm,
show (6 : Nat) = (Block.toCells newCur).length from
(Block.toCells_length newCur).symm,
List.drop_left]
have hT6i : T6 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₅) := by
rw [hT6]; simp
-- junction 7: park
set Wp := (Block.toCells newCur).reverse ++ (encodeBlocks mid).reverse
with hWp
have hassoc : (Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) =
Wp ++ [TapeSymbol.blank] := by
rw [hWp, List.append_assoc]
have hWp_nb : ∀ c ∈ Wp, c ≠ TapeSymbol.blank := by
intro c hc
rw [hWp] at hc
rcases List.mem_append.mp hc with h | h
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h)
· exact encodeBlocks_ne_blank _ c (List.mem_reverse.mp h)
obtain ⟨hlt', heq'⟩ := blank_scan_left_spec (Wp ++ [TapeSymbol.blank])
((encodeBlocks post ++ G₅).headD TapeSymbol.blank)
((encodeBlocks post ++ G₅).tail)
rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
have hlt : ∀ j, j < Wp.length →
((moveDir HeadMove.left)^[j + 1] (T6 i)).head ≠ TapeSymbol.blank := by
intro j hj
rw [hT6i, hassoc]
exact hlt' j hj
have heq : ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)).head =
TapeSymbol.blank := by
rw [hT6i, hassoc]
exact heq'
obtain ⟨G₇, hG₇, hret7⟩ := retreat_block Wp [TapeSymbol.blank] post G₅ hG₅
have hWrev : Wp.reverse = encodeBlocks mid ++ Block.toCells newCur := by
rw [hWp, List.reverse_append, List.reverse_reverse, List.reverse_reverse]
have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
ParkedTape (mid ++ newCur :: post) G₇ := by
rw [Function.iterate_succ_apply', hT6i, hassoc, hret7]
obtain ⟨r, R', hcons⟩ : ∃ r R',
Wp.reverse ++ (encodeBlocks post ++ G₇) = r :: R' := by
rw [hWrev]
cases hx : encodeBlocks mid ++ Block.toCells newCur ++
(encodeBlocks post ++ G₇) with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons,
show ([TapeSymbol.blank] : List TapeSymbol) =
TapeSymbol.blank :: [] from rfl,
cellsTape_moveLeft, ← hcons, hWrev, ParkedTape]
have henc : encodeBlocks (mid ++ newCur :: post) =
encodeBlocks mid ++ (Block.toCells newCur ++ encodeBlocks post) := by
rw [encodeBlocks_append, encodeBlocks_cons]
rw [henc]
simp [List.append_assoc]
set T7 := Function.update T6 i (ParkedTape (mid ++ newCur :: post) G₇)
with hT7
have htp7 : (((scanToBlank i HeadMove.left).step^[Wp.length * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
rw [scanToBlank_tape_of i HeadMove.left T6 Wp.length hlt heq, hT7]
show Function.update T6 i
((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)) = _
rw [hX7]
have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T6) (Wp.length * 4 + 3)
false := scanToBlank_spec_of i HeadMove.left T6 Wp.length hlt heq
-- assemble
have hC6 := chainStep (patchRun6_spec i allNormWindow T5 _ _ hT5i) htp6
hP7 htp7
have hC5 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T4) htp5
hC6.1 hC6.2
have hC4 := chainStep (patchRun6_spec i (symWindow side s true) T3 _ _ hT3i)
htp4 hC5.1 hC5.2
have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2) htp3
hC4.1 hC4.2
have hC2 := chainStep hw hwt hC3.1 hC3.2
have hC1 := chainStep (moveUpTo_spec i 1 HeadMove.right (by omega) tape)
htp1 hC2.1 hC2.2
refine ⟨G₇, hG₇, hC1.1, ?_⟩
have hfin := hC1.2
rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1] at hfin
simp only [scanTapesDir, Function.update_idem] at hfin
exact hfin
/-! ## The right variant, bounded — flag lands on an existing next block -/
theorem updateTrack_right_cons_bounded (side : TrackSide) (i : Fin tapes)
(s : TapeSymbol) (mid : List Block) (cur nxt : Block) (post' : List Block)
(hmid : ∀ b ∈ mid, side.getFlag b = false)
(hcur : side.getFlag cur = true) :
∃ cost, cost ≤ 100 * (mid ++ cur :: nxt :: post').length + 300 ∧
∀ (G : List TapeSymbol) (tape : Fin tapes → Tape),
AllBlank G → tape i = ParkedTape (mid ++ cur :: nxt :: post') G →
∃ G', AllBlank G' ∧
HaltsExactly (updateTrack side i s HeadMove.right)
((updateTrack side i s HeadMove.right).startCfg tape) cost false ∧
(((updateTrack side i s HeadMove.right).step^[cost])
((updateTrack side i s HeadMove.right).startCfg tape)).tape =
Function.update tape i
(ParkedTape (mid ++ setSymFlag side s false cur ::
setFlag side true nxt :: post') G') := by
classical
refine ⟨1 + 1 + ((loopCost (fun _ => blockReadSteps) mid.length +
blockReadSteps) + 1 + (6 + 1 + (6 + 1 + (0 + 1 + (6 + 1 +
((((Block.toCells (setFlag side true nxt)).reverse ++
((Block.toCells (setSymFlag side s false cur)).reverse ++
(encodeBlocks mid).reverse)).length) * 4 + 3)))))), ?_, ?_⟩
· rw [loopCost_const, blockReadSteps_eq]
simp only [List.length_append, List.length_reverse,
Block.toCells_length, encodeBlocks_length, List.length_cons]
omega
intro G tape hG hi
have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
set newCur := setSymFlag side s false cur with hnewCur
set T1 : Fin tapes → Tape := Function.update tape i
(cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: nxt :: post') ++ G)) with hT1
have htp1 : (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg tape)).tape = T1 := by
rw [moveUpTo_tape i 1 HeadMove.right (by omega) tape, hT1]
congr 1
rw [Function.iterate_one, hi, ParkedTape]
exact cellsTape_moveRight _ _ _
have hT1i : T1 i = cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: nxt :: post') ++ G) := by
rw [hT1]; simp
obtain ⟨hw, -, hwt⟩ := walkToFlag_spec side i T1 [TapeSymbol.blank] G
mid cur (nxt :: post') hmid hcur hT1i
set T2 := scanTapesDir T1 i HeadMove.right (6 * (mid.length + 1)) with hT2
have hsplit : encodeBlocks (mid ++ cur :: nxt :: post') =
encodeBlocks (mid ++ [cur]) ++ encodeBlocks (nxt :: post') := by
rw [← encodeBlocks_append]
congr 1
simp
have hT2i : T2 i =
cellsTape ((encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank])
(encodeBlocks (nxt :: post') ++ G) := by
rw [hT2, scanTapesDir_self, hT1i, hsplit, List.append_assoc,
show 6 * (mid.length + 1) = (encodeBlocks (mid ++ [cur])).length by
rw [encodeBlocks_length]; simp,
cellsTape_advance]
obtain ⟨G₃, hG₃, hret3⟩ := retreat_block (Block.toCells cur).reverse
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) (nxt :: post') G hG
set T3 := Function.update T2 i
(cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks (nxt :: post') ++ G₃))) with hT3
have htp3 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T2)).tape = T3 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T2, hT3]
congr 1
rw [hT2i,
show (encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank] =
(Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) by
rw [encodeBlocks_append]
simp [List.reverse_append, encodeBlocks_cons],
show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
rw [hret3, List.reverse_reverse]
have hT3i : T3 i = cellsTape
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks (nxt :: post') ++ G₃)) := by
rw [hT3]; simp
set T4 := Function.update T3 i
(cellsTape ((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks (nxt :: post') ++ G₃)) with hT4
have htp4 : (((patchRun6 i (symWindow side s false)).step^[6])
((patchRun6 i (symWindow side s false)).startCfg T3)).tape = T4 := by
rw [patchRun6_tape i _ T3 _ _ hT3i, hT4]
congr 1
rw [patchCellsN_symWindow, ← hnewCur,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
List.drop_left]
have hT4i : T4 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks (nxt :: post') ++ G₃) := by
rw [hT4]; simp
have h5 : HaltsExactly (moveUpTo i 0 HeadMove.left)
((moveUpTo i 0 HeadMove.left).startCfg T4) 0 true :=
moveUpTo_spec i 0 HeadMove.left (by omega) T4
have htp5 : (((moveUpTo i 0 HeadMove.left).step^[0])
((moveUpTo i 0 HeadMove.left).startCfg T4)).tape = T4 := rfl
set sNxt := setFlag side true nxt with hsNxt
have hR4 : T4 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(Block.toCells nxt ++ (encodeBlocks post' ++ G₃)) := by
rw [hT4i, encodeBlocks_cons, List.append_assoc]
set T6 := Function.update T4 i
(cellsTape ((Block.toCells sNxt).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
(encodeBlocks post' ++ G₃)) with hT6
have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
((patchRun6 i (flagWindow side)).startCfg T4)).tape = T6 := by
rw [patchRun6_tape i _ T4 _ _ hR4, hT6]
congr 1
rw [patchCellsN_flagWindow, ← hsNxt,
show (6 : Nat) = (Block.toCells nxt).length from
(Block.toCells_length nxt).symm,
List.drop_left]
have hT6i : T6 i = cellsTape
((Block.toCells sNxt).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
(encodeBlocks post' ++ G₃) := by
rw [hT6]; simp
set Wp := (Block.toCells sNxt).reverse ++
((Block.toCells newCur).reverse ++ (encodeBlocks mid).reverse)
with hWp
have hassoc : (Block.toCells sNxt).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])) =
Wp ++ [TapeSymbol.blank] := by
rw [hWp]
simp [List.append_assoc]
have hWp_nb : ∀ c ∈ Wp, c ≠ TapeSymbol.blank := by
intro c hc
rw [hWp] at hc
rcases List.mem_append.mp hc with h | h
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h)
· rcases List.mem_append.mp h with h' | h'
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h')
· exact encodeBlocks_ne_blank _ c (List.mem_reverse.mp h')
obtain ⟨hlt', heq'⟩ := blank_scan_left_spec (Wp ++ [TapeSymbol.blank])
((encodeBlocks post' ++ G₃).headD TapeSymbol.blank)
((encodeBlocks post' ++ G₃).tail)
rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
have hlt : ∀ j, j < Wp.length →
((moveDir HeadMove.left)^[j + 1] (T6 i)).head ≠ TapeSymbol.blank := by
intro j hj
rw [hT6i, hassoc]
exact hlt' j hj
have heq : ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)).head =
TapeSymbol.blank := by
rw [hT6i, hassoc]
exact heq'
obtain ⟨G₇, hG₇, hret7⟩ := retreat_block Wp [TapeSymbol.blank] post' G₃ hG₃
have hWrev : Wp.reverse = encodeBlocks mid ++
(Block.toCells newCur ++ Block.toCells sNxt) := by
rw [hWp]
simp [List.reverse_append]
have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
ParkedTape (mid ++ newCur :: sNxt :: post') G₇ := by
rw [Function.iterate_succ_apply', hT6i, hassoc, hret7]
obtain ⟨r, R', hcons⟩ : ∃ r R',
Wp.reverse ++ (encodeBlocks post' ++ G₇) = r :: R' := by
rw [hWrev]
cases hx : encodeBlocks mid ++
(Block.toCells newCur ++ Block.toCells sNxt) ++
(encodeBlocks post' ++ G₇) with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons,
show ([TapeSymbol.blank] : List TapeSymbol) =
TapeSymbol.blank :: [] from rfl,
cellsTape_moveLeft, ← hcons, hWrev, ParkedTape]
have henc : encodeBlocks (mid ++ newCur :: sNxt :: post') =
encodeBlocks mid ++ (Block.toCells newCur ++
(Block.toCells sNxt ++ encodeBlocks post')) := by
rw [encodeBlocks_append, encodeBlocks_cons, encodeBlocks_cons]
rw [henc]
simp [List.append_assoc]
set T7 := Function.update T6 i
(ParkedTape (mid ++ newCur :: sNxt :: post') G₇) with hT7
have htp7 : (((scanToBlank i HeadMove.left).step^[Wp.length * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
rw [scanToBlank_tape_of i HeadMove.left T6 Wp.length hlt heq, hT7]
show Function.update T6 i
((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)) = _
rw [hX7]
have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T6) (Wp.length * 4 + 3)
false := scanToBlank_spec_of i HeadMove.left T6 Wp.length hlt heq
have hC6 := chainStep (patchRun6_spec i (flagWindow side) T4 _ _ hR4)
htp6 hP7 htp7
have hC5 := chainStep h5 htp5 hC6.1 hC6.2
have hC4 := chainStep
(patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
hC5.1 hC5.2
have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
htp3 hC4.1 hC4.2
have hC2 := chainStep hw hwt hC3.1 hC3.2
have hC1 := chainStep
(moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
refine ⟨G₇, hG₇, hC1.1, ?_⟩
have hfin := hC1.2
rw [hT7, hT6, hT4, hT3, hT2, hT1] at hfin
simp only [scanTapesDir, Function.update_idem] at hfin
exact hfin
/-! ## The right variant, bounded — flag materialises a fresh block -/
theorem updateTrack_right_nil_bounded (side : TrackSide) (i : Fin tapes)
(s : TapeSymbol) (mid : List Block) (cur : Block)
(hmid : ∀ b ∈ mid, side.getFlag b = false)
(hcur : side.getFlag cur = true) :
∃ cost, cost ≤ 100 * (mid ++ [cur]).length + 300 ∧
∀ (G : List TapeSymbol) (tape : Fin tapes → Tape),
AllBlank G → tape i = ParkedTape (mid ++ [cur]) G →
∃ G', AllBlank G' ∧
HaltsExactly (updateTrack side i s HeadMove.right)
((updateTrack side i s HeadMove.right).startCfg tape) cost false ∧
(((updateTrack side i s HeadMove.right).step^[cost])
((updateTrack side i s HeadMove.right).startCfg tape)).tape =
Function.update tape i
(ParkedTape
(mid ++ [setSymFlag side s false cur, freshFlagged side])
G') := by
classical
refine ⟨1 + 1 + ((loopCost (fun _ => blockReadSteps) mid.length +
blockReadSteps) + 1 + (6 + 1 + (6 + 1 + (0 + 1 + (6 + 1 +
((((Block.toCells (freshFlagged side)).reverse ++
((Block.toCells (setSymFlag side s false cur)).reverse ++
(encodeBlocks mid).reverse)).length) * 4 + 3)))))), ?_, ?_⟩
· rw [loopCost_const, blockReadSteps_eq]
simp only [List.length_append, List.length_reverse,
Block.toCells_length, encodeBlocks_length, List.length_cons]
omega
intro G tape hG hi
have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
set newCur := setSymFlag side s false cur with hnewCur
set T1 : Fin tapes → Tape := Function.update tape i
(cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ [cur]) ++ G)) with hT1
have htp1 : (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg tape)).tape = T1 := by
rw [moveUpTo_tape i 1 HeadMove.right (by omega) tape, hT1]
congr 1
rw [Function.iterate_one, hi, ParkedTape]
exact cellsTape_moveRight _ _ _
have hT1i : T1 i = cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ [cur]) ++ G) := by
rw [hT1]; simp
obtain ⟨hw, -, hwt⟩ := walkToFlag_spec side i T1 [TapeSymbol.blank] G
mid cur [] hmid hcur hT1i
set T2 := scanTapesDir T1 i HeadMove.right (6 * (mid.length + 1)) with hT2
have hT2i : T2 i =
cellsTape ((encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank])
(encodeBlocks ([] : List Block) ++ G) := by
rw [hT2, scanTapesDir_self, hT1i,
show 6 * (mid.length + 1) = (encodeBlocks (mid ++ [cur])).length by
rw [encodeBlocks_length]; simp]
have h := cellsTape_advance (encodeBlocks (mid ++ [cur]))
[TapeSymbol.blank] G
simpa using h
obtain ⟨G₃, hG₃, hret3⟩ := retreat_block (Block.toCells cur).reverse
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) [] G hG
set T3 := Function.update T2 i
(cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks ([] : List Block) ++ G₃)))
with hT3
have htp3 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T2)).tape = T3 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T2, hT3]
congr 1
rw [hT2i,
show (encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank] =
(Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) by
rw [encodeBlocks_append]
simp [List.reverse_append, encodeBlocks_cons],
show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
rw [hret3, List.reverse_reverse]
have hT3i : T3 i = cellsTape
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks ([] : List Block) ++ G₃)) := by
rw [hT3]; simp
set T4 := Function.update T3 i
(cellsTape ((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks ([] : List Block) ++ G₃)) with hT4
have htp4 : (((patchRun6 i (symWindow side s false)).step^[6])
((patchRun6 i (symWindow side s false)).startCfg T3)).tape = T4 := by
rw [patchRun6_tape i _ T3 _ _ hT3i, hT4]
congr 1
rw [patchCellsN_symWindow, ← hnewCur,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
List.drop_left]
have hT4i : T4 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks ([] : List Block) ++ G₃) := by
rw [hT4]; simp
have h5 : HaltsExactly (moveUpTo i 0 HeadMove.left)
((moveUpTo i 0 HeadMove.left).startCfg T4) 0 true :=
moveUpTo_spec i 0 HeadMove.left (by omega) T4
have htp5 : (((moveUpTo i 0 HeadMove.left).step^[0])
((moveUpTo i 0 HeadMove.left).startCfg T4)).tape = T4 := rfl
have hR4 : T4 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])) G₃ := by
rw [hT4i]
simp
set T6 := Function.update T4 i
(cellsTape ((Block.toCells (freshFlagged side)).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
(G₃.drop 6)) with hT6
have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
((patchRun6 i (flagWindow side)).startCfg T4)).tape = T6 := by
rw [patchRun6_tape i _ T4 _ _ hR4, hT6]
congr 1
rw [patchCellsN_flagWindow_fresh side G₃ hG₃]
have hT6i : T6 i = cellsTape
((Block.toCells (freshFlagged side)).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])))
(G₃.drop 6) := by
rw [hT6]; simp
have hG₆ : AllBlank (G₃.drop 6) := hG₃.drop 6
set Wp := (Block.toCells (freshFlagged side)).reverse ++
((Block.toCells newCur).reverse ++ (encodeBlocks mid).reverse)
with hWp
have hassoc : (Block.toCells (freshFlagged side)).reverse ++
((Block.toCells newCur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])) =
Wp ++ [TapeSymbol.blank] := by
rw [hWp]
simp [List.append_assoc]
have hWp_nb : ∀ c ∈ Wp, c ≠ TapeSymbol.blank := by
intro c hc
rw [hWp] at hc
rcases List.mem_append.mp hc with h | h
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h)
· rcases List.mem_append.mp h with h' | h'
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h')
· exact encodeBlocks_ne_blank _ c (List.mem_reverse.mp h')
obtain ⟨hlt', heq'⟩ := blank_scan_left_spec (Wp ++ [TapeSymbol.blank])
((G₃.drop 6).headD TapeSymbol.blank) ((G₃.drop 6).tail)
rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
have hlt : ∀ j, j < Wp.length →
((moveDir HeadMove.left)^[j + 1] (T6 i)).head ≠ TapeSymbol.blank := by
intro j hj
rw [hT6i, hassoc]
exact hlt' j hj
have heq : ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)).head =
TapeSymbol.blank := by
rw [hT6i, hassoc]
exact heq'
obtain ⟨G₇, hG₇, hret7⟩ := retreat_block Wp [TapeSymbol.blank] []
(G₃.drop 6) hG₆
have hWrev : Wp.reverse = encodeBlocks mid ++
(Block.toCells newCur ++ Block.toCells (freshFlagged side)) := by
rw [hWp]
simp [List.reverse_append]
have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
ParkedTape (mid ++ [newCur, freshFlagged side]) G₇ := by
rw [Function.iterate_succ_apply', hT6i, hassoc]
have hret7' : (moveDir HeadMove.left)^[Wp.length]
(cellsTape (Wp ++ [TapeSymbol.blank]) (G₃.drop 6)) =
cellsTape [TapeSymbol.blank] (Wp.reverse ++ G₇) := by
have h := hret7
simpa using h
rw [hret7']
obtain ⟨r, R', hcons⟩ : ∃ r R', Wp.reverse ++ G₇ = r :: R' := by
rw [hWrev]
cases hx : encodeBlocks mid ++
(Block.toCells newCur ++
Block.toCells (freshFlagged side)) ++ G₇ with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons,
show ([TapeSymbol.blank] : List TapeSymbol) =
TapeSymbol.blank :: [] from rfl,
cellsTape_moveLeft, ← hcons, hWrev, ParkedTape]
have henc : encodeBlocks (mid ++ [newCur, freshFlagged side]) =
encodeBlocks mid ++ (Block.toCells newCur ++
Block.toCells (freshFlagged side)) := by
rw [encodeBlocks_append, encodeBlocks_cons, encodeBlocks_cons,
encodeBlocks_nil, List.append_nil]
rw [henc]
set T7 := Function.update T6 i
(ParkedTape (mid ++ [newCur, freshFlagged side]) G₇) with hT7
have htp7 : (((scanToBlank i HeadMove.left).step^[Wp.length * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
rw [scanToBlank_tape_of i HeadMove.left T6 Wp.length hlt heq, hT7]
show Function.update T6 i
((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)) = _
rw [hX7]
have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T6) (Wp.length * 4 + 3)
false := scanToBlank_spec_of i HeadMove.left T6 Wp.length hlt heq
have hC6 := chainStep (patchRun6_spec i (flagWindow side) T4 _ _ hR4)
htp6 hP7 htp7
have hC5 := chainStep h5 htp5 hC6.1 hC6.2
have hC4 := chainStep
(patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
hC5.1 hC5.2
have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
htp3 hC4.1 hC4.2
have hC2 := chainStep hw hwt hC3.1 hC3.2
have hC1 := chainStep
(moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
refine ⟨G₇, hG₇, hC1.1, ?_⟩
have hfin := hC1.2
rw [hT7, hT6, hT4, hT3, hT2, hT1] at hfin
simp only [scanTapesDir, Function.update_idem] at hfin
exact hfin
/-! ## The left variant, bounded — flag lands on an existing previous block -/
theorem updateTrack_left_concat_bounded (side : TrackSide) (i : Fin tapes)
(s : TapeSymbol) (mid' : List Block) (prv cur : Block)
(post : List Block)
(hmid : ∀ b ∈ mid' ++ [prv], side.getFlag b = false)
(hcur : side.getFlag cur = true) :
∃ cost, cost ≤ 100 * ((mid' ++ [prv]) ++ cur :: post).length + 300 ∧
∀ (G : List TapeSymbol) (tape : Fin tapes → Tape),
AllBlank G → tape i = ParkedTape ((mid' ++ [prv]) ++ cur :: post) G →
∃ G', AllBlank G' ∧
HaltsExactly (updateTrack side i s HeadMove.left)
((updateTrack side i s HeadMove.left).startCfg tape) cost false ∧
(((updateTrack side i s HeadMove.left).step^[cost])
((updateTrack side i s HeadMove.left).startCfg tape)).tape =
Function.update tape i
(ParkedTape (mid' ++ setFlag side true prv ::
setSymFlag side s false cur :: post) G') := by
classical
refine ⟨1 + 1 + ((loopCost (fun _ => blockReadSteps)
(mid' ++ [prv]).length + blockReadSteps) + 1 + (6 + 1 + (6 + 1 +
(12 + 1 + (6 + 1 +
((((Block.toCells (setFlag side true prv)).reverse ++
(encodeBlocks mid').reverse).length) * 4 + 3)))))), ?_, ?_⟩
· rw [loopCost_const, blockReadSteps_eq]
simp only [List.length_append, List.length_reverse,
Block.toCells_length, encodeBlocks_length, List.length_cons]
omega
intro G tape hG hi
have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
set newCur := setSymFlag side s false cur with hnewCur
set T1 : Fin tapes → Tape := Function.update tape i
(cellsTape [TapeSymbol.blank]
(encodeBlocks ((mid' ++ [prv]) ++ cur :: post) ++ G)) with hT1
have htp1 : (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg tape)).tape = T1 := by
rw [moveUpTo_tape i 1 HeadMove.right (by omega) tape, hT1]
congr 1
rw [Function.iterate_one, hi, ParkedTape]
exact cellsTape_moveRight _ _ _
have hT1i : T1 i = cellsTape [TapeSymbol.blank]
(encodeBlocks ((mid' ++ [prv]) ++ cur :: post) ++ G) := by
rw [hT1]; simp
obtain ⟨hw, -, hwt⟩ := walkToFlag_spec side i T1 [TapeSymbol.blank] G
(mid' ++ [prv]) cur post hmid hcur hT1i
set T2 := scanTapesDir T1 i HeadMove.right
(6 * ((mid' ++ [prv]).length + 1)) with hT2
have hsplit : encodeBlocks ((mid' ++ [prv]) ++ cur :: post) =
encodeBlocks ((mid' ++ [prv]) ++ [cur]) ++ encodeBlocks post := by
rw [← encodeBlocks_append]
congr 1
simp
have hT2i : T2 i =
cellsTape ((encodeBlocks ((mid' ++ [prv]) ++ [cur])).reverse ++
[TapeSymbol.blank])
(encodeBlocks post ++ G) := by
rw [hT2, scanTapesDir_self, hT1i, hsplit, List.append_assoc,
show 6 * ((mid' ++ [prv]).length + 1) =
(encodeBlocks ((mid' ++ [prv]) ++ [cur])).length by
rw [encodeBlocks_length]; simp,
cellsTape_advance]
obtain ⟨G₃, hG₃, hret3⟩ := retreat_block (Block.toCells cur).reverse
((encodeBlocks (mid' ++ [prv])).reverse ++ [TapeSymbol.blank]) post G hG
set T3 := Function.update T2 i
(cellsTape ((encodeBlocks (mid' ++ [prv])).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃))) with hT3
have htp3 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T2)).tape = T3 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T2, hT3]
congr 1
rw [hT2i,
show (encodeBlocks ((mid' ++ [prv]) ++ [cur])).reverse ++
[TapeSymbol.blank] =
(Block.toCells cur).reverse ++
((encodeBlocks (mid' ++ [prv])).reverse ++
[TapeSymbol.blank]) by
rw [encodeBlocks_append]
simp [List.reverse_append, encodeBlocks_cons],
show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
rw [hret3, List.reverse_reverse]
have hT3i : T3 i = cellsTape
((encodeBlocks (mid' ++ [prv])).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃)) := by
rw [hT3]; simp
set T4 := Function.update T3 i
(cellsTape ((Block.toCells newCur).reverse ++
((encodeBlocks (mid' ++ [prv])).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃)) with hT4
have htp4 : (((patchRun6 i (symWindow side s false)).step^[6])
((patchRun6 i (symWindow side s false)).startCfg T3)).tape = T4 := by
rw [patchRun6_tape i _ T3 _ _ hT3i, hT4]
congr 1
rw [patchCellsN_symWindow, ← hnewCur,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
List.drop_left]
have hT4i : T4 i = cellsTape
((Block.toCells newCur).reverse ++
((encodeBlocks (mid' ++ [prv])).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃) := by
rw [hT4]; simp
set sPrv := setFlag side true prv with hsPrv
have hL4 : (Block.toCells newCur).reverse ++
((encodeBlocks (mid' ++ [prv])).reverse ++ [TapeSymbol.blank]) =
((Block.toCells newCur).reverse ++ (Block.toCells prv).reverse) ++
((encodeBlocks mid').reverse ++ [TapeSymbol.blank]) := by
rw [encodeBlocks_append]
simp [List.reverse_append, encodeBlocks_cons, List.append_assoc]
obtain ⟨G₅, hG₅, hret5⟩ := retreat_block
((Block.toCells newCur).reverse ++ (Block.toCells prv).reverse)
((encodeBlocks mid').reverse ++ [TapeSymbol.blank]) post G₃ hG₃
set T5 := Function.update T4 i
(cellsTape ((encodeBlocks mid').reverse ++ [TapeSymbol.blank])
(Block.toCells prv ++ (Block.toCells newCur ++
(encodeBlocks post ++ G₅)))) with hT5
have htp5 : (((moveUpTo i 12 HeadMove.left).step^[12])
((moveUpTo i 12 HeadMove.left).startCfg T4)).tape = T5 := by
rw [moveUpTo_tape i 12 HeadMove.left (by omega) T4, hT5]
refine congrArg (Function.update T4 i) ?_
rw [hT4i, hL4,
show (12 : Nat) = ((Block.toCells newCur).reverse ++
(Block.toCells prv).reverse).length by
simp [Block.toCells_length]]
rw [hret5]
simp [List.reverse_append, List.append_assoc]
have hT5i : T5 i = cellsTape
((encodeBlocks mid').reverse ++ [TapeSymbol.blank])
(Block.toCells prv ++ (Block.toCells newCur ++
(encodeBlocks post ++ G₅))) := by
rw [hT5]; simp
set T6 := Function.update T5 i
(cellsTape ((Block.toCells sPrv).reverse ++
((encodeBlocks mid').reverse ++ [TapeSymbol.blank]))
(Block.toCells newCur ++ (encodeBlocks post ++ G₅))) with hT6
have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
((patchRun6 i (flagWindow side)).startCfg T5)).tape = T6 := by
rw [patchRun6_tape i _ T5 _ _ hT5i, hT6]
refine congrArg (Function.update T5 i) ?_
rw [patchCellsN_flagWindow, ← hsPrv,
show (6 : Nat) = (Block.toCells prv).length from
(Block.toCells_length prv).symm,
List.drop_left]
have hT6i : T6 i = cellsTape
((Block.toCells sPrv).reverse ++
((encodeBlocks mid').reverse ++ [TapeSymbol.blank]))
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
rw [hT6]; simp
set Wp := (Block.toCells sPrv).reverse ++ (encodeBlocks mid').reverse
with hWp
have hassoc : (Block.toCells sPrv).reverse ++
((encodeBlocks mid').reverse ++ [TapeSymbol.blank]) =
Wp ++ [TapeSymbol.blank] := by
rw [hWp, List.append_assoc]
have hWp_nb : ∀ c ∈ Wp, c ≠ TapeSymbol.blank := by
intro c hc
rw [hWp] at hc
rcases List.mem_append.mp hc with h | h
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h)
· exact encodeBlocks_ne_blank _ c (List.mem_reverse.mp h)
obtain ⟨hlt', heq'⟩ := blank_scan_left_spec (Wp ++ [TapeSymbol.blank])
((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).headD
TapeSymbol.blank)
((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).tail)
rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
have hlt : ∀ j, j < Wp.length →
((moveDir HeadMove.left)^[j + 1] (T6 i)).head ≠ TapeSymbol.blank := by
intro j hj
rw [hT6i, hassoc]
exact hlt' j hj
have heq : ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)).head =
TapeSymbol.blank := by
rw [hT6i, hassoc]
exact heq'
have hR6 : Block.toCells newCur ++ (encodeBlocks post ++ G₅) =
encodeBlocks (newCur :: post) ++ G₅ := by
rw [encodeBlocks_cons]
simp [List.append_assoc]
obtain ⟨G₇, hG₇, hret7⟩ := retreat_block Wp [TapeSymbol.blank]
(newCur :: post) G₅ hG₅
have hWrev : Wp.reverse = encodeBlocks mid' ++ Block.toCells sPrv := by
rw [hWp, List.reverse_append, List.reverse_reverse,
List.reverse_reverse]
have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
ParkedTape (mid' ++ sPrv :: newCur :: post) G₇ := by
rw [Function.iterate_succ_apply', hT6i, hassoc, hR6, hret7]
obtain ⟨r, R', hcons⟩ : ∃ r R',
Wp.reverse ++ (encodeBlocks (newCur :: post) ++ G₇) = r :: R' := by
rw [hWrev]
cases hx : encodeBlocks mid' ++ Block.toCells sPrv ++
(encodeBlocks (newCur :: post) ++ G₇) with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons,
show ([TapeSymbol.blank] : List TapeSymbol) =
TapeSymbol.blank :: [] from rfl,
cellsTape_moveLeft, ← hcons, hWrev, ParkedTape]
have henc : encodeBlocks (mid' ++ sPrv :: newCur :: post) =
encodeBlocks mid' ++ (Block.toCells sPrv ++
encodeBlocks (newCur :: post)) := by
rw [encodeBlocks_append, encodeBlocks_cons]
rw [henc]
simp [List.append_assoc]
set T7 := Function.update T6 i
(ParkedTape (mid' ++ sPrv :: newCur :: post) G₇) with hT7
have htp7 : (((scanToBlank i HeadMove.left).step^[Wp.length * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
rw [scanToBlank_tape_of i HeadMove.left T6 Wp.length hlt heq, hT7]
show Function.update T6 i
((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)) = _
rw [hX7]
have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T6) (Wp.length * 4 + 3)
false := scanToBlank_spec_of i HeadMove.left T6 Wp.length hlt heq
have hC6 := chainStep (patchRun6_spec i (flagWindow side) T5 _ _ hT5i)
htp6 hP7 htp7
have hC5 := chainStep (moveUpTo_spec i 12 HeadMove.left (by omega) T4)
htp5 hC6.1 hC6.2
have hC4 := chainStep
(patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
hC5.1 hC5.2
have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
htp3 hC4.1 hC4.2
have hC2 := chainStep hw hwt hC3.1 hC3.2
have hC1 := chainStep
(moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
refine ⟨G₇, hG₇, hC1.1, ?_⟩
have hfin := hC1.2
rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1] at hfin
simp only [scanTapesDir, Function.update_idem] at hfin
exact hfin
/-! ## The left variant, bounded — flag materialises before the region -/
theorem updateTrack_left_nil_bounded (side : TrackSide) (i : Fin tapes)
(s : TapeSymbol) (cur : Block) (post : List Block)
(hcur : side.getFlag cur = true) :
∃ cost, cost ≤ 100 * (cur :: post).length + 300 ∧
∀ (G : List TapeSymbol) (tape : Fin tapes → Tape),
AllBlank G → tape i = ParkedTape (cur :: post) G →
∃ G', AllBlank G' ∧
HaltsExactly (updateTrack side i s HeadMove.left)
((updateTrack side i s HeadMove.left).startCfg tape) cost false ∧
(((updateTrack side i s HeadMove.left).step^[cost])
((updateTrack side i s HeadMove.left).startCfg tape)).tape =
Function.update tape i
(ParkedTape (freshFlagged side ::
setSymFlag side s false cur :: post) G') := by
classical
refine ⟨1 + 1 + ((loopCost (fun _ => blockReadSteps) ([] : List Block).length +
blockReadSteps) + 1 + (6 + 1 + (6 + 1 + (12 + 1 + (6 + 1 +
(6 * 4 + 3)))))), ?_, ?_⟩
· rw [loopCost_const, blockReadSteps_eq]
simp only [List.length_cons, List.length_nil]
omega
intro G tape hG hi
have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
set newCur := setSymFlag side s false cur with hnewCur
have hmid : ∀ b ∈ ([] : List Block), side.getFlag b = false := by
intro b hb; simp at hb
set T1 : Fin tapes → Tape := Function.update tape i
(cellsTape [TapeSymbol.blank]
(encodeBlocks (cur :: post) ++ G)) with hT1
have htp1 : (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg tape)).tape = T1 := by
rw [moveUpTo_tape i 1 HeadMove.right (by omega) tape, hT1]
congr 1
rw [Function.iterate_one, hi, ParkedTape]
exact cellsTape_moveRight _ _ _
have hT1i : T1 i = cellsTape [TapeSymbol.blank]
(encodeBlocks ([] ++ cur :: post) ++ G) := by
rw [hT1]; simp
obtain ⟨hw, -, hwt⟩ := walkToFlag_spec side i T1 [TapeSymbol.blank] G
[] cur post hmid hcur hT1i
set T2 := scanTapesDir T1 i HeadMove.right
(6 * (([] : List Block).length + 1)) with hT2
have hT2i : T2 i =
cellsTape ((Block.toCells cur).reverse ++ [TapeSymbol.blank])
(encodeBlocks post ++ G) := by
rw [hT2, scanTapesDir_self, hT1i]
simp only [List.length_nil, List.nil_append, encodeBlocks_cons]
rw [show 6 * (0 + 1) = (Block.toCells cur).length by simp [hCl],
List.append_assoc]
exact cellsTape_advance (Block.toCells cur) [TapeSymbol.blank]
(encodeBlocks post ++ G)
obtain ⟨G₃, hG₃, hret3⟩ := retreat_block (Block.toCells cur).reverse
[TapeSymbol.blank] post G hG
set T3 := Function.update T2 i
(cellsTape [TapeSymbol.blank]
(Block.toCells cur ++ (encodeBlocks post ++ G₃))) with hT3
have htp3 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T2)).tape = T3 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T2, hT3]
congr 1
rw [hT2i,
show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
rw [hret3, List.reverse_reverse]
have hT3i : T3 i = cellsTape [TapeSymbol.blank]
(Block.toCells cur ++ (encodeBlocks post ++ G₃)) := by
rw [hT3]; simp
set T4 := Function.update T3 i
(cellsTape ((Block.toCells newCur).reverse ++ [TapeSymbol.blank])
(encodeBlocks post ++ G₃)) with hT4
have htp4 : (((patchRun6 i (symWindow side s false)).step^[6])
((patchRun6 i (symWindow side s false)).startCfg T3)).tape = T4 := by
rw [patchRun6_tape i _ T3 _ _ hT3i, hT4]
congr 1
rw [patchCellsN_symWindow, ← hnewCur,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
List.drop_left]
have hT4i : T4 i = cellsTape
((Block.toCells newCur).reverse ++ [TapeSymbol.blank])
(encodeBlocks post ++ G₃) := by
rw [hT4]; simp
obtain ⟨G₅, hG₅, hret5⟩ := retreat_block
((Block.toCells newCur).reverse ++ [TapeSymbol.blank]) [] post G₃ hG₃
have hret5' : (moveDir HeadMove.left)^[7]
(cellsTape ((Block.toCells newCur).reverse ++ [TapeSymbol.blank])
(encodeBlocks post ++ G₃)) =
cellsTape [] (TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅)) := by
have h7 : (7 : Nat) =
((Block.toCells newCur).reverse ++ [TapeSymbol.blank]).length := by
simp [Block.toCells_length]
rw [h7]
have h := hret5
rw [List.append_nil] at h
rw [h]
simp [List.reverse_append]
have hX5 : (moveDir HeadMove.left)^[12] (T4 i) =
cellsTape [] (List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅)) := by
rw [hT4i, show (12 : Nat) = 5 + 7 from rfl,
Function.iterate_add_apply, hret5']
exact cellsTape_retreat_past 5 TapeSymbol.blank
(Block.toCells newCur ++ (encodeBlocks post ++ G₅))
set T5 := Function.update T4 i
(cellsTape [] (List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅))) with hT5
have htp5 : (((moveUpTo i 12 HeadMove.left).step^[12])
((moveUpTo i 12 HeadMove.left).startCfg T4)).tape = T5 := by
rw [moveUpTo_tape i 12 HeadMove.left (by omega) T4, hT5]
exact congrArg (Function.update T4 i) hX5
have hT5i : T5 i = cellsTape []
(List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅)) := by
rw [hT5]; simp
have hR5eq : List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅) =
List.replicate 6 TapeSymbol.blank ++
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
rw [show List.replicate 6 TapeSymbol.blank =
List.replicate 5 TapeSymbol.blank ++ [TapeSymbol.blank] from
List.replicate_succ' .. ]
simp [List.append_assoc]
have hpatch : patchCellsN 6 (flagWindow side)
(List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅)) =
Block.toCells (freshFlagged side) := by
rw [hR5eq]
rw [patchCellsN_congr_prefix 6 (flagWindow side) _
(List.replicate 6 TapeSymbol.blank)
(by rw [List.take_left' (by simp), List.take_of_length_le (by simp)])]
exact patchCellsN_flagWindow_fresh side _
(fun c hc => (List.eq_of_mem_replicate hc))
have hdrop : (List.replicate 5 TapeSymbol.blank ++
TapeSymbol.blank :: Block.toCells newCur ++
(encodeBlocks post ++ G₅)).drop 6 =
Block.toCells newCur ++ (encodeBlocks post ++ G₅) := by
rw [hR5eq, List.drop_left' (by simp)]
set T6 := Function.update T5 i
(cellsTape ((Block.toCells (freshFlagged side)).reverse)
(Block.toCells newCur ++ (encodeBlocks post ++ G₅))) with hT6
have htp6 : (((patchRun6 i (flagWindow side)).step^[6])
((patchRun6 i (flagWindow side)).startCfg T5)).tape = T6 := by
rw [patchRun6_tape i _ T5 _ _ hT5i, hT6]
refine congrArg (Function.update T5 i) ?_
rw [hpatch, hdrop]
simp
have hT6i : T6 i = cellsTape
((Block.toCells (freshFlagged side)).reverse)
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) := by
rw [hT6]; simp
have hW_nb : ∀ c ∈ (Block.toCells (freshFlagged side)).reverse,
c ≠ TapeSymbol.blank := by
intro c hc
exact Block.toCells_ne_blank _ c (List.mem_reverse.mp hc)
obtain ⟨hlt', heq'⟩ := blank_scan_left_spec
((Block.toCells (freshFlagged side)).reverse)
((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).headD
TapeSymbol.blank)
((Block.toCells newCur ++ (encodeBlocks post ++ G₅)).tail)
rw [blankIndex_all _ hW_nb] at hlt' heq'
have hWl : ((Block.toCells (freshFlagged side)).reverse).length = 6 := by
simp [Block.toCells_length]
have hlt : ∀ j, j < 6 →
((moveDir HeadMove.left)^[j + 1] (T6 i)).head ≠ TapeSymbol.blank := by
intro j hj
rw [hT6i]
exact hlt' j (by omega)
have heq : ((moveDir HeadMove.left)^[6 + 1] (T6 i)).head =
TapeSymbol.blank := by
rw [hT6i]
have h := heq'
rw [hWl] at h
exact h
have hX7 : (moveDir HeadMove.left)^[6 + 1] (T6 i) =
ParkedTape (freshFlagged side :: newCur :: post) G₅ := by
rw [Function.iterate_succ_apply', hT6i]
obtain ⟨r, R', hcons⟩ : ∃ r R',
Block.toCells newCur ++ (encodeBlocks post ++ G₅) = r :: R' := by
cases hx : Block.toCells newCur ++ (encodeBlocks post ++ G₅) with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons, show (6 : Nat) =
((Block.toCells (freshFlagged side)).reverse).length from hWl.symm]
rw [cellsTape_retreat_nilL, List.reverse_reverse, ← hcons]
obtain ⟨r₂, R₂, hcons₂⟩ : ∃ r₂ R₂,
Block.toCells (freshFlagged side) ++
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) = r₂ :: R₂ := by
cases hx : Block.toCells (freshFlagged side) ++
(Block.toCells newCur ++ (encodeBlocks post ++ G₅)) with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons₂, cellsTape_moveLeft_nilL, ← hcons₂, ParkedTape]
simp [encodeBlocks_cons, List.append_assoc]
set T7 := Function.update T6 i
(ParkedTape (freshFlagged side :: newCur :: post) G₅) with hT7
have htp7 : (((scanToBlank i HeadMove.left).step^[6 * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
rw [scanToBlank_tape_of i HeadMove.left T6 6 hlt heq, hT7]
show Function.update T6 i
((moveDir HeadMove.left)^[6 + 1] (T6 i)) = _
rw [hX7]
have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T6) (6 * 4 + 3) false :=
scanToBlank_spec_of i HeadMove.left T6 6 hlt heq
have hC6 := chainStep (patchRun6_spec i (flagWindow side) T5 _ _ hT5i)
htp6 hP7 htp7
have hC5 := chainStep (moveUpTo_spec i 12 HeadMove.left (by omega) T4)
htp5 hC6.1 hC6.2
have hC4 := chainStep
(patchRun6_spec i (symWindow side s false) T3 _ _ hT3i) htp4
hC5.1 hC5.2
have hC3 := chainStep (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
htp3 hC4.1 hC4.2
have hC2 := chainStep hw hwt hC3.1 hC3.2
have hC1 := chainStep
(moveUpTo_spec i 1 HeadMove.right (by omega) tape) htp1 hC2.1 hC2.2
refine ⟨G₅, hG₅, hC1.1, ?_⟩
have hfin := hC1.2
rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1] at hfin
simp only [scanTapesDir, Function.update_idem] at hfin
exact hfin
/-! ## The read phase, bounded and ghost-uniform
The published `readPhase_spec` quantifies the ghost *outside* the cost, so each
ghost yields its own opaque cost and a nested phase has no fixed `k` to hand
its continuation. Here the cost comes first and the ghost and tape are
introduced inside — which is exactly the shape `hcont` consumes, so read
phases nest. -/
theorem readPhase_bounded (side : TrackSide) (i : Fin tapes) {S : Type}
(cont : TapeSymbol → TypedMachine tapes S)
(mid : List Block) (cur : Block) (post : List Block)
(hmid : ∀ b ∈ mid, side.getFlag b = false)
(hcur : side.getFlag cur = true)
(k : Nat) (v : Bool)
(hcontU : ∀ (G' : List TapeSymbol) (T : Fin tapes → Tape),
AllBlank G' → T i = ParkedTape (mid ++ cur :: post) G' →
HaltsExactly (cont (side.pick cur)) ((cont (side.pick cur)).startCfg T)
k v) :
∃ cost, cost ≤ 100 * (mid ++ cur :: post).length + 300 + k ∧
∀ (G : List TapeSymbol) (tape : Fin tapes → Tape),
AllBlank G → tape i = ParkedTape (mid ++ cur :: post) G →
∃ G', AllBlank G' ∧
HaltsExactly (readPhase side i cont)
((readPhase side i cont).startCfg tape) cost v ∧
((readPhase side i cont).step^[cost])
((readPhase side i cont).startCfg tape) =
TypedConfiguration.inRight true (TypedConfiguration.inRight false
(TypedConfiguration.inRight true (TypedConfiguration.inRight
(sideBit1 side cur) (TypedConfiguration.inRight true
(TypedConfiguration.inRight (sideBit2 side cur)
(TypedConfiguration.inRight false
(((cont (side.pick cur)).step^[k])
((cont (side.pick cur)).startCfg
(Function.update tape i
(ParkedTape (mid ++ cur :: post) G')))))))))) := by
refine ⟨1 + 1 + ((loopCost (fun _ => blockReadSteps) mid.length +
blockReadSteps) + 1 + (6 + 1 + (blockReadSteps + 1 + (6 + 1 +
(blockReadSteps + 1 +
((((Block.toCells cur).reverse ++
(encodeBlocks mid).reverse).length) * 4 + 3 + 1 + k)))))), ?_, ?_⟩
· rw [loopCost_const, blockReadSteps_eq]
simp only [List.length_append, List.length_reverse,
Block.toCells_length, encodeBlocks_length, List.length_cons]
omega
intro G tape hG hi
have hcont : ∀ (G' : List TapeSymbol), AllBlank G' →
HaltsExactly (cont (side.pick cur))
((cont (side.pick cur)).startCfg
(Function.update tape i (ParkedTape (mid ++ cur :: post) G'))) k v :=
fun G' hG' => hcontU G' _ hG' (by simp)
classical
have hCl : (Block.toCells cur).length = 6 := Block.toCells_length cur
-- ===== junction 1: enter =====
set T1 : Fin tapes → Tape := Function.update tape i
(cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: post) ++ G)) with hT1
have htp1 : (((moveUpTo i 1 HeadMove.right).step^[1])
((moveUpTo i 1 HeadMove.right).startCfg tape)).tape = T1 := by
rw [moveUpTo_tape i 1 HeadMove.right (by omega) tape, hT1]
congr 1
rw [Function.iterate_one, hi, ParkedTape]
exact cellsTape_moveRight _ _ _
have hT1i : T1 i = cellsTape [TapeSymbol.blank]
(encodeBlocks (mid ++ cur :: post) ++ G) := by
rw [hT1]; simp
-- ===== junction 2: walk =====
obtain ⟨hw, -, hwt⟩ := walkToFlag_spec side i T1 [TapeSymbol.blank] G
mid cur post hmid hcur hT1i
set W1 := loopCost (fun _ => blockReadSteps) mid.length + blockReadSteps
with hW1
set T2 := scanTapesDir T1 i HeadMove.right (6 * (mid.length + 1)) with hT2
have hsplit : encodeBlocks (mid ++ cur :: post) =
encodeBlocks (mid ++ [cur]) ++ encodeBlocks post := by
rw [← encodeBlocks_append]
congr 1
simp
have hT2i : T2 i =
cellsTape ((encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank])
(encodeBlocks post ++ G) := by
rw [hT2, scanTapesDir_self, hT1i, hsplit, List.append_assoc,
show 6 * (mid.length + 1) = (encodeBlocks (mid ++ [cur])).length by
rw [encodeBlocks_length]; simp,
cellsTape_advance]
-- ===== junction 3: back to the flagged block =====
obtain ⟨G₃, hG₃, hret3⟩ := retreat_block (Block.toCells cur).reverse
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G hG
set T3 := Function.update T2 i
(cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃))) with hT3
have htp3 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T2)).tape = T3 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T2, hT3]
congr 1
rw [hT2i,
show (encodeBlocks (mid ++ [cur])).reverse ++ [TapeSymbol.blank] =
(Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) by
rw [encodeBlocks_append]
simp [List.reverse_append, encodeBlocks_cons],
show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
rw [hret3, List.reverse_reverse]
have hT3i : T3 i = cellsTape
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₃)) := by
rw [hT3]; simp
-- ===== junction 4: first probe =====
have hread1 : HaltsExactly (blockRead i (sideBit1 side))
((blockRead i (sideBit1 side)).startCfg T3) blockReadSteps
(sideBit1 side cur) := by
have h := blockRead_spec i (sideBit1 side) T3
rwa [blockOfCells_cellsTape i T3 _ _ cur hT3i] at h
set T4 := Function.update T3 i
(cellsTape ((Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃)) with hT4
have htp4 : (((blockRead i (sideBit1 side)).step^[blockReadSteps])
((blockRead i (sideBit1 side)).startCfg T3)).tape = T4 := by
have h := blockRead_tape i (sideBit1 side) T3
rw [show (blockRead i (sideBit1 side)).startCfg T3 =
TypedConfiguration.inLeftState
((readCellRight i).startCfg T3) from rfl] at *
rw [h, hT4]
funext j
by_cases hj : j = i
· subst hj
rw [scanTapesDir_self, hT3i,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
cellsTape_advance]
simp
· simp [scanTapesDir, hj]
have hT4i : T4 i = cellsTape
((Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₃) := by
rw [hT4]; simp
-- ===== junction 5: back again =====
obtain ⟨G₅, hG₅, hret5⟩ := retreat_block (Block.toCells cur).reverse
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) post G₃ hG₃
set T5 := Function.update T4 i
(cellsTape ((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₅))) with hT5
have htp5 : (((moveUpTo i 6 HeadMove.left).step^[6])
((moveUpTo i 6 HeadMove.left).startCfg T4)).tape = T5 := by
rw [moveUpTo_tape i 6 HeadMove.left (by omega) T4, hT5]
congr 1
rw [hT4i,
show (6 : Nat) = ((Block.toCells cur).reverse).length by simp [hCl]]
rw [hret5, List.reverse_reverse]
have hT5i : T5 i = cellsTape
((encodeBlocks mid).reverse ++ [TapeSymbol.blank])
(Block.toCells cur ++ (encodeBlocks post ++ G₅)) := by
rw [hT5]; simp
-- ===== junction 6: second probe =====
have hread2 : HaltsExactly (blockRead i (sideBit2 side))
((blockRead i (sideBit2 side)).startCfg T5) blockReadSteps
(sideBit2 side cur) := by
have h := blockRead_spec i (sideBit2 side) T5
rwa [blockOfCells_cellsTape i T5 _ _ cur hT5i] at h
set T6 := Function.update T5 i
(cellsTape ((Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₅)) with hT6
have htp6 : (((blockRead i (sideBit2 side)).step^[blockReadSteps])
((blockRead i (sideBit2 side)).startCfg T5)).tape = T6 := by
have h := blockRead_tape i (sideBit2 side) T5
rw [show (blockRead i (sideBit2 side)).startCfg T5 =
TypedConfiguration.inLeftState
((readCellRight i).startCfg T5) from rfl] at *
rw [h, hT6]
funext j
by_cases hj : j = i
· subst hj
rw [scanTapesDir_self, hT5i,
show (6 : Nat) = (Block.toCells cur).length from hCl.symm,
cellsTape_advance]
simp
· simp [scanTapesDir, hj]
have hT6i : T6 i = cellsTape
((Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]))
(encodeBlocks post ++ G₅) := by
rw [hT6]; simp
-- ===== junction 7: park =====
set Wp := (Block.toCells cur).reverse ++ (encodeBlocks mid).reverse
with hWp
have hassoc : (Block.toCells cur).reverse ++
((encodeBlocks mid).reverse ++ [TapeSymbol.blank]) =
Wp ++ [TapeSymbol.blank] := by
rw [hWp, List.append_assoc]
have hWp_nb : ∀ c ∈ Wp, c ≠ TapeSymbol.blank := by
intro c hc
rw [hWp] at hc
rcases List.mem_append.mp hc with h | h
· exact Block.toCells_ne_blank _ c (List.mem_reverse.mp h)
· exact encodeBlocks_ne_blank _ c (List.mem_reverse.mp h)
obtain ⟨hlt', heq'⟩ := blank_scan_left_spec (Wp ++ [TapeSymbol.blank])
((encodeBlocks post ++ G₅).headD TapeSymbol.blank)
((encodeBlocks post ++ G₅).tail)
rw [blankIndex_written Wp [] hWp_nb] at hlt' heq'
have hlt : ∀ j, j < Wp.length →
((moveDir HeadMove.left)^[j + 1] (T6 i)).head ≠ TapeSymbol.blank := by
intro j hj
rw [hT6i, hassoc]
exact hlt' j hj
have heq : ((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)).head =
TapeSymbol.blank := by
rw [hT6i, hassoc]
exact heq'
obtain ⟨G₇, hG₇, hret7⟩ := retreat_block Wp [TapeSymbol.blank] post G₅ hG₅
have hWrev : Wp.reverse = encodeBlocks mid ++ Block.toCells cur := by
rw [hWp, List.reverse_append, List.reverse_reverse, List.reverse_reverse]
have hX7 : (moveDir HeadMove.left)^[Wp.length + 1] (T6 i) =
ParkedTape (mid ++ cur :: post) G₇ := by
rw [Function.iterate_succ_apply', hT6i, hassoc, hret7]
obtain ⟨r, R', hcons⟩ : ∃ r R',
Wp.reverse ++ (encodeBlocks post ++ G₇) = r :: R' := by
rw [hWrev]
cases hx : encodeBlocks mid ++ Block.toCells cur ++
(encodeBlocks post ++ G₇) with
| nil =>
exfalso
have := congrArg List.length hx
simp [Block.toCells] at this
| cons a as => exact ⟨a, as, rfl⟩
rw [hcons,
show ([TapeSymbol.blank] : List TapeSymbol) =
TapeSymbol.blank :: [] from rfl,
cellsTape_moveLeft, ← hcons, hWrev, ParkedTape]
have henc : encodeBlocks (mid ++ cur :: post) =
encodeBlocks mid ++ (Block.toCells cur ++ encodeBlocks post) := by
rw [encodeBlocks_append, encodeBlocks_cons]
rw [henc]
simp [List.append_assoc]
set T7 := Function.update T6 i (ParkedTape (mid ++ cur :: post) G₇)
with hT7
have htp7 : (((scanToBlank i HeadMove.left).step^[Wp.length * 4 + 3])
((scanToBlank i HeadMove.left).startCfg T6)).tape = T7 := by
rw [scanToBlank_tape_of i HeadMove.left T6 Wp.length hlt heq, hT7]
show Function.update T6 i
((moveDir HeadMove.left)^[Wp.length + 1] (T6 i)) = _
rw [hX7]
have hP7 : HaltsExactly (scanToBlank i HeadMove.left)
((scanToBlank i HeadMove.left).startCfg T6) (Wp.length * 4 + 3)
false := scanToBlank_spec_of i HeadMove.left T6 Wp.length hlt heq
-- ===== the continuation's start =====
have hT7flat : T7 = Function.update tape i
(ParkedTape (mid ++ cur :: post) G₇) := by
rw [hT7, hT6, hT5, hT4, hT3, hT2, hT1]
simp only [scanTapesDir, Function.update_idem]
have hK := hcont G₇ hG₇
rw [← hT7flat] at hK
-- ===== assemble, inside out =====
have hsym : symbolOfBits (sideBit1 side cur) (sideBit2 side cur) =
side.pick cur := symbolOfBits_decode side cur
have hC7 := chainStepD
(M₂ := fun _ => cont (symbolOfBits (sideBit1 side cur)
(sideBit2 side cur)))
hP7 htp7 (by rw [hsym]; exact hK)
have hC6 := chainStepD
(M₂ := fun b₂ => (scanToBlank i HeadMove.left).andThen fun _ =>
cont (symbolOfBits (sideBit1 side cur) b₂))
hread2 htp6 hC7.1
have hC5 := chainStepC (moveUpTo_spec i 6 HeadMove.left (by omega) T4)
htp5 hC6.1
have hC4 := chainStepD
(M₂ := fun b₁ => (moveUpTo i 6 HeadMove.left).andThen fun _ =>
(blockRead i (sideBit2 side)).andThen fun b₂ =>
(scanToBlank i HeadMove.left).andThen fun _ =>
cont (symbolOfBits b₁ b₂))
hread1 htp4 hC5.1
have hC3 := chainStepC (moveUpTo_spec i 6 HeadMove.left (by omega) T2)
htp3 hC4.1
have hC2 := chainStepC hw hwt hC3.1
have hC1 := chainStepC (moveUpTo_spec i 1 HeadMove.right (by omega) tape)
htp1 hC2.1
rw [show cont (side.pick cur) = cont (symbolOfBits (sideBit1 side cur)
(sideBit2 side cur)) by rw [hsym]]
refine ⟨G₇, hG₇, hC1.1, ?_⟩
have hfin := hC1.2
rw [hC2.2] at hfin
rw [hC3.2] at hfin
rw [hC4.2] at hfin
rw [hC5.2] at hfin
rw [hC6.2] at hfin
rw [hC7.2] at hfin
rw [hT7flat] at hfin
exact hfin
end SipserGacsLautemann