# The σ-game and cellular automata

@article{Sutner1990TheA, title={The $\sigma$-game and cellular automata}, author={Klaus Sutner}, journal={American Mathematical Monthly}, year={1990}, volume={97}, pages={24-34} }

1. SummaryIn an article in this journal Don Pelletier discussed the mathematics involved in a little battery operated toy called Merlin (see [3], and also the “Addenda” in this Monthly, Dec. 1987, page 994). Several years ago Stephen Wolfram, in another article that appeared in the Monthly, analyzed a number of simple cellular automata and the fractal patterns generated by some of these automata (see [6]). In this article we point out the close connection between MERLIN-type games and a class… Expand

#### 55 Citations

On a modular domination game

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

The number of equivalence classes that a given graph has, and the formulas for trees and special regular graphs are given, are investigated. Expand

sigma-Game, sigma+-Game, and Two-Dimensional Additive Cellular Automata

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

A simple algorithm for finding the number of solutions for the σ + -game is given and a necessary and sufficient condition for the existence of a unique solution is given, thus partially answering a question posed by Sutner. Expand

Two-Player Games on Cellular Automata

- Mathematics
- 2000

Cellular automata games have traditionally been solitaire games. We define a two-player cellular automata game played on a finite cyclic digraph G = (V,E). Each vertex assumes a weight w I {0,1}. A… Expand

Matrix algebraic formulae concerning some exceptional rules of two-dimensional cellular automata

- Computer Science
- Inf. Sci.
- 2004

An attempt has been made to characterise a number of exceptional transformations or rules, each of which behaving uniquely, not matching with any other rules, of two dimensional cellular automata with null and periodic boundary conditions. Expand

VLSI architecture of a cellular automata machine

- Mathematics
- 1997

Abstract In the past, Cellular Automata based models and machines [1] have been proposed for simulation of physical systems without any analytical insight into the behaviour of the underlying… Expand

Multidimenstional Sigma-Automata, Pi-Polynomials and Generalised S-Matrices

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

The notion of nearest neighbourhood to many dimensions and characterise invertibility of σ-automata with such neighbourhoods is generalised and related to the number theoretic properties of the number of dimensions and the lengths of the dimensions. Expand

Periodic binary harmonic functions on lattices

- Mathematics, Computer Science
- Adv. Appl. Math.
- 2008

This paper considers binary pluri-periodic harmonic functions f:Z^s->F"2=GF(2) on integer lattices, and addresses the problem of describing the set of possible multi-periods n@?=(n"1,...,n"s)@?N^s of such functions. 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

Virus Versus Mankind

- Mathematics, Computer Science
- Computers and Games
- 2000

The 3-fold motivation for exploring these games stems from complexity considerations in combinatorial game theory, extending the hitherto 0-player and solitaire cellular automata games to two-player games, and the theory of linear error correcting codes. Expand

Solutions to All-Colors Problem on Graph Cellular Automata

- Computer Science
- Complex.
- 2019

A new kind of All- Colors Problem is introduced, - Random Weak-All-Colors Problem, which is relevant to both combinatorial number theory and cellular automata theory. Expand

#### References

SHOWING 1-6 OF 6 REFERENCES

Statistical mechanics of cellular automata

- Physics
- 1983

Cellular automata are used as simple mathematical models to investigate self-organization in statistical mechanics. A detailed analysis is given of ''elementary'' cellular automata consisting of a… 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

Computer Software in Science and Mathematics.

- Computer Science
- 1984

The study of many complex systems, which have re sisted analysis by traditional mathemat ical methods, is consequently being made possible through computer exper iments and computer models, supplementing the long-standing methodologies of theory and experiment. Expand