# Tagged Questions

The tag has no usage guidance.

103 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 ...
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 ...
45 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 ...
161 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 ...
173 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 ...
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 ...
608 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 ...
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}$. ...
153 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 ...
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)$ ...
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 ...
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 ...
334 views

268 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 ...
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 ...
218 views

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 ...
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 (...
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$ ...
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 ...
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 ...
407 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 ...
439 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 ...
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 ...