Are Agents Just Automata? On the Formal Equivalence Between Agentic AI and the Chomsky Hierarchy

• ArXiv URL: http://arxiv.org/abs/2510.23487v1

• 作者: Maliheh Izadi; Anton Podkopaev; Roham Koohestani

• 发布机构: Constructor University; Delft University of Technology; JetBrains Research

---

TL;DR

本文通过将智能体（Agent）的内存架构与乔姆斯基层级（Chomsky hierarchy）中的抽象机进行类比，建立了一套形式化等价框架，指出智能体的计算能力和可验证性由其内存类型（无内存、堆栈、无限读写内存）决定，从而为设计更高效、更安全的智能体系统提供了理论基础和工程指导。

关键定义

• 正则智能体 (Regular Agent)：一种计算能力等同于有限自动机 (Finite Automaton, FA) 的智能体。它只拥有有限且大小恒定的内存，其行为完全由在一个预定义的、有限状态图中的位置决定。
• 上下文无关智能体 (Context-Free Agent)：一种计算能力等同于下推自动机 (Pushdown Automaton, PDA) 的智能体。它在有限状态控制的基础上，增加了一个堆栈（后进先出 LIFO 内存），使其能够管理和执行层级化的嵌套任务。
• 图灵完备智能体 (TC Agent)：一种计算能力等同于图灵机 (Turing Machine, TM) 的智能体。它能够访问一个无界的、可任意读写的内存（如“草稿纸”），这使其具备通用计算能力。
• 适当规模化 (Right-Sizing)：本文提出的核心工程原则，指在设计智能体时，应选择能够完成任务的、计算能力最弱的架构类别。目的是为了优化效率、降低成本，并尽可能地保留系统的可预测性和可验证性。
• 智能体接受 (Agent Acceptance)：定义当一个智能体的执行轨迹到达某个终结状态时，即认为该轨迹被“接受”。此定义与任务本身的成功与否无关，其目的是为了将智能体的行为形式化为语言接受问题，从而与自动机理论建立联系。

相关工作

当前，主流的智能体AI系统，如 ReAct 和 StateFlow，通常围绕一个“感知-规划-行动”(Sense-Plan-Act) 循环构建，并利用大语言模型 (LLM) 作为其决策核心。这些系统本质上是状态转移机器。尽管已有研究将模型检查 (model-checking)、线性时序逻辑 (Linear Temporal Logic, LTL) 等形式化方法应用于AI系统以增强其可靠性，但整个领域仍存在一个关键瓶颈。

目前缺乏一个统一的理论框架，来根据智能体的计算能力对其进行分类。这导致在设计上倾向于采用默认的“一刀切”模式，即赋予智能体图灵完备 (Turing-complete, TC) 的能力，即使任务本身远不需要如此高的复杂度。这种做法不仅导致系统效率低下、成本高昂，更严重的是，由于其理论上的不可判定性 (undecidability)，使得对智能体行为的形式化验证变得极为困难甚至不可能。

本文旨在解决这一问题，通过建立智能体架构与其底层计算模型之间的形式化联系，为智能体设计提供一种更具原则性的方法。

本文方法

本文的核心思想是：一个AI智能体的计算能力、可验证性和行为边界，从根本上是由其内存架构决定的。基于此，本文通过将不同内存复杂度的智能体映射到乔姆斯基层级中对应的自动机，构建了一个形式化的分类框架。

分类体系

本文将智能体划分为三个主要类别，并证明了它们与经典计算模型的等价性。

正则智能体 (Regular Agents) $\simeq$ 有限自动机 (Finite Automata, FA)

这类智能体的内存是有限且大小恒定的。其行为被严格限制在一个预先定义好的有限状态图中。即使使用LLM来决策，LLM也只能扮演一个“转移神谕”(transition oracle) 的角色，即在图中已有的状态转移路径中进行选择，而不能创造新的状态或访问外部持久化内存。

• 形式化定义：正则智能体可以被建模为一个带输出的有限自动机（Mealy Machine），其状态转移函数为 $\delta: S \times \Sigma \to S$，其中 $S$ 是有限的状态集，$\Sigma$ 是有限的输入符号集。
• 适用场景：适用于任务流程固定、无嵌套子任务的场景，例如简单的客户服务问答、设备控制等。
• 优点：由于状态空间有限，其行为完全可预测。可以使用成熟的模型检查技术来形式化地验证其安全性（如不会进入非法状态）和活性（如一定能完成任务）。

上下文无关智能体 (Context-Free Agents) $\simeq$ 下推自动机 (Pushdown Automata, PDA)

这类智能体在有限状态控制的基础上，增加了一个堆栈（后进先出 LIFO）内存。这个堆栈结构使其能够自然地处理层级化的任务分解和嵌套的子目标。例如，当一个智能体为了完成一个大任务（“发布产品”）而生成一系列子任务（“设计”、“开发”、“测试”）时，它会将这些子任务“压入”堆栈；每完成一个，就将其“弹出”，返回到上层任务。

• 形式化定义：其状态转移函数为 $\delta: S \times \Sigma \times Z \to S \times Z^*$，其中 $Z$ 是堆栈符号集。下一个状态不仅取决于当前状态和输入，还取决于栈顶的符号。
• 适用场景：需要分步规划和处理嵌套逻辑的复杂任务，如项目管理、多步骤代码生成。
• 优点：比正则智能体更强大，但其核心属性仍然是可判定的。可以验证层级规划的执行是否正确（例如，所有子程序最终都会返回）。

图灵完备智能体 (TC Agents) $\simeq$ 图灵机 (Turing Machines, TM)

这类智能体被授予访问一个无界的、可任意读写的内存，这类似于图灵机的“纸带”。这个内存可以是一个“草稿纸”文件、一个可无限扩展的向量数据库，或任何能被智能体自由修改和查询的外部存储。

• 形式化定义：其状态转移函数为 $\delta: S \times \Gamma \to S \times \Gamma \times {L, R}$，其中 $\Gamma$ 是带上可读写符号的集合。智能体可以根据内存内容改变状态、修改内存，并移动读写位置。
• 适用场景：需要进行开放式研究、持续学习和基于海量积累知识进行迭代推理的任务。
• 缺点：拥有通用计算能力的同时，也继承了图灵机的理论局限性。根据莱斯定理 (Rice’s Theorem)，任何关于这类智能体行为的非平凡属性（如“它是否会停止？”或“它是否会进入某个不安全状态？”）都是不可判定的。这意味着无法从理论上提供绝对的安全保证。

对多智能体系统的扩展

本文的框架同样适用于多智能体系统 (Multi-Agent Systems, MAS)。一个由多个正则智能体组成的系统，其整体行为等效于一个状态数量巨大但仍然是有限的单一状态机。然而，当这些简单的智能体被赋予访问一个共享的、无界的读写内存时，整个系统就发生了质变，其计算能力跃升至通用图灵机级别。

工程原则：适当规模化 (Right-Sizing)

基于上述分类，本文提出了适当规模化的核心工程原则：为任务选择满足需求的、计算能力最弱的智能体类别。这不仅能优化成本和延迟，更重要的是能在设计阶段就明确系统的能力边界和可验证性。

为了指导实践，本文提供了一个决策流程图来帮助开发者选择合适的智能体架构。

同时，本文还将当前流行的智能体框架映射到了这个分类体系中。

实验结论

本文是一篇理论研究，未包含传统的数值实验，其结论是基于形式化推导和理论分析得出的。

• 核心结论：通过将智能体架构与自动机理论联系起来，本文为AI安全和验证领域引入了计算理论中一个清晰的边界：可判定性与不可判定性。
  • 可验证的智能体 (正则/上下文无关)：对于等效于FA和PDA的智能体，其关键属性（如安全性、可达性）在理论上是可判定的。这意味着我们可以构建算法来自动、确定性地回答关于它们行为的问题，从而实现形式化验证。
  • 不可验证的智能体 (图灵完备)：对于等效于TM的智能体，其行为的几乎所有非平凡属性都是不可判定的。这意味着不存在一个通用算法能够保证其安全性或终止性。对这类智能体的验证只能依赖于测试、运行时监控等不完备的方法。

• 对工程实践的影响：“适当规模化”原则为智能体设计提供了务实的指导。选择计算能力较弱的架构（正则或上下文无关），不仅能大幅降低LLM推理成本和延迟，还能通过固有的结构限制来增强系统的可预测性和可靠性。在金融、医疗等安全攸关领域，这种设计使得形式化审计成为可能。

• 未来展望：
  • 概率化模型：本文的确定性框架为下一步研究奠定了基础，即通过引入概率自动机（如 Probabilistic Finite Automata, PFA）来对LLM的随机性进行建模。这将使验证问题从“智能体能否达到不安全状态？”转变为一个量化问题：“智能体达到不安全状态的概率是多少？”，从而实现量化风险分析。
  • 实用工具链：未来的研究方向包括：1) 最小类别综合：开发工具，将高级任务描述自动编译成能力最弱但足够的智能体架构。2) 混合架构：设计由可验证的FA/PDA“外壳”包裹的TM级核心组件，通过运行时守卫来强制执行安全策略，实现静态保证与动态验证的结合。