提出计算模型框架，揭示智能体系统能力边界与效率关系。
Computability of Agentic Systems
- 构建Quest图模型，形式化分析有限上下文智能体的推理能力。
- 证明参考增强型系统仅在状态查询下才具备图灵完备性，可指数提升效率。
- 适合研究智能体架构、理论计算复杂性的学者参考。
本文提出Quest图，一种用于分析具有有限上下文的智能体系统能力的形式化框架。通过定义建模常见推理技术的抽象，我们确立其计算能力：基础Quest图等价于无限制图灵机；广泛使用的前向仅限有限任务决策过程（FQDP）仅等价于下推自动机（上下文无关）；而参考增强型QDP（RQDP）仅在允许状态查询时才恢复图灵完备性。由于可计算性影响效率，我们进一步通过模拟计算图中的任务依赖关系，分析各模型的理论效率。结果表明，这种计算层级直接转化为实际性能权衡：参考增强型（图灵完备）系统在模拟复杂图时，效率可比非增强型（上下文无关）系统高出指数级。本工作提供了分类和理解智能体系统根本能力的形式化方法。
原文摘要 · Abstract (English)
This paper introduces the Quest Graph, a formal framework for analyzing the capabilities of agentic systems with finite context. We define abstractions that model common reasoning techniques and establish their computational power: the base Quest Graph is equivalent to an unrestricted Turing machine; the forward-only Finite Quest Decision Process (FQDP), despite its wide use, is only equivalent to a pushdown automaton (context-free); and the Reference-Augmented QDP (RQDP) regains Turing completeness only when stateful queries are allowed. Since computability affects efficiency, we then analyze the theoretical efficiency of each model by simulating task dependencies in computation graphs. We show that this computational hierarchy translates to concrete performance trade-offs: reference-augmented (Turing-complete) systems can be exponentially more efficient at simulating complex graphs than their non-augmented (context-free) counterparts. This work provides a formal methodology for classifying and understanding the fundamental capabilities of agentic systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。