Temporal Causal Models as a Model of Computation
Maksim Gladyshev, Natasha Alechina, Brian Logan · 2026
Read Temporal Causal Models as a Model of Computation by Maksim Gladyshev, Natasha Alechina, Brian Logan (2026) 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-2605-06292.txt.
Introduction
Maksim Gladyshev, Natasha Alechina, and Brian Logan show that temporal causal models can serve as a model of computation. Causal models, also called structural equation models, represent how events depend on each other and support reasoning about interventions and counterfactuals. Their temporal extension adds reasoning across time steps, and this paper asks how much computing power that formalism carries in its own right.
The authors prove temporal causal models can encode linear bounded automata, placing them at the level of context sensitive languages. With variables beyond any finite count, the models are Turing complete, matching the strongest standard notion of computation. These results formally connect causal reasoning with classical computation theory. Counterfactual tools from causal inference may therefore transfer into the theory of computation itself, the authors suggest.
Catalog record
| CREATOR | Maksim Gladyshev, Natasha Alechina, Brian Logan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.06292
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Temporal Causal Models as a Model of Computation Maksim Gladyshev, Natasha Alechina, Brian Logan Abstract Causal models, also known as Structural Equation Models (SEM), are a well-known formalism for representing and reasoning about causal dependencies between events. In this paper, we show that Temporal SEMs (TSEMs), which extend SEMs to support causal reasoning in temporal settings, can be interpreted as a model of computation. We prove that TSEMs can encode Linear Bounded Automata, and thus causal settings representable in context sensitive languages. We also prove that TSEMs with countably many variables are Turing complete. These results establish a formal connection between causal reasoning and classical models of computation, enabling the integration of counterfactual reasoning techniques from causal inference into the theory of computation. 1 Introduction Causal models in the form of Structural Equation Models (SEM) 29 ; 32 ; 21 have become the dominant AI framework for representing and analysing causal relations between events of interest. These models represent events as the assignment of values to variables, and encode causal dependencies between variables using structural equations which define how the value of each variable depends on the values of other variables. Being a relatively simple yet powerful formalism, they have found multiple applications in different disciplines, including Economics 22 , Medicine 19 and Machine Learning 1 . Causal frameworks can also be used to causally model and understand the temporally extended behaviour of natural systems or temporally extended processes. In many applications we are interested in reasoning about not only whether “event A causes event B” but also whether “event A happening at time t_{1} causes event B at time t_{2} ”, and a range of approaches to integrating temporal and causal reasoning have been proposed, based both on SEMs e.g., 11 ; 2 ; 10 ; 18 ; 12 , and on alternative frameworks, e.g., 14 ; 25 ; 4 ; 13 ; 16 . In this paper we argue that temporal causal models are not only an effective tool for reasoning about causal structures underlying physical, biological or social processes, but can also be viewed as a useful formalism for representing computing devices. Although other temporal formalisms, for example extensions of the logic LTL 27 , can be used to reason about computations, temporal causal models allow us to use techniques specifically developed for causal inference, e.g., counterfactual reasoning, to model and understand the dynamics of program behaviour. We show that Temporal Structural Equation Models (TSEM) 18 can encode Linear Bounded Automata and thus causal settings representable in context sensitive languages. We also prove that TSEMS with countably many variables are Turing complete, and sufficiently expressive for reasoning about computations in both deterministic and non-deterministic settings. Understanding the causal evolution of computational processes over time is important for computability theory, and we argue that TSEMs provide a useful framework to represent not only the sequence of computational states, but also the causal dependencies between state transitions. This allows us to analyse how specific inputs or intermediate steps causally affect computational outcomes. For example, TSEMs may be used to augment formal verification techniques to determine why certain errors occurred in a system, and what could prevent them. The contributions of this paper are as follows: 1. We introduce a non-deterministic extension of TSEMs and define interventions on TSEMs in Section 2 . 2. We prove that TSEMs are as expressive as Linear Bounded Automata in Section 3 . 3. We prove that TSEMs with countably many variables are as expressive as Turing machines in Section 4 . 4. We discuss how interventions on TSEMs can be used to answer computational questions in Section 5 . 2 Temporal Causal Models In this section, we introduce the main components of Temporal Structural Equation Models (TSEM). As we aim to encode nondeterministic Linear Bounded Automata and nondeterministic Turing Machines, we focus on nondeterministic causal models in which a set of events may result in more than one outcome. Let \mathcal{V}=\{X_{1},X_{2},\dots\} be a finite set of variables. A range function \mathcal{R} associates with every variable X_{i}\in\mathcal{V} a non-empty finite set \mathcal{R}(X_{i})=\{x_{1},\dots,x_{k}\} of possible values. The values of variables may change over time, and these changes are governed by temporal structural equations which describe how the current value of each X_{i}\in\mathcal{V} depends on the previous values of variables in \mathcal{V} . A domain function \mathcal{D}:\mathcal{V}\longrightarrow 2^{\mathcal{V}} maps each variable Y\in\mathcal{V} to a finite subset of variables, intuitively those variables whose values determine the possible next values of Y . A causal model \mathcal{M} over a signature \mathcal{S}=(\mathcal{V},\mathcal{R},\mathcal{D}) consists of a set of structural equations \mathcal{F}=\{\mathcal{F}_{Y}\mid Y\in\mathcal{V}\} specifying how the next values of Y depends on the previous values of the variables in its domain \mathcal{D}(Y) . Formally: Definition 1 (Temporal Structural Equation Model) . A (nondeterministic) Temporal Structural Equation Model (TSEM), over a signature \mathcal{S} is a tuple \mathcal{M}=(\mathcal{S},\mathcal{F}) , where \mathcal{F} associates with every variable Y\in\mathcal{V} a function \mathcal{F}_{Y}:\prod\limits_{X\in\mathcal{D}(Y)}\mathcal{R}(X)\longrightarrow 2^{\mathcal{R}(Y)} which defines the structural equation describing how the (next) value of Y depends on the (previous) values of the variables in its domain \mathcal{D}(Y) . 1 1 1 We abuse notation and interpret elements of \prod\limits_{X\in\{X_{1},\dots,X_{k}\}}\mathcal{R}(X) both as vectors of values (x_{1},\dots,x_{k}) and as vectors of assignments (X_{1}=x_{1},\dots,X_{k}=x_{k}) . A TSEM is deterministic if all structural equations always return a single value. The changes in the values of variables induced by a set of structural equations are described by a computation. A computation \mathcal{C} is a tree of configurations of \mathcal{M} , i.e., complete assignments of values to variables \mathcal{V} . We denote a complete assignment to \mathcal{V} by \vec{v} , and use \vec{v}^{|X} to denote \vec{v} restricted to X\in\mathcal{V} ; we also denote \vec{v} restricted to the variables in the domain of Y as \vec{v}^{|\mathcal{D}(Y)} . Let \mathit{Conf}^{CM}(\mathcal{M}) be the set of all possible configurations of a causal model \mathcal{M} . Definition 2 (Computation) . A computation \mathcal{C} for a TSEM \mathcal{M} with initial assignment \vec{v_{0}} is a tree \mathcal{T}^{\mathcal{C}} , whose nodes are elements of \mathit{Conf}^{CM}(\mathcal{M}) with root node \vec{v_{0}} , and \vec{v_{1}}\twoheadrightarrow_{\mathcal{M}}\vec{v_{2}} iff \forall X\in\mathcal{V},\vec{v_{2}}^{|X}\in\mathcal{F}_{X}(\vec{v_{1}}^{|\mathcal{D}(X)}) . As a simple illustration, consider a model \mathcal{M} with a single variable X : \mathcal{V}=\{X\} , such that \mathcal{R}(X)=\{0,\dots,9\} , \mathcal{D}(X)=\{X\} , and a single structural equation defined as follows: \mathcal{F}_{X}(X=x)=\begin{cases}9,\text{ if }x=9\\ \{0,x+1\},\text{ if }x\neq 9\\ \end{cases} If the value of X on the previous step of the computation is equal to 9, it remains so on the current step. However, if the previous value x of X is less than 9, \mathcal{F}_{X} makes a non-deterministic choice: either to continue counting and increase the value of X to x+1 or to reset X to 0. One of the key features of causal models is that they allow counterfactual reasoning , that is, they allow us to reason not only about the actual sequence of events, but also about hypothetical counterfactual sequences of events by means of so-called interventions . An intervention is an operation on causal model. An atomic intervention is denoted by do(Y^{n}\leftarrow y) , where Y\in\mathcal{V},n\in\mathbb{N},y\in\mathcal{R}(Y) , says that the value of the variable Y must be fixed to y at the n th step of the computation. An intervention do(\vec{Y}^{\vec{n}}\leftarrow\vec{y})=do(Y_{1}^{n_{1}}\leftarrow y_{1},\dots,Y_{i}^{n_{j}}\leftarrow y_{i}) is a vector of atomic interventions. Here we