Questions tagged [cellular-automata]
For questions on cellular automata, a discrete model consisting of a regular grid of cells.
139
questions
3
votes
1
answer
44
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 ...
- 3,472
0
votes
0
answers
17
views
A brief explanation of Isometries and Mobius Transformations used in animating Hyperbolic Cellular automata?
I've spent the past while digging into the code I asked about in Where to begin with animating over a 2D hyperbolic tessellation?, my answer there is in regards to digging into the MagicTile project's ...
- 3,472
1
vote
0
answers
30
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 ...
- 3,472
2
votes
1
answer
98
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 ...
3
votes
0
answers
94
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 ...
- 5,514
0
votes
0
answers
55
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 ...
- 477
9
votes
1
answer
161
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 ...
- 21.1k
2
votes
0
answers
57
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$ $...
- 21.1k
0
votes
0
answers
37
views
Regular language that specifies cycles of length 7 for rule 110
I found a language of which I may assume that it is regular, and now I want to know the grammar.
The words $w$ of the language have the form (A [0, 2, 4] B C+)+ ...
- 17.7k
1
vote
1
answer
58
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 &...
1
vote
0
answers
18
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
0
answers
65
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?
- 16.8k
2
votes
1
answer
120
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 ...
- 5,913
0
votes
0
answers
62
views
Canonical rule representation for elementary cellular automata
A rule of an elementary cellular automaton consists of eight subrules governing the behaviour of black and white pixels in different contexts:
for embedded pixels
at the right end of a sequence of ...
- 17.7k
2
votes
1
answer
103
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 ...
- 17.7k
1
vote
0
answers
58
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 ...
- 17.7k
22
votes
0
answers
320
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 ...
- 5,514
11
votes
0
answers
150
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 ...
- 12.1k
3
votes
0
answers
50
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.9k
3
votes
2
answers
84
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
10
votes
0
answers
174
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
2
votes
1
answer
164
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
2
votes
1
answer
39
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. ...
- 587
1
vote
1
answer
55
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
5
votes
0
answers
95
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 ...
- 177
5
votes
2
answers
201
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,676
1
vote
1
answer
99
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
12
votes
2
answers
537
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)...
- 312
115
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.
...
- 1,687
1
vote
1
answer
55
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 ...
- 5,514
2
votes
1
answer
169
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
2
votes
0
answers
216
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$...
- 5,514
16
votes
2
answers
527
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
3
votes
1
answer
177
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
0
answers
49
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 ...
- 5,514
1
vote
0
answers
191
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,181
1
vote
1
answer
108
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 ...
- 81
0
votes
1
answer
31
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-...
1
vote
0
answers
113
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 ...
- 17.7k
0
votes
0
answers
40
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 ...
4
votes
3
answers
407
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 ...
- 249
1
vote
0
answers
88
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 ...
3
votes
1
answer
126
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 $\...
- 85
2
votes
1
answer
108
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
0
answers
44
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
1
answer
193
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 ...
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 ...
- 111
2
votes
2
answers
113
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
1
answer
79
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 ...
- 215
2
votes
1
answer
112
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 ...
- 215