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

0
votes
0answers
15 views

analyzing moving pseudorandom sieve algorithm

the following is a rough simpification or "toy" version/ abstraction/ model (but still quite nontrivial) for/ inspired by a famous open math problem (which for now will remain nameless & may be ...
1
vote
1answer
52 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
46 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
39 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
94 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
31 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
83 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
268 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
153 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
185 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
83 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
870 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
360 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
90 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 ...