# Questions tagged [cellular-automata]

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

123 questions
Filter by
Sorted by
Tagged with
32 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 ...
• 29.3k
58 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 ...
• 133
160 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
138 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
36 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. ...
• 527
1 vote
46 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 ...
• 217
58 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 ...
• 157
150 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,656
1 vote
85 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
22 views

### Inversible turing complete cellular automata are easily inversible so why we can't inverse any inversible programme with them?

From what i've read: inverse of inversible cellular automata is also cellular automata (i wanted to prove that but sadly i'm 40 years late), so easily inversible; and inversible turing complet ...
369 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)...
10k 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,677
1 vote
45 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 ...
• 4,941
87 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
1 vote
164 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$...
• 4,941
465 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
128 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 ...
• 143
1 vote
43 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 ...
• 4,941
633 views

### how can I prove that if I have a regular language L, that L' is a regular language

how can I prove that if I have a regular language L and I create a new language L' where L' = (L but with last letter repeated) (i.e. if ab is in language L then abb is in language L') that L' is a ...
1 vote
135 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 ...
• 3,981
1 vote
75 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 ...
30 views

• 85
74 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?
• 912
1 vote
39 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
188 views

### Is there any 3D patterns, if we are to stack up each generation of "Conway's game of life" on top of each other?

1D Cellular Automata do not show any interesting patterns if we look at each state only one at a time in Succession, but if we put each state below each other, we can see patterns emerging. In the ...
1k views

### Fractal Pattern from Queen's Move Construction

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 ...
• 111
94 views

### Name of these Sierpinski-like fractals?

A Sierpinski triangle can be created by Starting with a row consisting of a single 1 Each row below is horizontally offset by a half-cell Each cell is the sum-mod-2 of the two cells above it Now ...
• 725
1 vote
66 views

### How does On/Off Reversal work in Life-Like Cellular Automata

I've recently been made aware of the concept of on-off rule reversal in life-like cellular automata. I understand the algorithm for calculating the rule reversal from a given rule. But I don't ...
• 75
95 views

### Are there any symmetries in rules of Life-Like Cellular Automata?

Life-like cellular automata have $2^{18}$ different possible rulesets, and I would like to test hypotheses/search through them all, however that's a lot of rulesets to test a simulation on, so I'm ...
• 75
69 views

### Prove that a recurrence for Rule 30 is: B2=MOD(A1+B1+(1+B1)*C1,2)

Prove that Rule 30 satisfies the recurrence: $$T(1, k) = [k = N]$$ $$T(n,k)=(T(n-1,k-1)+T(n-1,k)+(T(n-1,k)+1) T(n-1,+1+k)) \bmod 2$$ where [ ] is the Iverson bracket. ...
• 6,772
1 vote
98 views

### Finding Life-Like Cellular Automata Rules and Initial States with Guaranteed Still End States

My goal is to find all rulesets of life-like cellular automata and initial states that, when simulated in a toroidal grid (although non-toroidal would be interesting as well) of arbitrary finite ...
• 75
32 views

### Trouble understanding proof in "Aperiodicity in One-Dimensional Cellular Automata" paper by Erica Jen

From the proof of page 7 in https://digital.library.unt.edu/ark:/67531/metadc1443182/m2/1/high_res_d/7230855.pdf (page 10 of the PDF): The fact that $R$ is injective in its $(i+1)$-th component (...
• 53
116 views

### Noether's theorem in SmoothLife?

Conway's Game of Life, being discretized in both space and time domains, has no locally conserved quantities. SmoothLife, however, is a generalization of the Game of Life to a continuous and spatially-...
1 vote
70 views

### Simplest set of replacement rules which can include mathematical logic?

Things like the various Type Theories appear to be based on replacement rules of one kind or another. This got me thinking, what would be the simplest set of replacement rules (maybe even just one ...
• 3,981
135 views

### Are Cellular Automata models compatible with the Holographic Principle?

Cellular Automata are discrete models which have a regular finite dimensional grid of cells, each in one of a finite number of states, such as on and off. There are various scientists that have ...
• 131
349 views

### Cell state probabilities for a probabilistic version of Conway's Game of Life

I am given a version of Conway's Game of Life where each cell can be in any of 3 states: Dead (D), Alive (A) or Dying (X). The following transition rules exist: An Alive cell next to a Dying cell ...
• 167
66 views

I'm not sure anyone else than Tegmark himself can answer this, but why not give it a try. Would Tegmark consider a cellular automata a mathematical structure? If nature is mathematical, isn't it also ...
1k views

### Is Langton's Ant really Turing Complete

I recently watched a Numberphile video about Langton's Ant (and the extra footage). They mention that the ant always ends up creating a highway at some point in all the initial board configurations ...
• 123
107 views

### Infinitesimal Cellular Automaton

I thought about how a continuous (in time and space, but not in states) cellular automaton could look like. The most straightforward generalization which came to my mind is the following: Let $(X,*)$...
• 2,740
192 views

### Open problems in Cellular Automata field

here there is a link on Wolfram about 20 open problems of CA theory. Has anyone of them been solved or tested? I'm searching for literature.
• 470
198 views

### What reversible cellular automaton rule emulates all 256 Wolfram rules?

On page 648 of A New Kind of Science, there's a definition of a "universal" cellular automaton, which can emulate Wolfram's 256 elementary cellular automata. Furthermore, it emulates them in a "cell-...
• 357
235 views

### Reflector in Conway's Game of Life on Triangular Tessellations

Back in 1994, Carter Bays reports in "Cellular Automata in the Triangular Tessellation" that there are at least 6 Games of Life (GoL) living on triangular tessellations. A GoL has at least one glider (...
• 17.8k
228 views

### Project ideas on Chaos theory, Cellular Automata, Fractals, Games, IA [closed]

I'm a computer science student and I need to find a final year project. What interests me the most is Chaos, IA, Games, Fractals, CA.. Something I liked was the chaos theory within sudoku. The ...
• 568
Consider a $A \in Mat_{n}(\{+1,-1\})$ (square matrix consisted of +1,-1). Now we can make and operation majority , i.e. $a_{i,j} =$ median of his neighborhoods(closest elements around him, i.e. ...