论文略读：Ask, and it shall be given: On the Turing completeness of prompting

ICLR 2025 5566

自从 GPT 的成功以来，大型语言模型（LLMs）彻底革新了机器学习领域，催生了所谓的 LLM 提示范式（prompting paradigm）。在这一范式下，研究者倾向于训练一个通用的大模型，通过提供不同的提示（prompt）来完成不同的任务。

然而，尽管这一实践在经验上取得了巨大成功，目前对于其理论基础仍缺乏系统研究。

本工作是我们所知的首个对 LLM 提示范式进行的理论研究。我们证明了一个重要结论：提示（prompting）本质上是图灵完备的。也就是说，存在一个固定大小的 Transformer，使得对任何可计算函数，都存在一个对应的提示，使该 Transformer 能够计算该函数的输出。

进一步地，我们还证明：尽管仅使用一个有限大小的 Transformer，它依然能够实现接近于所有无限大小 Transformer 所能达到的复杂度上限。

总体而言，本研究表明：

• 提示工程不仅在实践中有效，也具备坚实的理论基础；

• 一个固定规模的 LLM，通过提示即可实现高效的通用计算能力，从而支持多任务与泛化能力的核心机制。

这一发现为 LLM 提示范式提供了理论支撑，也为提示工程（prompt engineering）的进一步研究与优化指明了方向。