Computational Irreducibility as the Foundation of Agency: A Formal Model Connecting Undecidability to Autonomous Behavior in Complex Systems
Poria Azadi · 2025
Read Computational Irreducibility as the Foundation of Agency: A Formal Model Connecting Undecidability to Autonomous Behavior in Complex Systems by Poria Azadi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-04646.txt.
Introduction
Poria Azadi argues that true self-rule in a system forces its future to be unknowable from outside, in a 2025 paper. The claim ties agency to a deep idea from computing: some processes cannot be shortcut, only run. Azadi builds a formal model in which any system that sets and steers by its own aims yields questions about its future acts that no method can settle in advance.
The bar is stricter than mere complexity, since a complex thing may still be fully forecast. On this view, the line between self-ruled and driven systems is a matter of proof, not taste. The frame draws on computing theory and biology, where new aims seem to arise inside living things. Azadi closes with what the result may mean for AI design, models of life, and old debates on free will.
Catalog record
| CREATOR | Poria Azadi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-04646
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Computational Irreducibility as the Foundation of Agency: A Formal Model Connecting Undecidability to Autonomous Behavior in Complex Systems Poria Azadi Abstract This article presents a formal model demonstrating that genuine autonomy, the ability of a system to self-regulate and pursue objectives, fundamentally implies computational unpredictability from an external perspective. We establish precise mathematical connections, proving that for any truly autonomous system, questions about its future behavior are fundamentally undecidable. This formal undecidability, rather than mere complexity, grounds a principled distinction between autonomous and non-autonomous systems. Our framework integrates insights from computational theory and biology, particularly regarding emergent agency and computational irreducibility, to explain how novel information and purpose can arise within a physical universe. The findings have significant implications for artificial intelligence, biological modeling, and philosophical concepts like free will. Keywords: Agency, Autonomy, Computational Constraints, Undecidability, Complex Systems 1 Introduction The concepts of agency and autonomy, pertaining to a system’s ability to function effectively, pursue objectives, and self-regulate, are central inquiries across biology, cognitive science, artificial intelligence, and philosophy [ 1 , 2 ] . Furthermore, previous formalization attempts, largely focused on logical or probabilistic frameworks, have frequently overlooked the inherent limitations imposed by computational constraints on a system’s capacity to process information and forecast its environment [ 6 , 7 ] . This article posits that a deeper understanding of agency can be achieved by examining the fundamental constraints of computation and logic within complex systems. Building upon insights from Gödel’s incompleteness theorems [ 8 ] , Turing’s work on decidability and computability [ 9 ] , and concepts from thermodynamics and information theory, we formulate a novel explanation. Our core thesis is that genuine autonomy necessarily implies unpredictability from an external perspective: for any truly autonomous system, there exist questions about its future behavior that are fundamentally undecidable. This provides a principled distinction between autonomous and non-autonomous systems without appealing to non-physical properties. We contend that agency specifically emerges in systems operating at the threshold of decidability. Here, Gödel-like constraints manifest as the system’s inability to internally represent complete predictive models of its surroundings [ 10 ] , while Turing-like undecidability signifies the inability to algorithmically ascertain certain future states without executing the entire computation. This leads to computational irreducibility, which generates an information gradient crucial for adaptive behavior [ 11 ] , implying that effective prediction necessitates direct simulation. We argue that this formal necessity is pivotal for comprehending authentic agency, requiring systems to generate novel computational solutions rather than merely retrieving pre-computed responses. To explore this, we propose a formal model of a ”minimal agent” interacting with an environment, clarifying essential concepts such as decidability, completeness, predictability, computational irreducibility, entropy, and information within this framework. We then introduce and formally prove theoretical assertions demonstrating how the undecidability of specific inquiries regarding an agent’s long-term goal-achieving behavior leads to its computational irreducibility, resulting in a lack of external predictability and the continuous generation of new information. This highlights the inherent need for autonomous action (agency) for the agent’s survival or goal accomplishment. To avoid circular reasoning and clarify the logical dependencies in our argument, we present the following logical structure of definitions and theorems: We begin with fundamental definitions (Definition 1 - Definition 4) of decidability, completeness, and computational irreducibility from established literature in theoretical computer science. We then propose Definition 4 of autonomy based on specific computational properties that can be independently verified, without presupposing Turing-completeness or undecidability. Theorem 1 then establishes that an autonomous agent, as defined in Definition 4, must necessarily be Turing-complete if it aims to achieve arbitrary goals. Corollary 1 follows from Theorem 1, showing that autonomous systems must be capable of performing computationally irreducible processes. Theorem 2 demonstrates that for autonomous agents, there exist undecidable questions about their goal-achieving behavior. Theorem 3 establishes the formal connection between undecidability and computational irreducibility. Finally, Theorem 2 (Autonomy Implies Undecidability), our central result, provides the formal proof that autonomy necessarily implies the existence of undecidable properties about the agent’s behavior. The overall structure of the paper is as follows: Section 1 introduces the topic and outlines the logical framework. Section 2 establishes the mathematical foundation and defines key concepts. Section 3 introduces the formal model of a minimal agent and its biological foundations. Section 4 presents our theoretical results, including proofs for autonomy implying Turing-completeness, undecidability, and computational irreducibility. Section 5 discusses emergent agency with illustrative examples. Section 6 details the theoretical implications and limitations. Finally, Section 7 outlines future research directions and concludes the paper. 2 Foundational Concepts and Definitions Definition 1 (Decidability) . A decision problem, denoted as P , is decidable if and only if there exists a Turing machine, M , such that: 1. M halts on every input w . 2. M accepts w if and only if w is a positive instance of P . 3. M rejects w if and only if w is a negative instance of P . Formally, a total computable function f:\Sigma^{*}\to\{0,1\} must exist. For all inputs w\in\Sigma^{*} (where \Sigma^{*} is the set of all possible strings over a finite alphabet), this function f(w)=1 if w\in P and f(w)=0 if w\notin P . In the context of agent behavior, a property P of an agent-environment system is decidable if an algorithm exists that, given a description of the agent, environment, and initial conditions, can determine in finite time whether property P will ever hold during the system’s evolution [ 13 ] . For environments exhibiting sufficient complexity (e.g., those equivalent to Class 4 cellular automata as described by Wolfram [ 14 ] ), determining certain future properties can be provably undecidable. This is often shown via reduction to the Halting Problem [ 15 ] , which asks whether an arbitrary program will finish running or continue to run forever. Definition 2 (Completeness) . A formal system S is complete if and only if for every statement \phi formulated in the language of S , either the statement itself or its negation is provable within the system S . Formally, for all statements \phi in the language L(S) of the system, either S\vdash\phi (meaning \phi is provable in S ) or S\vdash\neg\phi (meaning \neg\phi is provable in S ). A complete system, therefore, can, in principle, decide the truth or falsity of any statement expressible in its language. For an agent system, let S_{A} be the agent’s internal representational system (e.g., its knowledge base and reasoning rules), and let S_{E} represent the set of true statements about the environment. Completeness in this context means that for every truth about S_{E} that is necessary for the agent’s goal achievement, either \phi or \neg\phi is derivable within S_{A} . However, Gödel’s first incompleteness theorem [ 8 ] states that any consistent formal system S capable of representing elementary arithmetic contains statements that are true but unprovable within S . Therefore, for any sufficiently complex agent possessing a finite representational capacity, there will exist true environmental statements relevant to its goals that cannot be derived (proven true or false) using only its internal model [ 10 ] . Definition 3 (Computational Irreducibility) . A process P:I\to O (mapping inputs I to outputs O ) is computationally irreducible