Towards the frontier between decidability and undecidability for hyperbolic cellular automata

DOI10.1007/978-3-642-15349-5_8zbMATH Open1287.68116OpenAlexW2131504525MaRDI QIDQ3584965FDOQ3584965

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

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

zbMATH Keywords

cellular automatadecidabilitytilingshyperbolic spacesweak universality

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Cited In (8)

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)