Questions tagged [cellular-automata]

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

Filter by
Sorted by
Tagged with
3 votes
0 answers
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 ...
user avatar
3 votes
2 answers
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 ...
user avatar
  • 133
10 votes
0 answers
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
  • 123
2 votes
1 answer
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. ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 217
3 votes
0 answers
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 ...
user avatar
  • 157
5 votes
2 answers
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 ...
user avatar
  • 5,656
1 vote
1 answer
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. ...
user avatar
  • 143
0 votes
0 answers
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 ...
user avatar
11 votes
2 answers
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)...
user avatar
114 votes
7 answers
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. ...
user avatar
  • 1,677
1 vote
1 answer
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 ...
user avatar
  • 4,941
2 votes
1 answer
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 ...
user avatar
  • 123
1 vote
0 answers
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$...
user avatar
  • 4,941
16 votes
2 answers
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 ...
user avatar
  • 383
2 votes
1 answer
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 ...
user avatar
  • 143
1 vote
0 answers
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 ...
user avatar
  • 4,941
0 votes
2 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 3,981
1 vote
1 answer
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 ...
user avatar
0 votes
1 answer
30 views

Doubt about developing the summation $\sum_{n=2}^{\infty}(n-1) \cdot 3^{2n-2}(1-\varepsilon )^{2n}$.

In the book "Contours, Convex Sets and Cellular Automata" (Andrei Toom), I've found the following: [...] the probability that there is no percolation does not exceed $\sum_{n=2}^{\infty}(n-...
user avatar
1 vote
0 answers
110 views

Random processes on coloured graphs

Let a random process on a $k$-coloured graph be any set of rules that determine how nodes change their colour probabilistically from time step to time step, depending only on the colours of their ...
user avatar
0 votes
0 answers
37 views

Using the rule stated below, is there a way I can plant trees on a 2D plane such that there are no trees in the first k diagonals? [duplicate]

This question was part of the problem set for PROMYS Europe 2020, a maths (or math, just in case I made anyone unhappy) camp held at Oxford every year. It was the one which I couldn't do, and I am ...
user avatar
4 votes
3 answers
266 views

How to create a non-square 2D grid with spherical topology.

When programming Conway's Game of life on my computer. A problem arises; how to deal with the borders on the board? Do the cells at the border have to take into consideration less neighbours than the ...
user avatar
  • 218
1 vote
0 answers
75 views

is it possible to embed a fractal inside another fractal

I have been looking at one-dimensional (1D) cellular automata (CAs) which generate two-dimensional (2D) fractal patterns. Among the 256 1D elementary CAs, I tried to list down the fractal generating ...
user avatar
3 votes
1 answer
117 views

A basic transition automaton of ECA 30

I am reading this thesis, which on page no 14 talks about modeling. It also says in page no 15 that: The automata we construct to model the basic transition scan words over $\Sigma^2$, where $\...
user avatar
  • 85
2 votes
1 answer
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?
user avatar
  • 912
1 vote
0 answers
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 ...
user avatar
  • 21
1 vote
1 answer
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 ...
user avatar
11 votes
0 answers
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 ...
user avatar
2 votes
2 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 75
2 votes
1 answer
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 ...
user avatar
  • 75
0 votes
1 answer
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. ...
user avatar
  • 6,772
1 vote
1 answer
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 ...
user avatar
  • 75
0 votes
1 answer
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 (...
user avatar
  • 53
6 votes
0 answers
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-...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 3,981
2 votes
0 answers
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 ...
user avatar
3 votes
1 answer
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 ...
user avatar
  • 167
0 votes
0 answers
66 views

About Tegmark's mathematical universe

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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
  • 123
3 votes
0 answers
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,*)$...
user avatar
  • 2,740
3 votes
0 answers
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.
user avatar
  • 470
3 votes
1 answer
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-...
user avatar
  • 357
5 votes
0 answers
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 (...
user avatar
  • 17.8k
2 votes
0 answers
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 ...
user avatar
  • 568
5 votes
1 answer
158 views

Find minimal number of elements in matrix.

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. ...
user avatar
  • 5,958
1 vote
1 answer
48 views

Clustering computation in pair approximation model

Let's consider a square lattice of cells. Each cell can be either occupied by a species (1 or 2) or be empty (0). Each cell can be either in state 1, 2 or 0. In the pair approximation model, I ...
user avatar