在这项研究中，随机预言机图灵机（SOTM）框架被用于建模AI增强计算，该框架描述了一个概率图灵机与一个根据上下文依赖分布返回响应的预言机之间的交互。本文探讨了SOTM在两种预言机响应方案下的能力：
- 缓存响应预言机：每个独特查询只返回一个响应，该响应在之后的调用中被重用。
- 新响应预言机：每次调用返回一个独立的响应。
在这两种方案中，SOTM首先从其输入和内部随机源计算生成第一个查询，然后根据查询-响应记录（即发出查询和接收响应的记录）自适应地生成后续查询或最终输出。
缓存响应对可实现性能施加了两个基于记录的上限：
- 正确识别上限：由预言机隐藏状态诱导的记录分布之间的总变差距离决定。
- 输出质量上限：等于SOTM可以从记录中计算得出的最佳输出的期望得分。
新响应通过允许重复调用积累独立证据，从而提高这些上限。在二进制单信息查询的情况下，错误概率随着对同一查询调用次数的增加而以切尔诺夫速率指数下降。对于输出质量，查询计数界限表征了当得分函数作为SOTM的一部分时的阈值停止，而基于多数的增强界限则表征了当它不是时的二元候选输出模型。综上所述，研究结果揭示了响应重用、记录信息和对得分函数的访问如何决定SOTM的计算能力及其代价。
博主点评： 本文深入探讨了随机预言机在AI增强计算中的应用，提供了对性能上限的清晰理解，为未来的计算模型设计提供了重要的理论基础。