The Turing Discovery Gap Conjecture

Abstract

This paper conjectures a gap between available and accessible explanatory value: worlds generated by compact O(n) programs, with Omega(n^2) Turings of predictive gain available, where no probabilistic polynomial-time learner reliably captures a fixed fraction of that gain.

Claim A is proved, conditional on one-way functions: a counting lemma (Kraft bound on short residuals) plus a distinguisher turns any successful learner into a PRF distinguisher. Claim B, the unconditional separation, is proposed. Claim C, the AIEN program-reuse hypothesis that a retained verified library increases net held-out Turing gain under a fixed discovery budget, is specified as a draft preregistration (CEXP-1).

Preprint; not peer reviewed.

Research artifacts

Cite

@misc{stapleton2026discoverygap,
  author = {M. Drake Stapleton},
  title = {The Turing Discovery Gap Conjecture},
  year = {2026},
  month = {October},
  version = {rev 9},
  note = {Preprint, not peer reviewed},
  url = {https://aienos.com/research/turing-discovery-gap-conjecture}
}