A decidability result for the halting of cellular automata on the pentagrid

DOI10.25088/COMPLEXSYSTEMS.28.2.175MaRDI QIDQ5126853zbMATH OpenOpenAlexFDO

Authors M. Margenstern

Publication date 20 October 2020

Published in Complex Systems (Search for Journal in Brave)

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

zbMATH Keywords

cellular automatadecidabilityhalting problemhyperbolic planetilings

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Cellular automata (computational aspects) (68Q80)

Abstract: In this paper, we investigate the halting problem for deterministic cellula automata in the pentagrid. We prove that the problem is decidable when the cellular automaton starts its computation from a finite configuration and when it has at most two states, one of them being a quiescent state.

Recommendations

• Linear cellular automata and decidability
• Towards the frontier between decidability and undecidability for hyperbolic cellular automata
• Universality and the halting problem for cellular automata in hyperbolic spaces: the side of the halting problem
• Decidability and undecidability in cellular automata
• Reversibility and surjectivity problems of cellular automata

Cited in

(1)

• Universality and the halting problem for cellular automata in hyperbolic spaces: the side of the halting problem

This page was built for publication: A decidability result for the halting of cellular automata on the pentagrid

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