The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
80 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)$ ...
8
votes
0answers
192 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
1answer
588 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
0answers
247 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
1answer
405 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
2answers
685 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 ...
38
votes
7answers
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
1answer
271 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
1answer
253 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
1answer
128 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
2answers
210 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
1answer
133 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
1answer
343 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
2answers
807 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
1answer
408 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
0answers
194 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$ ...
22
votes
3answers
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
3answers
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
2answers
391 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
1answer
421 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
8answers
3k 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
1answer
293 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
3answers
695 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 ...