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
1 vote
0 answers
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 ...
Keen-ameteur's user avatar
  • 7,728
2 votes
0 answers
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 ...
EternalPropagation's user avatar
2 votes
0 answers
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 ...
PythonCZX's user avatar
  • 123
2 votes
0 answers
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. ...
mell_o_tron's user avatar
3 votes
0 answers
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: ...
shin chan's user avatar
  • 249
0 votes
0 answers
27 views

Choosing correct parameters in a model with hamiltonian equation

I am working on the hamiltonian of a system related to the extension of the Potts Model which is Cellular Potts Model. The total hamiltonian of the system is: $$ H = H_1 + H_2 $$ $$ H_1 = - J \sum_{\...
wallevic's user avatar
2 votes
1 answer
94 views

What is special about the "pentagrid" and "heptagrid" in Margenstern's work on Cellular Automata in Hyperbolic Spaces?

In his work he mainly focuses on the pentagrid {5,4} and heptagrid {7,3}: In what ways are these tilings special? How do they compare to hyperbolic tilings in general? I am wondering what insights ...
Lance's user avatar
  • 3,694
1 vote
0 answers
40 views

What are the various types of rules / rule systems created or commonly used for studying 2D cellular automata?

I am working on implementing a cellular automata framework in JavaScript, though I don't really have a good sense of what I'm doing yet. I have spent days searching for "rules" for cellular ...
Lance's user avatar
  • 3,694
2 votes
1 answer
421 views

Interesting discovery made in the Conway's Game of Life

When I was experimenting with the Game of Life by John Conway, I realised that any n by n diagonal square does not die off at the end; it always reaches a state where it oscillates or does not ...
FAN WENDI HCI's user avatar
3 votes
0 answers
112 views

Toy example of superdeterminism using Rule 30 [closed]

From what I understand of Bell's Theorem, it requires giving up local realism or embracing superdeterminism. I still haven't been able to understand why superdeterminism gets such a bad rap, so I've ...
Trevor's user avatar
  • 6,022
0 votes
0 answers
61 views

Wrong interpretation of probability in a scientific paper

I've been reading a scientific paper about a cellular automaton which models the spread of cancer cells. I've almost finished my model in C++ when I noticed a possible error in probability ...
ampersander's user avatar
9 votes
1 answer
179 views

Infected cubes puzzle in 3D with threshold 4

(Now cross-posted to Puzzling SE.) 3D infected cubes puzzle with threshold $4$: On an $n\times n\times n$ cube, some cells are infected; if a cell shares a face with $4$ infected cells, it becomes ...
Akiva Weinberger's user avatar
2 votes
0 answers
65 views

$k$-dimensional variation on the infected squares puzzle

The infected squares puzzle is a classic; you can read about it here. I'm interested in the $k$-dimensional version, specifically in establishing an upper bound. Consider an $n\times n\times\cdots n$ $...
Akiva Weinberger's user avatar
1 vote
1 answer
70 views

Why is the minimal polynomial's order different from the maximal cycle length for these two linear elementary cellular automata?

For any given 1D elementary and linear cellular automaton there exists a transition matrix. For example, for rule 60 the transition matrix is $$ \begin{bmatrix} 1 & 0 & 0 & \dots &...
Kostas's user avatar
  • 31
1 vote
0 answers
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 ...
Mircea's user avatar
  • 111
1 vote
0 answers
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?
user107952's user avatar
  • 20.7k
2 votes
1 answer
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 ...
Keen-ameteur's user avatar
  • 7,728
2 votes
1 answer
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 ...
Hans-Peter Stricker's user avatar
1 vote
0 answers
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 ...
Hans-Peter Stricker's user avatar
25 votes
1 answer
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 ...
Trevor's user avatar
  • 6,022
12 votes
0 answers
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 ...
user56834's user avatar
  • 13k
3 votes
0 answers
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 ...
Joseph O'Rourke's user avatar
2 votes
2 answers
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 ...
eMad's user avatar
  • 131
10 votes
0 answers
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 ...
MadScientist's user avatar
2 votes
1 answer
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 ...
maxy's user avatar
  • 123
2 votes
1 answer
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. ...
user446046's user avatar
0 votes
1 answer
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 ...
rwallace's user avatar
  • 245
4 votes
0 answers
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 ...
scottef's user avatar
  • 175
4 votes
2 answers
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 ...
Dario's user avatar
  • 5,749
1 vote
1 answer
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. ...
neph's user avatar
  • 143
12 votes
2 answers
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)...
Ron Shvartsman's user avatar
115 votes
7 answers
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. ...
VainMan's user avatar
  • 1,735
1 vote
1 answer
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 ...
Trevor's user avatar
  • 6,022
2 votes
1 answer
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 ...
zackit's user avatar
  • 123
2 votes
0 answers
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$...
Trevor's user avatar
  • 6,022
16 votes
2 answers
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 ...
user2471's user avatar
  • 383
3 votes
1 answer
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 ...
Milan's user avatar
  • 153
1 vote
0 answers
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 ...
Trevor's user avatar
  • 6,022
1 vote
0 answers
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 ...
zooby's user avatar
  • 4,343
1 vote
1 answer
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 ...
Ali Kwant's user avatar
0 votes
1 answer
32 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-...
Osniel Teixeira's user avatar
1 vote
0 answers
115 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 ...
Hans-Peter Stricker's user avatar
0 votes
0 answers
42 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 ...
wesupportthepalace's user avatar
4 votes
3 answers
586 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 ...
Swike's user avatar
  • 261
1 vote
0 answers
101 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 ...
half_degree_of_freedom's user avatar
3 votes
1 answer
137 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 $\...
ooo's user avatar
  • 85
2 votes
1 answer
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?
Mario's user avatar
  • 932
1 vote
0 answers
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 ...
Delpux's user avatar
  • 21
1 vote
1 answer
200 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 ...
Mathews George's 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 ...
Alec Jones's user avatar