The cellular-automata tag has no wiki summary.

**7**

votes

**0**answers

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

**6**

votes

**1**answer

532 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

**0**answers

214 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

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

**24**

votes

**2**answers

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

**37**

votes

**7**answers

3k 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

253 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

245 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

124 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

206 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

125 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

328 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 : ...

**7**

votes

**2**answers

690 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

400 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

187 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$ ...

**21**

votes

**3**answers

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

**8**

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

381 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

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

**6**

votes

**8**answers

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

**4**

votes

**1**answer

282 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

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