图灵发现差距猜想

摘要

本文提出一个可获得解释价值与可访问解释价值之间的差距：由紧凑 O(n) 程序生成的世界中，存在 Omega(n^2) 图灵的预测增益，但没有任何概率多项式时间学习者能可靠地捕捉其中固定比例的增益。

命题 A 在单向函数假设下已证明：一个计数引理（短残差的 Kraft 界）加上一个区分器，可将任何成功学习者转化为 PRF 区分器。命题 B（无条件分离）被提出。命题 C（AIEN 程序复用假设）指出，在固定发现预算下，保留的经验证库能提升净保留图灵增益，该假设作为草案预注册（CEXP-1）提出。

预印本；未经同行评审。

研究资料

引用

@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}
}