A one-dimensional physically universal cellular automaton

DOI10.1007/978-3-319-58741-7_35MaRDI QIDQ2011676zbMATHOpenAlexFDO

Authors Ville Salo, Ilkka A. Törmä

Publication date 4 August 2017

Full work available at URL https://arxiv.org/abs/1501.03988

zbMATH Keywords

reversibilitycellular automatonphysical universality

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Abstract: Physical universality of a cellular automaton was defined by Janzing in 2010 as the ability to implement an arbitrary transformation of spatial patterns. In 2014, Schaeffer gave a construction of a two-dimensional physically universal cellular automaton. We construct a one-dimensional version of the automaton.

Recommendations

• A physically universal cellular automaton
• A physically universal quantum cellular automaton
• A universal cellular automaton without sensitive subsystems
• Simple universal one-dimensional reversible cellular automata
• scientific article; zbMATH DE number 4195207

Cites work

• scientific article; zbMATH DE number 5117086 (Why is no real title available?)
• scientific article; zbMATH DE number 3692653 (Why is no real title available?)
• scientific article; zbMATH DE number 1962850 (Why is no real title available?)
• A physically universal cellular automaton
• A physically universal quantum cellular automaton
• P-completeness of Cellular Automaton Rule 110
• Universal pattern generation by cellular automata
• Universality in elementary cellular automata

Cited in

(15)

• Glider automorphisms and a finitary Ryan's theorem for transitive subshifts of finite type
• scientific article; zbMATH DE number 6255722 (Why is no real title available?)
• Glider automata on all transitive sofic shifts
• Constructibility of speed one signal on cellular automata
• Does universal controllability of physical systems prohibit thermodynamic cycles?
• scientific article; zbMATH DE number 5152031 (Why is no real title available?)
• Universal pattern generation by cellular automata
• scientific article; zbMATH DE number 7564193 (Why is no real title available?)
• scientific article; zbMATH DE number 7724182 (Why is no real title available?)
• Glider automorphisms on some shifts of finite type and a finitary Ryan's theorem
• On the absence of homogeneous scalar unitary cellular automata.
• A physically universal quantum cellular automaton
• A universal cellular automaton without sensitive subsystems
• A physically universal cellular automaton
• A physically universal Turing machine

This page was built for publication: A one-dimensional physically universal cellular automaton

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