# Questions tagged [cellular-automata]

For questions on cellular automata, a discrete model consisting of a regular grid of cells.

142 questions
Filter by
Sorted by
Tagged with
1 vote
32 views

### Properties of limit set for cellular automata

Is anyone familiar with results about properties of the limit set of the local rule for a cellular automaton? I haven't been able to find any good materials on the subject from an initial search, and ...
• 7,728
14 views

### How does adding only one xor operation sufficient to turn a non-reversible 1-dimensional cellular automaton into a reversible one?

Within Wolfram's 1D 2-state cellular automata rules, there are three bits (which we'll call bit_n-1, bit_n, bit_n+1) at t-1 that determine the state of bit_n at t-0. This means there are 2^3 = 8 ways ...
65 views

### Interesting Applications of Operads to Cellular Automata

I came across this Math Overflow question pertaining to the usage of sheaves in understanding CA. Piquing my curiosity, I did some quick searches and discovered that this particular application of ...
• 123
52 views

### Rule 30 Variation, revisited: Where does the constant come from?

Background In a previous question, user Trevor asked whether the ratio of "chaotic" to preceding "non chaotic" cells in a particular cellular automaton tended to the golden ratio. ...
• 538
49 views

### Modified version of Conway's Game of Life, ratio of alive cells becomes $\pi$?

I saw someone comment on a YouTube video with a weird result they had gotten, and then replicated that result myself. It is the following: Consider the following modification on Conway's Game of Life: ...
• 249
27 views

• 31
1 vote
22 views

### Maximum generations possible for any initial configuration on a Conway GOL Torus

Game of Life (GOL) is well known. I will not try to describe it myself. More details here: https://conwaylife.com/wiki/Conway%27s_Game_of_Life A Conway GOL Torus is a variation of GOL where the board ...
• 111
1 vote
114 views

### Is there a formal, rigorous definition of cellular automata?

I have recently been interested in cellular automata. However, I have never seen a formal definition of them. Is there one, and if so, what is the definition?
• 20.7k
133 views

### Relation between symbolic substitution and cellular automata

I think I have read somewhere that there is a connection between symbolic substitutions and cellular automata. I have some basic familiarity on the matter of symbolic substitutions, but I was ...
• 7,728
245 views

### Numerical regularities in the classification of cellular automata

This is a question about elementary cellular automata (ECA) and their classification into uniform (class I), periodic (class II), chaotic (class III), complex (class IV) due to Wolfram. Maybe I missed ...
• 18.2k
1 vote
64 views

### A natural coding scheme of ECA rules reveals some regularities but leaves questions open

This is a question about a coding scheme of numbers that might yield insights in cellular automata and the rules that govern them. Background Since Wolfram the rules defining elementary cellular ...
• 18.2k
453 views

### Golden Ratio appears in this Rule 30 variation?

The cellular automaton Rule 30 is most commonly explored starting with a single 1 cell against a background of infinitely many 0 ...
• 6,022
203 views

### Is there a simple maximally general generalization of Noether's theorem to arbitrary dynamical systems?

Noether's theorem informally states something like "symmetries in the dynamical law imply conserved quantities". However, the theorem is generally stated in terms of physics-specific classes ...
• 13k
61 views

### HexLife: Turing complete?

Has anything "interesting" been discovered if one generalizes Conway's Life on a rectangular grid to a hexagonal grid? There have been several explorations of Life on a hexagonal grid. In ...
• 30.3k
114 views

### Game of Life - Death by overpopulation example where only one cell changes in the next generation?

I'm new to Cellular Automata. I'm looking for examples of Game of Life board states in which only one cell changes in the next generation (to show the effect of the rule that was applied). I'm looking ...
• 131
188 views

### What is the expected length of the "Slimy Slug" cellular automata

A "Slimy Slug" is a simple probabilistic cellular automata defined as follows: The Slimy Slug lives on an infinite, two-dimensional, white-coloured, square grid. For each iteration, the slug ...
• 201
177 views

### How can I enumerate D6-symmetric cellular automaton rules?

I'm experimenting with rules for a cellular automaton in a hexagonal grid. I am wondering how to enforce symmetry. For example a cell can be either "alive" or "dead". Let's say a ...
• 123
43 views

### Question on automorphisms of shift dynamical systems and their inverses

Let $A$ be a finite set and let $\sigma:A^\mathbb{Z}\to A^\mathbb{Z}$ be the shift homeomorphism. Let $T:A^\mathbb{Z}\to A^\mathbb{Z}$ be a bijective homeomorphism that commutes with $\sigma$ (i.e. ...
• 636
67 views

### Simplest discrete interactable universe

Consider the set of all mathematically possible universes. Take only the deterministic ones, that run forward in a single dimension of time, the state at a given instant being uniquely determined by ...
• 245
174 views

### barriers/membranes in Conway's Game of Life

Has anyone working on Conway's Game of Life found a way to create barriers which divide zones, ideally between a potentially chaotic "outside" and a structured inside, which could then ...
• 175
235 views

### On the growth rate of Conway's game of life.

I'm reading a book in which Conway's game of life is mentioned: the author states that it can be proved that the growth rate cannot be exponential but it's at most quadratic. Can someone suggest me ...
• 5,749
1 vote
144 views

### how universal is Conway's game of life? is it reasonable to expect that a technological alien civilization would recognize, say, a glider?

This is a philosophical one, so apologies if it's not appropriate. I can think of several reasons that Conway's Game of Life would be rediscovered by any mathematically inclined biological life forms. ...
• 143
736 views

### What is the maximum "alive density" of cells in Conway's Game of Life when played on a torus?

I've read that Conway's Game of Life (CGOL) can have unbounded growth from a finite initial number of alive cells (e.g. a glider gun). However, if CGOL is played on a torus, space (the number of cells)...
11k views

### Is black hole pattern possible in Conway's Game of Life that eats/clears everything?

Is black hole pattern possible in Conway's Game of Life that eats/clears the infinite universe plane ? Formally, is there a pattern that satifies following requirements? The pattern has finite size. ...
• 1,735
1 vote
63 views

### Periodic columns in asymmetrical 1D cellular automata?

Does anyone know of or is able to track down a 2-color, 1-D cellular automaton admitting an aperiodic initial configuration and a ruleset that is asymmetrical, and which has at least one (but not ...
• 6,022
212 views

### how many unique patterns can be made on a 4x4 grid accounting for rotational symmetry?

I was working with higher range Margolus cellular automata neighborhoods and i ran into a problem, how many patterns you can make in a 4x4 square grid if you consider rotationally symmetric patterns ...
• 123
325 views

### Is Rule 30 Turing complete?

Rule 30 is a well-known ECA. Wikipedia has a fine introduction to that topic if you're unfamiliar. Here's a 60-second version of the mechanism: Let $s_0 \leftarrow 1$. Let $s_{i+1} \leftarrow s_{i}00$...
• 6,022
628 views

### Infection spread on a torus chessboard

In one of his books, Peter Winkler includes the following problem: A disease is spreading on a $n\times n$ chessboard as follows: if a healthy cell is neighboring at least 2 infected cells, it becomes ...
• 383
225 views

### Dimension of the Cantor set in the context of cellular automata

I'm reading the book "Cellular Automata and Complexity" by Wolfram. On page 426 he gives a very intuitive picture showing why any cellular automaton state $\{0,1\}^\infty$, can be uniquely ...
• 153
1 vote
51 views

### Can information transmission be proven in a Rule 30 ECA?

(This is hopefully a clearer version of an earlier post of mine.) I have been spending lots of time on the open challenge of proving the aperiodicity of the central column of a rule 30 cellular ...
• 6,022
1 vote
253 views

### Are there impossible patterns in Conway's game of life?

Given a grid representing a state in Conway's game of life, if there is no pattern that leads to this state, this means that there exists a forbidden $N\times N$ pattern for some $N$. If so what is ...
• 4,343
1 vote
145 views

### Cyclic cellular automaton with 3-neighborhood

Consider a 2D cyclic cellular automaton with randomized starting states and the usual von Neumann 4-neighborhood ruleset. It is well-known that this CA produces a stable and periodic state after a ...
32 views

• 85
138 views

### Elementary cellular automaton showing eventually periodic behavior after large number of iterations.

In this video: Cellular Automata and Rule 30 Stephen Wolfram talks about such an elementary cellular automaton at 17:01. Does anybody have an idea which one exactly he could be talking about?
• 932
1 vote
48 views

### What is a periodic pattern in 1D Cellular Automata

What is a periodic pattern in 1D cellular automata? I have this 3-color, code 1599 rule and I can see that a certain generation can be grouped together by their similar or foreseeable pattern, then ...
• 21
1 vote
This question relates to the OEIS sequence A279212. Fill an array by antidiagonals upwards; in the top left cell enter $a(0)=1$; thereafter, in the $n$-th cell, enter the sum of the entries of those ...