Universality in Elementary Cellular Automata

The purpose of this paper is to prove a conjecture made by Stephen Wolfram in 1985, that an elementary one dimensional cellular automaton known as "Rule 110" is capable of universal computation. I developed this proof of his conjecture while assisting Stephen Wolfram on research for A New Kind of Science [1].

• Publication year

  2004

• Venue

  Complex Systems

• Publication date

  2004-03-15

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.25088/complexsystems.15.1.1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Theory and Applications of Cellular Automata

  1986cited by this paper
• Universality and complexity in cellular automata

  1983cited by this paper
• Winning Ways for Your Mathematical Plays

  1983cited by this paper
• Simple Computation-Universal Cellular Spaces

  1971cited by this paper
• Elementary formal systems

  1961cited by this paper
• Universality in Elementary Cellular Automata

  year unknowncited by this paper

• Some conditions implying if P=NP then P=PSPACE

  2026cites this paper
• On the Spatiotemporal Dynamics of Generalization in Neural Networks

  2026cites this paper
• Quantum Cellular Automata on a Dual-Species Rydberg Processor

  2026cites this paper
• Enhancing Neuromorphic Robustness via Recurrence Resonance: The Role of Shared Weak Attractors in Quantum Logic Networks

  2026cites this paper
• Cellular Automaton Reducibility as a Measure of Complexity for Infinite Words

  2026cites this paper
• Discrete system phase space modification by vanishing noise

  2025cites this paper
• Post-apocalyptic computing from cellular automata

  2025cites this paper
• GOL in GOL in HOL: Verified Circuits in Conway's Game of Life

  2025cites this paper
• Counting Short Trajectories in Elementary Cellular Automata using the Transfer Matrix Method

  2025cites this paper
• What does it mean for a system to compute?

  2025cites this paper
• Neural Cellular Automata for ARC-AGI

  2025cites this paper
• Koopman-based data-driven soft artificial life: obtaining rulesets from observed data

  2025cites this paper
• Training a Generally Curious Agent

  2025cites this paper
• Rethinking Visual Intelligence: Insights from Video Pretraining

  2025cites this paper
• Computational Irreducibility as the Foundation of Agency: A Formal Model Connecting Undecidability to Autonomous Behavior in Complex Systems

  2025cites this paper
• A Framework for Objective-Driven Dynamical Stochastic Fields

  2025cites this paper
• Atomic Gliders and CA as Language Generators (Extended Version)

  2025cites this paper
• ECA110-Pooling: A Comparative Analysis of Pooling Strategies in Convolutional Neural Networks

  2025cites this paper
• Neural cellular automata: applications to biology and beyond classical AI

  2025cites this paper
• MaCE: General Mass Conserving Dynamics for Cellular Automata

  2025cites this paper
• Design and Implementation of a Virtual Reality Environment for the Frazetta Art Museum

  2025cites this paper
• Flying Register in a Three-State Face-Centered Cubic Cellular Automaton

  2025cites this paper
• Why cellular computations challenge our design principles.

  2025cites this paper
• Universality Frontier for Asynchronous Cellular Automata

  2025cites this paper
• Regional controllability of cellular automata as a SAT problem

  2025cites this paper
• Neural Field Turing Machine: A Differentiable Spatial Computer

  2025cites this paper
• Undecidability of Tiling with a Tromino

  2025cites this paper
• Translating Measures onto Mechanisms: The Cognitive Relevance of Higher-Order Information

  2025cites this paper
• Testing the Machine Consciousness Hypothesis

  2025cites this paper
• Controllable gliders in a nanomagnetic metamaterial

  2025cites this paper
• Building the connectome of a small brain with a simple stochastic developmental generative model

  2025cites this paper
• The Multi‐n‐Dimensional Cellular Automaton: A Unified Framework for Tensorial, Discrete, and Continuous Simulations—A Computational Definition of Time

  2025cites this paper
• On when is Reservoir Computing with Cellular Automata Beneficial?

  2024cites this paper
• A sensitivity analysis of cellular automata and heterogeneous topology networks: partially-local cellular automata and homogeneous homogeneous random boolean networks

  2024cites this paper
• Building a small brain with a simple stochastic generative model

  2024cites this paper
• The Role of the Substrate in CA-based Evolutionary Algorithms

  2024cites this paper
• The Need for a Big World Simulator: A Scientific Challenge for Continual Learning

  2024influential citation
• L-System on a Toroidal Topology: Crafting Refined Closed-Loop Mazes

  2024cites this paper
• Counting and hardness-of-finding fixed points in cellular automata on random graphs

  2024cites this paper
• A Silicon Photonic Universal Cellular Automaton

  2024cites this paper
• Quantum logic automata generalizing the edge of chaos in complex systems

  2024cites this paper
• Agent Motion Planning as Block Asynchronous Cellular Automata: Pushing, Pulling, Suplexing, and More

  2024cites this paper
• On principles of emergent organization

  2024cites this paper
• Emergent Information Processing: Observations, Experiments, and Future Directions

  2024cites this paper
• An Alternative Representation of Turing Machines by Means of the Iota-Delta Function

  2024influential citation
• Bipartite mutual information in classical many-body dynamics

  2024cites this paper
• Back Analysis of a Real Debris Flow, the Morino-Rendinara Test Case (Italy), Using RAMMS Software

  2024cites this paper
• The Mathematics of Cellular Automata

  2024cites this paper
• Reviews

  2024cites this paper
• Computational Complexities of Folding

  2024cites this paper
• Undecidability in physics: A review

  2024cites this paper
• Operator Entanglement Growth Quantifies Complexity of Cellular Automata

  2024cites this paper
• Evolutionary Implications of Self-Assembling Cybernetic Materials with Collective Problem-Solving Intelligence at Multiple Scales

  2024cites this paper
• An origami Universal Turing Machine design

  2024cites this paper
• A comprehensive taxonomy of cellular automata

  2024cites this paper
• Integrability of Goldilocks quantum cellular automata

  2024cites this paper
• Intelligence at the Edge of Chaos

  2024cites this paper
• Weird Machines in Package Managers: A Case Study of Input Language Complexity and Emergent Execution in Software Systems

  2024cites this paper
• Discretization-Dependent Dissolution of (Dis)Continuous Gliders: Non-Platonic Self-Organization in Complex Systems

  2024cites this paper
• Experiencing Hypothetical Datalog in SQL Puzzles

  2024cites this paper
• Probabilistic Finite Automaton Emptiness is undecidable

  2024influential citation
• Dissociating Artificial Intelligence from Artificial Consciousness

  2024cites this paper
• Autoregressive Large Language Models are Computationally Universal

  2024cites this paper
• A Virtual Reality Game Utilizing L-Systems for Dynamic Level Generation

  2024cites this paper
• End-to-end Image Classification in Linear Hybrid Cellular Automata

  2024cites this paper
• Tensor-Networks-based Learning of Probabilistic Cellular Automata Dynamics

  2024cites this paper
• A new strategy to generate scale free networks by capturing the information processing mechanism in a specific family of elementary cellular automata

  2024cites this paper
• Biological arrow of time: emergence of tangled information hierarchies and self-modelling dynamics

  2024cites this paper
• JaxLife: An Open-Ended Agentic Simulator

  2024cites this paper
• Networks of Binary Necklaces Induced by Elementary Cellular Automata Rules

  2024cites this paper
• CAX: Cellular Automata Accelerated in JAX

  2024cites this paper
• Convolutional unitary or orthogonal recurrent neural networks

  2023cites this paper
• The Design, Education and Evolution of a Robotic Baby

  2023cites this paper
• Social Simulation Models as Refuting Machines

  2023cites this paper
• Creative and Adversarial Cellular Automata for Simulating Resilience in Industry 5.0

  2023cites this paper
• Fusions of Consciousness

  2023cites this paper
• Investigating Rules and Parameters of Reservoir Computing with Elementary Cellular Automata, with a Criticism of Rule 90 and the Five-Bit Memory Benchmark

  2023cites this paper
• Memory Augmented Large Language Models are Computationally Universal

  2023cites this paper
• Deep learning with photonic neural cellular automata

  2023cites this paper
• Flat origami is Turing Complete

  2023influential citation
• Dartmouth Digital Commons Dartmouth Digital Commons

  2023cites this paper
• Mean-Field Analysis with Random Perturbations to Detect Gliders in Cellular Automata

  2023cites this paper
• Does a computer think if no one is around to see it?

  2023cites this paper
• Influence theory

  2023cites this paper
• Freezing 1-Tag Systems with States

  2023cites this paper
• Exploring Complex Toroidal Mazes with L-systems

  2023cites this paper
• Free Choice in Quantum Theory: A p-adic View

  2023cites this paper
• Causal Capabilities of Teleology and Teleonomy in Life and Evolution

  2023cites this paper
• On the Computational Power of Particle Methods

  2023cites this paper
• A study on the composition of elementary cellular automata

  2023cites this paper
• On countings and enumerations of block-parallel automata networks

  2023cites this paper
• MemCA: All-Memristor Design for Deterministic and Probabilistic Cellular Automata Hardware Realization

  2023cites this paper
• Simulation Limitations of Affine Cellular Automata

  2023cites this paper
• Characterisation of the elementary cellular automata with neighbourhood priority based deterministic updates

  2022cites this paper
• The Weak Universality of Two-Dimensional Five-State von Neumann Neighborhood Number-Conserving Cellular Automaton

  2022cites this paper
• Multiband linear cellular automata and endomorphisms of algebraic vector groups

  2022cites this paper
• A universal DNA computing model for solving NP-hard subset problems

  2022cites this paper
• Attention-based Neural Cellular Automata

  2022cites this paper
• The neuroconnectionist research programme

  2022cites this paper
• Agent-based modeling for a complex world

  2022influential citation