Tape observational equivalence for SGL machines, full module
Definitionsgl_tape_observational_equivalence_fullcomplexity-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.