Ask, and it shall be given: Turing completeness of prompting

自从GPT取得成功以来，大型语言模型（LLMs）一直在革新机器学习，并开启了所谓的LLM提示范式。在LLM时代，人们训练一个通用的大型语言模型，并通过提供不同的提示来执行不同的任务。然而，这种经验上的成功在很大程度上缺乏理论上的理解。据我们所知，本文首次对LLM提示范式进行了理论研究。在这项工作中，我们证明了提示实际上是图灵完备的：存在一个有限大小的Transformer，对于任何可计算函数，都存在一个相应的提示，使得该Transformer能够计算该函数。此外，我们还证明了即使只使用一个有限大小的Transformer，它仍然可以达到与所有无限大小Transformer类几乎相同的复杂度界限。总体而言，我们的结果揭示了提示可以使单个有限大小的Transformer高效地实现通用性，为实际中的提示工程提供了理论基础。

该论文试图从理论上探讨和理解大规模语言模型（LLM）通过提示（prompting）执行不同任务的能力。具体来说，它旨在证明单个有限大小的Transformer模型通过不同的提示可以实现计算上的通用性。

论文的关键思路是证明提示机制在理论上是图灵完备的，即存在一个有限大小的Transformer模型，对于任何可计算函数，都存在一个对应的提示，使得该模型能够计算该函数。此外，论文还展示了即使使用单一的有限大小Transformer，其复杂度边界也能接近无限大小Transformer的复杂度边界。

1. 该研究首次从理论上证明了提示机制的图灵完备性。 2. 实验设计包括数学证明和理论分析，没有使用特定的数据集或开源代码。 3. 研究结果为实际中的提示工程提供了理论基础，揭示了单个有限大小Transformer的高效通用性。 4. 值得进一步研究的方向包括如何优化提示的设计，以提高模型的性能和效率。

1. "On the Expressive Power of Transformer Models" - 这篇论文探讨了Transformer模型的表达能力。 2. "The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks" - 探讨了神经网络中的稀疏性和训练效率。 3. "Probing the Limits of Transformer Models for Natural Language Generation" - 研究了Transformer模型在自然语言生成任务中的极限。 4. "Understanding the Generalization Performance of Large-Scale Pretrained Models" - 分析了大规模预训练模型的泛化性能。