Preprocess-and-delegate DPT theorem up to observational tape equivalence
Definitionsgl_preprocess_delegate_obseqcomplexity-theorysipser-gacs-lautemannturing-machines
This helper is a robust variant of the standard preprocess-and-delegate construction for deterministic polynomial-time machines.
A finite preprocessing machine need not reset its tapes to the exact concrete zipper representation Tape.ofBits; it is enough to reach a configuration observationally equivalent to the transformed initial configuration. If the machine delegates future steps and result states to the base machine from that configuration, then the transformed predicate is still decidable in polynomial time.
This is designed for the Sipser--Gács--Lautemann scheduler obligations where scans may leave harmless extra blank cells in the list representation.
Definition code
import Solutions.Scratch_SipserGacsLautemann_preprocess_delegate_obseq
Source
Prove2me Sipser--Gács--Lautemann mission; combines sgl_preprocess_delegate with sgl_tape_observational_equivalence.