开创性研究揭示Prompt的理论基础
近日，伊利诺伊大学香槟分校的研究团队发布了一篇开创性论文，首次从理论层面证明了大语言模型(LLM)中的prompt机制具有图灵完备性。这意味着，通过合适的prompt设计，一个固定大小的Transformer模型理论上可以计算任何可计算函数。这一突破性发现为prompt工程提供了坚实的理论基础。
一、什么是图灵完备性？
在理解图灵完备性之前，我们不妨从一些日常经验中入手。你可能在学习阶段遇到过这样的考题：“下面哪种语言不是图灵完备的？” 选项中可能包括C++、Python、标准SQL和JavaScript。答案是标准SQL语言——对，这里只有标准SQL语言不是图灵完备的。这个问题有助于我们认识图灵完备性。
图灵完备性（Turing Completeness）是计算理论中的一个核心概念，用来描述某个计算系统的计算能力。如果一个系统具备条件分支、循环或递归能力，并具有理论上的无限存储，那么它可以被称为图灵完备。
这种系统能够模拟任意其他可计算的计算机，执行任何可编程的任务，只要给它足够的时间和资源。具备这些特征的系统可以用来模拟任何其他图灵完备的系统。因此，图灵完备的系统之间是等价的，理论上可以用来模拟任何其他图灵完备的系统。例如，大多数现代编程语言（如Python、JavaScript、C++）都是图灵完备的，而一些专用的计算系统（例如标准SQL）由于缺少循环结构则不是图灵完备的（加入Recursive CTE递归通用表表达式才是）。图灵机被认为是所有可计算过程的最终抽象，在传统计算理论中，用于衡量其他系统的计算能力。
当我们说LLM的提示是图灵完备的，意味着我们可以将LLM视为一个通用计算器，只需通过精心设计的提示，它就能够完成任何可以编程的任务。这为我们使用LLM解决复杂问题提供了一个全新的视角，也使Prompt工程师在实践中具有了更强的表达力和控制力。
二、研究背景：从经验走向理论
自GPT以来，提示工程(prompt engineering)已经成为使用LLM的主流范式。我们只需训练一个通用的大模型，然后通过不同的prompt来完成不同的任务。这种"一模多用"的范式在实践中取得了巨大成功，但其背后的理论基础一直未能得到充分解释。
本研究首次系统地回答了一个根本性问题：prompt范式的计算能力究竟有多强？
三、研究的主要贡献
为了帮助读者更好地理解本研究的贡献，以下是研究团队在理论和技术层面上的主要贡献：
表达能力：展示了提示的图灵完备性。研究者证明，存在一个固定大小的Transformer Γ，对于任何可计算函数 φ，存在一个相应的有限提示 πφ，使得对于任意输入 x，Transformer Γ 在提示 πφ 的指导下能够计算出 φ(x) 的结果。重要的是，构造的 Transformer Γ 与具体的函数 φ 无关，提示 πφ 与输入 x 也无关，且输入 x 可以是任意长度。
链式思维（CoT）复杂性：研究表明，构造的 Transformer Γ 可以在 O(t(n)) 步内计算任何 TIME2(t(n)) 类函数，并可以在 O(t(n) log t(n)) 步内计算任何 TIME(t(n)) 类函数，即使是对于长度为 n 的输入。值得注意的是，即使是单个 Transformer 也可以达到几乎与所有 Transformer 类相同的 CoT 复杂性。
精度复杂性：研究还展示了构造的 Transformer Γ 可以在 O(log(n + t(n))) 位精度内计算任何 TIME(t(n)) 类函数。这意味着，即使是单个 Transformer 也能够达到与所有 Transformer 类相同的精度复杂性。
这些贡献明确展示了提示在理论上具备的强大表达能力和复杂性管理能力，为提示工程的广泛应用奠定了坚实的基础。
三、研究证明过程概述
研究者们通过构建一个新的计算模型（称为2-PTM，即两带Post-Turing Machines）来证明提示的图灵完备性。核心思想是将任意可计算函数编码为提示（见下图算法），然后使用一个有限大小的Transformer来执行这些提示。以下是他们的证明过程的几个关键步骤：
构建2-PTM模型：2-PTM是一种扩展的图灵机模型，它使用两条双向无限的磁带，磁带上的每一个单元格都可以保存二进制符号0或1。2-PTM具有有限的指令集合，每条指令可以操作磁带的读写和移动。
提示的构建与编码：为了证明提示的图灵完备性，研究者需要构造一个能够描述任意可计算函数的提示。具体来说，他们将这些计算过程编码为一系列指令，通过一个有限的符号集合来表示。这些指令集的编码方式非常巧妙，采用了Shannon编码方法，确保能够有效地在提示中表达任意计算过程。
使用Transformer执行提示：研究者构造了一个有限大小的Transformer模型——这个Transformer可以理解这些提示，并且模拟2-PTM的行为，执行相关的计算。为了完成这一过程，Transformer需要通过链式思维（Chain of Thought, CoT）步骤记录计算过程，使得每一步都能跟踪到2-PTM的状态。
实现链式思维复杂性：为了实现Turing完备性，Transformer必须使用链式思维来记录执行过程中的每一步，从而能够恢复2-PTM在任意时刻的状态。研究者证明，通过这样的链式记录，Transformer可以在与任意图灵机近似相同的复杂性下计算任意可计算函数。
精度复杂性分析：研究表明，即使是一个有限大小的Transformer，也能够实现接近无限大小Transformer的精度复杂性。具体而言，Transformer在执行任何TIME(t(n))函数时，所需的精度与对所有Transformer的类相同，能够以O(log(n + t(n)))的精度完成计算。
四、提示的构建方法详解
在这项研究中，研究者提出了一种特殊的提示构建方法，以便让Transformer能够执行任意的计算任务。提示的构建主要包含以下几个步骤：
1. 编码可计算函数
对于任意可计算函数φ，研究者首先将其表示为一个形式化的描述，这一描述通过2-PTM的指令集来表示。这些指令包括移动磁带读写头、写入0或1、进行条件跳转等。然后，使用一个有限符号集合将这些指令编码为一个提示πφ。
这些指令的编码方案采用了一种称为Shannon编码的方法。Shannon编码确保了提示可以用有限的符号集合来表示，即使面对非常复杂的计算过程。这种编码方式通过将输入和输出的不同符号分开表示，从而有效区分不同计算状态。
2. 使用链式思维记录执行过程
为了使Transformer能够恢复2-PTM在任意时刻的状态，研究者利用链式思维步骤来记录计算的每一步。这种链式思维的作用类似于我们在编写程序时使用的日志记录，通过记录每个步骤的执行情况，确保可以随时回溯和继续计算。
研究者设计了一种记录执行步骤的方法，称为C函数。对于每一个执行步骤，C函数都会生成一条或多条链式思维步骤，这些步骤详细记录了当前的状态、磁带指针位置、读写状态等关键信息。通过这些记录，Transformer可以准确地模拟2-PTM的行为，完成复杂的计算任务。
3. 提示的具体形式
为了构建一个有效的提示，研究者设计了一个提示构造器P函数，用于将每条指令编码为一段提示。这些提示采用了统一的格式，使用了一些特殊的符号来标识不同的指令类型和状态转换，例如用符号@来表示跳转，用$来表示结束等。
构造出的提示形如：
ˆA?++++++++++++++@A0ALA0ALA?----@ARARA1ARBLB?++@A1#ARA?++++@B1BRB!+++@BLB!++++@B0ARB!-----------------------@
ALARARA?--@A0ALA0ALA?----@ARARA1#$.
这些符号编码代表了一系列复杂的磁带操作与条件判断，确保Transformer能够依次执行这些指令。
五、结果与意义
1. 核心发现：单个Transformer也能通用计算
研究团队证明了一个令人惊讶的结论：存在一个固定大小的Transformer模型，对于任何可计算函数，都存在一个相应的prompt使得该模型可以计算这个函数。更重要的是，这个固定大小的模型在计算复杂度上几乎可以达到所有不限大小的Transformer模型的理论上限。
定理：提示是图灵完备的。也就是说，存在一个有限大小的TransformerΓ和一个相应的提示πφ，对于任意一个可计算函数φ，都可以通过提示πφ使得TransformerΓ计算出φ(x)的结果。
这一结论的意义在于，它揭示了Prompt的真正潜力：通过合适的设计，我们可以让Transformer模型执行任何复杂的计算任务。提示不再只是一个简单的模型输入，它已经演变为一种通用编程的方式。看一看这篇文章，《用这条Prompt构建CoT+PoT验证器评估LLM输出，显著提高LLM推理准确性和一致性》，目前很多研究者已经将重心移向CoT+PoT，这种组合可以解决很多问题。工业界也有新的标准，《重磅！IBM：PDL提示词声明语言，帮你拿回Prompt控制权》
2. 提示工程的深远影响
对于Prompt工程师来说，这项研究提供了一个强大的理论工具。以往，我们对提示的设计更多依赖于经验和直觉，很多时候是通过不断试错来寻找最优的提示。而现在，我们知道只要提示设计得足够巧妙，它就可以模拟任意计算过程，这让Prompt工程具备了更深层次的科学基础。
具体来说，这意味着在设计提示时，我们不仅可以关注如何让模型理解任务，更可以从计算理论的角度出发，去设计能够高效完成计算的提示。提示工程师可以将提示看作一种编程语言，通过合适的语法和结构来表达复杂的逻辑和操作。
3. 提示的构造方法与思维链的重要性
研究表明，没有思维链机制的Transformer甚至无法计算简单的奇偶性函数。这理论上证明了思维链提示在处理复杂任务时的必要性。
此外，研究揭示了在使用prompt时存在精度和计算步骤之间的基本权衡。这提醒我们在设计prompt时需要考虑任务的复杂度特征，为不同复杂度的任务采用不同的提示策略。
六、研究面临的挑战与未解之题
尽管这项研究为提示的理论完备性提供了一个重要的证明，但在实际应用中仍然面临许多挑战。例如，虽然理论上一个有限大小的Transformer可以执行任意计算，但在实践中，如何找到合适的提示使得Transformer高效地学习这些计算过程仍是一个未解难题。
此外，研究中的Transformer模型使用了硬性最大注意力机制（Hardmax Attention），而实际应用中的LLM更多使用软性最大注意力机制（Softmax Attention）。如何在实际软性注意力机制下保持提示的图灵完备性，也是一个值得进一步探讨的问题。
未来的研究或许会在以下几个方向：
提示学习能力：当前的证明是构造性的，即证明了Transformer存在一个合适的提示使得它能够执行任意计算。然而，如何训练一个Transformer模型使其能够高效地学习这些提示仍然是一个未解的难题。未来的研究可能会探讨如何设计有效的训练方法，使得模型能够更好地理解和执行复杂提示。
提示效率的提升：尽管提示是图灵完备的，但在实践中，提示的长度和复杂性对Transformer的计算效率影响巨大。如何设计简洁而高效的提示，使得Transformer在有限的计算资源下完成复杂任务，也是未来研究的重要方向
提示工程的可能性：通过这项研究，提示工程的可能性得到了极大的拓展。提示的图灵完备性表明，我们可以通过设计适当的提示，使得一个有限大小的Transformer执行任意可计算的任务。只要有合适的设计，prompt就能够实现任何可计算的功能。这一理论为Prompt工程提供了坚实的基础，并赋予了Prompt设计更多的科学性和创造性。
对于Prompt工程师来说，提示不再只是给定模型的一段简单文本，而是一个可以编写复杂计算任务的编程工具。理解提示的图灵完备性，将有助于Prompt工程师在实践中更有效地设计提示，这对于正在探索LLM应用边界的工程师们无疑是一个重要的理论支持。
