作者： AI科技评论 来源： AI科技评论

ICLR 匿名研究：单一 Transformer 不具备图灵完备性，但多 Transformer 可以。

作者丨郭思、赖文昕

编辑丨陈彩娴

Transformer 自 2017 年出世以来就在 AI 领域高举高打，ChatGPT 引发全球大型语言模型热潮后更是在 NLP 领域被赋予了神话般的地位。

但近日，一篇正在审核中的 ICLR 2023 投稿论文（如下）经研究后提出一个观点：单一 Transformer 并不具备图灵完备性，其计算能力存在理论上的局限性，在圈内引起关注。

由于该论文正在审核中，作者信息没有被公开。

论文链接：https://openreview.net/pdf?id=MGWsPGogLH

与此同时，该论文新提出了一种名为“Find+Replace Transformer”的多 Transformer 架构，并证明了通过集成多个Transformer，能够解决单一 Transformer 无法胜任的任务。

这项研究直接对标并超越了当前最先进的GPT-4模型，在一系列极具挑战性的基准测试中展现了显著的优势和潜力。

1

被神化的 Transformer

局限在哪里？

图灵完备性是评判一个计算系统强大与否的关键指标。如果一个系统被确认为图灵完备，则理论上只要赋予其充足的运行时间和内存资源，即可以执行任何可计算的算法。

在实际应用中，尽管 Transformer 模型在诸多自然语言处理任务上表现卓越，但其能力受到设计上的固有限制，例如固定的上下文窗口长度和有限的词汇表大小。这意味着 Transformer 模型并不具备解决所有类型计算问题的能力，特别是那些需要无限存储空间或无限制迭代过程的问题。

在论文中，研究团队特别指出，基础的语言模型工作原理在于根据前 k 个词语的概率来预测下一个词语。在 NLP 领域，通常会构建一些专门针对固定长度输入输出序列设计的模型集合或框架，并将这类模型归入 MF_SMF 类别。

Transformer 作为 MF_SMF 这一框架下的具体实例，其图灵完备性的缺失得到了该研究团队的理论论证。他们基于以下逻辑：

首先，回顾计算理论的基础：图灵停机问题是不可判定的，意味着不存在一个通用的方法来判断任意给定程序何时终止运行，就如同无法找到一把万能钥匙预测每一场棋局结束时间一样。这一原理同样适用于评估模型是否会在执行过程中陷入无尽循环而无法自拔。

研究者进而分析了 MF_S（这里假设 MF_S 代表 MF_SMF 中的子集）集合中的模型：

• 假设可以构建一个算法H，它可以准确判断MF_S中任意模型m是否终止。

• 假设MF_S集合中存在一个模型m’，它足够强大以至于能够模拟任何图灵机的计算过程，包括那些永远不会停止的图灵机。

• 根据算法H的假设能力，如果MF_S集合中的模型m’能够模拟那些不会停止的图灵机，那么算法H应该能够预测m’在模拟这些图灵机时是否会停止。

• 然而，根据图灵的停机问题不可判定定理，我们知道实际上不可能存在这样一个算法H，因为它会与图灵的定理相矛盾。

• 因此，MF_S集合中不可能存在能够模拟所有图灵机行为的模型m’，也就是说，MF_S中没有任何模型是图灵完备的。

Transformer便属于 MF_SMF，所以 Transformer 不具备图灵完备性。

研究人员指出，Transformer在处理自然语言任务，尤其是在机器翻译方面，有明显的优势。这类模型能够通过递归的方式输入序列并生成更新后的序列，从而逐个预测下一个符号。

但是，尽管Transformer模型能够基于之前的字符序列连续生成新的字符序列，每次接收一段输入字符后产出相应的输出字符，并利用新产生的字符序列进行迭代计算，它还是受到了上下文长度k和词汇表大小v的限制。这意味着它能够处理的不同字符组合的数量不会超过v^k种。

例如，当 Transformer 遇到重复输入时，由于它的无状态特性（这有利于并行训练多个序列），模型必须保证对同一输入产生一致的输出结果。这可能导致在某些情况下，模型陷入无限循环的模式，即只能生成有限数量的、最多为v^k种不同的输出序列，或者在自我复制的过程中无法停止。

与Transformer相比，图灵在1936年提出的图灵机概念具有无限的计算潜力，不受这些结构性的限制，能够模拟任何可计算的过程，确保不会陷入类似的有限循环困境。

2

如何超越 GPT-4？

实验结果显示，单个 Transformer 架构并不具备图灵完备性，而多 Transformer 则有能力实现图灵完备（如论文中所提出的 Find+Replace Transformer）、并执行如 GPT-4 等最先进的 Transformer 模型所无法解决的问题。

论文中创新性地将 Find Transformer 与 Replace Transformer 相结合，构建了Find+Replace Transformer体系结构——这是一个能在任意长度序列上运行的多Transformer系统，在论文中被形象地比喻为“磁带”（Tape）。

该系统由 Find Transformer、Replace Transformer 以及 Map 三部分组成，其中 Map 是一个从 Replace Transformer 到 Find Transformer 所涉及的有序集合的函数映射关系。

具体运作时，Find Transformer 会在输入序列中定位并标识出需要由 Replace Transformer 处理的部分内容。这两个组件各自具有固定的上下文长度 k，并依次对“磁带”上的每个长度为k的子序列进行分析，Find Transformer 会选择那些在最终层产生最高激活值的特定子序列。

随后，Replace Transformer 会接收 Find Transformer 标识出的子序列作为输入，并基于此生成一个新的长度为k的输出序列，这个过程利用了 Map 关联的 f∈Map(r) 规则，确保了两个 Transformer 之间的协同工作及信息传递。

那这个 Find+Replace Transformer 的多 Transformer 系统是如何可以实现图灵完备的呢？

简单来说，Find+Replace Transformer 是一个学习简化的机器。在编程语言的基石 λ 演算 中，有三条被称为“归约”（Reduction）的规则:

• Alpha Reduction：这是一个绑定变量的重命名。它被用来避免命名冲突。例如，在λ 演算的项 λx.x，我们可以化简成 λy.y，且不改变其意思。

• Beta Reduction：这是将函数应用于其参数的过程。例如，在λ项(λx.x)y（表示将函数λx.x作用于参数y），我们可以化简成 y。

• Eta Reduction：这是对函数和参数的简化。如果你有一个函数比如λx.(fx)，而x不出现在f中，那么这个就可以化简为f。

Find+Replace Transformer 的多Transformer 系统之所以能够实现图灵完备性，关键在于其架构设计和训练方式允许模型通过一系列组合操作模拟类似于 λ 演算中的归约规则。尽管单个 Transformer 受限于上下文长度、词汇表大小等因素，但通过构建一个多 Transformer 协作的框架，并结合特定的学习机制，这些简单且局部的“查找与替换”操作得以在更复杂的计算任务中累积并形成强大的综合效应。

具体来说，在Find+Replace Transformer中，多个 Transformer 可能被专门设计来分别或协同地处理不同类型的简化（归约）任务，例如模拟 Alpha Reduction 进行变量重命名、模拟 Beta Reduction 执行函数应用以及模拟 Eta Reduction进行函数简化等。每个 Transformer 可能专注于理解和学习如何执行这类简单的转换操作，并将结果传递给下一个Transformer，从而逐步构建起复杂问题的解决方案。

虽然单个 Transformer 不具备图灵完备性，但当它们以特定的方式组织起来并协同工作时，可以模拟通用图灵机的逻辑行为，进而实现对任意可计算问题的解决能力。这样的体系结构让Find+Replace Transformer在处理大规模、多层次的复杂问题时展现出超越传统单一Transformer的性能表现，实现了更高阶的计算能力。

2023年当OpenAI 发布GPT-4时，微软研究院的研究人员发表了一篇题为“Sparks of Artificial General Intelligence(Bubeck et al., 2023)”的论文，阐述了早期AGI所面临的局限性。

研究者们以汉诺塔问题为例进行了说明。汉诺塔是一个经典的递归问题，要求玩家将按照大小顺序堆叠的圆盘从一根柱子移动到另一根柱子上，期间只能移动一个圆盘且任何时候大盘不能位于小盘之上，借助第三根柱子作为中转。

GPT-4无法解决这个复杂的推理问题，从而突显了当前Transformer在推理过程中缺乏规划能力。

研究者对比了几种模型在解决完整汉诺塔问题上的表现。随着问题规模增大，其难度呈指数级上升：规模为n的问题其解决方案需要2^n - 1步操作。Find+Replace Transformer在此任务上表现出色，甚至能生成比GPT-4至少长18倍的正确解决方案。

除了在汉诺塔这个GPT-4都难以解决的问题上表现优越之外，在其他AI任务，如创作满足特定条件的诗歌等，Find+Replace Transformer都能超越GPT-4，这反映了其在泛化能力上的优势。

3

结语

Find+Replace Transformer模型通过创新性地结合多个Transformer单元，并模拟λ演算中的归约规则，在处理如汉诺塔问题等复杂组合任务时展现出了超越传统单个Transformer的优越性能。

这一研究成果揭示了多Transformer系统在实现图灵完备性方面的潜力，也证明了在面对特定计算难题时，提高模型的逻辑推理和抽象表达能力的重要性。

而纵观整个人工智能技术的发展，从深度学习兴起到大模型浪潮来袭，每一次技术迭代，人们都对于新技术报以极大的热情与崇拜。

然而，无论是深度学习还是Transformer架构，亦或是如今新出现Find+Replace Transformer架构，所带给我们的启示是，在研究和应用深度学习技术时，都需要避免过分神化任何技术，应该理性地看待每一项技术，关注其优势和局限，并结合实际问题来选择和调整合适的技术。只有这样，才能不断地在通往人工通用智能（AGI）的道路上迈进。

本文作者长期关注大模型领域技术发展与行业动态，欢迎添加作者微信（lionceau2046 ）和（anna042023 ）交流，互通有无。

更多内容**，点击下方关注：**

未经「AI科技评论」授权，严禁以任何方式在网页、论坛、社区进行转载！

公众号转载请先在「AI科技评论」后台留言取得授权，转载时需标注来源并插入本公众号名片。

更多AI工具，参考Github-AiBard123，国内AiBard123