Questions tagged [cellular-automata]
The cellular-automata tag has no usage guidance.
75
questions
1
vote
1
answer
120
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
votes
2
answers
507
views
Vice-versa Erdős conjecture
Erdős conjectured that, except $1, 4$ and $256$, no power of $2$ is a sum of distinct powers of $3$.
A vice-versa conjecture may be: except $1$, $9$ and $81$, all powers of $3$ contains two ...
7
votes
0
answers
976
views
Absolute oscillator in Langton's Ant
We have a simple (or single) block of Langton's Ants colony which includes two ants looking in the same direction. Their positions can be interpreted as knight's walk. The distances between each next ...
0
votes
0
answers
65
views
A cellular automaton with an image that is not closed
Let $G$ be a non-locally finite periodic group and let $V$ be an infinite-dimensional vector space over a field $\mathbb{F}$. Does there exist a nontrivial topology on $V^G$ and a linear cellular ...
7
votes
1
answer
340
views
Rewrite Game of Life as a convolution and a nonlinearity
If you implement Conway's Game of Life on a computer, it's convenient to define the neighbor-counting kernel,
$$
k = \left[ \begin{array}{} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \...
2
votes
1
answer
148
views
A sensitive 2-dimensional cellular automaton with a blocking word
I'am a Ph.D student in the domain of discrete dynamical systems. My thesis is about spectral properties of cellular automata in higher dimension.
Kurka gives a classification for one dimensional ...
0
votes
0
answers
108
views
Growing gliders under rule 110
I found a glider in the evolution space of rule 110 that grows constantly in size. Normal gliders live in the so-called ether, e.g. the so-called E-glider:
Other – often complex – gliders exist in an ...
0
votes
0
answers
80
views
Relation between symbolic substitution and cellular automata
I recently asked this on Math Stackexchange recently in this thread. I was told that there is a relation between symbolic substitutions and cellular automata. I'm vaguely familiar with Cobham's ...
1
vote
0
answers
88
views
Asymptotic densities of rules of elementary cellular automata
In Tables of cellular automata, p.542, Wolfram defines the density $\delta$ of a rule to be the asymptotic density of nonzero sites when the initial configuration has density $1/2$. Wolfram quotes ...
3
votes
2
answers
233
views
Elementary cellular automata in stochastic modes
There are several ways to run a given elementary cellular automaton in a stochastic way:
by giving for each of the eight local configurations 000,100,010 and so on a probability by which the rule is ...
0
votes
0
answers
43
views
Cellular automata with different generating-cells configuration
I recently faced the problem of generating "interesting" binary matrices for testing a heuristics for the $3DCC$-problem, i.e. to check if the graph represented by the adjacency matrix ...
0
votes
1
answer
116
views
A special kind of pseudo-garden eden states in cellular automata
I'm currently investigating Wolfram's elementary cellular automata on finite grids with periodic boundary conditions, i.e. on $\mathbb{Z}/k$ for different $k$.
It is clear that for each rule $R$ and ...
1
vote
0
answers
26
views
How slowly can one be absorbed in the absorbing phase of the directed percolation universality class?
In absorbing state transitions on a lattice, one often considers "active" and "inactive" sites, with update rules describing how activity spreads or decays. When the lattice sites ...
0
votes
0
answers
106
views
Lengths of paths through Conway’s Game of Life
This question is inspired by the following challenge from CodeGolf.SE: https://codegolf.stackexchange.com/q/251510/88765.
Given positive integer $N$, we can consider a version of Conway’s game of life ...
2
votes
1
answer
388
views
Mysteries of Wolfram's rule 18
[Unfortunately, I made some mistakes in my original question. I tacitly corrected them wherever I found them.]
Wolfram's rule 18 gives rise to fractal patterns, but when started with two black cells ...
10
votes
0
answers
196
views
Robust (=error-correcting) configurations in Conway's Game of Life
Motivation / discussion: Conway's Game of Life automaton is often suggested as a model for either real (biological) life and/or computation, but one important trend in both real life and computer ...
0
votes
0
answers
98
views
Possible shifts in finite elementary cellular automata
I investigated the long term behaviour of a pair of black cells ■■ on a circle of $N$ cells under the action of each of Wolfram's rules $R$. For each combination $(R,N)$ I determined the first ...
2
votes
1
answer
238
views
"Rule 30" in the infinite setting
This question tries to get right what went wrong in an earlier question.
Let $\{0,1\}^\mathbb{Z}$ denote the set of all functions $x:\mathbb{Z}\to \{0,1\}$. Let $+$ denote addition modulo $2$ on $\{0,...
1
vote
1
answer
509
views
Possible finite periodicities of "Rule 150" in the infinite setting
"Rule 150" is a fascinating one-dimensional and simple cellular automaton giving raise to some quite chaotic behaviour. This is the starting point of this question.
Let $\{0,1\}^\mathbb{Z}$ ...
1
vote
0
answers
367
views
Astonishing affinity of Wolfram's rule 110 to the numbers 2 and 7
I investigated the evolution of a single black cell on 1-dimensional grids with periodic boundary conditions of variable sizes $N$ under Wolfram's rule 110 which is the only one for which Turing ...
1
vote
1
answer
124
views
Local rule for the product of two cellular automata
Consider two one-dimensional cellular automata $(A^{\mathbb Z},F)$ and $(B^{\mathbb Z},G)$ with alphabets $A$ and $B$ and global rules $F: A^{\mathbb Z} \to A^{\mathbb Z}$ and $G: B^{\mathbb Z} \to B^{...
46
votes
3
answers
7k
views
Does Conway's game of life admit a notion of energy?
(I am not sure if this is a mathematics or physics question so I am not sure where to post it. I am posting it here because the chief subject is an unreal universe that is purely a subject of ...
1
vote
1
answer
207
views
Is there a description of cellular automata in form of sheaves?
Cellular automata are defined through rules in a local neighborhood and sheaves, as far as I understand, can be used to glue local data to global data. Has there been any effort to bring those two ...
26
votes
1
answer
3k
views
Is rule 30 Turing complete? Is there a proof that it isn't?
It is well known that the elementary cellular automaton known as rule 110 is Turing complete.
Its cousin rule 30 also produces complicated behaviour. When I read Wolfram's a New Kind of Science (in ...
6
votes
1
answer
206
views
Topologically mixing cellular automata on groups
For which group-alphabet pairs $(G, A)$ does $(G, A^G)$ admit a topologically mixing cellular automaton?
Definitions:
Let $G$ be a (discrete) group. An alphabet is a finite set of cardinality at ...
3
votes
1
answer
144
views
Binary cellular automata: How slowly can an eroder remove $1$'s?
Consider some deterministic, monotonic, eroding binary cellular automata on some lattice $\mathbb{Z}^d$, and consider the set of initial states $I(L)$ in which all of the vertices are $0$ except for ...
1
vote
1
answer
161
views
Is Toom's rule robust under local but non-on-site noise?
Toom's rule is a 2-dimensional cellular automaton which is known to have two distinct stationary measures in the thermodynamic limit, even after small perturbations to a probabilistic cellular ...
3
votes
0
answers
106
views
Are there (probablistic) uniform 1D cellular automata which can fault-tolerantly store one bit?
In two dimensions, "Toom's rule" is known to be a cellular automaton which can fault-tolerantly store one bit of information. This means that, if we start with the all-0 configuration on an $...
3
votes
0
answers
118
views
Oscillator in Langton's ant
First of all, see Langton's ant Wikipedia page.
If we place a pair of ants looking north (using Golly or any another prog) on the coordinates $(x_1,y_1)$ and $(x_2,y_2)$ under the conditions:
$p=|x_1-...
14
votes
2
answers
726
views
Blinking graphs
For any simple graph $G$, assign its nodes a weight/bit of $0$ or $1$.
Call this a bit assignment for $G$.
Now, generate a new bit assignment as follows:
Each node $x$'s bit is replaced by $1$ if the ...
12
votes
9
answers
9k
views
Book recommendations on cellular automata?
I have been looking for books on cellular automata, and I really can't afford more than one book right now, so I really need to make the right choice. What would be the right book for someone with a ...
0
votes
0
answers
124
views
Spread of a disease on a modular chessboard (torus) - lower bound
I learned about the following result from one of Peter Winkler's books:
It is impossible to infect the entire $n\times n$ chessboard (usual chessboard) starting from fewer than $n$ infected cells.
The ...
6
votes
0
answers
219
views
2D quadrant sandpile: emergent highway structure
Consider the top-right quadrant of the plane divided into unit cells, each cell containing some number of chips. A cell containing at least two chips can fire two chips, one to the cell above it and ...
8
votes
1
answer
411
views
The graph of Rule 110 and vertices degree
Consider the elementary cellular automaton called Rule 110 (famous for being Turing complete):
It induces a map $R: \mathbb{N} \to \mathbb{N}$ such that the binary representation of $R(n)$ is ...
1
vote
0
answers
295
views
Life. Intermediate stages
My question is pure mathematics when restricted to the cellular automata theory.
John von Neumann got the grasp of and defined life. Many years later biologists supported von Neumann's definition of ...
4
votes
2
answers
625
views
Busy Beaver in cellular automata
The Busy Beaver function is usually studied for Turing machines. Of course, it's not a computable function, but for 2-state Turing machines, the first four values are known, and the fifth conjectured.
...
0
votes
1
answer
163
views
Probabilistic approach for cellular automata
Few months ago my scientific adviser asked me to use probabilistic ideas in such problem :
Consider a matrix NxN. Each element of matrix is a number 1 or 0. We may change all elements of this matrix ...
5
votes
4
answers
573
views
Why do some linear cellular automata over $Z_{2}$ on the torus have small order?
At https://dmishin.github.io/js-revca/index.html, you can play around with reversible cellular automata. I noticed that on that site, that for the reversible linear cellular automata (which I have ...
15
votes
3
answers
2k
views
Relativistic Cellular Automata
Cellular automata provide interesting models of physics: Google Scholar gives more than 25,000 results when searching for "cellular automata" physics.
Google Scholar still gives more than 2,...
18
votes
0
answers
2k
views
Distribution of digits of $pq$-adic idempotents (aka "automorphic numbers")
Let $p$ and $q$ be distinct primes. By the ring of $pq$-adic integers I mean the ring $\mathbb{Z}_{pq} := \varprojlim \mathbb{Z}/(pq)^n\mathbb{Z}$ which is obviously isomorphic to $\mathbb{Z}_p \...
3
votes
2
answers
355
views
Periodic configurations for elementary cellular automata
Let $L$ be an elementary cellular automaton. Then $L$ acts on $\{0,1\}^{\mathbb{Z}}$. We say that a configuration $w\in\{0,1\}^{\mathbb{Z}}$ is periodic if $L^{(n)}(w)=w$ for some $n\in\mathbb{N}$.
...
13
votes
1
answer
3k
views
The infinite X in Conway's game of life
In Conway's game of life, take the initial position to be two infinite diagonal lines of live cells, with a single cell in common. Does this thing converge to a stable configuration? I.e., is the ...
1
vote
1
answer
155
views
Errors in Waksman's Solution to Cellular Automaton Firing Squad Problem?
Recently, a student and I have been working through Waksman's paper ``An Optimum Solution to the Firing Squad Synchronization Problem.'' The paper claims that for any value of $n$, the proposed ...
7
votes
2
answers
475
views
The von Neumann algebra generated by a non-closable operator
Let $H$ be a separable Hilbert space and let $M$ be a densely defined operator $\mathcal{D}(M) \subset H \to H$. It is closable iff its adjoint $M^{\star}$ is densely defined, and then its closure $\...
1
vote
0
answers
121
views
Minimal period for a bounded Langton's ant moving on a tessellation
We consider Langton's ant on the 2D plane, but we replace the square lattice by a Voronoi tessellation obtained from a finite set of points (it could be another tessellation, however directions such ...
23
votes
1
answer
2k
views
Time for Langton's ant to cover a "square" torus
Langton's ant is a cellular automaton running as follows:
Squares on a plane are colored variously either black or white. We
arbitrarily identify one square as the "ant". The ant can travel in
...
4
votes
0
answers
123
views
Percolation in torus under threshold rule
As part of my graduate research I am currently studying the last section in the paper "Random Majority Percolation" by Balister, Bollobas et al. The paper itself is very complicated but the last two ...
22
votes
4
answers
2k
views
The 1-step vanishing polyplets on Conway's game of life
A $n$-polyplet is a collection of $n$ cells on a grid which are orthogonally or diagonally connected.
The number of $n$-polyplets is given by the OEIS sequence A030222: $1, 2, 5, 22, 94, 524, 3031, \...
4
votes
2
answers
583
views
Intermediate results for Langton's ant highway conjecture
This paper states the following theorem about Langton's ant:
The set of cells that are visited infinitely often by the ant (for a given initial configuration) has no corners. A corner of a set is a ...
31
votes
1
answer
1k
views
Vanishing line on Conway's game of life
If the initial state of Conway's game of life is a line of $n \in [0,100]$ alive cells, then it vanishes completely after some steps iff $n \in \{0,1,2,6,14,15,18,19,23,24 \}$. See below for $n=24$.
...