SGL zigzag local correctness
Definitionsgl_zigzag_correctnesscomplexity-theorysipser-gacs-lautemannturing-machines
This auxiliary module proves the local scan and update correctness lemmas for the zigzag simulator. The results identify the encoded physical tape representation with the intended virtual tape contents after each scan or update phase.
Definition code
import Definitions.Def_sgl_zigzag_simulator
import Mathlib.Data.List.GetD
namespace SipserGacsLautemann
/-- The fixed zigzag enumeration
`0, +1, -1, +2, -2, ...` used by the simulator. -/
def zigzagCoordinate : Nat → Int
| 0 => 0
| n + 1 =>
if n % 2 = 0 then
Int.ofNat (n / 2 + 1)
else
Int.negSucc (n / 2)
/-- The inverse index of an integer in the zigzag enumeration. -/
def zigzagIndex : Int → Nat
| .ofNat n =>
if n = 0 then 0 else 2 * (n - 1) + 1
| .negSucc n => 2 * n + 2
@[simp]
theorem zigzagCoordinate_zero :
zigzagCoordinate 0 = 0 := rfl
@[simp]
theorem zigzagCoordinate_positive (n : Nat) :
zigzagCoordinate (2 * n + 1) = Int.ofNat (n + 1) := by
simp [zigzagCoordinate]
@[simp]
theorem zigzagCoordinate_negative (n : Nat) :
zigzagCoordinate (2 * n + 2) = Int.negSucc n := by
have hrewrite : 2 * n + 2 = (2 * n + 1) + 1 := by omega
rw [hrewrite]
simp [zigzagCoordinate]
omega
@[simp]
theorem zigzagCoordinate_index (coordinate : Int) :
zigzagCoordinate (zigzagIndex coordinate) = coordinate := by
cases coordinate with
| ofNat n =>
cases n with
| zero => rfl
| succ n => simp [zigzagIndex]
| negSucc n =>
simp [zigzagIndex]
@[simp]
theorem zigzagIndex_coordinate (index : Nat) :
zigzagIndex (zigzagCoordinate index) = index := by
cases index with
| zero => rfl
| succ predecessor =>
rcases Nat.mod_two_eq_zero_or_one predecessor with
heven | hodd
· have hdecompose :=
Nat.mod_add_div predecessor 2
rw [show
zigzagCoordinate (predecessor + 1) =
Int.ofNat (predecessor / 2 + 1) by
simp only [zigzagCoordinate, heven, if_true]]
change
(if predecessor / 2 + 1 = 0 then 0
else 2 * (predecessor / 2 + 1 - 1) + 1) =
predecessor + 1
rw [if_neg (by omega)]
omega
· have hdecompose :=
Nat.mod_add_div predecessor 2
rw [show
zigzagCoordinate (predecessor + 1) =
Int.negSucc (predecessor / 2) by
simp only [zigzagCoordinate, hodd,
one_ne_zero, if_false]]
change
2 * (predecessor / 2) + 2 =
predecessor + 1
omega
theorem zigzagIndex_injective :
Function.Injective zigzagIndex := by
intro a b equality
have := congrArg zigzagCoordinate equality
simpa using this
theorem zigzagCoordinate_injective :
Function.Injective zigzagCoordinate := by
intro a b equality
have := congrArg zigzagIndex equality
simpa using this
/-- Read a zipper tape at an integer offset from its current head. -/
def Tape.readRelative (tape : Tape) : Int → TapeSymbol
| .ofNat 0 => tape.head
| .ofNat (n + 1) => tape.right.getD n .blank
| .negSucc n => tape.left.getD n .blank
@[simp]
theorem Tape.readRelative_zero (tape : Tape) :
tape.readRelative 0 = tape.head := rfl
@[simp]
theorem Tape.readRelative_ofNat_succ
(tape : Tape) (n : Nat) :
tape.readRelative (Int.ofNat (n + 1)) =
tape.right.getD n .blank := rfl
@[simp]
theorem Tape.readRelative_negSucc
(tape : Tape) (n : Nat) :
tape.readRelative (Int.negSucc n) =
tape.left.getD n .blank := rfl
theorem Tape.readRelative_write
(tape : Tape) (write : TapeSymbol) (offset : Int) :
(tape.write write).readRelative offset =
if offset = 0 then write else tape.readRelative offset := by
cases tape with
| mk left head right =>
cases offset with
| ofNat n =>
cases n with
| zero => simp [Tape.readRelative, Tape.write]
| succ n =>
have hnonzero : (n : Int) + 1 ≠ 0 := by omega
simp [Tape.readRelative, Tape.write,
Int.ofNat_eq_coe, hnonzero]
| negSucc n =>
simp [Tape.readRelative, Tape.write]
theorem Tape.readRelative_move_right
(tape : Tape) (offset : Int) :
(tape.move .right).readRelative offset =
tape.readRelative (offset + 1) := by
cases tape with
| mk left head right =>
cases right with
| nil =>
cases offset with
| ofNat n =>
cases n with
| zero => rfl
| succ n =>
have h :
(Int.ofNat (n + 1) : Int) + 1 =
Int.ofNat (n + 2) := by
rw [Int.ofNat_eq_coe, Int.ofNat_eq_coe]
omega
rw [h]
rfl
| negSucc n =>
cases n with
| zero => rfl
| succ n =>
have h :
Int.negSucc (n + 1) + 1 =
Int.negSucc n := by omega
rw [h]
simp [Tape.readRelative, Tape.move,
List.getD]
| cons next rest =>
cases offset with
| ofNat n =>
cases n with
| zero => rfl
| succ n =>
have h :
(Int.ofNat (n + 1) : Int) + 1 =
Int.ofNat (n + 2) := by
rw [Int.ofNat_eq_coe, Int.ofNat_eq_coe]
omega
rw [h]
simp [Tape.readRelative, Tape.move,
List.getD]
| negSucc n =>
cases n with
| zero => rfl
| succ n =>
have h :
Int.negSucc (n + 1) + 1 =
Int.negSucc n := by omega
rw [h]
simp [Tape.readRelative, Tape.move,
List.getD]
theorem Tape.readRelative_move_left
(tape : Tape) (offset : Int) :
(tape.move .left).readRelative offset =
tape.readRelative (offset - 1) := by
cases tape with
| mk left head right =>
cases left with
| nil =>
cases offset with
| ofNat n =>
cases n with
| zero => rfl
| succ n =>
have h :
(Int.ofNat (n + 1) : Int) - 1 =
Int.ofNat n := by
rw [Int.ofNat_eq_coe, Int.ofNat_eq_coe]
omega
rw [h]
cases n <;>
simp [Tape.readRelative, Tape.move,
List.getD]
| negSucc n =>
cases n with
| zero => rfl
| succ n =>
have h :
Int.negSucc (n + 1) - 1 =
Int.negSucc (n + 2) := by omega
rw [h]
rfl
| cons previous rest =>
cases offset with
| ofNat n =>
cases n with
| zero => rfl
| succ n =>
have h :
(Int.ofNat (n + 1) : Int) - 1 =
Int.ofNat n := by
rw [Int.ofNat_eq_coe, Int.ofNat_eq_coe]
omega
rw [h]
cases n <;>
simp [Tape.readRelative, Tape.move,
List.getD]
| negSucc n =>
cases n with
| zero => rfl
| succ n =>
have h :
Int.negSucc (n + 1) - 1 =
Int.negSucc (n + 2) := by omega
rw [h]
simp [Tape.readRelative, Tape.move,
List.getD]
def HeadMove.displacement : HeadMove → Int
| .left => -1
| .stay => 0
| .right => 1
def HeadMove.updatePosition
(move : HeadMove) (position : Int) : Int :=
position + move.displacement
theorem Tape.readRelative_move_recenter
(tape : Tape) (move : HeadMove) (offset : Int) :
(tape.move move).readRelative offset =
tape.readRelative (offset + move.displacement) := by
cases move with
| left =>
simpa [HeadMove.displacement, sub_eq_add_neg,
add_assoc] using tape.readRelative_move_left offset
| stay =>
simp [HeadMove.displacement, Tape.move]
| right =>
simpa [HeadMove.displacement] using
tape.readRelative_move_right offset
def zigzagRecordFlag (position : Int) (index : Nat) : Bool :=
decide (index = zigzagIndex position)
def zigzagRecordSymbol
(tape : Tape) (position : Int) (index : Nat) :
TapeSymbol :=
tape.readRelative (zigzagCoordinate index - position)
def zigzagRecordBits
(tape : Tape) (position : Int) (index : Nat) :
List Bool :=
[zigzagRecordFlag position index,
(encodeTapeSymbol
(zigzagRecordSymbol tape position index)).1,
(encodeTapeSymbol
(zigzagRecordSymbol tape position index)).2]
def zigzagWorkBitsFrom
(tape : Tape) (position : Int) (firstIndex : Nat) :
Nat → List Bool
| 0 => []
| recordCount + 1 =>
zigzagRecordBits tape position firstIndex ++
zigzagWorkBitsFrom tape position
(firstIndex + 1) recordCount
def zigzagWorkBits
(tape : Tape) (position : Int) (recordCount : Nat) :
List Bool :=
zigzagWorkBitsFrom tape position 0 recordCount
@[simp]
theorem zigzagWorkBitsFrom_zero
(tape : Tape) (position : Int) (firstIndex : Nat) :
zigzagWorkBitsFrom tape position firstIndex 0 = [] := rfl
@[simp]
theorem zigzagWorkBitsFrom_succ
(tape : Tape) (position : Int)
(firstIndex recordCount : Nat) :
zigzagWorkBitsFrom tape position firstIndex
(recordCount + 1) =
zigzagRecordBits tape position firstIndex ++
zigzagWorkBitsFrom tape position
(firstIndex + 1) recordCount := rfl
@[simp]
theorem zigzagRecordBits_length
(tape : Tape) (position : Int) (index : Nat) :
(zigzagRecordBits tape position index).length = 3 := by
simp [zigzagRecordBits]
@[simp]
theorem zigzagWorkBitsFrom_length
(tape : Tape) (position : Int)
(firstIndex recordCount : Nat) :
(zigzagWorkBitsFrom tape position
firstIndex recordCount).length =
3 * recordCount := by
induction recordCount generalizing firstIndex with
| zero => rfl
| succ recordCount ih =>
simp [zigzagWorkBitsFrom, ih]
omega
@[simp]
theorem zigzagWorkBits_length
(tape : Tape) (position : Int) (recordCount : Nat) :
(zigzagWorkBits tape position recordCount).length =
3 * recordCount := by
simp [zigzagWorkBits]
def zigzagPhysicalTape
(archive : List TapeSymbol)
(tape : Tape) (position : Int) (recordCount : Nat) :
Tape where
left := archive
head := .blank
right :=
(zigzagWorkBits tape position recordCount).map .bit
def ZigzagEncodingCovers
(tape : Tape) (position : Int) (recordCount : Nat) :
Prop :=
zigzagIndex position < recordCount ∧
∀ offset : Int,
tape.readRelative offset ≠ .blank →
zigzagIndex (position + offset) < recordCount
theorem zigzagRecordSymbol_at_head
(tape : Tape) (position : Int) :
zigzagRecordSymbol tape position (zigzagIndex position) =
tape.head := by
simp [zigzagRecordSymbol]
theorem zigzagRecordFlag_eq_true_iff
(position : Int) (index : Nat) :
zigzagRecordFlag position index = true ↔
index = zigzagIndex position := by
simp [zigzagRecordFlag]
def applyPhysicalAction
(tape : Tape) (action : TapeSymbol × HeadMove) : Tape :=
(tape.write action.1).move action.2
def zigzagScanConfigurationStep
(configuration : ZigzagScanLocal × Tape) :
ZigzagScanLocal × Tape :=
let action :=
zigzagScanLocalStep configuration.1
configuration.2.head
(action.1,
applyPhysicalAction configuration.2 action.2)
def returningScanTape
(towardCenter archive : List TapeSymbol)
(current : TapeSymbol) (outward : List TapeSymbol) :
Tape :=
⟨towardCenter ++ .blank :: archive,
current, outward⟩
theorem zigzagScan_returning_move
(cached : TapeSymbol) (indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(current : Bool) (outward : List TapeSymbol) :
zigzagScanConfigurationStep
(.returning cached indexClass,
returningScanTape towardCenter archive
(.bit current) outward) =
match towardCenter with
| [] =>
(.returning cached indexClass,
⟨archive, .blank, .bit current :: outward⟩)
| next :: rest =>
(.returning cached indexClass,
returningScanTape rest archive next
(.bit current :: outward)) := by
cases towardCenter <;>
rfl
theorem zigzagScan_returning_blank
(cached : TapeSymbol) (indexClass : ZigzagIndexClass)
(archive outward : List TapeSymbol) :
zigzagScanConfigurationStep
(.returning cached indexClass,
⟨archive, .blank, outward⟩) =
(.done cached indexClass,
⟨archive, .blank, outward⟩) := by
rfl
theorem zigzagScan_iterate_returning
(cached : TapeSymbol) (indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(current : Bool) (outward : List TapeSymbol)
(hbits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
(zigzagScanConfigurationStep ^[
towardCenter.length + 2])
(.returning cached indexClass,
returningScanTape towardCenter archive
(.bit current) outward) =
(.done cached indexClass,
⟨archive, .blank,
towardCenter.reverse ++
.bit current :: outward⟩) := by
induction towardCenter generalizing current outward with
| nil =>
simp only [List.length_nil, zero_add,
Function.iterate_succ_apply,
Function.iterate_one]
rw [zigzagScan_returning_move]
exact zigzagScan_returning_blank
cached indexClass archive
(.bit current :: outward)
| cons next rest ih =>
have htime :
(next :: rest).length + 2 =
(rest.length + 2) + 1 := by simp
obtain ⟨nextBit, rfl⟩ :=
hbits next (by simp)
have hrest :
∀ symbol ∈ rest,
∃ bit, symbol = .bit bit := by
intro symbol hsymbol
exact hbits symbol (by simp [hsymbol])
rw [htime, Function.iterate_succ_apply]
rw [zigzagScan_returning_move]
rw [ih nextBit (.bit current :: outward) hrest]
simp
def falseZigzagRecordSymbols
(bits : Bool × Bool) : List TapeSymbol :=
[.bit false, .bit bits.1, .bit bits.2]
def falseZigzagRecordsSymbols
(records : List (Bool × Bool)) : List TapeSymbol :=
records.flatMap falseZigzagRecordSymbols
def focusedBitTape
(towardCenter archive : List TapeSymbol)
(current : Bool) (outward : List TapeSymbol) :
Tape :=
⟨towardCenter ++ .blank :: archive,
.bit current, outward⟩
theorem zigzagScan_false_record_three_steps
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(first second nextFlag : Bool)
(outward : List TapeSymbol) :
(zigzagScanConfigurationStep^[3])
(.atFlag indexClass,
focusedBitTape towardCenter archive false
(.bit first :: .bit second ::
.bit nextFlag :: outward)) =
(.atFlag indexClass.next,
focusedBitTape
(.bit second :: .bit first ::
.bit false :: towardCenter)
archive nextFlag outward) := by
rfl
theorem zigzagScan_marker_three_steps
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(first second : Bool)
(outward : List TapeSymbol) :
(zigzagScanConfigurationStep^[3])
(.atFlag indexClass,
focusedBitTape towardCenter archive true
(.bit first :: .bit second :: outward)) =
(.returning
(decodeTapeSymbol (first, second)) indexClass,
focusedBitTape
(.bit true :: towardCenter)
archive first (.bit second :: outward)) := by
rfl
theorem falseZigzagRecordsSymbols_all_bits
(records : List (Bool × Bool)) :
∀ symbol ∈ falseZigzagRecordsSymbols records,
∃ bit, symbol = .bit bit := by
intro symbol hsymbol
induction records with
| nil =>
simp [falseZigzagRecordsSymbols] at hsymbol
| cons record records ih =>
simp only [falseZigzagRecordsSymbols,
List.flatMap_cons,
falseZigzagRecordSymbols] at hsymbol
simp only [List.mem_append, List.mem_cons,
List.not_mem_nil, or_false] at hsymbol
rcases hsymbol with hrecord | hsymbol
· rcases hrecord with hfalse | hfirst | hsecond
· subst symbol
exact ⟨false, rfl⟩
· subst symbol
exact ⟨record.1, rfl⟩
· subst symbol
exact ⟨record.2, rfl⟩
· exact ih hsymbol
def zigzagScanRecordStream
(records : List (Bool × Bool))
(markerFirst markerSecond : Bool)
(outward : List TapeSymbol) : List TapeSymbol :=
falseZigzagRecordsSymbols records ++
[.bit true, .bit markerFirst, .bit markerSecond] ++
outward
def zigzagScanStreamFlag :
List (Bool × Bool) → Bool
| [] => true
| _ :: _ => false
def zigzagScanStreamAfterFlag
(records : List (Bool × Bool))
(markerFirst markerSecond : Bool)
(outward : List TapeSymbol) : List TapeSymbol :=
match records with
| [] =>
[.bit markerFirst, .bit markerSecond] ++ outward
| (first, second) :: rest =>
[.bit first, .bit second] ++
zigzagScanRecordStream rest
markerFirst markerSecond outward
theorem zigzagScanRecordStream_eq
(records : List (Bool × Bool))
(markerFirst markerSecond : Bool)
(outward : List TapeSymbol) :
zigzagScanRecordStream records
markerFirst markerSecond outward =
.bit (zigzagScanStreamFlag records) ::
zigzagScanStreamAfterFlag records
markerFirst markerSecond outward := by
cases records <;>
simp [zigzagScanRecordStream,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
falseZigzagRecordsSymbols,
falseZigzagRecordSymbols]
theorem zigzagScanRecordStream_cons
(first second : Bool)
(records : List (Bool × Bool))
(markerFirst markerSecond : Bool)
(outward : List TapeSymbol) :
zigzagScanRecordStream
((first, second) :: records)
markerFirst markerSecond outward =
[.bit false, .bit first, .bit second] ++
zigzagScanRecordStream records
markerFirst markerSecond outward := by
simp [zigzagScanRecordStream,
falseZigzagRecordsSymbols,
falseZigzagRecordSymbols,
List.append_assoc]
def focusedScanStreamTape
(towardCenter archive : List TapeSymbol)
(records : List (Bool × Bool))
(markerFirst markerSecond : Bool)
(outward : List TapeSymbol) : Tape :=
focusedBitTape towardCenter archive
(zigzagScanStreamFlag records)
(zigzagScanStreamAfterFlag records
markerFirst markerSecond outward)
theorem zigzagScanRecordStream_move_right
(archive : List TapeSymbol)
(records : List (Bool × Bool))
(markerFirst markerSecond : Bool)
(outward : List TapeSymbol) :
Tape.move
⟨archive, .blank,
zigzagScanRecordStream records
markerFirst markerSecond outward⟩
.right =
focusedScanStreamTape [] archive records
markerFirst markerSecond outward := by
rw [zigzagScanRecordStream_eq]
cases records <;> rfl
theorem zigzagScan_iterate_records_marker
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(records : List (Bool × Bool))
(markerFirst markerSecond : Bool)
(outward : List TapeSymbol)
(hcenterBits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
(zigzagScanConfigurationStep^[
6 * records.length + towardCenter.length + 6])
(.atFlag indexClass,
focusedScanStreamTape towardCenter archive
records markerFirst markerSecond outward) =
(.done (decodeTapeSymbol
(markerFirst, markerSecond))
((ZigzagIndexClass.next^[records.length])
indexClass),
⟨archive, .blank,
towardCenter.reverse ++
zigzagScanRecordStream records
markerFirst markerSecond outward⟩) := by
induction records generalizing
indexClass towardCenter with
| nil =>
simp only [List.length_nil, Nat.mul_zero,
Nat.zero_add, focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
Function.iterate_zero_apply,
zigzagScanRecordStream,
falseZigzagRecordsSymbols,
List.flatMap_nil, List.nil_append,
List.cons_append, List.append_assoc]
change
(zigzagScanConfigurationStep^[
towardCenter.length + 6])
(.atFlag indexClass,
focusedBitTape towardCenter archive true
(.bit markerFirst ::
.bit markerSecond :: outward)) =
(.done
(decodeTapeSymbol
(markerFirst, markerSecond))
indexClass,
⟨archive, .blank,
towardCenter.reverse ++
(.bit true :: .bit markerFirst ::
.bit markerSecond :: outward)⟩)
have hthree :=
zigzagScan_marker_three_steps
indexClass towardCenter
archive markerFirst markerSecond outward
have hreturn :=
zigzagScan_iterate_returning
(decodeTapeSymbol (markerFirst, markerSecond))
indexClass
(.bit true :: towardCenter)
archive markerFirst
(.bit markerSecond :: outward)
(by
intro symbol hsymbol
simp only [List.mem_cons] at hsymbol
rcases hsymbol with rfl | hsymbol
· exact ⟨true, rfl⟩
· exact hcenterBits symbol hsymbol)
have htime :
towardCenter.length + 6 =
((.bit true :: towardCenter).length + 2) +
3 := by
simp
rw [htime, Function.iterate_add_apply,
hthree]
simpa [focusedBitTape, returningScanTape] using
hreturn
| cons record records ih =>
rcases record with ⟨first, second⟩
rw [zigzagScanRecordStream_cons]
simp only [List.length_cons,
focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
List.cons_append]
simp only [List.nil_append]
rw [zigzagScanRecordStream_eq]
change
(zigzagScanConfigurationStep^[
6 * (records.length + 1) +
towardCenter.length + 6])
(.atFlag indexClass,
focusedBitTape towardCenter archive false
(.bit first :: .bit second ::
.bit (zigzagScanStreamFlag records) ::
zigzagScanStreamAfterFlag records
markerFirst markerSecond outward)) =
(.done
(decodeTapeSymbol
(markerFirst, markerSecond))
((ZigzagIndexClass.next^[
records.length + 1]) indexClass),
⟨archive, .blank,
towardCenter.reverse ++
(.bit false :: .bit first :: .bit second ::
.bit (zigzagScanStreamFlag records) ::
zigzagScanStreamAfterFlag records
markerFirst markerSecond outward)⟩)
have hfirst :=
zigzagScan_false_record_three_steps
indexClass towardCenter archive
first second
(zigzagScanStreamFlag records)
(zigzagScanStreamAfterFlag records
markerFirst markerSecond outward)
let nextTowardCenter :=
.bit second :: .bit first ::
.bit false :: towardCenter
have hnextBits :
∀ symbol ∈ nextTowardCenter,
∃ bit, symbol = .bit bit := by
intro symbol hsymbol
simp only [nextTowardCenter,
List.mem_cons] at hsymbol
rcases hsymbol with rfl | rfl | rfl | hsymbol
· exact ⟨second, rfl⟩
· exact ⟨first, rfl⟩
· exact ⟨false, rfl⟩
· exact hcenterBits symbol hsymbol
have ih' :=
ih indexClass.next nextTowardCenter
hnextBits
have htime :
6 * (records.length + 1) +
towardCenter.length + 6 =
(6 * records.length +
nextTowardCenter.length + 6) +
3 := by
simp [nextTowardCenter]
omega
rw [htime, Function.iterate_add_apply,
hfirst]
rw [Function.iterate_succ_apply]
simpa [nextTowardCenter,
focusedScanStreamTape,
zigzagScanRecordStream_eq] using ih'
def zigzagRecordPairsFrom
(tape : Tape) (position : Int) (firstIndex : Nat) :
Nat → List (Bool × Bool)
| 0 => []
| count + 1 =>
encodeTapeSymbol
(zigzagRecordSymbol tape position firstIndex) ::
zigzagRecordPairsFrom tape position
(firstIndex + 1) count
@[simp]
theorem zigzagRecordPairsFrom_length
(tape : Tape) (position : Int)
(firstIndex count : Nat) :
(zigzagRecordPairsFrom tape position
firstIndex count).length = count := by
induction count generalizing firstIndex with
| zero => rfl
| succ count ih =>
simp [zigzagRecordPairsFrom, ih]
theorem zigzagRecordFlag_false_of_lt
(position : Int) (index : Nat)
(hindex : index < zigzagIndex position) :
zigzagRecordFlag position index = false := by
simp [zigzagRecordFlag, ne_of_lt hindex]
theorem zigzagWorkBitsFrom_before_marker
(tape : Tape) (position : Int)
(firstIndex count : Nat)
(hbefore :
firstIndex + count ≤ zigzagIndex position) :
(zigzagWorkBitsFrom tape position
firstIndex count).map TapeSymbol.bit =
falseZigzagRecordsSymbols
(zigzagRecordPairsFrom tape position
firstIndex count) := by
induction count generalizing firstIndex with
| zero =>
rfl
| succ count ih =>
have hfirst :
firstIndex < zigzagIndex position := by
omega
have hrest :
firstIndex + 1 + count ≤
zigzagIndex position := by
omega
rw [zigzagWorkBitsFrom_succ]
simp only [List.map_append,
zigzagRecordBits,
zigzagRecordFlag_false_of_lt
position firstIndex hfirst,
List.map_cons, List.map_nil,
falseZigzagRecordsSymbols,
List.flatMap_cons,
falseZigzagRecordSymbols,
zigzagRecordPairsFrom]
rw [ih (firstIndex + 1) hrest]
rfl
theorem zigzagWorkBitsFrom_marker
(tape : Tape) (position : Int) (extra : Nat) :
(zigzagWorkBitsFrom tape position
(zigzagIndex position) (extra + 1)).map
TapeSymbol.bit =
[.bit true,
.bit (encodeTapeSymbol tape.head).1,
.bit (encodeTapeSymbol tape.head).2] ++
(zigzagWorkBitsFrom tape position
(zigzagIndex position + 1) extra).map
TapeSymbol.bit := by
rw [zigzagWorkBitsFrom_succ]
simp only [List.map_append, zigzagRecordBits,
zigzagRecordFlag, decide_true, List.map_cons,
List.map_nil, zigzagRecordSymbol_at_head]
theorem zigzagWorkBitsFrom_add
(tape : Tape) (position : Int)
(firstIndex firstCount secondCount : Nat) :
zigzagWorkBitsFrom tape position firstIndex
(firstCount + secondCount) =
zigzagWorkBitsFrom tape position firstIndex
firstCount ++
zigzagWorkBitsFrom tape position
(firstIndex + firstCount) secondCount := by
induction firstCount generalizing firstIndex with
| zero =>
simp [zigzagWorkBitsFrom]
| succ firstCount ih =>
rw [show firstCount + 1 + secondCount =
(firstCount + secondCount) + 1 by omega]
rw [zigzagWorkBitsFrom_succ,
zigzagWorkBitsFrom_succ]
rw [ih (firstIndex + 1)]
rw [show firstIndex + 1 + firstCount =
firstIndex + (firstCount + 1) by omega]
simp [List.append_assoc]
theorem zigzagWorkBits_split_at_marker
(tape : Tape) (position : Int) (extra : Nat) :
(zigzagWorkBitsFrom tape position 0
(zigzagIndex position + 1 + extra)).map
TapeSymbol.bit =
falseZigzagRecordsSymbols
(zigzagRecordPairsFrom tape position 0
(zigzagIndex position)) ++
[.bit true,
.bit (encodeTapeSymbol tape.head).1,
.bit (encodeTapeSymbol tape.head).2] ++
(zigzagWorkBitsFrom tape position
(zigzagIndex position + 1) extra).map
TapeSymbol.bit := by
have hsplit :
zigzagWorkBitsFrom tape position 0
(zigzagIndex position + 1 + extra) =
zigzagWorkBitsFrom tape position 0
(zigzagIndex position) ++
zigzagWorkBitsFrom tape position
(zigzagIndex position)
(extra + 1) := by
simpa [Nat.add_assoc, Nat.add_comm] using
zigzagWorkBitsFrom_add tape position 0
(zigzagIndex position) (extra + 1)
rw [hsplit, List.map_append,
zigzagWorkBitsFrom_before_marker
tape position 0 (zigzagIndex position)
(by simp),
zigzagWorkBitsFrom_marker]
simp [List.append_assoc]
def ZigzagIndexClass.atIndex : Nat → ZigzagIndexClass
| 0 => .zero
| index + 1 => (ZigzagIndexClass.atIndex index).next
theorem ZigzagIndexClass.iterate_next_zero
(index : Nat) :
(ZigzagIndexClass.next^[index])
ZigzagIndexClass.zero =
ZigzagIndexClass.atIndex index := by
induction index with
| zero => rfl
| succ index ih =>
rw [Function.iterate_succ_apply']
rw [ih]
rfl
theorem zigzagScan_physicalTape
(archive : List TapeSymbol)
(tape : Tape) (position : Int)
(extra : Nat) :
(zigzagScanConfigurationStep^[
6 * zigzagIndex position + 6])
(.atFlag .zero,
Tape.move
(zigzagPhysicalTape archive tape position
(zigzagIndex position + 1 + extra))
.right) =
(.done tape.head
(ZigzagIndexClass.atIndex
(zigzagIndex position)),
zigzagPhysicalTape archive tape position
(zigzagIndex position + 1 + extra)) := by
have hscan :=
zigzagScan_iterate_records_marker
ZigzagIndexClass.zero [] archive
(zigzagRecordPairsFrom tape position 0
(zigzagIndex position))
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2
((zigzagWorkBitsFrom tape position
(zigzagIndex position + 1) extra).map
TapeSymbol.bit)
(by simp)
rw [zigzagRecordPairsFrom_length,
ZigzagIndexClass.iterate_next_zero] at hscan
let records :=
zigzagRecordPairsFrom tape position 0
(zigzagIndex position)
let tail :=
(zigzagWorkBitsFrom tape position
(zigzagIndex position + 1) extra).map
TapeSymbol.bit
have hinitial :
Tape.move
(zigzagPhysicalTape archive tape position
(zigzagIndex position + 1 + extra))
.right =
focusedScanStreamTape [] archive records
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2 tail := by
simp only [zigzagPhysicalTape, zigzagWorkBits]
rw [show
(zigzagWorkBitsFrom tape position 0
(zigzagIndex position + 1 + extra)).map
TapeSymbol.bit =
falseZigzagRecordsSymbols records ++
[.bit true,
.bit (encodeTapeSymbol tape.head).1,
.bit (encodeTapeSymbol tape.head).2] ++
tail by
exact zigzagWorkBits_split_at_marker
tape position extra]
cases records with
| nil =>
rfl
| cons record records =>
rcases record with ⟨first, second⟩
rfl
have hfinal :
(⟨archive, .blank,
falseZigzagRecordsSymbols records ++
[.bit true,
.bit (encodeTapeSymbol tape.head).1,
.bit (encodeTapeSymbol tape.head).2] ++ tail⟩ :
Tape) =
zigzagPhysicalTape archive tape position
(zigzagIndex position + 1 + extra) := by
unfold zigzagPhysicalTape
congr 1
exact (zigzagWorkBits_split_at_marker
tape position extra).symm
have hstream :
zigzagScanRecordStream records
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2 tail =
falseZigzagRecordsSymbols records ++
[.bit true,
.bit (encodeTapeSymbol tape.head).1,
.bit (encodeTapeSymbol tape.head).2] ++ tail := by
rfl
rw [hstream] at hscan
simp only [List.length_nil, Nat.add_zero,
List.reverse_nil, List.nil_append] at hscan
rw [hfinal] at hscan
rw [hinitial]
simpa [records, tail,
decodeTapeSymbol_encodeTapeSymbol] using hscan
@[simp]
theorem ZigzagIndexClass.atIndex_zero :
ZigzagIndexClass.atIndex 0 = .zero := rfl
@[simp]
theorem ZigzagIndexClass.atIndex_positiveOne :
ZigzagIndexClass.atIndex 1 = .positiveOne := rfl
theorem ZigzagIndexClass.atIndex_add_two
(index : Nat) :
ZigzagIndexClass.atIndex (index + 2) =
(ZigzagIndexClass.atIndex index).next.next := by
rw [show index + 2 = (index + 1) + 1 by omega]
rfl
theorem ZigzagIndexClass.atIndex_negative_positive
(n : Nat) :
ZigzagIndexClass.atIndex (2 * n + 2) = .negative ∧
ZigzagIndexClass.atIndex (2 * n + 3) = .positive := by
induction n with
| zero => exact ⟨rfl, rfl⟩
| succ n ih =>
constructor
· rw [show 2 * (n + 1) + 2 =
(2 * n + 2) + 2 by omega]
rw [ZigzagIndexClass.atIndex_add_two]
rw [ih.1]
rfl
· rw [show 2 * (n + 1) + 3 =
(2 * n + 3) + 2 by omega]
rw [ZigzagIndexClass.atIndex_add_two]
rw [ih.2]
rfl
@[simp]
theorem ZigzagIndexClass.atIndex_positive
(n : Nat) :
ZigzagIndexClass.atIndex (2 * n + 3) = .positive :=
(ZigzagIndexClass.atIndex_negative_positive n).2
@[simp]
theorem ZigzagIndexClass.atIndex_negative
(n : Nat) :
ZigzagIndexClass.atIndex (2 * n + 2) = .negative :=
(ZigzagIndexClass.atIndex_negative_positive n).1
theorem ZigzagIndexClass.at_zigzagIndex
(position : Int) :
ZigzagIndexClass.atIndex (zigzagIndex position) =
match position with
| .ofNat 0 => .zero
| .ofNat 1 => .positiveOne
| .ofNat (_ + 2) => .positive
| .negSucc _ => .negative := by
cases position with
| ofNat n =>
cases n with
| zero => rfl
| succ n =>
cases n with
| zero => rfl
| succ n =>
simp [zigzagIndex]
exact
ZigzagIndexClass.atIndex_positive n
| negSucc n =>
simp [zigzagIndex]
theorem zigzagRecordSymbol_after_write_move
(tape : Tape) (position : Int)
(write : TapeSymbol) (move : HeadMove)
(index : Nat) :
zigzagRecordSymbol
((tape.write write).move move)
(move.updatePosition position) index =
if zigzagCoordinate index = position then
write
else
zigzagRecordSymbol tape position index := by
simp only [zigzagRecordSymbol,
HeadMove.updatePosition,
Tape.readRelative_move_recenter,
Tape.readRelative_write]
by_cases hcoordinate :
zigzagCoordinate index = position
· rw [if_pos hcoordinate]
rw [if_pos]
omega
· rw [if_neg hcoordinate]
rw [if_neg]
· congr 1
omega
· intro hequal
apply hcoordinate
omega
theorem zigzagRecordSymbol_old_head_after_write_move
(tape : Tape) (position : Int)
(write : TapeSymbol) (move : HeadMove) :
zigzagRecordSymbol
((tape.write write).move move)
(move.updatePosition position)
(zigzagIndex position) =
write := by
rw [zigzagRecordSymbol_after_write_move]
simp
theorem zigzagRecordSymbol_away_after_write_move
(tape : Tape) (position : Int)
(write : TapeSymbol) (move : HeadMove)
(index : Nat)
(hindex : index ≠ zigzagIndex position) :
zigzagRecordSymbol
((tape.write write).move move)
(move.updatePosition position) index =
zigzagRecordSymbol tape position index := by
rw [zigzagRecordSymbol_after_write_move]
rw [if_neg]
intro hcoordinate
apply hindex
apply zigzagCoordinate_injective
simpa using hcoordinate
theorem zigzagIndex_updatePosition
(position : Int) (move : HeadMove) :
let oldIndex := zigzagIndex position
let newIndex :=
zigzagIndex (move.updatePosition position)
match zigzagRelocation move
(ZigzagIndexClass.atIndex oldIndex) with
| none => newIndex = oldIndex
| some relocation =>
if relocation.direction = .outward then
newIndex = oldIndex + relocation.distance.val / 3
else
oldIndex =
newIndex + relocation.distance.val / 3 := by
cases position with
| ofNat n =>
cases n with
| zero =>
cases move with
| left =>
change
zigzagIndex (Int.negSucc 0) =
0 + 6 / 3
rfl
| stay => rfl
| right => rfl
| succ n =>
cases n with
| zero =>
cases move with
| left => rfl
| stay => rfl
| right => rfl
| succ n =>
cases move with
| left =>
have hposition :
Int.ofNat (n + 2) + (-1) =
Int.ofNat (n + 1) := by
rw [Int.ofNat_eq_coe,
Int.ofNat_eq_coe]
omega
simp only [HeadMove.updatePosition,
HeadMove.displacement]
rw [hposition]
have hold :
zigzagIndex
(Int.ofNat (n + 1 + 1)) =
2 * n + 3 := by
simp [zigzagIndex]
omega
have hnew :
zigzagIndex (Int.ofNat (n + 1)) =
2 * n + 1 := by
simp [zigzagIndex]
rw [hold, hnew]
rw [ZigzagIndexClass.atIndex_positive]
simp [zigzagRelocation]
| stay => rfl
| right =>
have hposition :
Int.ofNat (n + 2) + 1 =
Int.ofNat (n + 3) := by
rw [Int.ofNat_eq_coe,
Int.ofNat_eq_coe]
omega
simp only [HeadMove.updatePosition,
HeadMove.displacement]
rw [hposition]
have hold :
zigzagIndex
(Int.ofNat (n + 1 + 1)) =
2 * n + 3 := by
simp [zigzagIndex]
omega
have hnew :
zigzagIndex (Int.ofNat (n + 3)) =
2 * n + 5 := by
simp [zigzagIndex]
omega
rw [hold, hnew]
rw [ZigzagIndexClass.atIndex_positive]
simp [zigzagRelocation]
| negSucc n =>
cases move with
| left =>
have hposition :
Int.negSucc n + (-1) =
Int.negSucc (n + 1) := by
simpa [sub_eq_add_neg] using
Int.negSucc_sub_one n
simp [HeadMove.updatePosition,
HeadMove.displacement, hposition,
zigzagIndex, zigzagRelocation]
omega
| stay => rfl
| right =>
cases n with
| zero => rfl
| succ n =>
have hposition :
Int.negSucc (n + 1) + 1 =
Int.negSucc n := by omega
simp [HeadMove.updatePosition,
HeadMove.displacement, hposition,
zigzagIndex, zigzagRelocation]
omega
def zigzagUpdateConfigurationStep
(write : TapeSymbol) (move : HeadMove)
(configuration : ZigzagUpdateLocal × Tape) :
ZigzagUpdateLocal × Tape :=
let action :=
zigzagUpdateLocalStep write move
configuration.1 configuration.2.head
(action.1,
applyPhysicalAction configuration.2 action.2)
theorem zigzagUpdate_returning_move
(write : TapeSymbol) (move : HeadMove)
(towardCenter archive : List TapeSymbol)
(current : Bool) (outward : List TapeSymbol) :
zigzagUpdateConfigurationStep write move
(.returning,
returningScanTape towardCenter archive
(.bit current) outward) =
match towardCenter with
| [] =>
(.returning,
⟨archive, .blank, .bit current :: outward⟩)
| next :: rest =>
(.returning,
returningScanTape rest archive next
(.bit current :: outward)) := by
cases towardCenter <;>
rfl
theorem zigzagUpdate_returning_blank
(write : TapeSymbol) (move : HeadMove)
(archive outward : List TapeSymbol) :
zigzagUpdateConfigurationStep write move
(.returning,
⟨archive, .blank, outward⟩) =
(.done, ⟨archive, .blank, outward⟩) := by
rfl
theorem zigzagUpdate_iterate_returning
(write : TapeSymbol) (move : HeadMove)
(towardCenter archive : List TapeSymbol)
(current : Bool) (outward : List TapeSymbol)
(hbits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
((zigzagUpdateConfigurationStep write move)^[
towardCenter.length + 2])
(.returning,
returningScanTape towardCenter archive
(.bit current) outward) =
(.done,
⟨archive, .blank,
towardCenter.reverse ++
.bit current :: outward⟩) := by
induction towardCenter generalizing current outward with
| nil =>
simp only [List.length_nil, zero_add,
Function.iterate_succ_apply]
rw [zigzagUpdate_returning_move]
exact zigzagUpdate_returning_blank
write move archive (.bit current :: outward)
| cons next rest ih =>
have htime :
(next :: rest).length + 2 =
(rest.length + 2) + 1 := by simp
obtain ⟨nextBit, rfl⟩ :=
hbits next (by simp)
have hrest :
∀ symbol ∈ rest,
∃ bit, symbol = .bit bit := by
intro symbol hsymbol
exact hbits symbol (by simp [hsymbol])
rw [htime, Function.iterate_succ_apply]
rw [zigzagUpdate_returning_move]
rw [ih nextBit (.bit current :: outward) hrest]
simp
theorem zigzagUpdate_false_record_three_steps
(write : TapeSymbol) (move : HeadMove)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(first second nextFlag : Bool)
(outward : List TapeSymbol) :
((zigzagUpdateConfigurationStep write move)^[3])
(.atFlag indexClass,
focusedBitTape towardCenter archive false
(.bit first :: .bit second ::
.bit nextFlag :: outward)) =
(.atFlag indexClass.next,
focusedBitTape
(.bit second :: .bit first ::
.bit false :: towardCenter)
archive nextFlag outward) := by
rfl
theorem zigzagUpdate_marker_four_steps
(write : TapeSymbol) (move : HeadMove)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(oldFirst oldSecond : Bool)
(outward : List TapeSymbol) :
((zigzagUpdateConfigurationStep write move)^[4])
(.atFlag indexClass,
focusedBitTape towardCenter archive true
(.bit oldFirst :: .bit oldSecond :: outward)) =
(match zigzagRelocation move indexClass with
| none => .setHead
| some relocation =>
.relocate relocation.direction relocation.distance,
focusedBitTape towardCenter archive false
(.bit (encodeTapeSymbol write).1 ::
.bit (encodeTapeSymbol write).2 :: outward)) := by
cases move <;> cases indexClass <;> rfl
theorem zigzagUpdate_setHead_three_steps
(write : TapeSymbol) (move : HeadMove)
(towardCenter archive : List TapeSymbol)
(first second : Bool)
(outward : List TapeSymbol) :
((zigzagUpdateConfigurationStep write move)^[3])
(.setHead,
focusedBitTape towardCenter archive false
(.bit first :: .bit second :: outward)) =
(.returning,
focusedBitTape
(.bit true :: towardCenter)
archive first (.bit second :: outward)) := by
rfl
theorem zigzagUpdate_iterate_stay_marker
(write : TapeSymbol)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(oldFirst oldSecond : Bool)
(outward : List TapeSymbol)
(hbits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
((zigzagUpdateConfigurationStep write .stay)^[
towardCenter.length + 10])
(.atFlag indexClass,
focusedBitTape towardCenter archive true
(.bit oldFirst :: .bit oldSecond :: outward)) =
(.done,
⟨archive, .blank,
towardCenter.reverse ++
[.bit true,
.bit (encodeTapeSymbol write).1,
.bit (encodeTapeSymbol write).2] ++ outward⟩) := by
have hmarker :=
zigzagUpdate_marker_four_steps
write .stay indexClass towardCenter archive
oldFirst oldSecond outward
have hset :=
zigzagUpdate_setHead_three_steps
write .stay towardCenter archive
(encodeTapeSymbol write).1
(encodeTapeSymbol write).2 outward
have hreturn :=
zigzagUpdate_iterate_returning
write .stay (.bit true :: towardCenter)
archive (encodeTapeSymbol write).1
(.bit (encodeTapeSymbol write).2 :: outward)
(by
intro symbol hsymbol
simp only [List.mem_cons] at hsymbol
rcases hsymbol with rfl | hsymbol
· exact ⟨true, rfl⟩
· exact hbits symbol hsymbol)
have htime :
towardCenter.length + 10 =
((.bit true :: towardCenter).length + 2) +
3 + 4 := by simp
rw [htime, Function.iterate_add_apply,
Function.iterate_add_apply,
hmarker]
simp only [zigzagRelocation]
rw [hset]
simpa [focusedBitTape, returningScanTape,
List.append_assoc] using hreturn
def zigzagUpdatedStayStream
(records : List (Bool × Bool))
(write : TapeSymbol)
(outward : List TapeSymbol) : List TapeSymbol :=
falseZigzagRecordsSymbols records ++
[.bit true,
.bit (encodeTapeSymbol write).1,
.bit (encodeTapeSymbol write).2] ++ outward
theorem zigzagUpdate_iterate_records_stay
(write : TapeSymbol)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(records : List (Bool × Bool))
(oldFirst oldSecond : Bool)
(outward : List TapeSymbol)
(hcenterBits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
((zigzagUpdateConfigurationStep write .stay)^[
6 * records.length + towardCenter.length + 10])
(.atFlag indexClass,
focusedScanStreamTape towardCenter archive
records oldFirst oldSecond outward) =
(.done,
⟨archive, .blank,
towardCenter.reverse ++
zigzagUpdatedStayStream records write outward⟩) := by
induction records generalizing
indexClass towardCenter with
| nil =>
simp only [List.length_nil, Nat.mul_zero,
Nat.zero_add, focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
List.cons_append, List.nil_append,
zigzagUpdatedStayStream,
falseZigzagRecordsSymbols,
List.flatMap_nil]
simpa [List.append_assoc] using
zigzagUpdate_iterate_stay_marker
write indexClass towardCenter archive
oldFirst oldSecond outward hcenterBits
| cons record records ih =>
rcases record with ⟨first, second⟩
simp only [List.length_cons,
focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
List.cons_append, List.nil_append,
zigzagUpdatedStayStream,
falseZigzagRecordsSymbols,
List.flatMap_cons,
falseZigzagRecordSymbols]
rw [zigzagScanRecordStream_eq]
let nextTowardCenter :=
.bit second :: .bit first ::
.bit false :: towardCenter
have hnextBits :
∀ symbol ∈ nextTowardCenter,
∃ bit, symbol = .bit bit := by
intro symbol hsymbol
simp only [nextTowardCenter,
List.mem_cons] at hsymbol
rcases hsymbol with rfl | rfl | rfl | hsymbol
· exact ⟨second, rfl⟩
· exact ⟨first, rfl⟩
· exact ⟨false, rfl⟩
· exact hcenterBits symbol hsymbol
have hfirst :=
zigzagUpdate_false_record_three_steps
write .stay indexClass towardCenter archive
first second
(zigzagScanStreamFlag records)
(zigzagScanStreamAfterFlag records
oldFirst oldSecond outward)
have ih' :=
ih indexClass.next nextTowardCenter hnextBits
have htime :
6 * (records.length + 1) +
towardCenter.length + 10 =
(6 * records.length +
nextTowardCenter.length + 10) + 3 := by
simp [nextTowardCenter]
omega
rw [htime, Function.iterate_add_apply,
hfirst]
simpa [nextTowardCenter,
focusedScanStreamTape,
zigzagScanRecordStream_eq,
zigzagUpdatedStayStream,
falseZigzagRecordsSymbols,
falseZigzagRecordSymbols,
List.append_assoc] using ih'
theorem zigzagUpdate_relocate_outward_three
(write : TapeSymbol) (move : HeadMove)
(towardCenter archive : List TapeSymbol)
(oldFirst oldSecond nextFlag : Bool)
(nextFirst nextSecond : Bool)
(outward : List TapeSymbol) :
((zigzagUpdateConfigurationStep write move)^[4])
(.relocate .outward ⟨3, by decide⟩,
focusedBitTape towardCenter archive false
(.bit oldFirst :: .bit oldSecond ::
.bit nextFlag :: .bit nextFirst ::
.bit nextSecond :: outward)) =
(.setHead,
focusedBitTape
(.bit oldSecond :: .bit oldFirst ::
.bit false :: towardCenter)
archive nextFlag
(.bit nextFirst :: .bit nextSecond :: outward)) := by
rfl
theorem zigzagUpdate_relocate_outward_six
(write : TapeSymbol) (move : HeadMove)
(towardCenter archive : List TapeSymbol)
(oldFirst oldSecond middleFlag : Bool)
(middleFirst middleSecond nextFlag : Bool)
(nextFirst nextSecond : Bool)
(outward : List TapeSymbol) :
((zigzagUpdateConfigurationStep write move)^[7])
(.relocate .outward ⟨6, by decide⟩,
focusedBitTape towardCenter archive false
(.bit oldFirst :: .bit oldSecond ::
.bit middleFlag :: .bit middleFirst ::
.bit middleSecond :: .bit nextFlag ::
.bit nextFirst :: .bit nextSecond :: outward)) =
(.setHead,
focusedBitTape
(.bit middleSecond :: .bit middleFirst ::
.bit middleFlag :: .bit oldSecond ::
.bit oldFirst :: .bit false :: towardCenter)
archive nextFlag
(.bit nextFirst :: .bit nextSecond :: outward)) := by
rfl
theorem zigzagUpdate_relocate_inward_three
(write : TapeSymbol) (move : HeadMove)
(towardCenter archive : List TapeSymbol)
(previousFlag previousFirst previousSecond : Bool)
(oldFirst oldSecond : Bool)
(outward : List TapeSymbol) :
((zigzagUpdateConfigurationStep write move)^[4])
(.relocate .inward ⟨3, by decide⟩,
focusedBitTape
(.bit previousSecond :: .bit previousFirst ::
.bit previousFlag :: towardCenter)
archive false
(.bit oldFirst :: .bit oldSecond :: outward)) =
(.setHead,
focusedBitTape towardCenter archive previousFlag
(.bit previousFirst :: .bit previousSecond ::
.bit false :: .bit oldFirst ::
.bit oldSecond :: outward)) := by
rfl
theorem zigzagUpdate_relocate_inward_six
(write : TapeSymbol) (move : HeadMove)
(towardCenter archive : List TapeSymbol)
(targetFlag targetFirst targetSecond : Bool)
(middleFlag middleFirst middleSecond : Bool)
(oldFirst oldSecond : Bool)
(outward : List TapeSymbol) :
((zigzagUpdateConfigurationStep write move)^[7])
(.relocate .inward ⟨6, by decide⟩,
focusedBitTape
(.bit middleSecond :: .bit middleFirst ::
.bit middleFlag :: .bit targetSecond ::
.bit targetFirst :: .bit targetFlag ::
towardCenter)
archive false
(.bit oldFirst :: .bit oldSecond :: outward)) =
(.setHead,
focusedBitTape towardCenter archive targetFlag
(.bit targetFirst :: .bit targetSecond ::
.bit middleFlag :: .bit middleFirst ::
.bit middleSecond :: .bit false ::
.bit oldFirst :: .bit oldSecond :: outward)) := by
rfl
theorem zigzagUpdate_iterate_outward_three_marker
(write : TapeSymbol) (move : HeadMove)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(oldFirst oldSecond nextFirst nextSecond : Bool)
(outward : List TapeSymbol)
(hrelocation :
zigzagRelocation move indexClass =
some ⟨.outward, ⟨3, by decide⟩⟩)
(hbits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
((zigzagUpdateConfigurationStep write move)^[
towardCenter.length + 17])
(.atFlag indexClass,
focusedBitTape towardCenter archive true
(.bit oldFirst :: .bit oldSecond ::
.bit false :: .bit nextFirst ::
.bit nextSecond :: outward)) =
(.done,
⟨archive, .blank,
towardCenter.reverse ++
[.bit false,
.bit (encodeTapeSymbol write).1,
.bit (encodeTapeSymbol write).2,
.bit true, .bit nextFirst,
.bit nextSecond] ++ outward⟩) := by
let relocatedToward :=
.bit (encodeTapeSymbol write).2 ::
.bit (encodeTapeSymbol write).1 ::
.bit false :: towardCenter
have hmarker :=
zigzagUpdate_marker_four_steps
write move indexClass towardCenter archive
oldFirst oldSecond
(.bit false :: .bit nextFirst ::
.bit nextSecond :: outward)
have hrelocate :=
zigzagUpdate_relocate_outward_three
write move towardCenter archive
(encodeTapeSymbol write).1
(encodeTapeSymbol write).2 false
nextFirst nextSecond outward
have hset :=
zigzagUpdate_setHead_three_steps
write move relocatedToward archive
nextFirst nextSecond outward
have hreturn :=
zigzagUpdate_iterate_returning
write move (.bit true :: relocatedToward)
archive nextFirst (.bit nextSecond :: outward)
(by
intro symbol hsymbol
simp only [relocatedToward,
List.mem_cons] at hsymbol
rcases hsymbol with
rfl | rfl | rfl | rfl | hsymbol
· exact ⟨true, rfl⟩
· exact ⟨(encodeTapeSymbol write).2, rfl⟩
· exact ⟨(encodeTapeSymbol write).1, rfl⟩
· exact ⟨false, rfl⟩
· exact hbits symbol hsymbol)
have htime :
towardCenter.length + 17 =
((.bit true :: relocatedToward).length + 2) +
3 + 4 + 4 := by
simp [relocatedToward]
rw [htime, Function.iterate_add_apply,
Function.iterate_add_apply,
Function.iterate_add_apply, hmarker]
rw [hrelocation, hrelocate, hset]
simpa [relocatedToward, focusedBitTape,
returningScanTape, List.append_assoc] using hreturn
theorem zigzagUpdate_iterate_outward_six_marker
(write : TapeSymbol) (move : HeadMove)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(oldFirst oldSecond middleFirst middleSecond
nextFirst nextSecond : Bool)
(outward : List TapeSymbol)
(hrelocation :
zigzagRelocation move indexClass =
some ⟨.outward, ⟨6, by decide⟩⟩)
(hbits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
((zigzagUpdateConfigurationStep write move)^[
towardCenter.length + 23])
(.atFlag indexClass,
focusedBitTape towardCenter archive true
(.bit oldFirst :: .bit oldSecond ::
.bit false :: .bit middleFirst ::
.bit middleSecond :: .bit false ::
.bit nextFirst :: .bit nextSecond :: outward)) =
(.done,
⟨archive, .blank,
towardCenter.reverse ++
[.bit false,
.bit (encodeTapeSymbol write).1,
.bit (encodeTapeSymbol write).2,
.bit false, .bit middleFirst,
.bit middleSecond,
.bit true, .bit nextFirst,
.bit nextSecond] ++ outward⟩) := by
let relocatedToward :=
.bit middleSecond :: .bit middleFirst ::
.bit false ::
.bit (encodeTapeSymbol write).2 ::
.bit (encodeTapeSymbol write).1 ::
.bit false :: towardCenter
have hmarker :=
zigzagUpdate_marker_four_steps
write move indexClass towardCenter archive
oldFirst oldSecond
(.bit false :: .bit middleFirst ::
.bit middleSecond :: .bit false ::
.bit nextFirst :: .bit nextSecond :: outward)
have hrelocate :=
zigzagUpdate_relocate_outward_six
write move towardCenter archive
(encodeTapeSymbol write).1
(encodeTapeSymbol write).2 false
middleFirst middleSecond false
nextFirst nextSecond outward
have hset :=
zigzagUpdate_setHead_three_steps
write move relocatedToward archive
nextFirst nextSecond outward
have hreturn :=
zigzagUpdate_iterate_returning
write move (.bit true :: relocatedToward)
archive nextFirst (.bit nextSecond :: outward)
(by
intro symbol hsymbol
simp only [relocatedToward,
List.mem_cons] at hsymbol
rcases hsymbol with
rfl | rfl | rfl | rfl | rfl | rfl | rfl | hsymbol
· exact ⟨true, rfl⟩
· exact ⟨middleSecond, rfl⟩
· exact ⟨middleFirst, rfl⟩
· exact ⟨false, rfl⟩
· exact ⟨(encodeTapeSymbol write).2, rfl⟩
· exact ⟨(encodeTapeSymbol write).1, rfl⟩
· exact ⟨false, rfl⟩
· exact hbits symbol hsymbol)
have htime :
towardCenter.length + 23 =
((.bit true :: relocatedToward).length + 2) +
3 + 7 + 4 := by
simp [relocatedToward]
rw [htime, Function.iterate_add_apply,
Function.iterate_add_apply,
Function.iterate_add_apply, hmarker]
rw [hrelocation, hrelocate, hset]
simpa [relocatedToward, focusedBitTape,
returningScanTape, List.append_assoc] using hreturn
theorem zigzagUpdate_iterate_inward_three_marker
(write : TapeSymbol) (move : HeadMove)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(previousFirst previousSecond oldFirst oldSecond : Bool)
(outward : List TapeSymbol)
(hrelocation :
zigzagRelocation move indexClass =
some ⟨.inward, ⟨3, by decide⟩⟩)
(hbits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
((zigzagUpdateConfigurationStep write move)^[
towardCenter.length + 14])
(.atFlag indexClass,
focusedBitTape
(.bit previousSecond :: .bit previousFirst ::
.bit false :: towardCenter)
archive true
(.bit oldFirst :: .bit oldSecond :: outward)) =
(.done,
⟨archive, .blank,
towardCenter.reverse ++
[.bit true, .bit previousFirst,
.bit previousSecond,
.bit false,
.bit (encodeTapeSymbol write).1,
.bit (encodeTapeSymbol write).2] ++ outward⟩) := by
have hmarker :=
zigzagUpdate_marker_four_steps
write move indexClass
(.bit previousSecond :: .bit previousFirst ::
.bit false :: towardCenter)
archive oldFirst oldSecond outward
have hrelocate :=
zigzagUpdate_relocate_inward_three
write move towardCenter archive false
previousFirst previousSecond
(encodeTapeSymbol write).1
(encodeTapeSymbol write).2 outward
have hset :=
zigzagUpdate_setHead_three_steps
write move towardCenter archive
previousFirst previousSecond
(.bit false ::
.bit (encodeTapeSymbol write).1 ::
.bit (encodeTapeSymbol write).2 :: outward)
have hreturn :=
zigzagUpdate_iterate_returning
write move (.bit true :: towardCenter)
archive previousFirst
(.bit previousSecond :: .bit false ::
.bit (encodeTapeSymbol write).1 ::
.bit (encodeTapeSymbol write).2 :: outward)
(by
intro symbol hsymbol
simp only [List.mem_cons] at hsymbol
rcases hsymbol with rfl | hsymbol
· exact ⟨true, rfl⟩
· exact hbits symbol hsymbol)
have htime :
towardCenter.length + 14 =
((.bit true :: towardCenter).length + 2) +
3 + 4 + 4 := by simp
rw [htime, Function.iterate_add_apply,
Function.iterate_add_apply,
Function.iterate_add_apply, hmarker]
rw [hrelocation, hrelocate, hset]
simpa [focusedBitTape, returningScanTape,
List.append_assoc] using hreturn
theorem zigzagUpdate_iterate_inward_six_marker
(write : TapeSymbol) (move : HeadMove)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(targetFirst targetSecond middleFirst middleSecond
oldFirst oldSecond : Bool)
(outward : List TapeSymbol)
(hrelocation :
zigzagRelocation move indexClass =
some ⟨.inward, ⟨6, by decide⟩⟩)
(hbits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
((zigzagUpdateConfigurationStep write move)^[
towardCenter.length + 17])
(.atFlag indexClass,
focusedBitTape
(.bit middleSecond :: .bit middleFirst ::
.bit false :: .bit targetSecond ::
.bit targetFirst :: .bit false ::
towardCenter)
archive true
(.bit oldFirst :: .bit oldSecond :: outward)) =
(.done,
⟨archive, .blank,
towardCenter.reverse ++
[.bit true, .bit targetFirst,
.bit targetSecond,
.bit false, .bit middleFirst,
.bit middleSecond,
.bit false,
.bit (encodeTapeSymbol write).1,
.bit (encodeTapeSymbol write).2] ++ outward⟩) := by
have hmarker :=
zigzagUpdate_marker_four_steps
write move indexClass
(.bit middleSecond :: .bit middleFirst ::
.bit false :: .bit targetSecond ::
.bit targetFirst :: .bit false :: towardCenter)
archive oldFirst oldSecond outward
have hrelocate :=
zigzagUpdate_relocate_inward_six
write move towardCenter archive false
targetFirst targetSecond false
middleFirst middleSecond
(encodeTapeSymbol write).1
(encodeTapeSymbol write).2 outward
have hset :=
zigzagUpdate_setHead_three_steps
write move towardCenter archive
targetFirst targetSecond
(.bit false :: .bit middleFirst ::
.bit middleSecond :: .bit false ::
.bit (encodeTapeSymbol write).1 ::
.bit (encodeTapeSymbol write).2 :: outward)
have hreturn :=
zigzagUpdate_iterate_returning
write move (.bit true :: towardCenter)
archive targetFirst
(.bit targetSecond :: .bit false ::
.bit middleFirst :: .bit middleSecond ::
.bit false ::
.bit (encodeTapeSymbol write).1 ::
.bit (encodeTapeSymbol write).2 :: outward)
(by
intro symbol hsymbol
simp only [List.mem_cons] at hsymbol
rcases hsymbol with rfl | hsymbol
· exact ⟨true, rfl⟩
· exact hbits symbol hsymbol)
have htime :
towardCenter.length + 17 =
((.bit true :: towardCenter).length + 2) +
3 + 7 + 4 := by simp
rw [htime, Function.iterate_add_apply,
Function.iterate_add_apply,
Function.iterate_add_apply, hmarker]
rw [hrelocation, hrelocate, hset]
simpa [focusedBitTape, returningScanTape,
List.append_assoc] using hreturn
theorem zigzagRecordBits_after_write_stay_away
(tape : Tape) (position : Int)
(write : TapeSymbol) (index : Nat)
(hindex : index ≠ zigzagIndex position) :
zigzagRecordBits
((tape.write write).move .stay)
position index =
zigzagRecordBits tape position index := by
unfold zigzagRecordBits
have hsymbol :=
zigzagRecordSymbol_away_after_write_move
tape position write .stay index hindex
simp only [HeadMove.updatePosition,
HeadMove.displacement, Int.add_zero] at hsymbol
rw [hsymbol]
theorem zigzagRecordBits_after_write_stay_head
(tape : Tape) (position : Int)
(write : TapeSymbol) :
zigzagRecordBits
((tape.write write).move .stay)
position (zigzagIndex position) =
[true, (encodeTapeSymbol write).1,
(encodeTapeSymbol write).2] := by
have hsymbol :=
zigzagRecordSymbol_old_head_after_write_move
tape position write .stay
simp only [HeadMove.updatePosition,
HeadMove.displacement, Int.add_zero] at hsymbol
unfold zigzagRecordBits
rw [hsymbol]
simp [zigzagRecordFlag]
theorem zigzagRecordPairsFrom_after_write_stay_before
(tape : Tape) (position : Int)
(write : TapeSymbol)
(firstIndex count : Nat)
(hbefore :
firstIndex + count ≤ zigzagIndex position) :
zigzagRecordPairsFrom
((tape.write write).move .stay)
position firstIndex count =
zigzagRecordPairsFrom tape position
firstIndex count := by
induction count generalizing firstIndex with
| zero => rfl
| succ count ih =>
have hfirst :
firstIndex ≠ zigzagIndex position := by
omega
have hrest :
firstIndex + 1 + count ≤
zigzagIndex position := by
omega
simp only [zigzagRecordPairsFrom]
have hsymbol :=
zigzagRecordSymbol_away_after_write_move
tape position write .stay firstIndex hfirst
simp only [HeadMove.updatePosition,
HeadMove.displacement, Int.add_zero] at hsymbol
rw [hsymbol, ih (firstIndex + 1) hrest]
theorem zigzagWorkBitsFrom_after_write_stay_after
(tape : Tape) (position : Int)
(write : TapeSymbol)
(firstIndex count : Nat)
(hafter :
zigzagIndex position < firstIndex) :
zigzagWorkBitsFrom
((tape.write write).move .stay)
position firstIndex count =
zigzagWorkBitsFrom tape position
firstIndex count := by
induction count generalizing firstIndex with
| zero => rfl
| succ count ih =>
have hfirst :
firstIndex ≠ zigzagIndex position := by
omega
have hrest :
zigzagIndex position < firstIndex + 1 := by
omega
simp only [zigzagWorkBitsFrom_succ]
rw [zigzagRecordBits_after_write_stay_away
tape position write firstIndex hfirst]
rw [ih (firstIndex + 1) hrest]
theorem zigzagUpdate_physicalTape_stay
(archive : List TapeSymbol)
(tape : Tape) (position : Int)
(recordCount : Nat)
(write : TapeSymbol)
(hhead : zigzagIndex position < recordCount) :
((zigzagUpdateConfigurationStep write .stay)^[
6 * zigzagIndex position + 10])
(.atFlag .zero,
Tape.move
(zigzagPhysicalTape archive tape position
recordCount)
.right) =
(.done,
zigzagPhysicalTape archive
((tape.write write).move .stay)
position recordCount) := by
obtain ⟨extra, hcount⟩ :
∃ extra,
recordCount =
zigzagIndex position + 1 + extra := by
use recordCount - (zigzagIndex position + 1)
omega
subst recordCount
let records :=
zigzagRecordPairsFrom tape position 0
(zigzagIndex position)
let tail :=
(zigzagWorkBitsFrom tape position
(zigzagIndex position + 1) extra).map
TapeSymbol.bit
have hupdate :=
zigzagUpdate_iterate_records_stay
write ZigzagIndexClass.zero [] archive
records
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2
tail (by simp)
rw [zigzagRecordPairsFrom_length] at hupdate
simp only [List.length_nil, Nat.add_zero,
List.reverse_nil, List.nil_append] at hupdate
have hinitial :
Tape.move
(zigzagPhysicalTape archive tape position
(zigzagIndex position + 1 + extra))
.right =
focusedScanStreamTape [] archive records
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2 tail := by
simp only [zigzagPhysicalTape, zigzagWorkBits]
rw [show
(zigzagWorkBitsFrom tape position 0
(zigzagIndex position + 1 + extra)).map
TapeSymbol.bit =
falseZigzagRecordsSymbols records ++
[.bit true,
.bit (encodeTapeSymbol tape.head).1,
.bit (encodeTapeSymbol tape.head).2] ++
tail by
exact zigzagWorkBits_split_at_marker
tape position extra]
cases records with
| nil => rfl
| cons record records =>
rcases record with ⟨first, second⟩
rfl
have hprefix :
zigzagRecordPairsFrom
(((tape.write write).move .stay))
position 0 (zigzagIndex position) =
records := by
exact
zigzagRecordPairsFrom_after_write_stay_before
tape position write 0 (zigzagIndex position)
(by simp)
have htail :
(zigzagWorkBitsFrom
((tape.write write).move .stay)
position (zigzagIndex position + 1)
extra).map TapeSymbol.bit =
tail := by
rw [zigzagWorkBitsFrom_after_write_stay_after
tape position write
(zigzagIndex position + 1) extra (by omega)]
have hsplit :=
zigzagWorkBits_split_at_marker
((tape.write write).move .stay)
position extra
have hheadWrite :
((tape.write write).move .stay).head = write := by
rfl
rw [hprefix, htail, hheadWrite] at hsplit
have hfinal :
(⟨archive, .blank,
zigzagUpdatedStayStream records write tail⟩ :
Tape) =
zigzagPhysicalTape archive
((tape.write write).move .stay)
position
(zigzagIndex position + 1 + extra) := by
unfold zigzagPhysicalTape zigzagWorkBits
congr 1
exact hsplit.symm
rw [hfinal] at hupdate
rw [hinitial]
exact hupdate
theorem zigzagRecordBits_after_write_move_away
(tape : Tape) (position : Int)
(write : TapeSymbol) (move : HeadMove)
(index : Nat)
(hold :
index ≠ zigzagIndex position)
(hnew :
index ≠
zigzagIndex (move.updatePosition position)) :
zigzagRecordBits
((tape.write write).move move)
(move.updatePosition position) index =
zigzagRecordBits tape position index := by
unfold zigzagRecordBits zigzagRecordFlag
have hsymbol :=
zigzagRecordSymbol_away_after_write_move
tape position write move index hold
rw [hsymbol]
simp [hold, hnew]
theorem zigzagRecordBits_after_write_move_old
(tape : Tape) (position : Int)
(write : TapeSymbol) (move : HeadMove)
(hmove :
zigzagIndex (move.updatePosition position) ≠
zigzagIndex position) :
zigzagRecordBits
((tape.write write).move move)
(move.updatePosition position)
(zigzagIndex position) =
[false, (encodeTapeSymbol write).1,
(encodeTapeSymbol write).2] := by
have hsymbol :=
zigzagRecordSymbol_old_head_after_write_move
tape position write move
have hmove' :
zigzagIndex position ≠
zigzagIndex (move.updatePosition position) :=
Ne.symm hmove
unfold zigzagRecordBits zigzagRecordFlag
rw [hsymbol]
simp [hmove']
theorem zigzagRecordBits_after_write_move_new
(tape : Tape) (position : Int)
(write : TapeSymbol) (move : HeadMove)
(hmove :
zigzagIndex (move.updatePosition position) ≠
zigzagIndex position) :
zigzagRecordBits
((tape.write write).move move)
(move.updatePosition position)
(zigzagIndex (move.updatePosition position)) =
[true,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex
(move.updatePosition position)))).1,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex
(move.updatePosition position)))).2] := by
have hsymbol :=
zigzagRecordSymbol_away_after_write_move
tape position write move
(zigzagIndex (move.updatePosition position))
hmove
unfold zigzagRecordBits zigzagRecordFlag
rw [hsymbol]
simp
theorem zigzagWorkBitsFrom_after_write_move_away
(tape : Tape) (position : Int)
(write : TapeSymbol) (move : HeadMove)
(firstIndex count : Nat)
(holdAway :
∀ offset < count,
firstIndex + offset ≠ zigzagIndex position)
(hnewAway :
∀ offset < count,
firstIndex + offset ≠
zigzagIndex (move.updatePosition position)) :
zigzagWorkBitsFrom
((tape.write write).move move)
(move.updatePosition position)
firstIndex count =
zigzagWorkBitsFrom tape position
firstIndex count := by
induction count generalizing firstIndex with
| zero => rfl
| succ count ih =>
have hold :
firstIndex ≠ zigzagIndex position := by
simpa using holdAway 0 (by omega)
have hnew :
firstIndex ≠
zigzagIndex (move.updatePosition position) := by
simpa using hnewAway 0 (by omega)
have holdRest :
∀ offset < count,
firstIndex + 1 + offset ≠
zigzagIndex position := by
intro offset hoffset
have := holdAway (offset + 1) (by omega)
simpa [Nat.add_assoc, Nat.add_comm,
Nat.add_left_comm] using this
have hnewRest :
∀ offset < count,
firstIndex + 1 + offset ≠
zigzagIndex
(move.updatePosition position) := by
intro offset hoffset
have := hnewAway (offset + 1) (by omega)
simpa [Nat.add_assoc, Nat.add_comm,
Nat.add_left_comm] using this
simp only [zigzagWorkBitsFrom_succ]
rw [zigzagRecordBits_after_write_move_away
tape position write move firstIndex hold hnew]
rw [ih (firstIndex + 1) holdRest hnewRest]
def zigzagUpdatedOutwardThreeStream
(records : List (Bool × Bool))
(write : TapeSymbol)
(nextFirst nextSecond : Bool)
(outward : List TapeSymbol) : List TapeSymbol :=
falseZigzagRecordsSymbols records ++
[.bit false,
.bit (encodeTapeSymbol write).1,
.bit (encodeTapeSymbol write).2,
.bit true, .bit nextFirst,
.bit nextSecond] ++ outward
theorem zigzagUpdate_iterate_records_outward_three
(write : TapeSymbol) (move : HeadMove)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(records : List (Bool × Bool))
(oldFirst oldSecond nextFirst nextSecond : Bool)
(outward : List TapeSymbol)
(hrelocation :
zigzagRelocation move
((ZigzagIndexClass.next^[records.length])
indexClass) =
some ⟨.outward, ⟨3, by decide⟩⟩)
(hcenterBits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
((zigzagUpdateConfigurationStep write move)^[
6 * records.length +
towardCenter.length + 17])
(.atFlag indexClass,
focusedScanStreamTape towardCenter archive
records oldFirst oldSecond
(.bit false :: .bit nextFirst ::
.bit nextSecond :: outward)) =
(.done,
⟨archive, .blank,
towardCenter.reverse ++
zigzagUpdatedOutwardThreeStream
records write nextFirst nextSecond
outward⟩) := by
induction records generalizing
indexClass towardCenter with
| nil =>
simp only [List.length_nil, Nat.mul_zero,
Nat.zero_add, Function.iterate_zero_apply,
focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
List.cons_append, List.nil_append,
zigzagUpdatedOutwardThreeStream,
falseZigzagRecordsSymbols,
List.flatMap_nil]
simpa [List.append_assoc] using
zigzagUpdate_iterate_outward_three_marker
write move indexClass towardCenter archive
oldFirst oldSecond nextFirst nextSecond
outward hrelocation hcenterBits
| cons record records ih =>
rcases record with ⟨first, second⟩
simp only [List.length_cons,
focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
List.cons_append, List.nil_append,
zigzagUpdatedOutwardThreeStream,
falseZigzagRecordsSymbols,
List.flatMap_cons,
falseZigzagRecordSymbols]
rw [zigzagScanRecordStream_eq]
let nextTowardCenter :=
.bit second :: .bit first ::
.bit false :: towardCenter
have hnextBits :
∀ symbol ∈ nextTowardCenter,
∃ bit, symbol = .bit bit := by
intro symbol hsymbol
simp only [nextTowardCenter,
List.mem_cons] at hsymbol
rcases hsymbol with rfl | rfl | rfl | hsymbol
· exact ⟨second, rfl⟩
· exact ⟨first, rfl⟩
· exact ⟨false, rfl⟩
· exact hcenterBits symbol hsymbol
have hrelocation' :
zigzagRelocation move
((ZigzagIndexClass.next^[records.length])
indexClass.next) =
some ⟨.outward, ⟨3, by decide⟩⟩ := by
simpa [Function.iterate_succ_apply] using
hrelocation
have hfirst :=
zigzagUpdate_false_record_three_steps
write move indexClass towardCenter archive
first second
(zigzagScanStreamFlag records)
(zigzagScanStreamAfterFlag records
oldFirst oldSecond
(.bit false :: .bit nextFirst ::
.bit nextSecond :: outward))
have ih' :=
ih indexClass.next nextTowardCenter
hrelocation' hnextBits
have htime :
6 * (records.length + 1) +
towardCenter.length + 17 =
(6 * records.length +
nextTowardCenter.length + 17) + 3 := by
simp [nextTowardCenter]
omega
rw [htime, Function.iterate_add_apply,
hfirst]
simpa [nextTowardCenter,
focusedScanStreamTape,
zigzagScanRecordStream_eq,
zigzagUpdatedOutwardThreeStream,
falseZigzagRecordsSymbols,
falseZigzagRecordSymbols,
List.append_assoc] using ih'
def zigzagUpdatedOutwardSixStream
(records : List (Bool × Bool))
(write : TapeSymbol)
(middleFirst middleSecond nextFirst nextSecond : Bool)
(outward : List TapeSymbol) : List TapeSymbol :=
falseZigzagRecordsSymbols records ++
[.bit false,
.bit (encodeTapeSymbol write).1,
.bit (encodeTapeSymbol write).2,
.bit false, .bit middleFirst,
.bit middleSecond,
.bit true, .bit nextFirst,
.bit nextSecond] ++ outward
theorem zigzagUpdate_iterate_records_outward_six
(write : TapeSymbol) (move : HeadMove)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(records : List (Bool × Bool))
(oldFirst oldSecond middleFirst middleSecond
nextFirst nextSecond : Bool)
(outward : List TapeSymbol)
(hrelocation :
zigzagRelocation move
((ZigzagIndexClass.next^[records.length])
indexClass) =
some ⟨.outward, ⟨6, by decide⟩⟩)
(hcenterBits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
((zigzagUpdateConfigurationStep write move)^[
6 * records.length +
towardCenter.length + 23])
(.atFlag indexClass,
focusedScanStreamTape towardCenter archive
records oldFirst oldSecond
(.bit false :: .bit middleFirst ::
.bit middleSecond :: .bit false ::
.bit nextFirst :: .bit nextSecond ::
outward)) =
(.done,
⟨archive, .blank,
towardCenter.reverse ++
zigzagUpdatedOutwardSixStream
records write middleFirst middleSecond
nextFirst nextSecond outward⟩) := by
induction records generalizing
indexClass towardCenter with
| nil =>
simp only [List.length_nil, Nat.mul_zero,
Nat.zero_add, Function.iterate_zero_apply,
focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
List.cons_append, List.nil_append,
zigzagUpdatedOutwardSixStream,
falseZigzagRecordsSymbols,
List.flatMap_nil]
simpa [List.append_assoc] using
zigzagUpdate_iterate_outward_six_marker
write move indexClass towardCenter archive
oldFirst oldSecond middleFirst middleSecond
nextFirst nextSecond outward
hrelocation hcenterBits
| cons record records ih =>
rcases record with ⟨first, second⟩
simp only [List.length_cons,
focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
List.cons_append, List.nil_append,
zigzagUpdatedOutwardSixStream,
falseZigzagRecordsSymbols,
List.flatMap_cons,
falseZigzagRecordSymbols]
rw [zigzagScanRecordStream_eq]
let nextTowardCenter :=
.bit second :: .bit first ::
.bit false :: towardCenter
have hnextBits :
∀ symbol ∈ nextTowardCenter,
∃ bit, symbol = .bit bit := by
intro symbol hsymbol
simp only [nextTowardCenter,
List.mem_cons] at hsymbol
rcases hsymbol with rfl | rfl | rfl | hsymbol
· exact ⟨second, rfl⟩
· exact ⟨first, rfl⟩
· exact ⟨false, rfl⟩
· exact hcenterBits symbol hsymbol
have hrelocation' :
zigzagRelocation move
((ZigzagIndexClass.next^[records.length])
indexClass.next) =
some ⟨.outward, ⟨6, by decide⟩⟩ := by
simpa [Function.iterate_succ_apply] using
hrelocation
have hfirst :=
zigzagUpdate_false_record_three_steps
write move indexClass towardCenter archive
first second
(zigzagScanStreamFlag records)
(zigzagScanStreamAfterFlag records
oldFirst oldSecond
(.bit false :: .bit middleFirst ::
.bit middleSecond :: .bit false ::
.bit nextFirst :: .bit nextSecond ::
outward))
have ih' :=
ih indexClass.next nextTowardCenter
hrelocation' hnextBits
have htime :
6 * (records.length + 1) +
towardCenter.length + 23 =
(6 * records.length +
nextTowardCenter.length + 23) + 3 := by
simp [nextTowardCenter]
omega
rw [htime, Function.iterate_add_apply,
hfirst]
simpa [nextTowardCenter,
focusedScanStreamTape,
zigzagScanRecordStream_eq,
zigzagUpdatedOutwardSixStream,
falseZigzagRecordsSymbols,
falseZigzagRecordSymbols,
List.append_assoc] using ih'
theorem zigzagWorkBits_after_move_outward_one
(tape : Tape) (position : Int)
(write : TapeSymbol) (move : HeadMove)
(extra : Nat)
(hnew :
zigzagIndex (move.updatePosition position) =
zigzagIndex position + 1) :
zigzagWorkBitsFrom
((tape.write write).move move)
(move.updatePosition position) 0
(zigzagIndex position + 2 + extra) =
zigzagWorkBitsFrom tape position 0
(zigzagIndex position) ++
[false, (encodeTapeSymbol write).1,
(encodeTapeSymbol write).2,
true,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex position + 1))).1,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex position + 1))).2] ++
zigzagWorkBitsFrom tape position
(zigzagIndex position + 2) extra := by
let updatedTape := (tape.write write).move move
let newPosition := move.updatePosition position
have hsplit :=
zigzagWorkBitsFrom_add updatedTape newPosition 0
(zigzagIndex position) (2 + extra)
have hprefix :
zigzagWorkBitsFrom updatedTape newPosition 0
(zigzagIndex position) =
zigzagWorkBitsFrom tape position 0
(zigzagIndex position) := by
apply zigzagWorkBitsFrom_after_write_move_away
· intro offset hoffset
omega
· intro offset hoffset
rw [hnew]
omega
have hold :=
zigzagRecordBits_after_write_move_old
tape position write move (by omega)
have hnewRecord :=
zigzagRecordBits_after_write_move_new
tape position write move (by omega)
rw [hnew] at hnewRecord
have htail :
zigzagWorkBitsFrom updatedTape newPosition
(zigzagIndex position + 2) extra =
zigzagWorkBitsFrom tape position
(zigzagIndex position + 2) extra := by
apply zigzagWorkBitsFrom_after_write_move_away
· intro offset hoffset
omega
· intro offset hoffset
rw [hnew]
omega
rw [show zigzagIndex position + 2 + extra =
zigzagIndex position + (2 + extra) by omega]
rw [hsplit, hprefix]
simp only [Nat.zero_add]
rw [show 2 + extra = (extra + 1) + 1 by omega,
zigzagWorkBitsFrom_succ,
zigzagWorkBitsFrom_succ]
rw [hold, hnewRecord, htail]
simp [List.append_assoc]
theorem zigzagWorkBits_after_move_outward_two
(tape : Tape) (position : Int)
(write : TapeSymbol) (move : HeadMove)
(extra : Nat)
(hnew :
zigzagIndex (move.updatePosition position) =
zigzagIndex position + 2) :
zigzagWorkBitsFrom
((tape.write write).move move)
(move.updatePosition position) 0
(zigzagIndex position + 3 + extra) =
zigzagWorkBitsFrom tape position 0
(zigzagIndex position) ++
[false, (encodeTapeSymbol write).1,
(encodeTapeSymbol write).2,
false,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex position + 1))).1,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex position + 1))).2,
true,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex position + 2))).1,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex position + 2))).2] ++
zigzagWorkBitsFrom tape position
(zigzagIndex position + 3) extra := by
let updatedTape := (tape.write write).move move
let newPosition := move.updatePosition position
have hsplit :=
zigzagWorkBitsFrom_add updatedTape newPosition 0
(zigzagIndex position) (3 + extra)
have hprefix :
zigzagWorkBitsFrom updatedTape newPosition 0
(zigzagIndex position) =
zigzagWorkBitsFrom tape position 0
(zigzagIndex position) := by
apply zigzagWorkBitsFrom_after_write_move_away
· intro offset hoffset
omega
· intro offset hoffset
rw [hnew]
omega
have hold :=
zigzagRecordBits_after_write_move_old
tape position write move (by omega)
have hmiddle :=
zigzagRecordBits_after_write_move_away
tape position write move
(zigzagIndex position + 1)
(by omega) (by omega)
have hnewRecord :=
zigzagRecordBits_after_write_move_new
tape position write move (by omega)
rw [hnew] at hnewRecord
have htail :
zigzagWorkBitsFrom updatedTape newPosition
(zigzagIndex position + 3) extra =
zigzagWorkBitsFrom tape position
(zigzagIndex position + 3) extra := by
apply zigzagWorkBitsFrom_after_write_move_away
· intro offset hoffset
omega
· intro offset hoffset
rw [hnew]
omega
rw [show zigzagIndex position + 3 + extra =
zigzagIndex position + (3 + extra) by omega]
rw [hsplit, hprefix]
simp only [Nat.zero_add]
rw [show 3 + extra = (extra + 2) + 1 by omega,
zigzagWorkBitsFrom_succ]
rw [show extra + 2 = (extra + 1) + 1 by omega,
zigzagWorkBitsFrom_succ,
zigzagWorkBitsFrom_succ]
rw [hold, hmiddle, hnewRecord, htail]
simp [zigzagRecordBits, zigzagRecordFlag,
List.append_assoc]
theorem zigzagUpdate_physicalTape_outward_one
(archive : List TapeSymbol)
(tape : Tape) (position : Int)
(recordCount : Nat)
(write : TapeSymbol) (move : HeadMove)
(hnew :
zigzagIndex (move.updatePosition position) =
zigzagIndex position + 1)
(hrelocation :
zigzagRelocation move
(ZigzagIndexClass.atIndex
(zigzagIndex position)) =
some ⟨.outward, ⟨3, by decide⟩⟩)
(hroom :
zigzagIndex position + 1 < recordCount) :
((zigzagUpdateConfigurationStep write move)^[
6 * zigzagIndex position + 17])
(.atFlag .zero,
Tape.move
(zigzagPhysicalTape archive tape position
recordCount)
.right) =
(.done,
zigzagPhysicalTape archive
((tape.write write).move move)
(move.updatePosition position) recordCount) := by
obtain ⟨extra, hcount⟩ :
∃ extra,
recordCount =
zigzagIndex position + 2 + extra := by
use recordCount - (zigzagIndex position + 2)
omega
subst recordCount
let records :=
zigzagRecordPairsFrom tape position 0
(zigzagIndex position)
let nextSymbol :=
zigzagRecordSymbol tape position
(zigzagIndex position + 1)
let tail :=
(zigzagWorkBitsFrom tape position
(zigzagIndex position + 2) extra).map
TapeSymbol.bit
have hrelocation' :
zigzagRelocation move
((ZigzagIndexClass.next^[records.length])
ZigzagIndexClass.zero) =
some ⟨.outward, ⟨3, by decide⟩⟩ := by
rw [zigzagRecordPairsFrom_length,
ZigzagIndexClass.iterate_next_zero]
exact hrelocation
have hupdate :=
zigzagUpdate_iterate_records_outward_three
write move ZigzagIndexClass.zero [] archive
records
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2
(encodeTapeSymbol nextSymbol).1
(encodeTapeSymbol nextSymbol).2
tail hrelocation' (by simp)
rw [zigzagRecordPairsFrom_length] at hupdate
simp only [List.length_nil, Nat.add_zero,
List.reverse_nil, List.nil_append] at hupdate
have holdSplit :=
zigzagWorkBits_split_at_marker tape position
(1 + extra)
have hafterMarker :
(zigzagWorkBitsFrom tape position
(zigzagIndex position + 1)
(1 + extra)).map TapeSymbol.bit =
[.bit false,
.bit (encodeTapeSymbol nextSymbol).1,
.bit (encodeTapeSymbol nextSymbol).2] ++
tail := by
rw [show 1 + extra = extra + 1 by omega,
zigzagWorkBitsFrom_succ]
simp [zigzagRecordBits, zigzagRecordFlag,
nextSymbol, tail, List.append_assoc]
rw [hafterMarker] at holdSplit
have hinitial :
Tape.move
(zigzagPhysicalTape archive tape position
(zigzagIndex position + 2 + extra))
.right =
focusedScanStreamTape [] archive records
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2
(.bit false ::
.bit (encodeTapeSymbol nextSymbol).1 ::
.bit (encodeTapeSymbol nextSymbol).2 ::
tail) := by
simp only [zigzagPhysicalTape, zigzagWorkBits]
rw [show zigzagIndex position + 2 + extra =
zigzagIndex position + 1 + (1 + extra) by
omega]
rw [holdSplit]
simpa [zigzagScanRecordStream,
List.append_assoc] using
zigzagScanRecordStream_move_right archive records
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2
(.bit false ::
.bit (encodeTapeSymbol nextSymbol).1 ::
.bit (encodeTapeSymbol nextSymbol).2 :: tail)
have htargetBits :=
zigzagWorkBits_after_move_outward_one
tape position write move extra hnew
have hprefix :=
zigzagWorkBitsFrom_before_marker
tape position 0 (zigzagIndex position)
(by simp)
have htargetSymbols :
(zigzagWorkBitsFrom
((tape.write write).move move)
(move.updatePosition position) 0
(zigzagIndex position + 2 + extra)).map
TapeSymbol.bit =
zigzagUpdatedOutwardThreeStream records write
(encodeTapeSymbol nextSymbol).1
(encodeTapeSymbol nextSymbol).2 tail := by
rw [htargetBits, List.map_append,
List.map_append, hprefix]
rfl
have hfinal :
(⟨archive, .blank,
zigzagUpdatedOutwardThreeStream records write
(encodeTapeSymbol nextSymbol).1
(encodeTapeSymbol nextSymbol).2 tail⟩ :
Tape) =
zigzagPhysicalTape archive
((tape.write write).move move)
(move.updatePosition position)
(zigzagIndex position + 2 + extra) := by
unfold zigzagPhysicalTape zigzagWorkBits
congr 1
exact htargetSymbols.symm
rw [hfinal] at hupdate
rw [hinitial]
exact hupdate
theorem zigzagUpdate_physicalTape_outward_two
(archive : List TapeSymbol)
(tape : Tape) (position : Int)
(recordCount : Nat)
(write : TapeSymbol) (move : HeadMove)
(hnew :
zigzagIndex (move.updatePosition position) =
zigzagIndex position + 2)
(hrelocation :
zigzagRelocation move
(ZigzagIndexClass.atIndex
(zigzagIndex position)) =
some ⟨.outward, ⟨6, by decide⟩⟩)
(hroom :
zigzagIndex position + 2 < recordCount) :
((zigzagUpdateConfigurationStep write move)^[
6 * zigzagIndex position + 23])
(.atFlag .zero,
Tape.move
(zigzagPhysicalTape archive tape position
recordCount)
.right) =
(.done,
zigzagPhysicalTape archive
((tape.write write).move move)
(move.updatePosition position) recordCount) := by
obtain ⟨extra, hcount⟩ :
∃ extra,
recordCount =
zigzagIndex position + 3 + extra := by
use recordCount - (zigzagIndex position + 3)
omega
subst recordCount
let records :=
zigzagRecordPairsFrom tape position 0
(zigzagIndex position)
let middleSymbol :=
zigzagRecordSymbol tape position
(zigzagIndex position + 1)
let nextSymbol :=
zigzagRecordSymbol tape position
(zigzagIndex position + 2)
let tail :=
(zigzagWorkBitsFrom tape position
(zigzagIndex position + 3) extra).map
TapeSymbol.bit
have hrelocation' :
zigzagRelocation move
((ZigzagIndexClass.next^[records.length])
ZigzagIndexClass.zero) =
some ⟨.outward, ⟨6, by decide⟩⟩ := by
rw [zigzagRecordPairsFrom_length,
ZigzagIndexClass.iterate_next_zero]
exact hrelocation
have hupdate :=
zigzagUpdate_iterate_records_outward_six
write move ZigzagIndexClass.zero [] archive
records
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2
(encodeTapeSymbol middleSymbol).1
(encodeTapeSymbol middleSymbol).2
(encodeTapeSymbol nextSymbol).1
(encodeTapeSymbol nextSymbol).2
tail hrelocation' (by simp)
rw [zigzagRecordPairsFrom_length] at hupdate
simp only [List.length_nil, Nat.add_zero,
List.reverse_nil, List.nil_append] at hupdate
have holdSplit :=
zigzagWorkBits_split_at_marker tape position
(2 + extra)
have hafterMarker :
(zigzagWorkBitsFrom tape position
(zigzagIndex position + 1)
(2 + extra)).map TapeSymbol.bit =
[.bit false,
.bit (encodeTapeSymbol middleSymbol).1,
.bit (encodeTapeSymbol middleSymbol).2,
.bit false,
.bit (encodeTapeSymbol nextSymbol).1,
.bit (encodeTapeSymbol nextSymbol).2] ++
tail := by
have hmiddleNe :
zigzagIndex position + 1 ≠
zigzagIndex position := by omega
have hnextNe :
zigzagIndex position + 1 + 1 ≠
zigzagIndex position := by omega
rw [show 2 + extra = (extra + 1) + 1 by omega,
zigzagWorkBitsFrom_succ,
zigzagWorkBitsFrom_succ]
simp [zigzagRecordBits, zigzagRecordFlag,
middleSymbol, nextSymbol, tail,
hmiddleNe, hnextNe, List.append_assoc]
rw [hafterMarker] at holdSplit
have hinitial :
Tape.move
(zigzagPhysicalTape archive tape position
(zigzagIndex position + 3 + extra))
.right =
focusedScanStreamTape [] archive records
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2
(.bit false ::
.bit (encodeTapeSymbol middleSymbol).1 ::
.bit (encodeTapeSymbol middleSymbol).2 ::
.bit false ::
.bit (encodeTapeSymbol nextSymbol).1 ::
.bit (encodeTapeSymbol nextSymbol).2 ::
tail) := by
simp only [zigzagPhysicalTape, zigzagWorkBits]
rw [show zigzagIndex position + 3 + extra =
zigzagIndex position + 1 + (2 + extra) by
omega]
rw [holdSplit]
simpa [zigzagScanRecordStream,
List.append_assoc] using
zigzagScanRecordStream_move_right archive records
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2
(.bit false ::
.bit (encodeTapeSymbol middleSymbol).1 ::
.bit (encodeTapeSymbol middleSymbol).2 ::
.bit false ::
.bit (encodeTapeSymbol nextSymbol).1 ::
.bit (encodeTapeSymbol nextSymbol).2 :: tail)
have htargetBits :=
zigzagWorkBits_after_move_outward_two
tape position write move extra hnew
have hprefix :=
zigzagWorkBitsFrom_before_marker
tape position 0 (zigzagIndex position)
(by simp)
have htargetSymbols :
(zigzagWorkBitsFrom
((tape.write write).move move)
(move.updatePosition position) 0
(zigzagIndex position + 3 + extra)).map
TapeSymbol.bit =
zigzagUpdatedOutwardSixStream records write
(encodeTapeSymbol middleSymbol).1
(encodeTapeSymbol middleSymbol).2
(encodeTapeSymbol nextSymbol).1
(encodeTapeSymbol nextSymbol).2 tail := by
rw [htargetBits, List.map_append,
List.map_append, hprefix]
rfl
have hfinal :
(⟨archive, .blank,
zigzagUpdatedOutwardSixStream records write
(encodeTapeSymbol middleSymbol).1
(encodeTapeSymbol middleSymbol).2
(encodeTapeSymbol nextSymbol).1
(encodeTapeSymbol nextSymbol).2 tail⟩ :
Tape) =
zigzagPhysicalTape archive
((tape.write write).move move)
(move.updatePosition position)
(zigzagIndex position + 3 + extra) := by
unfold zigzagPhysicalTape zigzagWorkBits
congr 1
exact htargetSymbols.symm
rw [hfinal] at hupdate
rw [hinitial]
exact hupdate
def zigzagUpdatedInwardThreeStream
(records : List (Bool × Bool))
(targetFirst targetSecond : Bool)
(write : TapeSymbol)
(outward : List TapeSymbol) : List TapeSymbol :=
falseZigzagRecordsSymbols records ++
[.bit true, .bit targetFirst, .bit targetSecond,
.bit false,
.bit (encodeTapeSymbol write).1,
.bit (encodeTapeSymbol write).2] ++ outward
theorem zigzagUpdate_iterate_records_inward_three
(write : TapeSymbol) (move : HeadMove)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(records : List (Bool × Bool))
(targetFirst targetSecond oldFirst oldSecond : Bool)
(outward : List TapeSymbol)
(hrelocation :
zigzagRelocation move
((ZigzagIndexClass.next^[
records.length + 1]) indexClass) =
some ⟨.inward, ⟨3, by decide⟩⟩)
(hcenterBits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
((zigzagUpdateConfigurationStep write move)^[
6 * records.length +
towardCenter.length + 17])
(.atFlag indexClass,
focusedScanStreamTape towardCenter archive
(records ++ [(targetFirst, targetSecond)])
oldFirst oldSecond outward) =
(.done,
⟨archive, .blank,
towardCenter.reverse ++
zigzagUpdatedInwardThreeStream
records targetFirst targetSecond
write outward⟩) := by
induction records generalizing
indexClass towardCenter with
| nil =>
simp only [List.length_nil, Nat.mul_zero,
Nat.zero_add, focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
List.cons_append, List.nil_append,
zigzagScanRecordStream,
zigzagUpdatedInwardThreeStream,
falseZigzagRecordsSymbols,
List.flatMap_nil]
have hfirst :=
zigzagUpdate_false_record_three_steps
write move indexClass towardCenter archive
targetFirst targetSecond true
(.bit oldFirst :: .bit oldSecond :: outward)
have hrelocation' :
zigzagRelocation move indexClass.next =
some ⟨.inward, ⟨3, by decide⟩⟩ := by
simpa [Function.iterate_succ_apply] using
hrelocation
have hmarker :=
zigzagUpdate_iterate_inward_three_marker
write move indexClass.next towardCenter archive
targetFirst targetSecond oldFirst oldSecond
outward hrelocation' hcenterBits
have htime :
towardCenter.length + 17 =
(towardCenter.length + 14) + 3 := by omega
rw [htime, Function.iterate_add_apply,
hfirst]
simpa [focusedBitTape,
List.append_assoc] using hmarker
| cons record records ih =>
rcases record with ⟨first, second⟩
simp only [List.length_cons,
focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
List.cons_append, List.nil_append,
zigzagUpdatedInwardThreeStream,
falseZigzagRecordsSymbols,
List.flatMap_cons,
falseZigzagRecordSymbols]
rw [zigzagScanRecordStream_eq]
let nextTowardCenter :=
.bit second :: .bit first ::
.bit false :: towardCenter
have hnextBits :
∀ symbol ∈ nextTowardCenter,
∃ bit, symbol = .bit bit := by
intro symbol hsymbol
simp only [nextTowardCenter,
List.mem_cons] at hsymbol
rcases hsymbol with rfl | rfl | rfl | hsymbol
· exact ⟨second, rfl⟩
· exact ⟨first, rfl⟩
· exact ⟨false, rfl⟩
· exact hcenterBits symbol hsymbol
have hrelocation' :
zigzagRelocation move
((ZigzagIndexClass.next^[
records.length + 1])
indexClass.next) =
some ⟨.inward, ⟨3, by decide⟩⟩ := by
simp only [List.length_cons] at hrelocation
rw [show records.length + 1 + 1 =
(records.length + 1) + 1 by omega] at hrelocation
simpa [Function.iterate_succ_apply] using
hrelocation
have hfirst :=
zigzagUpdate_false_record_three_steps
write move indexClass towardCenter archive
first second
(zigzagScanStreamFlag
(records ++ [(targetFirst, targetSecond)]))
(zigzagScanStreamAfterFlag
(records ++ [(targetFirst, targetSecond)])
oldFirst oldSecond outward)
have ih' :=
ih indexClass.next nextTowardCenter
hrelocation' hnextBits
have htime :
6 * (records.length + 1) +
towardCenter.length + 17 =
(6 * records.length +
nextTowardCenter.length + 17) + 3 := by
simp [nextTowardCenter]
omega
rw [htime, Function.iterate_add_apply,
hfirst]
simpa [nextTowardCenter,
focusedScanStreamTape,
zigzagScanRecordStream_eq,
zigzagUpdatedInwardThreeStream,
falseZigzagRecordsSymbols,
falseZigzagRecordSymbols,
List.append_assoc] using ih'
def zigzagUpdatedInwardSixStream
(records : List (Bool × Bool))
(targetFirst targetSecond
middleFirst middleSecond : Bool)
(write : TapeSymbol)
(outward : List TapeSymbol) : List TapeSymbol :=
falseZigzagRecordsSymbols records ++
[.bit true, .bit targetFirst, .bit targetSecond,
.bit false, .bit middleFirst, .bit middleSecond,
.bit false,
.bit (encodeTapeSymbol write).1,
.bit (encodeTapeSymbol write).2] ++ outward
theorem zigzagUpdate_iterate_records_inward_six
(write : TapeSymbol) (move : HeadMove)
(indexClass : ZigzagIndexClass)
(towardCenter archive : List TapeSymbol)
(records : List (Bool × Bool))
(targetFirst targetSecond middleFirst middleSecond
oldFirst oldSecond : Bool)
(outward : List TapeSymbol)
(hrelocation :
zigzagRelocation move
((ZigzagIndexClass.next^[
records.length + 2]) indexClass) =
some ⟨.inward, ⟨6, by decide⟩⟩)
(hcenterBits :
∀ symbol ∈ towardCenter,
∃ bit, symbol = .bit bit) :
((zigzagUpdateConfigurationStep write move)^[
6 * records.length +
towardCenter.length + 23])
(.atFlag indexClass,
focusedScanStreamTape towardCenter archive
(records ++
[(targetFirst, targetSecond),
(middleFirst, middleSecond)])
oldFirst oldSecond outward) =
(.done,
⟨archive, .blank,
towardCenter.reverse ++
zigzagUpdatedInwardSixStream
records targetFirst targetSecond
middleFirst middleSecond write
outward⟩) := by
induction records generalizing
indexClass towardCenter with
| nil =>
simp only [List.length_nil, Nat.mul_zero,
Nat.zero_add, focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
List.cons_append, List.nil_append,
zigzagScanRecordStream,
zigzagUpdatedInwardSixStream,
falseZigzagRecordsSymbols,
List.flatMap_cons, List.flatMap_nil,
falseZigzagRecordSymbols]
have htarget :=
zigzagUpdate_false_record_three_steps
write move indexClass towardCenter archive
targetFirst targetSecond false
(.bit middleFirst :: .bit middleSecond ::
.bit true :: .bit oldFirst ::
.bit oldSecond :: outward)
let afterTargetToward :=
.bit targetSecond :: .bit targetFirst ::
.bit false :: towardCenter
have hmiddle :=
zigzagUpdate_false_record_three_steps
write move indexClass.next afterTargetToward
archive middleFirst middleSecond true
(.bit oldFirst :: .bit oldSecond :: outward)
have hrelocation' :
zigzagRelocation move indexClass.next.next =
some ⟨.inward, ⟨6, by decide⟩⟩ := by
simpa [Function.iterate_succ_apply] using
hrelocation
have hmarker :=
zigzagUpdate_iterate_inward_six_marker
write move indexClass.next.next towardCenter archive
targetFirst targetSecond
middleFirst middleSecond
oldFirst oldSecond outward
hrelocation' hcenterBits
have htime :
towardCenter.length + 23 =
(towardCenter.length + 17) + 3 + 3 := by
omega
rw [htime, Function.iterate_add_apply,
Function.iterate_add_apply, htarget]
rw [hmiddle]
simpa [afterTargetToward, focusedBitTape,
List.append_assoc] using hmarker
| cons record records ih =>
rcases record with ⟨first, second⟩
simp only [List.length_cons,
focusedScanStreamTape,
zigzagScanStreamFlag,
zigzagScanStreamAfterFlag,
List.cons_append, List.nil_append,
zigzagUpdatedInwardSixStream,
falseZigzagRecordsSymbols,
List.flatMap_cons,
falseZigzagRecordSymbols]
rw [zigzagScanRecordStream_eq]
let nextTowardCenter :=
.bit second :: .bit first ::
.bit false :: towardCenter
have hnextBits :
∀ symbol ∈ nextTowardCenter,
∃ bit, symbol = .bit bit := by
intro symbol hsymbol
simp only [nextTowardCenter,
List.mem_cons] at hsymbol
rcases hsymbol with rfl | rfl | rfl | hsymbol
· exact ⟨second, rfl⟩
· exact ⟨first, rfl⟩
· exact ⟨false, rfl⟩
· exact hcenterBits symbol hsymbol
have hrelocation' :
zigzagRelocation move
((ZigzagIndexClass.next^[
records.length + 2])
indexClass.next) =
some ⟨.inward, ⟨6, by decide⟩⟩ := by
simp only [List.length_cons] at hrelocation
rw [show records.length + 1 + 2 =
(records.length + 2) + 1 by omega] at hrelocation
simpa [Function.iterate_succ_apply] using
hrelocation
have hfirst :=
zigzagUpdate_false_record_three_steps
write move indexClass towardCenter archive
first second
(zigzagScanStreamFlag
(records ++
[(targetFirst, targetSecond),
(middleFirst, middleSecond)]))
(zigzagScanStreamAfterFlag
(records ++
[(targetFirst, targetSecond),
(middleFirst, middleSecond)])
oldFirst oldSecond outward)
have ih' :=
ih indexClass.next nextTowardCenter
hrelocation' hnextBits
have htime :
6 * (records.length + 1) +
towardCenter.length + 23 =
(6 * records.length +
nextTowardCenter.length + 23) + 3 := by
simp [nextTowardCenter]
omega
rw [htime, Function.iterate_add_apply,
hfirst]
simpa [nextTowardCenter,
focusedScanStreamTape,
zigzagScanRecordStream_eq,
zigzagUpdatedInwardSixStream,
falseZigzagRecordsSymbols,
falseZigzagRecordSymbols,
List.append_assoc] using ih'
theorem zigzagRecordPairsFrom_add
(tape : Tape) (position : Int)
(firstIndex firstCount secondCount : Nat) :
zigzagRecordPairsFrom tape position firstIndex
(firstCount + secondCount) =
zigzagRecordPairsFrom tape position firstIndex
firstCount ++
zigzagRecordPairsFrom tape position
(firstIndex + firstCount) secondCount := by
induction firstCount generalizing firstIndex with
| zero =>
simp [zigzagRecordPairsFrom]
| succ firstCount ih =>
rw [show firstCount + 1 + secondCount =
(firstCount + secondCount) + 1 by omega]
simp only [zigzagRecordPairsFrom]
rw [ih (firstIndex + 1)]
rw [show firstIndex + 1 + firstCount =
firstIndex + (firstCount + 1) by omega]
simp [List.cons_append]
theorem zigzagWorkBits_after_move_inward_one
(tape : Tape) (position : Int)
(write : TapeSymbol) (move : HeadMove)
(extra : Nat)
(hnew :
zigzagIndex position =
zigzagIndex (move.updatePosition position) + 1) :
zigzagWorkBitsFrom
((tape.write write).move move)
(move.updatePosition position) 0
(zigzagIndex position + 1 + extra) =
zigzagWorkBitsFrom tape position 0
(zigzagIndex (move.updatePosition position)) ++
[true,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex
(move.updatePosition position)))).1,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex
(move.updatePosition position)))).2,
false, (encodeTapeSymbol write).1,
(encodeTapeSymbol write).2] ++
zigzagWorkBitsFrom tape position
(zigzagIndex position + 1) extra := by
let oldIndex := zigzagIndex position
let newIndex :=
zigzagIndex (move.updatePosition position)
let updatedTape := (tape.write write).move move
let newPosition := move.updatePosition position
have hsplit :=
zigzagWorkBitsFrom_add updatedTape newPosition 0
newIndex (2 + extra)
have hprefix :
zigzagWorkBitsFrom updatedTape newPosition 0
newIndex =
zigzagWorkBitsFrom tape position 0
newIndex := by
apply zigzagWorkBitsFrom_after_write_move_away
· intro offset hoffset
simp only [oldIndex, newIndex] at *
omega
· intro offset hoffset
simp only [newIndex] at *
omega
have hnewRecord :=
zigzagRecordBits_after_write_move_new
tape position write move (by
simp only [oldIndex, newIndex] at *
omega)
have hold :=
zigzagRecordBits_after_write_move_old
tape position write move (by
simp only [oldIndex, newIndex] at *
omega)
have htail :
zigzagWorkBitsFrom updatedTape newPosition
(oldIndex + 1) extra =
zigzagWorkBitsFrom tape position
(oldIndex + 1) extra := by
apply zigzagWorkBitsFrom_after_write_move_away
· intro offset hoffset
simp only [oldIndex] at *
omega
· intro offset hoffset
simp only [oldIndex, newIndex] at *
omega
rw [show oldIndex + 1 + extra =
newIndex + (2 + extra) by
simp only [oldIndex, newIndex] at *
omega]
rw [hsplit, hprefix]
simp only [Nat.zero_add]
rw [show 2 + extra = (extra + 1) + 1 by omega,
zigzagWorkBitsFrom_succ,
zigzagWorkBitsFrom_succ]
rw [show newIndex + 1 = oldIndex by
simp only [oldIndex, newIndex] at *
omega]
rw [hnewRecord, hold, htail]
simp [oldIndex, newIndex, List.append_assoc]
theorem zigzagWorkBits_after_move_inward_two
(tape : Tape) (position : Int)
(write : TapeSymbol) (move : HeadMove)
(extra : Nat)
(hnew :
zigzagIndex position =
zigzagIndex (move.updatePosition position) + 2) :
zigzagWorkBitsFrom
((tape.write write).move move)
(move.updatePosition position) 0
(zigzagIndex position + 1 + extra) =
zigzagWorkBitsFrom tape position 0
(zigzagIndex (move.updatePosition position)) ++
[true,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex
(move.updatePosition position)))).1,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex
(move.updatePosition position)))).2,
false,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex
(move.updatePosition position) + 1))).1,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(zigzagIndex
(move.updatePosition position) + 1))).2,
false, (encodeTapeSymbol write).1,
(encodeTapeSymbol write).2] ++
zigzagWorkBitsFrom tape position
(zigzagIndex position + 1) extra := by
let oldIndex := zigzagIndex position
let newIndex :=
zigzagIndex (move.updatePosition position)
let updatedTape := (tape.write write).move move
let newPosition := move.updatePosition position
have hsplit :=
zigzagWorkBitsFrom_add updatedTape newPosition 0
newIndex (3 + extra)
have hprefix :
zigzagWorkBitsFrom updatedTape newPosition 0
newIndex =
zigzagWorkBitsFrom tape position 0
newIndex := by
apply zigzagWorkBitsFrom_after_write_move_away
· intro offset hoffset
simp only [oldIndex, newIndex] at *
omega
· intro offset hoffset
simp only [newIndex] at *
omega
have hnewRecord :=
zigzagRecordBits_after_write_move_new
tape position write move (by
simp only [oldIndex, newIndex] at *
omega)
have hmiddleOld :
newIndex + 1 ≠ zigzagIndex position := by
dsimp [newIndex]
omega
have hmiddleNew :
newIndex + 1 ≠
zigzagIndex (move.updatePosition position) := by
dsimp [newIndex]
omega
have hmiddle :=
zigzagRecordBits_after_write_move_away
tape position write move (newIndex + 1)
hmiddleOld hmiddleNew
have hmiddleBits :
zigzagRecordBits tape position (newIndex + 1) =
[false,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(newIndex + 1))).1,
(encodeTapeSymbol
(zigzagRecordSymbol tape position
(newIndex + 1))).2] := by
unfold zigzagRecordBits zigzagRecordFlag
simp [hmiddleOld]
have hold :=
zigzagRecordBits_after_write_move_old
tape position write move (by
simp only [oldIndex, newIndex] at *
omega)
have htail :
zigzagWorkBitsFrom updatedTape newPosition
(oldIndex + 1) extra =
zigzagWorkBitsFrom tape position
(oldIndex + 1) extra := by
apply zigzagWorkBitsFrom_after_write_move_away
· intro offset hoffset
simp only [oldIndex] at *
omega
· intro offset hoffset
simp only [oldIndex, newIndex] at *
omega
rw [show oldIndex + 1 + extra =
newIndex + (3 + extra) by
simp only [oldIndex, newIndex] at *
omega]
rw [hsplit, hprefix]
simp only [Nat.zero_add]
rw [show 3 + extra = (extra + 2) + 1 by omega,
zigzagWorkBitsFrom_succ]
rw [show extra + 2 = (extra + 1) + 1 by omega,
zigzagWorkBitsFrom_succ,
zigzagWorkBitsFrom_succ]
rw [show newIndex + 1 + 1 = oldIndex by
simp only [oldIndex, newIndex] at *
omega]
rw [hnewRecord, hmiddle, hmiddleBits, hold, htail]
simp [zigzagRecordBits, zigzagRecordFlag,
oldIndex, newIndex, List.append_assoc]
theorem zigzagUpdate_physicalTape_inward_one
(archive : List TapeSymbol)
(tape : Tape) (position : Int)
(recordCount : Nat)
(write : TapeSymbol) (move : HeadMove)
(hnew :
zigzagIndex position =
zigzagIndex (move.updatePosition position) + 1)
(hrelocation :
zigzagRelocation move
(ZigzagIndexClass.atIndex
(zigzagIndex position)) =
some ⟨.inward, ⟨3, by decide⟩⟩)
(hhead : zigzagIndex position < recordCount) :
((zigzagUpdateConfigurationStep write move)^[
6 * zigzagIndex (move.updatePosition position) +
17])
(.atFlag .zero,
Tape.move
(zigzagPhysicalTape archive tape position
recordCount)
.right) =
(.done,
zigzagPhysicalTape archive
((tape.write write).move move)
(move.updatePosition position) recordCount) := by
obtain ⟨extra, hcount⟩ :
∃ extra,
recordCount =
zigzagIndex position + 1 + extra := by
use recordCount - (zigzagIndex position + 1)
omega
subst recordCount
let newIndex :=
zigzagIndex (move.updatePosition position)
let records :=
zigzagRecordPairsFrom tape position 0 newIndex
let targetSymbol :=
zigzagRecordSymbol tape position newIndex
let tail :=
(zigzagWorkBitsFrom tape position
(zigzagIndex position + 1) extra).map
TapeSymbol.bit
have hrelocation' :
zigzagRelocation move
((ZigzagIndexClass.next^[
records.length + 1])
ZigzagIndexClass.zero) =
some ⟨.inward, ⟨3, by decide⟩⟩ := by
rw [zigzagRecordPairsFrom_length]
rw [show newIndex + 1 =
zigzagIndex position by
simp only [newIndex] at *
omega]
rw [ZigzagIndexClass.iterate_next_zero]
exact hrelocation
have hupdate :=
zigzagUpdate_iterate_records_inward_three
write move ZigzagIndexClass.zero [] archive
records
(encodeTapeSymbol targetSymbol).1
(encodeTapeSymbol targetSymbol).2
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2
tail hrelocation' (by simp)
rw [zigzagRecordPairsFrom_length] at hupdate
simp only [List.length_nil, Nat.add_zero,
List.reverse_nil, List.nil_append] at hupdate
have hrecordsSplit :
zigzagRecordPairsFrom tape position 0
(zigzagIndex position) =
records ++
[(encodeTapeSymbol targetSymbol)] := by
have hsplit :=
zigzagRecordPairsFrom_add tape position 0
newIndex 1
rw [show newIndex + 1 =
zigzagIndex position by
simp only [newIndex] at *
omega] at hsplit
simpa [records, targetSymbol,
zigzagRecordPairsFrom] using hsplit
have holdSplit :=
zigzagWorkBits_split_at_marker tape position extra
rw [hrecordsSplit] at holdSplit
have hinitial :
Tape.move
(zigzagPhysicalTape archive tape position
(zigzagIndex position + 1 + extra))
.right =
focusedScanStreamTape [] archive
(records ++
[((encodeTapeSymbol targetSymbol).1,
(encodeTapeSymbol targetSymbol).2)])
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2 tail := by
simp only [zigzagPhysicalTape, zigzagWorkBits]
rw [holdSplit]
simpa [zigzagScanRecordStream,
falseZigzagRecordsSymbols,
falseZigzagRecordSymbols,
List.append_assoc] using
zigzagScanRecordStream_move_right archive
(records ++
[((encodeTapeSymbol targetSymbol).1,
(encodeTapeSymbol targetSymbol).2)])
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2 tail
have htargetBits :=
zigzagWorkBits_after_move_inward_one
tape position write move extra hnew
have hprefix :=
zigzagWorkBitsFrom_before_marker
tape position 0 newIndex (by
dsimp [newIndex]
omega)
have htargetSymbols :
(zigzagWorkBitsFrom
((tape.write write).move move)
(move.updatePosition position) 0
(zigzagIndex position + 1 + extra)).map
TapeSymbol.bit =
zigzagUpdatedInwardThreeStream records
(encodeTapeSymbol targetSymbol).1
(encodeTapeSymbol targetSymbol).2
write tail := by
rw [htargetBits, List.map_append,
List.map_append, hprefix]
rfl
have hfinal :
(⟨archive, .blank,
zigzagUpdatedInwardThreeStream records
(encodeTapeSymbol targetSymbol).1
(encodeTapeSymbol targetSymbol).2
write tail⟩ : Tape) =
zigzagPhysicalTape archive
((tape.write write).move move)
(move.updatePosition position)
(zigzagIndex position + 1 + extra) := by
unfold zigzagPhysicalTape zigzagWorkBits
congr 1
exact htargetSymbols.symm
rw [hfinal] at hupdate
rw [hinitial]
simpa [newIndex] using hupdate
theorem zigzagUpdate_physicalTape_inward_two
(archive : List TapeSymbol)
(tape : Tape) (position : Int)
(recordCount : Nat)
(write : TapeSymbol) (move : HeadMove)
(hnew :
zigzagIndex position =
zigzagIndex (move.updatePosition position) + 2)
(hrelocation :
zigzagRelocation move
(ZigzagIndexClass.atIndex
(zigzagIndex position)) =
some ⟨.inward, ⟨6, by decide⟩⟩)
(hhead : zigzagIndex position < recordCount) :
((zigzagUpdateConfigurationStep write move)^[
6 * zigzagIndex (move.updatePosition position) +
23])
(.atFlag .zero,
Tape.move
(zigzagPhysicalTape archive tape position
recordCount)
.right) =
(.done,
zigzagPhysicalTape archive
((tape.write write).move move)
(move.updatePosition position) recordCount) := by
obtain ⟨extra, hcount⟩ :
∃ extra,
recordCount =
zigzagIndex position + 1 + extra := by
use recordCount - (zigzagIndex position + 1)
omega
subst recordCount
let newIndex :=
zigzagIndex (move.updatePosition position)
let records :=
zigzagRecordPairsFrom tape position 0 newIndex
let targetSymbol :=
zigzagRecordSymbol tape position newIndex
let middleSymbol :=
zigzagRecordSymbol tape position (newIndex + 1)
let tail :=
(zigzagWorkBitsFrom tape position
(zigzagIndex position + 1) extra).map
TapeSymbol.bit
have hrelocation' :
zigzagRelocation move
((ZigzagIndexClass.next^[
records.length + 2])
ZigzagIndexClass.zero) =
some ⟨.inward, ⟨6, by decide⟩⟩ := by
rw [zigzagRecordPairsFrom_length]
rw [show newIndex + 2 =
zigzagIndex position by
simp only [newIndex] at *
omega]
rw [ZigzagIndexClass.iterate_next_zero]
exact hrelocation
have hupdate :=
zigzagUpdate_iterate_records_inward_six
write move ZigzagIndexClass.zero [] archive
records
(encodeTapeSymbol targetSymbol).1
(encodeTapeSymbol targetSymbol).2
(encodeTapeSymbol middleSymbol).1
(encodeTapeSymbol middleSymbol).2
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2
tail hrelocation' (by simp)
rw [zigzagRecordPairsFrom_length] at hupdate
simp only [List.length_nil, Nat.add_zero,
List.reverse_nil, List.nil_append] at hupdate
have hrecordsSplit :
zigzagRecordPairsFrom tape position 0
(zigzagIndex position) =
records ++
[(encodeTapeSymbol targetSymbol),
(encodeTapeSymbol middleSymbol)] := by
have hsplit :=
zigzagRecordPairsFrom_add tape position 0
newIndex 2
rw [show newIndex + 2 =
zigzagIndex position by
simp only [newIndex] at *
omega] at hsplit
simpa [records, targetSymbol, middleSymbol,
zigzagRecordPairsFrom] using hsplit
have holdSplit :=
zigzagWorkBits_split_at_marker tape position extra
rw [hrecordsSplit] at holdSplit
have hinitial :
Tape.move
(zigzagPhysicalTape archive tape position
(zigzagIndex position + 1 + extra))
.right =
focusedScanStreamTape [] archive
(records ++
[((encodeTapeSymbol targetSymbol).1,
(encodeTapeSymbol targetSymbol).2),
((encodeTapeSymbol middleSymbol).1,
(encodeTapeSymbol middleSymbol).2)])
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2 tail := by
simp only [zigzagPhysicalTape, zigzagWorkBits]
rw [holdSplit]
simpa [zigzagScanRecordStream,
falseZigzagRecordsSymbols,
falseZigzagRecordSymbols,
List.append_assoc] using
zigzagScanRecordStream_move_right archive
(records ++
[((encodeTapeSymbol targetSymbol).1,
(encodeTapeSymbol targetSymbol).2),
((encodeTapeSymbol middleSymbol).1,
(encodeTapeSymbol middleSymbol).2)])
(encodeTapeSymbol tape.head).1
(encodeTapeSymbol tape.head).2 tail
have htargetBits :=
zigzagWorkBits_after_move_inward_two
tape position write move extra hnew
have hprefix :=
zigzagWorkBitsFrom_before_marker
tape position 0 newIndex (by
dsimp [newIndex]
omega)
have htargetSymbols :
(zigzagWorkBitsFrom
((tape.write write).move move)
(move.updatePosition position) 0
(zigzagIndex position + 1 + extra)).map
TapeSymbol.bit =
zigzagUpdatedInwardSixStream records
(encodeTapeSymbol targetSymbol).1
(encodeTapeSymbol targetSymbol).2
(encodeTapeSymbol middleSymbol).1
(encodeTapeSymbol middleSymbol).2
write tail := by
rw [htargetBits, List.map_append,
List.map_append, hprefix]
rfl
have hfinal :
(⟨archive, .blank,
zigzagUpdatedInwardSixStream records
(encodeTapeSymbol targetSymbol).1
(encodeTapeSymbol targetSymbol).2
(encodeTapeSymbol middleSymbol).1
(encodeTapeSymbol middleSymbol).2
write tail⟩ : Tape) =
zigzagPhysicalTape archive
((tape.write write).move move)
(move.updatePosition position)
(zigzagIndex position + 1 + extra) := by
unfold zigzagPhysicalTape zigzagWorkBits
congr 1
exact htargetSymbols.symm
rw [hfinal] at hupdate
rw [hinitial]
simpa [newIndex] using hupdate
theorem zigzagUpdate_pad
(write : TapeSymbol) (move : HeadMove)
(initial final :
ZigzagUpdateLocal × Tape)
(steps bound : Nat)
(hle : steps ≤ bound)
(hrun :
((zigzagUpdateConfigurationStep write move)^[
steps]) initial = final)
(hfinal : final.1 = .done) :
((zigzagUpdateConfigurationStep write move)^[
bound]) initial = final := by
obtain ⟨extra, hbound⟩ :=
Nat.exists_eq_add_of_le hle
rw [hbound, Nat.add_comm,
Function.iterate_add_apply, hrun]
apply Function.iterate_fixed
rcases final with ⟨state, tape⟩
simp only at hfinal
subst state
rfl
theorem zigzagUpdate_physicalTape
(archive : List TapeSymbol)
(tape : Tape) (position : Int)
(recordCount : Nat)
(write : TapeSymbol) (move : HeadMove)
(hroom :
zigzagIndex position + 2 < recordCount) :
((zigzagUpdateConfigurationStep write move)^[
6 * zigzagIndex position + 23])
(.atFlag .zero,
Tape.move
(zigzagPhysicalTape archive tape position
recordCount)
.right) =
(.done,
zigzagPhysicalTape archive
((tape.write write).move move)
(move.updatePosition position) recordCount) := by
have hhead :
zigzagIndex position < recordCount := by omega
cases move with
| stay =>
apply zigzagUpdate_pad write .stay _ _
(6 * zigzagIndex position + 10)
(6 * zigzagIndex position + 23)
(by omega)
· simpa [HeadMove.updatePosition,
HeadMove.displacement] using
zigzagUpdate_physicalTape_stay
archive tape position recordCount write hhead
· rfl
| left =>
cases position with
| ofNat n =>
cases n with
| zero =>
apply zigzagUpdate_physicalTape_outward_two
· rfl
· rfl
· exact hroom
| succ n =>
cases n with
| zero =>
have hnew :
zigzagIndex (Int.ofNat 1) =
zigzagIndex
(HeadMove.left.updatePosition
(Int.ofNat 1)) + 1 := by
rfl
have hrun :=
zigzagUpdate_physicalTape_inward_one
archive tape (Int.ofNat 1)
recordCount write .left hnew
(by rfl) hhead
apply zigzagUpdate_pad write .left _ _
(6 * zigzagIndex
(HeadMove.left.updatePosition
(Int.ofNat 1)) + 17)
(6 * zigzagIndex (Int.ofNat 1) + 23)
· simp [HeadMove.updatePosition,
HeadMove.displacement, zigzagIndex]
· exact hrun
· rfl
| succ n =>
have hnew :
zigzagIndex (Int.ofNat (n + 2)) =
zigzagIndex
(HeadMove.left.updatePosition
(Int.ofNat (n + 2))) + 2 := by
simpa [zigzagRelocation,
ZigzagIndexClass.at_zigzagIndex] using
(zigzagIndex_updatePosition
(Int.ofNat (n + 2)) .left)
have hrelocation :
zigzagRelocation .left
(ZigzagIndexClass.atIndex
(zigzagIndex
(Int.ofNat (n + 2)))) =
some
⟨.inward, ⟨6, by decide⟩⟩ := by
rw [ZigzagIndexClass.at_zigzagIndex]
rfl
have hrun :=
zigzagUpdate_physicalTape_inward_two
archive tape (Int.ofNat (n + 2))
recordCount write .left hnew
hrelocation (by simpa using hhead)
apply zigzagUpdate_pad write .left _ _
(6 * zigzagIndex
(HeadMove.left.updatePosition
(Int.ofNat (n + 2))) + 23)
(6 * zigzagIndex
(Int.ofNat (n + 2)) + 23)
· omega
· exact hrun
· rfl
| negSucc n =>
have hnew :
zigzagIndex
(HeadMove.left.updatePosition
(Int.negSucc n)) =
zigzagIndex (Int.negSucc n) + 2 := by
simpa [zigzagRelocation,
ZigzagIndexClass.at_zigzagIndex] using
(zigzagIndex_updatePosition
(Int.negSucc n) .left)
have hrelocation :
zigzagRelocation .left
(ZigzagIndexClass.atIndex
(zigzagIndex (Int.negSucc n))) =
some ⟨.outward, ⟨6, by decide⟩⟩ := by
rw [ZigzagIndexClass.at_zigzagIndex]
rfl
exact
zigzagUpdate_physicalTape_outward_two
archive tape (Int.negSucc n) recordCount
write .left hnew hrelocation
(by simpa using hroom)
| right =>
cases position with
| ofNat n =>
cases n with
| zero =>
have hrun :=
zigzagUpdate_physicalTape_outward_one
archive tape (0 : Int) recordCount
write .right
(by rfl) (by rfl)
(by
have hroom' :
zigzagIndex (Int.ofNat 0) + 1 <
recordCount := by
omega
simpa [zigzagIndex] using hroom')
apply zigzagUpdate_pad write .right _ _
17 23 (by omega)
· simpa [zigzagIndex] using hrun
· rfl
| succ n =>
cases n with
| zero =>
exact
zigzagUpdate_physicalTape_outward_two
archive tape (Int.ofNat 1)
recordCount write .right
(by rfl) (by rfl)
(by simpa using hroom)
| succ n =>
have hnew :
zigzagIndex
(HeadMove.right.updatePosition
(Int.ofNat (n + 2))) =
zigzagIndex (Int.ofNat (n + 2)) + 2 := by
simpa [zigzagRelocation,
ZigzagIndexClass.at_zigzagIndex] using
(zigzagIndex_updatePosition
(Int.ofNat (n + 2)) .right)
have hrelocation :
zigzagRelocation .right
(ZigzagIndexClass.atIndex
(zigzagIndex
(Int.ofNat (n + 2)))) =
some
⟨.outward, ⟨6, by decide⟩⟩ := by
rw [ZigzagIndexClass.at_zigzagIndex]
rfl
exact
zigzagUpdate_physicalTape_outward_two
archive tape (Int.ofNat (n + 2))
recordCount write .right hnew
hrelocation (by simpa using hroom)
| negSucc n =>
have hnew :
zigzagIndex (Int.negSucc n) =
zigzagIndex
(HeadMove.right.updatePosition
(Int.negSucc n)) + 2 := by
simpa [zigzagRelocation,
ZigzagIndexClass.at_zigzagIndex] using
(zigzagIndex_updatePosition
(Int.negSucc n) .right)
have hrelocation :
zigzagRelocation .right
(ZigzagIndexClass.atIndex
(zigzagIndex (Int.negSucc n))) =
some ⟨.inward, ⟨6, by decide⟩⟩ := by
rw [ZigzagIndexClass.at_zigzagIndex]
rfl
have hrun :=
zigzagUpdate_physicalTape_inward_two
archive tape (Int.negSucc n) recordCount
write .right hnew hrelocation
(by simpa using hhead)
apply zigzagUpdate_pad write .right _ _
(6 * zigzagIndex
(HeadMove.right.updatePosition
(Int.negSucc n)) + 23)
(6 * zigzagIndex (Int.negSucc n) + 23)
· omega
· exact hrun
· rfl
end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.