# Tagged Questions

The tag has no usage guidance.

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 ...
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 ...
867 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 stable-...
609 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 ...
469 views

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 ...
920 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 '...
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 ...
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 ...
494 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 ...
250 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 ...
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 ...
1k 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 ...
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 ...
334 views

104 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 ...
310 views

145 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 ...
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 ...
88 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}$. ...
154 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 ...
89 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)$ ...
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 ...
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$ ...