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

learn more… | top users | synonyms

3
votes
3answers
55 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 ...
0
votes
0answers
26 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. ...
1
vote
1answer
40 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 ...
4
votes
2answers
73 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 ...
0
votes
0answers
20 views

Classification of one-dimensional CA based on the number of inputs each cell receives during an update?

Consider Wolfram's rule 30 and Wolfram's rule 62. In the case of rule 30, only two bits of information must be passed to each new cell in the CA during an update, while for Wolfram's rule 62, three ...
1
vote
1answer
59 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 ...
0
votes
0answers
100 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 ...
1
vote
1answer
46 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 ...
4
votes
3answers
149 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 ...
2
votes
2answers
65 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 ...
2
votes
0answers
130 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 ...
1
vote
1answer
425 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 ...
9
votes
2answers
186 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 ...
6
votes
1answer
238 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?
2
votes
2answers
88 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 ...
4
votes
1answer
1k 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, ...
11
votes
3answers
452 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 ...
8
votes
1answer
102 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 ...