Computational Irreducibility from a Causal Perspective via Temporal Causal Models
Computational irreducibility is often discussed informally as the inability to shortcut a system’s evolution, but it lacks a unified causal-operational characterization. This project proposes a Temporal Causal Models (TCM)-based framework to define and measure irreducibility in dynamical computations. We will formalize notions of causal depth, simulation shortcut limits, and intervention-based predictability, then evaluate them across synthetic and benchmark sequential systems. The expected impact is a clearer theory of when fast prediction is fundamentally impossible and practical tools to diagnose irreducibility in real computational processes.
Problem Workspace
Problem Statement
This project investigates computational irreducibility through the lens of Temporal Causal Models (TCMs), treating computation as a time-indexed causal process rather than only an input-output mapping. The core scope is to define irreducibility in terms of causal structure over trajectories: whether accurate prediction of future states can be achieved without reconstructing key intermediate causal pathways. We will formulate irreducibility criteria using interventional semantics, path-dependent state abstractions, and lower bounds on shortcut simulators constrained by causal sufficiency. The work is organized into three tracks. First, a theoretical track will define formal quantities (for example, temporal causal depth, intervention sensitivity profiles, and minimal sufficient trajectory summaries) and prove relationships between them and shortcut simulation complexity. Second, an empirical track will instantiate TCMs for controlled systems (cellular automata,…Read more
Read less
Execution plan
Metrics: (1) multi-step prediction error under intervention and observational settings, (2) shortcut efficiency ratio = runtime/compute needed by best constrained shortcut vs full rollout, (3) causal depth estimates, (4) intervention sensitivity concentration, and (5) calibration/uncertainty of irreducibility scores. Baselines: naive full simulation, standard sequence predictors (RNN/Transformer/state-space models), symbolic shortcut heuristics, and non-causal complexity proxies (e.g., entropy/compressibility-based indicators). Data and splits: synthetic families with known dynamics (multiple cellular automata rules, random and structured Boolean networks, selected algorithmic process traces), with train/validation/test splits by initial conditions and out-of-distribution splits by rule/topology class. Acceptance criteria: proposed causal irreducibility metrics must significantly improve discrimination between reducible and irreducible regimes over non-causal baselines, remain stable across random seeds and perturbations, and demonstrate consistent ranking under controlled interventions; additionally, at least one formal result must match empirical behavior on benchmark cases.