Universality of causal graph dynamics

Causal Graph Dynamics generalize Cellular Automata, extending them to bounded degree, time varying graphs. The dynamics rewrite the graph at each time step with respect to two physics-like symmetries: causality (bounded speed of information) and homogeneity (the rewriting acts the same everywhere on the graph, at every time step). Universality is the ability simulating every other instances of another (or the same) model of computation. In this work, we study three different notions of simulation for Causal Graph Dynamics, each of them leading to a definition of universality.

• Publication year

  2016

• Venue

  arXiv.org

• Publication date

  2016-02-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1602.01352
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An Intrinsically Universal Family of Causal Graph Dynamics

  2015cited by this paper
• On Goles' universal machines: A computational point of view

  2013cited by this paper
• Intrinsic Universality of Causal Graph Dynamics

  2013cited by this paper
• Intrinsic Simulations between Stochastic Cellular Automata

  2012cited by this paper
• Computing Issues of Asynchronous CA

  2012cited by this paper
• Generalized Cayley Graphs and Cellular Automata over them

  2012cited by this paper
• Structural Complexity II

  2012cited by this paper
• Partitioned quantum cellular automata are intrinsically universal

  2010cited by this paper
• Intrinsically Universal Cellular Automata

  2009cited by this paper
• One-Dimensional Quantum Cellular Automata over Finite, Unbounded Configurations

  2007cited by this paper
• Intrinsically Universal One-dimensional Quantum Cellular Automata in Two Flavours

  2007cited by this paper
• A single-copy minimal-time simulation of a torus of automata by a ring of automata

  2007cited by this paper
• Intrinsic Universality of a 1-Dimensional Reversible Cellular Automaton

  1997cited by this paper
• Cellular Automata Universality Revisited

  1997cited by this paper
• Structural Complexity I

  1995cited by this paper
• The firing squad synchronization problem on Cayley graphs

  1995cited by this paper
• A Recursive Introduction to the Theory of Computation

  1994cited by this paper
• Garden of Eden Configurations for Cellular Automata on Cayley Graphs of Groups

  1993cited by this paper
• From universal Turing machines to self-reproduction

  1988cited by this paper
• A Six-State Minimal Time Solution to the Firing Squad Synchronization Problem

  1987cited by this paper
• Brains, Machines, and Mathematics

  1987cited by this paper
• An Overview of the Firing Squad Synchronization Problem

  1986cited by this paper
• An introduction to the general theory of algorithms

  1978cited by this paper
• INTELLIGENT GRAPHS: NETWORKS OF FINITE AUTOMATA CAPABLE OF SOLVING GRAPH PROBLEMS

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

  1971cited by this paper
• Author's Personal Copy Information and Computation Causal Graph Dynamics

  year unknowncited by this paper

• No citing papers are available for this paper.