Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

SGL zigzag local correctness

Definition
sgl_zigzag_correctness

by Henry Yuen · Jul 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-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 hrelocation :
                      zigzagRelocation .left
                          (ZigzagIndexClass.atIndex
                            (zigzagIndex
                              (Int.ofNat (n + 2)))) =
                        some
                          ⟨.inward, ⟨6, by decide⟩⟩ := by
                    rw [ZigzagIndexClass.at_zigzagIndex]
                    rfl
                  have hnew :
                      zigzagIndex (Int.ofNat (n + 2)) =
                        zigzagIndex
                            (HeadMove.left.updatePosition
                              (Int.ofNat (n + 2))) + 2 := by
                    have h :=
                      zigzagIndex_updatePosition
                        (Int.ofNat (n + 2)) .left
                    simp only [hrelocation] at h
                    exact h
                  have hrun :=
                    zigzagUpdate_physicalTape_inward_two
                      archive tape (Int.ofNat (n + 2))
                      recordCount write .left hnew
                      hrelocation 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 hrelocation :
                      zigzagRelocation .right
                          (ZigzagIndexClass.atIndex
                            (zigzagIndex
                              (Int.ofNat (n + 2)))) =
                        some
                          ⟨.outward, ⟨6, by decide⟩⟩ := by
                    rw [ZigzagIndexClass.at_zigzagIndex]
                    rfl
                  have hnew :
                      zigzagIndex
                          (HeadMove.right.updatePosition
                            (Int.ofNat (n + 2))) =
                        zigzagIndex (Int.ofNat (n + 2)) + 2 := by
                    have h :=
                      zigzagIndex_updatePosition
                        (Int.ofNat (n + 2)) .right
                    simp only [hrelocation] at h
                    exact h
                  exact
                    zigzagUpdate_physicalTape_outward_two
                      archive tape (Int.ofNat (n + 2))
                      recordCount write .right hnew
                      hrelocation 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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me