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 ...
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 ...
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 ...
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?
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 ...
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, ...
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 ...
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 ...