A computational model composed of a grid of stateful cells and a set of rules describing when to change a cell's state.
5
votes
1answer
47 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
126 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
71 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
212 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, ...
9
votes
3answers
237 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
67 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 ...
