![[2602.13222] Computability of Agentic Systems](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.13222] Computability of Agentic Systems
Summary
This paper presents the Quest Graph framework for analyzing agentic systems' capabilities, establishing a computational hierarchy and efficiency trade-offs among different models.
Why It Matters
Understanding the computability of agentic systems is crucial for advancements in artificial intelligence and computational complexity. This research provides a formal methodology to classify these systems, which can lead to more efficient AI applications and better performance in complex tasks.
Key Takeaways
- Introduces the Quest Graph framework for analyzing agentic systems.
- Establishes a computational hierarchy among different reasoning models.
- Demonstrates that reference-augmented systems can be exponentially more efficient than non-augmented ones.
- Provides insights into the theoretical efficiency of agentic systems.
- Highlights the importance of computability in AI performance.
Computer Science > Computational Complexity arXiv:2602.13222 (cs) [Submitted on 26 Jan 2026] Title:Computability of Agentic Systems Authors:Chatavut Viriyasuthee View a PDF of the paper titled Computability of Agentic Systems, by Chatavut Viriyasuthee View PDF Abstract: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. Subjects: Computational Complexity (cs.CC); Artificial Intelligence (cs.AI); Formal Languages and Automata Theory (cs.FL) Cite as: arXiv:2602.13222 [cs.C...
