Skip to main content

Questions tagged [cellular-automata]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
73 views

Probabilistic 2D cellular automata with memory lifetime increasing like $e^{L^2}$

Consider 2-state probabilistic cellular automata on an $L\times L$ torus square lattice which has the all-$0$ and all-$1$ configurations as fixed points, thinking of something similar to Toom's rule ...
Andi Bauer's user avatar
  • 2,911
1 vote
1 answer
140 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
0 votes
0 answers
66 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 ...
mahdi meisami's user avatar
2 votes
1 answer
162 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 ...
Nassima AIT SADI's user avatar
0 votes
0 answers
113 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 ...
Hans-Peter Stricker's user avatar
0 votes
0 answers
81 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 ...
Keen-ameteur's user avatar
3 votes
2 answers
240 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 ...
Hans-Peter Stricker's user avatar
1 vote
0 answers
91 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 ...
Hans-Peter Stricker's user avatar
0 votes
0 answers
49 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 ...
Manfred Weis's user avatar
  • 12.8k
0 votes
1 answer
123 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 ...
Hans-Peter Stricker's user avatar
1 vote
0 answers
27 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 ...
user196574's user avatar
0 votes
0 answers
108 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 ...
Zach Hunter's user avatar
  • 3,469
2 votes
1 answer
393 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 ...
Hans-Peter Stricker's user avatar
10 votes
0 answers
206 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 ...
Gro-Tsen's user avatar
  • 30.8k
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 ...
Hans-Peter Stricker's user avatar
2 votes
1 answer
241 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,...
Dominic van der Zypen's user avatar
1 vote
1 answer
513 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}$ ...
Dominic van der Zypen's user avatar
1 vote
0 answers
372 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 ...
Hans-Peter Stricker's user avatar
1 vote
1 answer
127 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^{...
kiki 's user avatar
  • 51
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 ...
The_Sympathizer's user avatar
7 votes
1 answer
351 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 \...
user avatar
1 vote
1 answer
217 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 ...
mathoverflowUser's user avatar
3 votes
1 answer
152 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 ...
user196574's user avatar
1 vote
1 answer
179 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 ...
Andi Bauer's user avatar
  • 2,911
3 votes
0 answers
118 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 $...
Andi Bauer's user avatar
  • 2,911
3 votes
0 answers
123 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-...
Notamathematician's user avatar
0 votes
0 answers
128 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 ...
Steve's user avatar
  • 1
6 votes
0 answers
222 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 ...
Mikhail Tikhomirov's user avatar
6 votes
1 answer
214 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 ...
Ville Salo's user avatar
  • 6,457
4 votes
2 answers
677 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. ...
rwallace's user avatar
  • 203
7 votes
0 answers
1k 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 ...
user514787's user avatar
0 votes
1 answer
168 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 ...
openspace's user avatar
  • 137
1 vote
1 answer
159 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 ...
Andrew Penland's user avatar
1 vote
0 answers
123 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 ...
ahstat's user avatar
  • 111
4 votes
0 answers
124 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 ...
Marcle's user avatar
  • 41
7 votes
2 answers
481 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 $\...
Sebastien Palcoux's user avatar
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, \...
Sebastien Palcoux's user avatar
8 votes
1 answer
421 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 ...
Sebastien Palcoux's user avatar
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$. ...
Sebastien Palcoux's user avatar
6 votes
0 answers
133 views

At what rates can creatures in a conservative cellular automata expand?

Let $A$ be a finite set, and suppose $0\in A$. For each $a\in A\setminus\{0\}$, let $w_{a}$ be a positive integer called the weight of $a$, and let $w_{0}=0$. Give $A$ the discrete topology and $A^{\...
Joseph Van Name's user avatar
5 votes
4 answers
584 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 ...
Joseph Van Name's user avatar
4 votes
2 answers
589 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 ...
user76284's user avatar
  • 1,823
7 votes
2 answers
514 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 ...
Douzi Hassan's user avatar
1 vote
0 answers
298 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 ...
Włodzimierz Holsztyński's user avatar
3 votes
0 answers
89 views

Lattice Boltzman derivation for vorticity eqn $\omega_{t}+ v\cdot \nabla \omega=\mu \Delta \omega$

So as showed by Frisch et al. (a), the 2D Euler equation $$v_{t}+ v\cdot \nabla v=\mu \Delta v$$ can be derived by the Hexagonal-placed automaton (for low velocity). I am curious about the existence ...
user133100's user avatar
3 votes
1 answer
1k views

How to get $\omega$-regular expression from buchi automaton

Is there an algorithm or a trick on how to get $\omega$-regular expressions from Buchi automatons? If yes, is there also some way to do create minimal such regular expressions? It is extremely ...
Fabio's user avatar
  • 33
14 votes
2 answers
729 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 ...
Joseph O'Rourke's user avatar
3 votes
1 answer
214 views

Is the variety of algebras $(A,*,+)$ that satisfy $(x*y)+(y*z)=(x+y)*(y+z)$ generated by its finite algebras?

The finite algebras $(A,*,+)$ that satisfy the identity $(x*y)+(y*z)=(x+y)*(y+z)$ are precisely the algebras such that the one-dimensional cellular automata produced by $*$ and $+$ are commutative ...
Joseph Van Name's user avatar
3 votes
2 answers
390 views

Does the 2-shift map have a root automorphism?

By the 2-shift map I mean the map $T:\{0,1\}^\mathbb{Z}\to \{0,1\}^\mathbb{Z}$ that shifts the sequence leftwise. By a root I mean an homeomorphism $\psi:\{0,1\}^\mathbb{Z}\to\{0,1\}^\mathbb{Z}$ that ...
EvaristoCarriego's user avatar
13 votes
1 answer
589 views

Does Langton's ant cover every n by 6 gridded torus?

This post follows this other post about times cover by Langton's ant of $n$ by $n$ gridded torus. For $n$ by $n$ gridded torus, I've checked for $n \le 1000$ that the ant covers all. This fact needs ...
Sebastien Palcoux's user avatar