Types of computational models

Below is a structured list of computational models. The spectrum is organized from fully deterministic and centralized at one end, to decentralized, adaptive, and emergent systems at the other.

#	Model Type	Name	Key Properties	Position
1	Deterministic	Finite State Machine (FSM)	Static states, input-driven transitions, no memory beyond state	Minimal autonomy, centralized
2	Deterministic	Pushdown Automaton (PDA)	FSM + stack (memory), suitable for parsing nested structures	FSM with memory
3	Deterministic	Turing Machine	Infinite tape memory, theoretical basis of general computation	Centralized but powerful
4	Reactive Systems	Event-Driven Architectures (EDA)	Stateless or stateful, reacts to events, e.g., microcontrollers	Still centralized or module-local
5	Distributed State Machines	State Machine Replication (SMR)	FSMs replicated across nodes (e.g., Raft, Paxos), ensuring consistency	Blockchain consensus layer fits here
6	Distributed Execution	Smart Contracts (on Blockchain)	FSM-like, deterministic, distributed, passive, consensus-driven	Bridges centralized logic and distributed deployment
7	Logic-based	Rule-Based Systems / Expert Systems	IF-THEN rules, possibly with a working memory	Central but symbolic reasoning
8	Knowledge-based	Production Systems	Rule sets with inference engine and memory (e.g., OPS5, CLIPS)	Local reasoning; semi-autonomous
9	Object-Oriented	Actors Model	Concurrent entities with private state, communicate via async messages	Distributed, loosely coupled
10	Declarative/Reactive Constraint Satisfaction Systems	Solves problems by propagating constraints across variables	Reactive, can be distributed
11	Autonomous Agents	BDI Agents (Belief-Desire-Intention)	Agents with internal goals, beliefs, and planning	Autonomous, goal-directed
12	Adaptive	Reinforcement Learning Agents	Learn behavior through environment interaction and reward	Adaptive, often centralized
13	Distributed Autonomous	Swarm Intelligence / Stigmergic Systems	Indirect coordination via environment (stigmergy), e.g., ant colony	Bottom-up emergence, no central control
14	Distributed Coordination	Multi-Agent Systems (MAS)	Autonomous agents, possible learning, social protocols, communication	Fully distributed and adaptive
15	Hybrid Adaptive	Cognitive Architectures (e.g., SOAR, ACT-R, Brain-CA, CogTwin)	Integrates perception, planning, memory, learning	High autonomy, often hybrid centralized-distributed
16	Decentralized Social Machines	Holonic Systems / Digital Ecosystems (ex. HoL, Flexible Holons (MIT CCS), Adaptive Holonic Architectures (ACM 2008)	Self-similar agents (holons), recursive coordination, adaptability	Edge of MAS and beyond

Holonic and digital ecosystem systems are advancing rapidly across distributed AI, industrial IoT, and hybrid agentic frameworks. These architectures merge self-similar recursive structures (holons) with adaptive, cooperative intelligence at the edge of multi-agent systems (MAS).

both cognitive architectures (like SOAR and ACT‑R) and holonic/digital ecosystem systems can reasonably be classified as non‑deterministic computational models, although in subtly different ways.

Cognitive architectures typically combine deterministic rule‑based logic with stochastic learning or adaptive mechanisms, producing behavior that is non‑deterministic in outcome even if deterministic in structure.

Architectures such as SOAR, ACT‑R, and Sigma employ fixed control cycles and production rules (deterministic bases), but their performance depends on activation levels, probabilistic retrievals, and environmental stimuli, making identical inputs sometimes yield different results.

This is referred to as “soft determinism” or stochastic rule interaction, similar to probabilistic AI systems that adapt or explore within constraint spaces.

The result is bounded non‑determinism, where the architecture remains explainable but can flexibly handle uncertainty, incomplete data, or noise — essential for human‑like cognition.

Holonic systems and digital ecosystems extend non‑determinism to structural and organizational levels:

A holon’s state and behavior are locally autonomous yet recursively influenced by higher‑level holarchies, creating emergent global patterns not predictable from initial states alone.

Because these systems rely on distributed decision‑making, self‑organization, and recursive feedback, they behave as non‑deterministic complex adaptive systems — similar in spirit to non‑deterministic constraint logic models, where multiple valid computational paths coexist until resolution.

In modern implementations (e.g., decentralized holonic control in manufacturing or IoT), agents negotiate and reorganize dynamically, producing multiple possible outcomes from identical starting configurations.

From a theoretical standpoint:

Deterministic computation maps one input to one output.
Non‑deterministic computation explores multiple simultaneous paths or probabilistic transitions, aligning with adaptive, agentic, and emergent architectures.

Thus, cognitive architectures are algorithmically deterministic but functionally non‑deterministic, while holonic/digital ecosystems are organizationally non‑deterministic, showing emergent, multi‑path computation. Both embody adaptive non‑determinism — systems whose behavior is not fully predictable yet remains structured and goal‑oriented within defined boundaries.

Key Axes of Differentiation

Axis	Examples of Shift
Statefulness	FSM → PDA → Turing Machine → Smart Contract
Execution Environment	Centralized → Distributed (e.g. Smart Contracts, Actor Model)
Adaptivity	Rule-Based → BDI → RL → MAS
Agency / Autonomy	FSM (none) → Actors → BDI → MAS
Coordination Direct	call → Message passing → Stigmergy → Emergence
Emergent Behavior	Absent in FSM, present in Swarm Systems, MAS
Learning Capability	Only appears in RL agents and above

Summary Diagram (Linear Spectrum Approximation)

FSM ─ PDA ─ Turing ─ EDA ─ SMR ─ Smart Contracts ─ Actor Model ─ BDI ─ RL Agents ─ Swarm ─ MAS

->-------------------------------------------------------------------------------------------------------------------------------------<-

Deterministic, Centralized------------------------------------------------Distributed, Adaptive, Emergent

Relationship to Smart Contracts

Smart Contracts (on Blockchain)

Structure: Typically deterministic, formalized as state machines (e.g., Ethereum's contracts are like extended FSMs with internal variables and persistent storage).
Deployment context: Distributed (across nodes of the blockchain).
Autonomy: Very limited – they do not initiate actions on their own (no built-in scheduler or perception of external states unless triggered by a transaction).
Adaptability: None or very limited – unless explicitly coded, they don’t learn or adapt.
Concurrency: Handled via the consensus layer, not by the contracts themselves.
Coordination: Possible via message passing (events, calls between contracts), but hard-coded.
So smart contracts are deterministic, immutable, and reactive, functioning more like passive agents or services that respond to externally triggered inputs (transactions). They maintain state, but do not exhibit emergent behavior or learning.

Smart contracts could be:

Implemented as FSMs (e.g., token contracts: Minted → Active → Burned).
Hosted within replicated state machines (e.g., Ethereum Virtual Machine).
Used by multi-agent systems as coordination primitives, rules enforcement, registries, or economic boundary conditions.

They lack:

Adaptation (no learning),
Proactivity (they don’t initiate),
Perception (they don’t sense beyond what is input),
Multi-agent awareness (no negotiation or emergent coordination).

Smart contracts are more advanced than FSMs due to their persistence, distributed execution, and ability to encode rich transactional logic, but they lack the autonomy, learning, and dynamic coordination mechanisms of multi-agent systems.

Smart contracts are like distributed finite state machines embedded in a shared, tamper-resistant ledger. They serve as deterministic, passive components in a distributed system, closer to FSMs, but operationally deployed in a distributed context like MAS.

They can serve as infrastructure for MAS, e.g., as rule enforcement layers, registries, or coordination contracts in larger multi-agent frameworks. But by themselves, smart contracts are not agents, nor are they adaptive.

Smart contracts on blockchain technology sit at a unique intersection within computational paradigms:

Closer to a finite state machine (FSM): Smart contracts are typically implemented as deterministic automata. Each contract has well-defined logic, transitions state based on inputs (transactions or calls), and moves through a series of discrete states. For instance, an Ethereum smart contract maintains a state that changes only in response to specific function calls in transactions, much like an FSM processes events to change state.
Distributed, but not adaptive/multi-agent in the Holochain sense: Blockchain smart contracts are distributed in that their state and logic are replicated across many nodes for consensus and fault-tolerance, but each contract instance acts according to its predetermined logic and does not autonomously adapt or "learn" in interaction with others. In contrast, truly distributed, adaptive, multi-agent systems feature autonomous agents capable of negotiation, dynamic behavior adaptation, and collaborative problem-solving—none of which are inherent in typical smart contracts.

The theoretical and practical limits of state machines for governing human communities

Based on extensive research across computer science, complexity theory, governance studies, and real-world implementations, finite state machines (FSMs) face insurmountable theoretical and practical limitations when applied to governing human communities at scale. These limitations stem from fundamental mathematical constraints, empirical evidence of systemic failures, and deep philosophical incompatibilities with human agency and democratic values.

The computational impossibility of modeling human societies

At the most fundamental level, FSMs occupy the bottom tier of the Chomsky hierarchy, capable only of recognizing regular languages. This severely limits their computational expressiveness compared to the requirements of modeling human social systems. Research from formal language theory conclusively demonstrates that FSMs cannot handle context-sensitive behaviors, recursive structures, or unbounded memory requirements - all essential features of human social interaction.

The state explosion problem renders FSM-based governance mathematically impossible for realistic populations. To model even a small city of 100,000 people with minimal behavioral tracking would require approximately 10^200,000 states - a number so large it exceeds the total atoms in the observable universe by factors beyond comprehension. Memory requirements alone would make such systems impossible with any conceivable technology. Industrial verification tools struggle with systems containing more than 10^9 states, while meaningful social modeling would require exponentially more. This isn't merely a matter of needing more powerful computers. The computational complexity grows exponentially with population size, creating fundamental barriers that no amount of optimization can overcome. Even sophisticated mitigation strategies like hierarchical state machines or symbolic representations only reduce constants without addressing the underlying exponential growth.

Evidence from real-world algorithmic governance failures

Empirical evidence from attempts at algorithmic governance reveals consistent patterns of failure when rigid state-based approaches encounter the complexity of human societies. The Netherlands' System Risk Indication (SyRI) was shut down by courts in 2020 for violating human rights through opaque algorithmic discrimination. Despite years of operation, it failed to detect any new fraud cases while systematically targeting low-income neighborhoods.

The UK's National Programme for IT in healthcare became one of history's most expensive IT failures, wasting over £12 billion attempting to model complex healthcare workflows as state machines. Similarly, the US Healthcare.gov launch in 2013 crashed immediately when real-world usage patterns exceeded the rigid assumptions built into its state-based architecture. Historical attempts at cybernetic governance provide particularly instructive failures. The Soviet Union's OGAS project, which aimed to manage the entire economy through networked computers and state machines, collapsed due to bureaucratic resistance and the fundamental inability to capture economic complexity in predetermined states. Chile's Project Cybersyn under Allende showed initial promise but revealed the limitations of trying to model dynamic social and economic systems through formal state representations. The emergence and adaptability challenge

Human social systems exhibit emergent properties that fundamentally exceed the capabilities of finite state machines. Research from the Santa Fe Institute and complexity science demonstrates that social systems generate genuinely novel behaviors through non-linear dynamics and self-organization. These emergent phenomena cannot be captured by predetermined state transitions - they require computational models capable of generating new states and rules dynamically.

FSMs fail catastrophically when encountering Black Swan events - statistically improbable occurrences with massive impact that lie outside the originally conceived state space. The 2008 financial crisis, Arab Spring, and COVID-19 pandemic all demonstrated how human societies face genuinely unprecedented situations requiring adaptive responses that no predetermined state machine could handle. Human creativity and innovation further expose FSM limitations. Innovation often involves breaking existing rules rather than following them - a capability fundamentally beyond state machines that can only execute predefined transitions. Successful human institutions exhibit "institutional learning" and evolve their own governing principles, requiring meta-governance capabilities that transcend fixed rule systems.

Comparative analysis reveals superior alternatives

Empirical comparisons between different computational approaches to social coordination consistently show the limitations of centralized, state-based systems. Multi-agent systems demonstrate O(N log N) computational complexity for modeling social interactions, compared to the exponential complexity of equivalent FSM representations. Agent-based models, being computationally universal (subject to the Church-Turing thesis), can capture emergent behaviors and adapt to new situations in ways FSMs cannot. Real-world comparative studies reinforce these theoretical findings. Wikipedia's hybrid human-algorithm governance model successfully scaled to millions of articles while maintaining quality, but its increasing automation correlates with declining editor retention and diversity. Blockchain governance experiments reveal that even with transparency advantages, rigid protocol-based systems struggle with adaptation and crisis response compared to traditional institutional flexibility.

Philosophical and democratic incompatibilities

Beyond technical limitations, FSMs embody a vision of governance fundamentally incompatible with human freedom and democratic values. Hannah Arendt's concept of "natality" - the human capacity for spontaneous, unpredictable action - stands in direct opposition to the deterministic nature of state machines. Politics requires accommodating genuine human action, not merely predictable behavior that follows predetermined patterns.

The drive toward algorithmic legibility exemplifies what James C. Scott identified as "high modernist" failures - technocratic schemes that ignore local knowledge and human complexity. FSMs represent the ultimate expression of this impulse to make populations "legible" through standardized categories, but this reductionism systematically excludes the practical wisdom (metis) essential for effective governance.

Democratic theorists like Cristina Lafont argue that algorithmic governance creates impermissible "shortcuts" around democratic deliberation. True democratic legitimacy requires that citizens see themselves as authors of the laws governing them - impossible when those laws are encoded in opaque state machines designed by technical elites. The "black box" nature of complex state systems makes democratic accountability and contestation impossible. The multi-agent alternative

Research consistently points toward distributed, adaptive, multi-agent approaches as more suitable for social coordination. Unlike FSMs, multi-agent systems can:

Handle emergent behaviors through agent interactions
Adapt to new situations without reprogramming
Scale efficiently with population size
Accommodate human agency and creativity
Integrate local knowledge and context

Successful digital governance initiatives like Estonia's e-governance system and Taiwan's vTaiwan platform employ distributed architectures that preserve human agency while leveraging computational efficiency. These systems succeed precisely because they don't attempt to reduce human complexity to finite states but instead create frameworks for human-computer collaboration.

Conclusion: fundamental incompatibility

The evidence overwhelmingly demonstrates that finite state machines are not merely inadequate but fundamentally incompatible with governing human communities. This incompatibility manifests at multiple levels:

Computationally, FSMs lack the expressiveness to model context-sensitive human behaviors and face insurmountable state explosion problems. Practically, real-world implementations consistently fail when confronting the complexity and unpredictability of human societies. Philosophically, FSMs embody a reductionist, deterministic vision of governance that violates principles of human freedom, democratic participation, and dignity.
While FSMs remain valuable for modeling simple, well-defined processes with clear state transitions, the attempt to use them for governing entire human communities represents a category error - trying to force the rich complexity of human social life into the impoverished framework of regular languages and finite states. The future of computational governance lies not in more sophisticated state machines but in adaptive, distributed systems that enhance rather than replace human agency and democratic deliberation.

Computational model

Contents