# A strongly universal cellular automaton with four states

@article{Margenstern2021ASU, title={A strongly universal cellular automaton with four states}, author={M. Margenstern}, journal={ArXiv}, year={2021}, volume={abs/2107.04843} }

In this paper, we prove that there is a strongly universal cellular automaton in the dodecagrid, the tessellation {5, 3, 4} of the hyperbolic 3D space, with four states but, it is not rotation invariant as the automaton of [9] is with five states. The present paper is not an improvement of [9]. The reduction to four states of the automaton of the present paper results from a relaxation of the condition of rotation invariance. However, the relaxation is not complete: the rules are invariant with… Expand

#### Figures and Tables from this paper

#### One Citation

An outer totalistic weakly universal cellular automaton in the dodecagrid with four states

- Computer Science
- ArXiv
- 2021

It is proved that there is an outer totalistic weakly universal cellular automaton in the dodecagrid, the tessellation of the hyperbolic 3D space, with four states, the first result in such a context. Expand

#### References

SHOWING 1-10 OF 12 REFERENCES

A Weakly Universal Cellular Automaton in the Heptagrid of the Hyperbolic Plane

- Computer Science, Mathematics
- Complex Syst.
- 2018

A weakly universal cellular automaton in the heptagrid is constructed which is not rotation invariant but which is truly planar, and under these conditions, cannot be improved for the tessellations. Expand

A strongly universal cellular automaton on the heptagrid with seven states

- Computer Science
- J. Cell. Autom.
- 2021

In this paper, we prove that there is a strongly universal cellular automaton on the heptagrid with seven states which is rotation invariant. This improves a previous paper of the author where the… Expand

A New Universal Cellular Automaton on the Pentagrid

- Computer Science, Mathematics
- Parallel Process. Lett.
- 2008

This paper significantly improves a result of the first author, and lowers the number of states for a weakly universal cellular automaton down to 9. Expand

An Upper Bound on the Number of States for a Strongly Universal Hyperbolic Cellular Automaton on the Pentagrid

- Computer Science, Mathematics
- JAC
- 2010

It is proved that there is a hyperbolic cellular automaton which is rotation invariant and whose halting problem is undecidable and which has 9~states. Expand

A Weakly Universal Cellular Automaton in the Pentagrid with Five States

- Physics, Computer Science
- Computing with New Resources
- 2014

A cellular automaton on the pentagrid which is planar, weakly universal and which have five states only is constructed, which much improves the best result which was with nine states. Expand

A universal cellular automaton in the hyperbolic plane

- Computer Science
- Theor. Comput. Sci.
- 2003

The paper gives the construction of a universal CA with 22 states in the regular rectangular pentagonal grid of the hyperbolic plane. The CA implements a railway circuit which simulates a register… Expand

Computation Finite And Infinite Machines

- Computer Science
- 2016

There are very few individuals today who doubt that the computer and its relatives are developing rapidly in capability and complexity, and that these machines are destined to play important (though not as yet fully understood) roles in society's future. Expand

A strongly universal cellular automaton on the dodecagrid with five states, arXiv:2104.01561

- 2021

A weakly universal cellular automaton in the heptagrid with three states, arXiv:1410.1864v1

- 2014

Cellular Automata in Hyperbolic Spaces, vol. 2, Implementations and Computations, Collection: Advances in Unconventional Computing and Cellular Automata, Editor: Andrew Adamatzky, Old City Publishing

- 2008