# Classifying circular cellular automata

@article{Sutner1991ClassifyingCC, title={Classifying circular cellular automata}, author={Klaus Sutner}, journal={Physica D: Nonlinear Phenomena}, year={1991}, volume={45}, pages={386-395} }

We introduce a hierarchy of linear cellular automata based on their limiting behavior on spatially periodic configurations. We show that it is undecidable to which class in the hierarchy a cellular automaton belongs. In particular, it is undecidable whether all spatially periodic configurations evolve to a fixed point. Furthermore, there is no computable bound on the period lengths of these configurations. Our arguments are based on a non-standard simulation of Turing machines on circular… Expand

#### 188 Citations

Almost Periodic Configurations on Linear Cellular Automata

- Mathematics, Computer Science
- Fundam. Informaticae
- 2003

It is shown that the degree structure of the orbits of cellular automata is the same on these configurations as on the space of finite configurations and that it is undecidable whether the cellular automaton exhibits complicated behavior on configurations of sufficiently long spatial periods. Expand

Linear Cellular Automata and Fischer Automata

- Computer Science
- Parallel Comput.
- 1997

A class of binary linear cellular automata whose corresponding minimal automata exhibit full exponential blow-up and corresponding minimal Fischer automata as well as the minimal DFAs have maximal complexity are constructed. Expand

Turing Degrees of Limit Sets of Cellular Automata

- Computer Science, Mathematics
- ICALP
- 2014

This article gives a full characterization of the sets of Turing degrees of limit sets of cellular automata: they are the same as the set of Turing Degrees of effectively closed sets containing a computable point. Expand

Universality and Cellular Automata

- Computer Science
- MCU
- 2004

A classification for cellular automata that is based on computably enumerable degrees is discussed, in this setting the full structure of the semilattice of the c.e. degrees is inherited by the Cellular automata. Expand

Reversible Cellular Automata

- Computer Science
- Developments in Language Theory
- 2005

This paper is a short survey of research on reversible cellular automata over the past fourty plus years and discusses the classic results by Hedlund, Moore and Myhill that relate injectivity, surjectivity and reversibility with each other. Expand

Predecessors of cellular automata states, III.: Garden of Eden classification of cellular automata

- Mathematics
- 1994

Abstract A procedure is given which determines all finite sequences without pre-images for any one dimensional cellular automata with entries in Z 2 . On this basis we determine some properties of… Expand

On the Computational Complexity of Finite Cellular Automata

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1995

The problem of deciding whether a configuration has a predecessor is shown to be NLOG-complete for one-dimensional cellular automata, and the question whether a target configuration occurs in the orbit of a source configuration may be P- complete, NP-complete or PSPACE-complete, depending on the type of cellular automaton. Expand

The complexity of reversible cellular automata

- Mathematics, Computer Science
- Theor. Comput. Sci.
- 2004

It is shown that the Turing degree structure of the orbits of these automata is the same as for general cellular automata, especially those whose orbits have arbitrary recursively enumerable degree. Expand

Some results on invertible cellular automata

- Mathematics, Computer Science
- Proceedings Workshop on Physics and Computation. PhysComp '94
- 1994

This work explicitly construct a cellular automaton in a class (a residual class) previously known not to be empty only via a nonconstructive existence proof, and shows a class that contains invertible cellular automata having bounded neighborhood, but whose inverses constitute a class of Cellular automata for which there isn't any recursive function bounding all the neighborhood. Expand

A brief history of cellular automata

- Computer Science
- CSUR
- 2000

A history of cellular automata from their beginnings with von Neumann to the present day is traced, mainly on topics closer to computer science and mathematics rather than physics, biology or other applications. Expand

#### References

SHOWING 1-10 OF 22 REFERENCES

Universality and complexity in cellular automata

- Computer Science, Mathematics
- 1983

Evidence is presented that all one-dimensional cellular automata fall into four distinct universality classes, and one class is probably capable of universal computation, so that properties of its infinite time behaviour are undecidable. Expand

Algebraic properties of cellular automata

- Mathematics
- 1984

Cellular automata are discrete dynamical systems, of simple construction but complex and varied behaviour. Algebraic techniques are used to give an extensive analysis of the global properties of a… Expand

Computation theory of cellular automata

- Mathematics
- 1984

Self-organizing behaviour in cellular automata is discussed as a computational process. Formal language theory is used to extend dynamical systems theory descriptions of cellular automata. The sets… Expand

The Constructibility of a Configuration in a Cellular automaton

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 1973

A configuration is said to be with finite support if the states of all but fintely many cells in the array are quiescent and it is recursively unsolvable when d>=2, for a configuration c with finiteSupport in a d-dimensional cellular automaton. Expand

Cellular Automata Machines

- Computer Science
- Complex Syst.
- 1987

A cellular automata machine is a computer optimized for the simulation of cellular Automata that allows it to run thousands of times faster than a general-purpose computer of comparable cost programmed to do the same task. Expand

Theory of Recursive Functions and Effective Computability

- Mathematics
- 1969

Central concerns of the book are related theories of recursively enumerable sets, of degree of un-solvability and turing degrees in particular. A second group of topics has to do with generalizations… Expand

Tessellations with Local Transformations

- Mathematics, Computer Science
- J. Comput. Syst. Sci.
- 1972

The Garden of Eden theorem plus compactness of the product topology is used to obtain the following: It a local transformation is a one-to-one function, it must also be onto and have a local inverse. Expand

Undecidability and nonperiodicity for tilings of the plane

- Mathematics
- 1971

This paper is related to the work of Hao Wang and others growing out of a problem which he proposed in [8], w 4.1. Suppose that we are given a finite set of unit squares with colored edges, placed… Expand

Undecidability of CA Classification Schemes

- Computer Science, Mathematics
- Complex Syst.
- 1988

It is shown that it is undecidable to which class a given cellula r automaton belongs, even when choosing only between the two simp lest classes. Expand

The converse of Moore’s Garden-of-Eden theorem

- Mathematics
- 1963

We presuppose the terminology of Moore [1]. In this paper, Moore proves that the existence of two mutually erasable configurations in a tessellation universe is a sufficient condition for the… Expand