Towards the frontier between decidability and undecidability for hyperbolic cellular automata

DOI10.1007/978-3-642-15349-5_8MaRDI QIDQ3584965zbMATH OpenOpenAlexFDO

Authors M. Margenstern

Publication date 31 August 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15349-5_8

zbMATH Keywords

cellular automatadecidabilitytilingshyperbolic spacesweak universality

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Recommendations

• ON A CHARACTERIZATION OF CELLULAR AUTOMATA IN TILINGS OF THE HYPERBOLIC PLANE
• Cellular automata and hyperbolic spaces
• scientific article; zbMATH DE number 2111977
• scientific article; zbMATH DE number 2040939
• Linear cellular automata and decidability

Cited in

(8)

• scientific article; zbMATH DE number 2111977 (Why is no real title available?)
• scientific article; zbMATH DE number 2040939 (Why is no real title available?)
• Decidability of sensitivity and equicontinuity for linear higher-order cellular automata
• NP problems are tractable in the space of cellular automata in the hyperbolic plane
• The Injectivity of the Global Function of a Cellular Automaton in the Hyperbolic Plane is Undecidable
• A decidability result for the halting of cellular automata on the pentagrid
• Universality and the halting problem for cellular automata in hyperbolic spaces: the side of the halting problem
• On the dynamical behaviour of linear higher-order cellular automata and its decidability

This page was built for publication: Towards the frontier between decidability and undecidability for hyperbolic cellular automata

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