Lemma G.2 — approximating v from a decider, including its space bound
OpenGPTIP632.Classical.Supplement.lemma_G_2Let . For a nonempty bit string , write , and let have yes-instances satisfying and no-instances satisfying . If a total decision function is correct on these two sets, put , with when the set is empty. Then for every ,
Moreover, for every deterministic total machine using at most cells on all inputs of length , there are a constant and one transducer that, on input , halts and outputs the binary digits of within cells for every . This assertion holds whether or not the total machine decides a comparison promise problem, and in particular applies to every decider above. The constant and transducer are chosen after and before .
This lemma recovers approximations to the coordinate from a decider; both its strict error estimate and its space assertion are retained.
Differences from the source:
- generalization: D is a total algorithm deciding L_v → the numerical bound permits any total Boolean function deciding L_v; the output-space assertion applies to every total space-bounded OTM, independently of promise correctness; reason: the numerical estimate uses only the values of D, while enumerating accepted strings uses only totality and the space bound
- encoding: binary fractions and the largest accepted m-bit fraction, or zero → exact rationals with denominator 2^m, a finite maximum of natural numerators with bottom zero, and exactly m output bits in most-significant-first order; reason: this preserves each binary fraction and the empty-acceptance convention without an unbounded real supremum
- encoding: positive string lengths and O(s(m)) space → m >= 1, an empty-oracle OTM with input and query cells counted, and an existential positive natural c with output space at most c*s(m); reason: the comparison problem excludes empty strings, and s(m) >= m absorbs fixed overhead for positive m; c is uniform in m and depends only on D and s
import Mathlib import Definitions.Def_GPTIP632_Classical_Supplement_BinaryComparison import Definitions.Def_GPTIP632_Classical_Supplement_SpaceTransducer
namespace GPTIP632.Classical.Supplement
theorem lemma_G_2 :
(∀ (v : ℝ), 0 < v → v < 1 → ∀ D : List Bool → Bool,
DecidesComparison D v → ∀ m : ℕ, 1 ≤ m →
|v - (acceptedMaximum D m : ℝ)| < 1 / (m : ℝ) ^ 2 + 1 / (2 : ℝ) ^ m) ∧
(∀ (D : QAdvFew.PoQOracle.OTM) (s : ℕ → ℕ),
(∀ m : ℕ, m ≤ s m) → TotalInSpace D s →
∃ c : ℕ, 0 < c ∧ ∃ A : QAdvFew.PoQOracle.OTM,
ComputesUnaryInSpace A (acceptedDigits (machineDecision D)) (fun m => c * s m)) := by sorry
end GPTIP632.Classical.Supplement