Tape observational equivalence for SGL machines
Definitionsgl_tape_observational_equivalencecomplexity-theorysipser-gacs-lautemannturing-machines
This helper replaces exact tape-list equality by observational equivalence: two tapes are equivalent when every integer-offset read from the current head returns the same symbol.
The file proves that this equivalence is preserved by writes, head moves, machine steps, and machine runs. Consequently, two initial configurations that are observationally equivalent produce the same accepting and rejecting result at every fixed time.
This is intended to remove brittle exact-reset obligations in the Sipser--Gács--Lautemann machine-construction proofs, where finite scans can leave harmless extra blank cells in the concrete list representation.
Definition code
import Solutions.Scratch_SipserGacsLautemann_tape_observational_equivalence
Source
Prove2me Sipser--Gács--Lautemann mission; derived from the tape read-relative API in sgl_zigzag_correctness.