arxiv: 2605.06292 · v1 · submitted 2026-05-07 · 💻 cs.FL

Recognition: unknown

Temporal Causal Models as a Model of Computation

Maksim Gladyshev , Natasha Alechina , Brian Logan

Authors on Pith no claims yet

Pith reviewed 2026-05-08 03:17 UTC · model grok-4.3

classification 💻 cs.FL

keywords temporal causal modelsstructural equation modelsmodels of computationlinear bounded automataTuring completenesscausal inferencecontext-sensitive languagescounterfactual reasoning

0 comments

The pith

Temporal causal models can encode linear bounded automata and achieve Turing completeness with countably many variables.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper shows that temporal structural equation models extend standard causal models to handle time and can function as models of computation. The authors prove these models simulate linear bounded automata, covering causal settings expressible in context-sensitive languages, and that versions with countably many variables are Turing complete. This creates a direct link between causal reasoning and classical computation theory. A sympathetic reader would care because it opens the possibility of applying counterfactual queries and other causal techniques to analyze or verify computational processes. The central effort is to preserve the ability to reason about interventions while mapping causal dependencies to computational transitions.

Core claim

TSEMs can encode Linear Bounded Automata, and thus causal settings representable in context sensitive languages. 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.

What carries the argument

Temporal Structural Equation Models (TSEMs), the temporal extension of SEMs in which causal dependencies over time are aligned with the transition rules of automata.

If this is right

Causal reasoning techniques such as counterfactual queries can be integrated into the theory of computation.
Causal settings in context-sensitive languages can be represented and reasoned about using TSEMs.
This provides a new way to model and analyze temporal computational processes with causal tools.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This link could allow causal discovery methods to be used for inferring the rules of unknown computational systems from data.
Extensions might map other causal model features to different classes of automata or complexity measures.
Practical systems could use TSEMs to simulate computations while querying what would have happened under different causal interventions.

Load-bearing premise

The temporal extension of SEMs can be defined such that the causal dependencies directly correspond to the transition rules of automata and Turing machines without losing the ability to perform counterfactual reasoning.

What would settle it

A specific linear bounded automaton for a known context-sensitive language that cannot be encoded by any TSEM, or a Turing machine that no countable-variable TSEM can simulate.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows TSEMs encode LBAs and are Turing complete with countably many variables, but the key question is whether the temporal construction preserves well-defined interventions and counterfactuals.

read the letter

The main point is that the authors prove temporal structural equation models can represent linear bounded automata, hence context-sensitive languages, and that versions with countably many variables are Turing complete. This gives a direct encoding where automaton transitions become causal dependencies via time-indexed variables and structural equations. If the details check out, it lets counterfactual reasoning from causal inference apply to computational models in a formal way. That connection is not standard in either the causal models literature or automata theory, so the result is new on its face. The abstract frames the extension cleanly and sticks to the encoding claims without overreaching into applications. The work builds on ordinary SEM definitions and standard Turing machine notions, which keeps the circularity burden low. The soft spot is the verification of the central assumption. The temporal indexing must map transitions to causal functions without creating cycles, non-local dependencies, or cases where interventions become undefined under do-calculus. If any of that happens, the model is only a syntactic simulation and the causal reasoning part does not fully transfer. The abstract gives no definitions of TSEMs or proof outlines, so it is impossible to tell from the given text whether the constructions avoid those problems. The Turing completeness claim with countably many variables is also strong and would benefit from seeing how counterfactual queries behave in the infinite case. This is for readers who already know both causal models and computability theory and want to explore crossovers. Someone working on either side who is open to new formal bridges would get value from checking the proofs. I would send it to peer review because the claims are specific enough to be tested and the potential link is worth confirming even if revisions are needed on the preservation of causal semantics.

Referee Report

2 major / 1 minor

Summary. The paper introduces Temporal Structural Equation Models (TSEMs) as an extension of standard Structural Equation Models (SEMs) to temporal settings. It claims to prove that TSEMs can encode Linear Bounded Automata (LBAs), thereby representing causal settings in context-sensitive languages, and that TSEMs with countably many variables are Turing complete. This is presented as establishing a formal connection between causal reasoning and classical models of computation, enabling the use of counterfactual techniques from causal inference in computability theory.

Significance. If the encodings and proofs hold while preserving well-defined interventions and counterfactuals under do-calculus, the work would create a substantive bridge between causal models and automata/Turing theory, with potential for new analyses of computation via interventions. The explicit claims of LBA encoding and countable-variable Turing completeness are strengths that provide concrete, falsifiable links between the formalisms.

major comments (2)

[§2] §2 (TSEM definition): The temporal extension of SEMs is not fully specified with respect to how structural equations are indexed over time and how next-state functions are encoded as causal dependencies; without this, it cannot be verified that the constructions avoid implicit cycles or non-local dependencies that would render some interventions undefined.
[§4] §4 (LBA encoding proof): The claim that TSEMs encode LBAs (and thus context-sensitive languages) rests on mapping automaton transitions to causal dependencies, but the manuscript provides no explicit construction or verification that the resulting model still admits standard counterfactual queries; this is load-bearing for the central claim that TSEMs function as causal models of computation rather than mere syntactic simulations.

minor comments (1)

[Notation] Notation for time-indexed variables (e.g., X^{(t)}) should be defined once at the outset and used consistently to avoid ambiguity with standard SEM notation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. The concerns about specification and explicit verification are well-taken and can be addressed through targeted clarifications and expansions in a revised version, without altering the core results.

read point-by-point responses

Referee: [§2] §2 (TSEM definition): The temporal extension of SEMs is not fully specified with respect to how structural equations are indexed over time and how next-state functions are encoded as causal dependencies; without this, it cannot be verified that the constructions avoid implicit cycles or non-local dependencies that would render some interventions undefined.

Authors: Section 2 defines TSEMs via time-indexed variables where each structural equation for a variable at time t depends exclusively on variables at prior time steps, directly encoding next-state transitions as causal parents. This structure is intended to maintain acyclicity within and across slices. We agree that the indexing and cycle-avoidance argument would benefit from greater formality. We will revise §2 to include an explicit inductive definition of the indexing, a formal statement that dependencies are strictly backward in time, and a short lemma confirming that all interventions remain well-defined under the standard do-calculus. revision: yes
Referee: [§4] §4 (LBA encoding proof): The claim that TSEMs encode LBAs (and thus context-sensitive languages) rests on mapping automaton transitions to causal dependencies, but the manuscript provides no explicit construction or verification that the resulting model still admits standard counterfactual queries; this is load-bearing for the central claim that TSEMs function as causal models of computation rather than mere syntactic simulations.

Authors: Section 4 supplies a construction that maps each LBA configuration (state, head position, tape contents) to a finite collection of time-indexed TSEM variables, with structural equations implementing the transition relation. Interventions on initial variables then correspond to changes in starting configuration, and the resulting counterfactuals recover the automaton's behavior. We acknowledge that the explicit mapping and the preservation of do-calculus queries could be stated more formally. We will expand §4 with the full construction, a diagram of the variable dependencies, and a proposition verifying that standard counterfactual queries remain valid in the encoded model. revision: yes

Circularity Check

0 steps flagged

No circularity: encodings are explicit constructions from standard automata definitions into TSEM equations

full rationale

The paper defines TSEMs by extending standard SEMs with temporal indexing of variables and structural equations that directly mirror automaton transitions (next-state variables as deterministic functions of prior configuration). The proofs consist of exhibiting these mappings for LBAs and countable-variable Turing machines, then verifying that the resulting models remain acyclic and admit do-calculus interventions. No step reduces a claimed result to a fitted parameter, self-citation, or definitional renaming; the constructions are independent of the target theorems and rely only on the external definitions of automata and SEM semantics. The central claim therefore does not collapse to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the assumption that TSEMs preserve causal semantics while allowing direct mapping to computational transition functions; no free parameters or new entities are introduced beyond the temporal extension itself.

axioms (1)

domain assumption Temporal extension of SEMs preserves the ability to represent and reason about causal dependencies in a manner compatible with automata encodings.
Invoked to justify that the TSEM formalism can simulate computation without additional constraints on counterfactual reasoning.

pith-pipeline@v0.9.0 · 5401 in / 1063 out tokens · 29898 ms · 2026-05-08T03:17:13.917735+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

29 extracted references · 4 canonical work pages

[1]

[Albahriet al., 2022 ] A. S. Albahri, Alhamzah Alnoor, A. A. Zaidan, O. S. Albahri, Hamsa Hameed, B. B. Zaidan, S. S. Peh, A. B. Zain, S. B. Siraj, A. H. B. Masnan, and A. A. Yass. Hybrid artificial neural network and structural equa- tion modelling techniques: a survey.Complex & Intelli- gent Systems, 8(2):1781–1801,

2022
[2]

Assaad, Emilie Devijver, and Eric Gaussier

[Assaadet al., 2022 ] Charles K. Assaad, Emilie Devijver, and Eric Gaussier. Survey and evaluation of causal dis- covery methods for time series.J. Artif. Int. Res., 73, May

2022
[3]

On the logic of interven- tionist counterfactuals under indeterministic causal laws

[Barbero, 2024] Fausto Barbero. On the logic of interven- tionist counterfactuals under indeterministic causal laws. In Arne Meier and Magdalena Ortiz, editors,Foundations of Information and Knowledge Systems, pages 203–221, Cham,

2024
[4]

[Batusov and Soutchanski, 2018] Vitaliy Batusov and Mikhail Soutchanski

Springer Nature Switzerland. [Batusov and Soutchanski, 2018] Vitaliy Batusov and Mikhail Soutchanski. Situation calculus semantics for actual causality.Proceedings of the AAAI Conference on Artificial Intelligence, 32(1),

2018
[5]

[Beckers and Halpern, 2019] Sander Beckers and Joseph Y . Halpern. Abstracting causal models. InProceedings of the Thirty-Third AAAI Conference on Artificial Intel- ligence and Thirty-First Innovative Applications of Ar- tificial Intelligence Conference and Ninth AAAI Sympo- sium on Educational Advances in Artificial Intelligence, AAAI’19/IAAI’19/EAAI’19....

2019
[6]

[Boeken and Mooij, 2024] Philip Boeken and Joris M. Mooij. Dynamic structural causal models.arXiv preprint arXiv:2406.01161,

work page arXiv 2024
[7]

[Bongerset al., 2022 ] Stephan Bongers, Tineke Blom, and Joris M. Mooij. Causal modeling of dynamical systems. arXiv preprint arXiv:1803.08784,

work page arXiv 2022
[8]

A practical ap- proach to causal inference over time.Proceedings of the AAAI Conference on Artificial Intelligence, 39(14):14832– 14839, Apr

[Cinquiniet al., 2025 ] Martina Cinquini, Isacco Beretta, Salvatore Ruggieri, and Isabel Valera. A practical ap- proach to causal inference over time.Proceedings of the AAAI Conference on Artificial Intelligence, 39(14):14832– 14839, Apr

2025
[9]

Comparing semantics for temporal stit logic

[Ciuni and Lorini, 2018] Roberto Ciuni and Emiliano Lorini. Comparing semantics for temporal stit logic. Logique et Analyse, (243):pp. 299–339,

2018
[10]

Temporal constraint satisfaction on causal models.Information Sciences, 68(1):1–32,

[Console and Torasso, 1993] Luca Console and Pietro Torasso. Temporal constraint satisfaction on causal models.Information Sciences, 68(1):1–32,

1993
[11]

Model checking causality

[de Lima and Lorini, 2024] Tiago de Lima and Emiliano Lorini. Model checking causality. InThirty-Third Interna- tional Joint Conference on Artificial Intelligence (IJCAI- 24), pages 3324–3332,

2024
[12]

Synthesis of temporal causality

[Finkbeineret al., 2024 ] Bernd Finkbeiner, Hadar Frenkel, Niklas Metzger, and Julian Siber. Synthesis of temporal causality. InComputer Aided Verification: 36th Interna- tional Conference, CAV 2024, Montreal, QC, Canada, July 24–27, 2024, Proceedings, Part III, page 87–111, Berlin, Heidelberg,

2024
[13]

Temporal causal reasoning with (non- recursive) structural equation models.arXiv preprint arXiv:2501.10190,

[Gladyshevet al., 2025b ] Maksim Gladyshev, Natasha Alechina, Mehdi Dastani, Dragan Doder, and Brian Logan. Temporal causal reasoning with (non- recursive) structural equation models.arXiv preprint arXiv:2501.10190,

work page arXiv
[14]

CRC Press, 02

[Gunzleret al., 2021 ] Douglas Gunzler, Adam Perzynski, and Adam Carle.Structural Equation Modeling for Health and Medicine. CRC Press, 02

2021
[15]

Halpern and Spencer Peters

[Halpern and Peters, 2022] Joseph Y . Halpern and Spencer Peters. Reasoning about causal models with infinitely many variables.Proceedings of the AAAI Conference on Artificial Intelligence, 36(5):5668–5675, Jun

2022
[16]

Halpern.Actual Causality

[Halpern, 2016] Joseph Y . Halpern.Actual Causality. The MIT Press,

2016
[17]

Causality and econometrics

[Heckman and Pinto, 2022] James J Heckman and Rodrigo Pinto. Causality and econometrics. Working Paper 29787, National Bureau of Economic Research, February

2022
[18]

Airbus says most of its recalled 6,000 a320 jets now modified.Reuters, 1 Dec

[Hepheret al., 2025 ] Tim Hepher, Allison Lampert, and David Shepardson. Airbus says most of its recalled 6,000 a320 jets now modified.Reuters, 1 Dec

2025
[19]

[Hopcroft and Ullman, 1979] John E

Available at: https://www.reuters.com/business/aerospace-defense/ airbus-narrows-software-crisis-airlines-ride-out-a320 -recall-2025-12-01/. [Hopcroft and Ullman, 1979] John E. Hopcroft and Jef- frey D. Ullman.Introduction to Automata Theory, Lan- guages, and Computation (1st ed.). Addison-Wesley,

2025
[20]

Temporal logic and its ap- plication to normative reasoning.Journal of Applied Non- Classical Logics, 23(4):372–399,

[Lorini, 2013] Emiliano Lorini. Temporal logic and its ap- plication to normative reasoning.Journal of Applied Non- Classical Logics, 23(4):372–399,

2013
[21]

Mukherjee, J

[Mukherjeeet al., 2005 ] S.S. Mukherjee, J. Emer, and S.K. Reinhardt. The soft error problem: an architectural per- spective. In11th International Symposium on High- Performance Computer Architecture, pages 243–247,

2005
[22]

Synchronizing ams assertions with ams simulation: From theory to prac- tice.ACM Transactions on Design Automation of Elec- tronic Systems (TODAES), 17(4):1–25,

[Mukherjeeet al., 2012 ] Subhankar Mukherjee, Pallab Das- gupta, Siddhartha Mukhopadhyay, Scott Little, John Havlicek, and Srikanth Chandrasekaran. Synchronizing ams assertions with ams simulation: From theory to prac- tice.ACM Transactions on Design Automation of Elec- tronic Systems (TODAES), 17(4):1–25,

2012
[23]

[Pearl, 2000] Judea Pearl.Causality: Models, Reasoning, and Inference.Cambridge University Press, New York,

2000
[24]

Rubenstein, Sebastian Weichwald, Stephan Bongers, Joris M

[Rubensteinet al., 2017 ] Paul K Rubenstein, Sebastian We- ichwald, Stephan Bongers, Joris M Mooij, Dominik Janz- ing, Moritz Grosse-Wentrup, and Bernhard Sch ¨olkopf. Causal consistency of structural equation models.arXiv preprint arXiv:1707.00819,

work page arXiv 2017
[25]

WORLD SCIENTIFIC,

[Simovici and Tenney, 1999] Dan Simovici and Richard L Tenney.Theory of Formal Languages with Applications. WORLD SCIENTIFIC,

1999
[26]

The MIT Press,

[Spirteset al., 2001 ] Peter Spirtes, Clark Glymour, and Richard Scheines.Causation, Prediction, and Search. The MIT Press,

2001
[27]

Do not marginal- ize mechanisms, rather consolidate! InThirty-seventh Conference on Neural Information Processing Systems,

[Williget al., 2023 ] Moritz Willig, Matej Ze ˇcevi´c, Deven- dra Singh Dhami, and Kristian Kersting. Do not marginal- ize mechanisms, rather consolidate! InThirty-seventh Conference on Neural Information Processing Systems,

2023
[28]

Reasoning About Actual Causality in An- swer Set Programming

[ ¨Ozcanet al., 2025 ] Daniel ¨Ozcan, Dalal Alrajeh, and Robert Craven. Reasoning About Actual Causality in An- swer Set Programming. InProceedings of the 22nd In- ternational Conference on Principles of Knowledge Rep- resentation and Reasoning, pages 610–620, 10

2025
[29]

We start with a definition of NTM [Hopcroft and Ullman, 1979]

The overall argu- ment is very similar to Section 3, except the numeration of the tape cells. We start with a definition of NTM [Hopcroft and Ullman, 1979]. Definition 12.A non-deterministic Turing Machine (NTM) is a tupleT ∗ = (Q, q 0, F,Σ,Γ, δ ∗), in which all elements exceptδ ∗ are identical to TM (Definition 8), and the transition function is replaced...

1979