Temporal Causal Models as a Model of Computation

Summary

This partial ingest is based on the extracted full PDF text. Gladyshev, Alechina, and Logan show that temporal structural equation models can be read as a model of computation. They introduce nondeterministic TSEMs, define interventions over computation trees, encode linear bounded automata as causal calculators, prove equivalence between LBA acceptance and TSEM acceptance, and show that TSEMs with countably many variables are Turing complete.

Key Claims

• Temporal causal models are not only tools for reasoning about causal processes; they can also represent computing devices.
• TSEMs can simulate linear bounded automata, so they can represent computations over context-sensitive languages.
• With countably many variables, TSEMs can simulate Turing machines, including nondeterministic Turing machines.
• Interventions on TSEMs make it possible to ask counterfactual questions about computations, such as which input bit or intermediate transition was causally necessary for an output.
• Fixed-step causality questions for the presented calculators are decidable, but richer temporal outcome formulas can reintroduce undecidability through halting-style questions.

Methods / Formalism

• A nondeterministic TSEM over signature (V,R,D) has structural equations

$$F_Y:\prod _{X\in D(Y)}R(X)\to 2^{R(Y)}.$$

• A computation is a tree of complete assignments where v_1 -> v_2 iff each next value belongs to the corresponding structural-equation output.
• Atomic interventions do(Y^n <- y) fix variable Y at computation step n across all branches.
• The paper defines a strong but-for temporal cause: changing X at specified time points prevents the target outcome on every branch, with minimality over subsets of the cause variables.
• The LBA causal calculator represents the current automaton state, written symbol, head movement, and tape contents in TSEM variables; the paper proves that the LBA accepts a string iff the corresponding causal calculator accepts it.
• Temporal Structural Equation Models records the reusable TSEM computation and intervention schema.

Evidence / Experiments

• The paper is theoretical.
• Main results: TSEMs encode LBAs; TSEMs with countably many variables encode deterministic TMs; nondeterministic TSEMs encode NTMs stepwise.
• Applications discussed include causal influence of input bits, counterfactual path analysis, and soft-error/fault-tolerance analysis in computational systems.

Connections

• Extends Temporal Causal Models from temporal reasoning about systems to computability-theoretic expressivity.
• Builds on Gladyshev2025 - Temporal Causal Reasoning with Non-Recursive SEMs by using TSEMs as causal calculators.
• Connects Causality to Formal Methods and Algorithms and Data Structures through LBA/Turing-machine encodings.
• Supports explainability of computations by exposing causal dependencies among steps and intermediate values.

Open Questions

• The TSEM calculators are designed constructions; their practical value depends on whether useful program or system models can be represented compactly.
• Structure interventions and richer causal queries are left as future directions.
• Generalizing actual-causality definitions beyond simple but-for causes in nondeterministic temporal models remains open.

Citation

Gladyshev, M., Alechina, N., and Logan, B. (2026). Temporal Causal Models as a Model of Computation. arXiv:2605.06292v1.