The cellular-automata tag has no usage guidance.

**3**

votes

**1**answer

89 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 ...

**11**

votes

**2**answers

462 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 ...

**0**

votes

**0**answers

41 views

### The orbit-structure of an automorphism of the full shift

My question concerns reversible cellular automaton rules on a one-dimensional wraparound universe consisting of $m$ sites each capable of being in any of $n$ states, or equivalently, the actions of ...

**3**

votes

**1**answer

156 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 ...

**3**

votes

**2**answers

172 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 ...

**11**

votes

**0**answers

337 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 ...

**20**

votes

**0**answers

598 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 ...

**1**

vote

**0**answers

87 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}$.
...

**1**

vote

**0**answers

150 views

### Math behind Conway's Game of Life [closed]

I'm an undergraduate student intending to double major in Computer Science and Pure Math, and I wish to do research on cellular automata in the future. My question is: what kind of mathematical basis ...

**0**

votes

**1**answer

88 views

### reference request for automata of this type [closed]

Consider the list of length $m$ $(1,0,\dots 0)$ we call this list $l_1$, we now define a sequence of lists recursively, where $l_1$ is the previous list, and if $l_n$ is the list $(a_1,a_2\dots a_n)$ ...

**9**

votes

**0**answers

247 views

### Infinite time game of life

Today in a talk with a friend of mine I had an idea of extending cellular automatons to transfinite working time. I know it has already been considered, but, as far as I can tell, GoL extended to ...

**8**

votes

**1**answer

988 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 ...

**8**

votes

**0**answers

320 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 ...

**9**

votes

**1**answer

481 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 ...

**23**

votes

**2**answers

853 views

### Is there any superstable configuration in the game of life?

This question spins off of Gil Kalai's recent question on Conway's game of life for a random initial configuration.
There are numerous configurations in the game of life that are known to be ...

**39**

votes

**7**answers

4k views

### Conway's game of life for random initial position

What is the behavior of Conway's game of life when the initial position is random? -- We can ask this question on an infinite grid or on an $n$ by $n$ table (planar or on a torus). Specifically ...

**3**

votes

**1**answer

307 views

### Invariant measures for Cellular automata

An easy question that I have never been able to answer.
Suppose we have the CA on $\{ 0,1,2 \}^{\mathbb{N}}$ with local rule given by $f(x,y)=A_{x,y}$ and $A$ the $3\times 3$ matrix ...

**2**

votes

**1**answer

264 views

### What is the dual of a pre-injective map?

In [M. Gromov, Endomorphisms of symbolic algebraic varieties, J. Eur. Math.
Soc. (JEMS) 1 (1999), 109–197], Gromov introduces the notion of pre-injective map. Recasting this notion in the setting of ...

**1**

vote

**1**answer

141 views

### Ergodicity and convergence time in Probabilistic Cellular Automata

Has the following conjecture been prooved, or has any step in the direction of its proof been done?
"ANY Probabilistic Cellular Automata converge fast on the stationary probability distribution iff ...

**3**

votes

**2**answers

216 views

### Ergodicity for a Probabilistic Cellular Automaton on a finite space

Let's consider a Probabilistic Cellular Automaton on a one dimensional lattice $S$. Each site of the lattice can have two states, $0$ and $1$. The transition probability acting on each site is: ...

**1**

vote

**1**answer

139 views

### Staggered timing on 2-D random walks by multiple agents

In 2-D lattice random walks by multiple drunks who can't step onto each other, mathematically I would just say the whole cellular automaton updates "at once".
But to simulate this on a computer, I ...

**2**

votes

**1**answer

376 views

### Turing-Complete Cellular Automata and Sym(Z)

Does there exist a Turing complete, cellular automata with universe and alphabet $\mathbb{Z}$ such that the only allowable configurations are permutations of $\mathbb{Z}$? Formally, consider $\tau : ...

**8**

votes

**2**answers

1k views

### Solving PDE via Cellular Automata

Is there a theory for solving PDE by using Cellular Automata ? Something which is on the line of, passing to the limit (scale) i.e., if you increase the number of grid points the solution to the ...

**3**

votes

**1**answer

431 views

### Are all quantum cellular automata invertible & representable?

A little background: As far as I know there is no standard definition of a quantum cellular automaton in the literature. Different authors use different definitions. Here I propose my own definition ...

**0**

votes

**0**answers

214 views

### Recurrence relation with Hadamard Product

I've been drawn to a problem that requires ascertaining the existence of fixed points in the following recurrence relation, any ideas would be much appreciated. I seek neccessary conditions on $A,B$ ...

**25**

votes

**3**answers

2k views

### Ax–Grothendieck and the Garden of Eden

It's an obvious consequence of the pigeonhole principle that any injective function over finite sets is bijective. But there are some similar results in different areas of mathematics that apply to ...

**9**

votes

**3**answers

1k 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,000 ...

**4**

votes

**2**answers

406 views

### Algorithms for modeling asynchronicity in Asynchronous Cellular Automata

Most cellular automata are defined as being updated synchronously. I am interested in asynchronous automata, where they do not all have to update simultaneously. I am restricting myself to cellular ...

**3**

votes

**1**answer

438 views

### Graviton-like cellular automaton

Gravitons are presumed to change the shape of space-time, and if there are enough of them, perhaps even its topology. Does anyone know of any cellular automata that, say, change the neighborhood ...

**8**

votes

**8**answers

4k 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 ...

**5**

votes

**1**answer

347 views

### What's the name of this 2D cellular automaton?

Does this 2D cellular automaton have a known name and history?
n colors (numbered 1 to n), assigned randomly at the start.
For each generation, every cell that has at least one neighbour cell with a ...

**11**

votes

**3**answers

882 views

### An intuitive reason why the “Rule 30” CA is random/pseudorandom?

I'm a little bit hesitant to ask this here, so please notice the tag. My hope is that someone will have a more satisfying answer than what I've heard before...
A long time ago I read (perhaps ...