# Tagged Questions

A computational model composed of a grid of stateful cells and a set of rules describing when to change a cell's state.

20 views

### How to identify strongly confluent cellular automatas?

Lets represent a class of cellular automata as a finite, unidimensional bit array state : [Bit], plus a rewrite rule ...
36 views

### Is there any count-preserving cellular automata which tends do “10101010…”?

Suppose that I have a bit string of finite length. Is there any bit rewriting rule rewrire :: (Bit,Bit,Bit) -> (Bit,Bit,Bit), that doesn't change the total count ...
46 views

### What does Cellular Automata Pre-image problem actually means?

I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata. In the 2nd page he lists three NP-Complete ...
114 views

### Complexity of $n \times \log n$ tiling problem

Is there a polynomial time algorithm for an $n \times \log n$ tiling problem? For instance: Suppose $A$ is a finite alphabet. A tile is a $2 \times 2$ matrix of elements from $A$. A tiling is a ...
290 views

### Is the halting problem decidable for 3 symbol one dimensional cellular automata?

I've been trying to figure out if the halting problem is decidable for 3-symbol one-dimensional cellular automata. Definition Let $f(w,i)$ denote the configuration of the system at time step $i$. ...
48 views

### Consistent Simulation of Cellular Automata on Infinite Grid

Let's say that you have an infinite grid of cells. A program is run per cell, where you have read access to some finite number of cells (for the previous state in time), but you only have write ...
171 views

### How rule 110 would be proven to be universal if the tag system did not exist?

I was reading about Cellular Automata and I read in this question that Matthew Cook proved that rule 110 is universal, and that his proof relied upon showing how rule 110 can simulate a tag system. ...
51 views

### Are Cellular Automata always computers?

I was reading on Complex Systems journal and found a paper where the author states that a cellular automaton can be viewed as a computer. In the introduction part: Cellular automata can be ...
77 views

### Why some rules in Elementary Cellular Automata halt and others don't?

I was looking over stephen wolfram's work mainly about Elementary Cellular Automata, i see that for all rules with N steps {i.e 200 steps} they show the same pattern {i,e rule 90 running on 20 steps ...
28 views

### Is there a similar categorization to Elementary Cellular Automata?

Elementry cellular Automata shows different systems and fractals like rule 30, 90 & 110, i want to know if there is another classification ortype which shows similar structures just like in ECA. ...
25 views

### What is the relation between universality and chaotic behavior in Elementary Cellular Automata?

So i know that rule 110 from Elementary Cellular Automata is universal but i am wondering if we had other chaotic behaviors let's say there exists a system that shows nearly infinite chaotic behaviors ...
120 views

### What is the difference between computational model, model of computation and a computer?

I was browsing the forum where i came by this question, it says that rule 110 from {ECA} is a computation model. What is the difference between a computation model and model of computation and how ...
53 views

### What is the relation between pure mathematics, applied mathematics and Cellular Automata?

I was reading about pure mathematics and I am wondering if there is a relation between it and Cellular Automata. Broadly speaking, pure mathematics is mathematics that studies entirely abstract ...
24 views

### What is the relation between Universality and simulations of Cellular Automata structures?

Elementary Cellular Automata and Conway's Game of Life show interesting Cellular structures, suppose we have a computational model {a Cellular Auotmaton} that can simulate both CA types (ECA & ...
62 views

### How Cellular Automata is related to Automata Theory?

I have read about Automata Theory where it is about the study of abstract machines and automata. And i know that an abstract machine takes the input, process it and create the output, just like ...
27 views

### What is the relation between Universality and Geometric shapes in cellular automata?

When wolfram described Elementary Cellular Automata, most of the rules appeared as triangle and lines. Now, Rule 110 consists of triangles which is proved to be universal. Is there a relation ...
142 views

### How to prove universality in complex systems?

I'm working on my graduation project for CS, which is about cellular automata. Recently, i was able to build a system where the input is transferred to multiple different structures at once. The ...
134 views

### Does solving mathematical equations with Cellular Automata structures means it is universal?

I'm working on a research about Elementary Cellular Automata (ECA), and i found a method to build a system that can solve mathematical equations by using a specific cellular automaton structure. The ...
53 views

### Can a cellular automata structure simulates another cellular automata structure?

In Elementary Cellular Automata, rules can show one pattern, but i am wondering if there is something where a cellular automata structure can simulate another structure? Is there a category for this ...
132 views

### Are Elementary Cellular Automata structures considered to be fractals?

I know that a fractal is a non ending pattern, like Pascal's triangle or Sierpinski's triangle, which are the same as Rule 90 from Elementary Cellular Automata. But, what about the other rules from ...
140 views

### Are deterministic and nondeterministic Cellular Automata equivalent?

It seems that in CA context nondeterministic (ND) means probabilistic, not ND as in NFSMs. At least I haven't seen a paper or book which discusses NCAs, without talking about probabilistic CAs. I ...
38 views

### Immutable data structures for 2d+ lattices

I would like to find an immutable/persistent data structure that allows efficient updating for 2d (or higher) lattices/arrays/matrices, and reasonable performance when appending in any direction. ...
47 views

### Which cellular automata rules are suitable for randomizing an input sequence?

S. Wolfram has in has book "A New Kind of Science" listed 256 simple rules of cellular automata. Which of these rules could via iteration essentially contribute to render an input sequence more random ...
113 views

### Is the number of inequivalent elementary cellular automata rules really 88?

Everywhere from Wolfram's "New Kind of Science" (p. 57) to Wikipedia they say that, out of all possible 256 (=2^8) elementary cellular automata rules, 88 are inequivalent (as defined in the Wikipedia ...
63 views

### How to synchronize a 2d cellular automaton in $\Theta(\sqrt{n} \log n)$ steps

Let's assume we have given a two dimensional cellular automaton with an initial configuration where alls cells are in an quiescent state, expect for one square of cells. Let $n$ be the number of cells ...
177 views

### How to simulate a cellular automaton via a Turing machine

It is rather easy to see that every cellular automaton can be simulated by a Turing machine: We can simulate a cellular automaton with an appropriate C program and every C program can be simulated by ...
56 views

### Cellular Automata Using Small Boards

I'm working on making patterns for a digital lava lamp (essentially, making interesting patterns using a 4x10 grid), and I've been looking into cellular automata. I tried implementing some variations ...
254 views

### What is the distribution of Garden of Eden patterns in cellular automata with increasing pattern size?

In a given cellular automaton, such as Conway's Game of Life, is there anything known about how many Garden of Eden patterns there are by pattern size? Say, pattern size is n x n, what's the ...
76 views

### Does the state of a cell in cellular automata has to be from a finite set?

In most (all I have seen) work on cellular automata, the state of a cell is from a finite set. Such as a cell can take value from a binary set, or from among few colors. Can we define the state to be ...
136 views

### Time Complexity of Simulating CA with TM

This question is a follow up to the question: Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines. To simulate a CA with a TM, I used a construction which placed a marker on ...
498 views

### Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines

I'm considering an automaton $A$ over a alphabet $\Sigma$, with a set of states $Q$, such that $\Sigma \subset Q$, which includes special "accept" and "blank" states not in $\Sigma$. It also has an ...
228 views

### 1/r attractive force by cellular automaton

Does there exist a cellular automaton (in 2D) which simulates a $1/r$ force between particles? More specifically, I would like to know whether it is possible, with strictly local update rules, to ...
326 views

### Cell walls in Conway's Game of Life?

Do there exist robust structures in Conway's Game of Life? For instance, has anyone constructed a spaceship with a shield that absorbs all small oscillators and gliders it collides with?
105 views

### How does an automaton actually “compute”?

In my studies in computability I have come across the notion of the "machine", an abstract representation of a device that essentially computes. I have read about Turing Machines and Wolfram's binary ...
2k views

### How is the rule 110 Turing complete?

I've read the wikipedia page for rule 110 in cellular automata, and I more or less know how they work (a set of rules decides where to draw the next 1 or 0). I've just read they're Turing complete, ...
547 views

### Are today's massive parallel processing units able to run cellular automata efficiently?

I wonder whether the massively parallel computation units provided in graphic cards nowadays (one that is programmable in OpenCL, for example) are good enough to simulate 1D cellular automata (or ...
127 views

### Influence of the dimension of cellular automata on complexity classes

Let's take as an example the 3d → 2d reduction: What's the cost of simulating a 3d cellular automaton by a 2d cellular automaton? Here is a bunch of more specific questions: What kind of algorithms ...