Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Tape observational equivalence for SGL machines, full module

Definition
sgl_tape_observational_equivalence_full

by Henry Yuen · Jul 24, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theorysipser-gacs-lautemannturing-machines

Full-code module defining observational equivalence of SGL tapes and configurations. Two tapes are equivalent when every integer-offset read from the current head returns the same symbol. The module proves preservation under writes, moves, machine steps, and machine runs, so observationally equivalent initial configurations have the same accepting and rejecting results at every fixed time.

Definition code
import Definitions.Def_sgl_zigzag_correctness

namespace SipserGacsLautemann

namespace Tape

def ObsEq (left right : Tape) : Prop :=
  ∀ offset : Int, left.readRelative offset = right.readRelative offset

theorem ObsEq.refl (tape : Tape) : ObsEq tape tape := by
  intro offset
  rfl

theorem ObsEq.symm {left right : Tape}
    (h : ObsEq left right) : ObsEq right left := by
  intro offset
  exact (h offset).symm

theorem ObsEq.trans {a b c : Tape}
    (hab : ObsEq a b) (hbc : ObsEq b c) :
    ObsEq a c := by
  intro offset
  exact (hab offset).trans (hbc offset)

theorem ObsEq.head_eq {left right : Tape}
    (h : ObsEq left right) :
    left.head = right.head := by
  simpa [Tape.readRelative] using h 0

theorem ObsEq.write {left right : Tape}
    (h : ObsEq left right) (symbol : TapeSymbol) :
    ObsEq (left.write symbol) (right.write symbol) := by
  intro offset
  rw [Tape.readRelative_write, Tape.readRelative_write]
  by_cases hzero : offset = 0
  · simp [hzero]
  · simp [hzero, h offset]

theorem ObsEq.move {left right : Tape}
    (h : ObsEq left right) (move : HeadMove) :
    ObsEq (left.move move) (right.move move) := by
  intro offset
  rw [Tape.readRelative_move_recenter,
    Tape.readRelative_move_recenter]
  exact h (offset + move.displacement)

theorem ObsEq.write_move {left right : Tape}
    (h : ObsEq left right)
    (symbol : TapeSymbol) (move : HeadMove) :
    ObsEq ((left.write symbol).move move)
      ((right.write symbol).move move) := by
  exact (h.write symbol).move move

end Tape

def Configuration.ObsEq {tapes states : Nat}
    (left right : Configuration tapes states) : Prop :=
  left.state = right.state ∧
    ∀ i : Fin tapes, Tape.ObsEq (left.tape i) (right.tape i)

namespace Configuration

theorem ObsEq.refl {tapes states : Nat}
    (configuration : Configuration tapes states) :
    ObsEq configuration configuration := by
  constructor
  · rfl
  · intro i
    exact Tape.ObsEq.refl _

theorem ObsEq.symm {tapes states : Nat}
    {left right : Configuration tapes states}
    (h : ObsEq left right) :
    ObsEq right left := by
  constructor
  · exact h.1.symm
  · intro i
    exact (h.2 i).symm

theorem ObsEq.trans {tapes states : Nat}
    {a b c : Configuration tapes states}
    (hab : ObsEq a b) (hbc : ObsEq b c) :
    ObsEq a c := by
  constructor
  · exact hab.1.trans hbc.1
  · intro i
    exact (hab.2 i).trans (hbc.2 i)

theorem ObsEq.heads_eq {tapes states : Nat}
    {left right : Configuration tapes states}
    (h : ObsEq left right) :
    (fun i : Fin tapes => (left.tape i).head) =
      fun i : Fin tapes => (right.tape i).head := by
  funext i
  exact (h.2 i).head_eq

end Configuration

theorem Machine.step_obsEq {tapes states : Nat}
    (machine : Machine tapes states)
    {left right : Configuration tapes states}
    (h : Configuration.ObsEq left right) :
    Configuration.ObsEq
      (machine.step left) (machine.step right) := by
  cases left with
  | mk leftState leftTape =>
    cases right with
    | mk rightState rightTape =>
      rcases h with ⟨hstate, htape⟩
      change leftState = rightState at hstate
      subst rightState
      cases hresult : machine.result leftState with
      | some result =>
          simp [Machine.step, hresult, Configuration.ObsEq,
            htape]
      | none =>
          have hheads :
              (fun i : Fin tapes => (leftTape i).head) =
                fun i : Fin tapes => (rightTape i).head := by
            funext i
            exact (htape i).head_eq
          simp only [Machine.step, hresult]
          rw [hheads]
          constructor
          · rfl
          · intro i
            exact
              (htape i).write_move
                ((machine.transition leftState
                  (fun i => (rightTape i).head)).2 i).1
                ((machine.transition leftState
                  (fun i => (rightTape i).head)).2 i).2

theorem Machine.run_obsEq {tapes states : Nat}
    (machine : Machine tapes states)
    {left right : Configuration tapes states}
    (h : Configuration.ObsEq left right) :
    ∀ steps : Nat,
      Configuration.ObsEq
        ((machine.step^[steps]) left)
        ((machine.step^[steps]) right)
  | 0 => h
  | steps + 1 => by
      rw [Function.iterate_succ_apply',
        Function.iterate_succ_apply']
      exact machine.step_obsEq
        (machine.run_obsEq h steps)

theorem Machine.result_eq_of_obsEq {tapes states : Nat}
    (machine : Machine tapes states)
    {left right : Configuration tapes states}
    (h : Configuration.ObsEq left right) :
    machine.result left.state = machine.result right.state := by
  rw [h.1]

theorem Machine.result_iterate_eq_of_obsEq {tapes states : Nat}
    (machine : Machine tapes states)
    {left right : Configuration tapes states}
    (h : Configuration.ObsEq left right)
    (steps : Nat) :
    machine.result ((machine.step^[steps]) left).state =
      machine.result ((machine.step^[steps]) right).state := by
  exact machine.result_eq_of_obsEq
    (machine.run_obsEq h steps)

theorem Machine.run_result_eq_of_initial_obsEq
    {tapes states : Nat}
    (machine : Machine tapes states)
    (input₁ input₂ : Fin tapes → List Bool)
    (hinput :
      Configuration.ObsEq
        (initialConfiguration machine input₁)
        (initialConfiguration machine input₂))
    (steps : Nat) :
    machine.result (machine.run input₁ steps).state =
      machine.result (machine.run input₂ steps).state := by
  have hrun :
      Configuration.ObsEq
        (machine.run input₁ steps)
        (machine.run input₂ steps) := by
    induction steps with
    | zero =>
        exact hinput
    | succ steps ih =>
        rw [Machine.run, Machine.run]
        exact machine.step_obsEq ih
  exact machine.result_eq_of_obsEq hrun

theorem Machine.acceptsWithin_iff_of_initial_obsEq
    {tapes states : Nat}
    (machine : Machine tapes states)
    (input₁ input₂ : Fin tapes → List Bool)
    (hinput :
      Configuration.ObsEq
        (initialConfiguration machine input₁)
        (initialConfiguration machine input₂))
    (steps : Nat) :
    machine.acceptsWithin input₁ steps ↔
      machine.acceptsWithin input₂ steps := by
  unfold Machine.acceptsWithin
  rw [machine.run_result_eq_of_initial_obsEq
    input₁ input₂ hinput steps]

theorem Machine.rejectsWithin_iff_of_initial_obsEq
    {tapes states : Nat}
    (machine : Machine tapes states)
    (input₁ input₂ : Fin tapes → List Bool)
    (hinput :
      Configuration.ObsEq
        (initialConfiguration machine input₁)
        (initialConfiguration machine input₂))
    (steps : Nat) :
    machine.rejectsWithin input₁ steps ↔
      machine.rejectsWithin input₂ steps := by
  unfold Machine.rejectsWithin
  rw [machine.run_result_eq_of_initial_obsEq
    input₁ input₂ hinput steps]

end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; full-code replacement for the stubbed observational-equivalence helper.

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