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

1
vote
1answer
36 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 ...
3
votes
2answers
68 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
0answers
29 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
77 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
231 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
141 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
166 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
80 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
680 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, ...
10
votes
3answers
313 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 ...
7
votes
1answer
83 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 ...