Temporal Causal Models as a Model of Computation
For researchers in causal inference and computation theory, this work provides a foundational link between causal models and models of computation, enabling integration of counterfactual reasoning into computation theory.
This paper shows that Temporal Structural Equation Models (TSEMs) can encode Linear Bounded Automata and are Turing complete with countably many variables, establishing a formal connection between causal reasoning and classical computation.
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.