If you strip away the rhetoric about “thinking” machines and “cognitive” agents, most of today’s agentic AIs still boil down to something familiar from the 1950s: automata.
That’s the thesis of Are Agents Just Automata? by Koohestani et al. (2025), a paper that reinterprets modern agentic AI through the lens of the Chomsky hierarchy—the foundational classification of computational systems by their memory architectures. It’s an argument that connects LLM-based agents not to psychology, but to formal language theory. And it’s surprisingly clarifying.
Memory as the True Measure of Agency
The authors propose a deceptively simple idea: the computational power of an AI agent is determined by its memory model. If you know what kind of memory an agent can use, you can formally predict what kinds of tasks it can perform—and whether its behavior is even verifiable.
| Agent Type | Equivalent Automaton | Memory Model | Example Frameworks |
|---|---|---|---|
| Regular Agent | Finite Automaton (FA) | No memory or fixed state transitions | IFTTT, rule-based chatbots |
| Context-Free Agent | Pushdown Automaton (PDA) | Stack (LIFO) memory for nested plans | CrewAI, LangGraph (acyclic) |
| Turing-Complete Agent | Turing Machine (TM) | Unbounded read/write memory | ReAct, AutoGPT, LangGraph (cyclic) |
This mapping reframes agent design as an engineering discipline of right-sizing: build the weakest class of agent sufficient for the job. If a finite-state agent can execute a workflow reliably, don’t hand it an infinite tape.
The Right-Sizing Principle
In practice, agent design has trended in the opposite direction—everything wants to be a mini–Turing Machine. This is convenient for generality but disastrous for verification. Once an agent can modify its own scratchpad freely, you inherit the entire burden of computability theory: you can’t prove that it will halt, that it will stay safe, or that it will never go rogue.
Koohestani’s framework doesn’t just make this point philosophically—it draws a formal line in the sand. Regular and context-free agents belong to decidable domains: their safety, reachability, and liveness properties can be proven with existing verification tools. Turing-complete agents cross into the realm of the undecidable, where assurance collapses into empirical testing and runtime monitoring.
The payoff is profound: by classifying your agent’s architecture, you immediately know which mathematical guarantees apply—and which are impossible.
Engineering with Formal Limits in Mind
Viewed through this lens, the Chomsky hierarchy becomes a blueprint for safe agent design. Instead of building opaque, endlessly looping ReAct-style agents, engineers could design modular systems where untrusted reasoning components operate within verifiable shells—finite or pushdown layers that constrain what the agent can do.
In safety-critical contexts like finance or healthcare, this could transform compliance: a finite-state controller can be audited, since every state and transition is explicit. Even if an LLM is used inside as a transition oracle, its choices are bounded by a formally defined structure.
The economic argument is just as strong. Limiting memory and recursion depth doesn’t only make agents safer—it cuts cost and latency by eliminating unnecessary reasoning loops. Formal simplicity translates directly into computational efficiency.
From Absolute Safety to Quantitative Risk
Real-world agents, however, are probabilistic. LLM transitions are not deterministic—they sample. The authors extend their framework accordingly: probabilistic agents can be modeled as Probabilistic Finite Automata (PFA) or Probabilistic Pushdown Automata (PPDA). This opens the door to a new kind of verification—one based not on binary safety guarantees but on quantitative risk analysis.
In other words, instead of asking “Can the agent fail?”, we can ask “What’s the probability it will fail?”—a framing far more useful for enterprise risk management and policy contexts.
Why This Matters
At a time when “agentic AI” has become a catch-all buzzword, Koohestani et al. offer a rigorous skeleton key. Their Automata-Agent Framework grounds a field drunk on demos in something much older—and sturdier. It reminds us that every “intelligent” system ultimately lives somewhere on a well-known map between finite, stack-based, and Turing-unbounded computation.
For the next generation of AI engineers, this might be the missing bridge between empirical experimentation and formal assurance—between the art of prompting and the science of computability.
Cognaptus: Automate the Present, Incubate the Future