Binary TM simulation of Teutsch’s folded disperser neighbor queries
ProvedCNFEncComplexity.teutschNbr_polytimeLet be a fixed, coin-free log-cost RAM program and let be fixed natural numbers. On a binary query , set and use the degree budget to decode into a layer and a local slot. Reject layers outside the range of or above , and reject .
For a valid layer , simulate on for steps starting with zero-filled memory elsewhere. Treat a halted state’s cell zero as the list length and cells as the entries. An existing entry at the decoded slot is folded by a power-of-two residue and copy index and translated into its disjoint layer interval. The query returns no label when the program has not halted or the slot is out of range.
The resulting optional label function has a deterministic multitape Turing machine running in time polynomial in the binary query length. The machine may depend on . The result supplies the bit-model implementation of the explicit neighbor algorithm independently of the disperser coverage theorem.
Formalization Note The query and result are encoded by encNbrIn and encOptNat. The functions mergeNbr and ramFoldedLayer specify the slot decoding, folding and treatment of invalid inputs.
import Mathlib.Computability.TuringMachine.Computable import Definitions.Def_CNFEncComplexity_encNbrIn import Definitions.Def_CNFEncComplexity_teutschNbr
namespace CNFEncComplexity
/-- The binary evaluator for the disjoint union of folded log-cost RAM neighbor lists
has a polynomial-time multitape implementation. -/
theorem teutschNbr_polytime (P : TimeSpaceMA.Program) (e C a : ℕ)
(hP : P.CoinFree) :
Nonempty (Turing.TM2ComputableInPolyTime encNbrIn encOptNat
(mergeNbr (fun N => a * (Nat.log 2 N + 1)^a) (ramFoldedLayer P e C))) := by sorry
end CNFEncComplexity