Cellular automata are generic

MaRDI QIDQ5013888zbMATH OpenFDO

Authors Nachum Dershowitz, Evgenia Falkovich

Publication date 3 December 2021

Full work available at URL https://arxiv.org/abs/1504.03013, http://eptcs.web.cse.unsw.edu.au/paper.cgi?DCM2014.2

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Classical models of computation (Turing machines, etc.) (68Q04)

Recommendations

• scientific article; zbMATH DE number 4195207
• General algorithm for two-dimensional totalistic cellular automata
• Computations on one-dimensional cellular automata
• Cellular automata -- a computational point of view
• Efficient unidimensional universal cellular automaton

Cites work

• scientific article; zbMATH DE number 3728250 (Why is no real title available?)
• scientific article; zbMATH DE number 7340320 (Why is no real title available?)
• A Natural Axiomatization of Computability and Proof of Church's Thesis
• A formalization and proof of the extended Church-Turing thesis (extended abstract)
• Causal Graph Dynamics
• Choiceless polynomial time
• Evolving Algebras 1993: Lipari Guide
• Exact exploration and hanging algorithms
• Limiting recursion
• On Gurevich's theorem on sequential algorithms
• On polynomial time computation over unordered structures
• Sequential abstract-state machines capture sequential algorithms
• The Church-Turing Thesis over Arbitrary Domains
• The physical Church thesis as an explanation of the Galileo thesis
• Trial and error predicates and the solution to a problem of Mostowski

Cited in

(9)

• A simple three-dimensional real-time reliable cellular array
• A lattice model for cellular (systolic) algorithms
• Preface to the second special session CAAA 2011 on cellular automata algorithms \& architectures
• scientific article; zbMATH DE number 176335 (Why is no real title available?)
• Cellular automata and naive discrete lines. I
• Implantation of cellular automata
• Algorithms with active cells modeled by cellular automata with write-access (CA-w)
• General algorithm for two-dimensional totalistic cellular automata
• Simulation limitations of affine cellular automata

This page was built for publication: Cellular automata are generic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5013888)