8
votes
Accepted
Langton's Ant Periodic Behavior
The so-called Kohen–Kong theorem (described and attributed, without citation, to X.P. Kong and E.G.D. Kohen by Stewart (1994) (PDF); sometimes apparently misspelled as the "Kohen–Kung theorem") says ...
- 2,195
7
votes
Accepted
Does P = NP in Cellular Automata of Hyperbolic Spaces?
The P vs. NP problem is a question about Turing machines $T$, because the complexity classes P and NP are defined in terms of these theoretical machines. Let's call these classes $P_T$ and $NP_T$ from ...
- 8,332
5
votes
Accepted
Turing-completeness, Conway's Game of Life and Logical Gates
A form of conditional repetition or conditional jump (while, for, if and goto)
A way to read and write to some storage mechanism
The computer you typed this message onto is Turing Complete (well, ...
- 1,720
4
votes
Is it there any computer/cellular automaton/brain to compute logically impossible and incomputable things?
This question is just playing with words. According to Ludwig Wittgenstein, "whereof one cannot speak, thereof one must be silent". OK, I don't know what that quote means. Well, I do not know what ...
- 39.1k
3
votes
Accepted
Strategy for searching for elementary cellular automata (cyclic boundary conditions) that repeat
Yes, all initial states under all CA rules on a finite grid will eventually lead to a cycle (or a fixed state, which can be viewed as a cycle of length 1). More generally, iterating any fixed ...
- 2,195
3
votes
Accepted
Cellular automata on the Eisenstein integers?
Yes, such cellular automata have been studied. However, you're unlikely to find much about them using terms like "Eisenstein integers", since the convention in the field is to describe ...
- 2,195
3
votes
Whats the signifgance of Conway's Game of Life?
I'd say it's "the most famous" cellular automaton, in the sense that the structures its rules generate have been studied and given names to.
One property that it does have, that makes it ...
- 287
3
votes
Accepted
Generalization of Cellular Automata
Cellular automata can be defined on Cayley graphs of arbitrary groups.
Intuitively, the states go on the nodes of the graph, and the neighborhood of a node is defined using the edges.
The $d$-...
- 288
3
votes
Accepted
Conway's Game of Life: Is it really P-complete?
Your misunderstanding is the meaning of parallelize.
In this context, an algorithm can be parallelized if using polynomially many processors, you can compute the answer (in this case, the value of ...
- 279k
2
votes
Accepted
2d cellular automata Wolfram binary codes
The description given on the page you linked to is correct:
"In each case the base 2 digit sequence for the code number specifies the rule as follows. The last digit specifies what color the ...
- 2,195
2
votes
Accepted
How to create a cellular automata rule to achieve a desired pattern?
One way to achieve what you describe would be to encode your problem as a SAT instance, with clauses decribing the desired initial and final pattern and the state transitions under the (fully or ...
- 2,195
2
votes
Accepted
Difference between this grammar
Let us assume a variant of your example, one that indeed has a pair of equivalent grammars.
$X\to x \mid xyz$
$X\to x Y \hspace{1cm} Y\to yz \mid \varepsilon$
Here the second grammar is preferable to ...
- 31.1k
2
votes
Conway's Game of Life to expand QR code
Compression is often relative: using $n$ bits of information, you cannot represent more than $2^n$ different informations.
So, sure, using an $n\times n$ QR-code as a seed to encode an $N\times N$ ...
- 16.9k
2
votes
Accepted
What is the meaning of conservative dynamics in the context of Conway's Game of Life
Some relevant quotes from the paper:
We investigate the dynamics of a conservative version of Conway’s Game of Life, in which a pair consisting
of a dead and a living cell can switch their states ...
- 279k
1
vote
Had Conway's Game of Life or any C-A been demonstrated to generate non-repeating pattern?
Rule 110 is a cellular automaton that is Turing complete, hence it can generate non-repeating patterns. Since it is Turing complete it can certainly compute the square root of a fixed-point number.
- 17.1k
1
vote
How to motivate freshman students towards automatic groups?
There is no way this is at an appropriate level for students just graduating from high school. Save it for much more advanced students. It requires considerable mathematical sophistication -- and ...
D.W.♦
- 166k
1
vote
Accepted
Can Sutner's (1991) quadratic algorithm for testing reversibility of Cellular Automata be applied to 1-D CA with even sized neighborhoods?
A CA with neighborhood size $s$ can be trivially emulated by a CA with any neighborhood size $s' > s$ that just ignores the extra cells in the neighborhood. So if the method works for CA with odd ...
- 2,195
1
vote
Why is Rule 110 considered "weakly" universal?
Universality of Turing machines and Turing completeness of arbitrary computational systems are two different things. There is a concept of a weakly universal Turing machine, but no analogous concept ...
- 2,275
1
vote
Difference between this grammar
They are not equivalent. Consider the string xy.
With the first grammar, the string can be generated.
$$
X \rightarrow xY \rightarrow xyZ \rightarrow xy
$$
However, ...
- 11
1
vote
Is it possible to reverse engineer cellular automata?
As long appropriate initial constraints on the CA rule (and, in particular, on the neighborhood size) are provided, yes, this is possible.
In fact, the basic algorithm is quite simple. It relies on ...
- 2,195
1
vote
Is it possible to reverse engineer cellular automata?
This problem is somewhat similar to programming by example
https://en.wikipedia.org/wiki/Programming_by_example
In this paradigm, a system is given a sequence of states (examples) and asked to ...
1
vote
How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?
You seem to be looking to enumerate (and/or randomly sample from) the set of isotropic two-state two-dimensional cellular automata on the Moore neighborhood.
The general way to this is simply to find ...
- 2,195
1
vote
How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?
I won't go into the details of your specific case but try to answer the general problem.
In the unrestricted case there is a mapping from each of the $n$ (=512) input states to one of 2 output states ...
- 584
1
vote
Does any algorithm exist for computing the state of a non-trivial cellular automaton after an arbitrary number of time steps?
Two answers...
There is a trivial algorithm to do it: "Just" run the automaton for the required steps.
No, there is no general way to compress the computation. If you can prove that the automaton ...
- 14.1k
1
vote
Is there any model of Game of Life compatible with hypercomputation?
Cellular automata can be simulated with an ordinary Turing machine, so they don't have any more power than an ordinary Turing machine -- they can't perform "hypercomputation".
D.W.♦
- 166k
1
vote
Accepted
Algorithm to estimate the probability that a "0 and 1 matrix" fills up following the bootstrap percolation rules
Here is a reasonably fast approach to estimate $p_c$. We will perform $N$ different trials, count the number of successes $M$, and estimate the result as $M/N \pm 1/\sqrt{N}$ (better estimates are ...
- 279k
1
vote
Accepted
Classes of outer totalistic cellular automata
Here is a fairly old link, which only lists a few classes specifically, but it might be a place to start.
I'd agree with David Eppstein that a longer list might not be all that useful. There's no ...
- 126
1
vote
Turing-completeness, Conway's Game of Life and Logical Gates
I think that your plan is good, but the most important is for it to be intuitive for you ! If you don't feel secure with it, just change it !
Then, for GOL, I made multiple lectures, but as I'm ...
- 11
1
vote
Is there any field that studies the equivalent of cellular automata, but for arbitrary graphs rather than 1D cells?
Graph dynamical systems is a general term for systems where each vertex of a graph carries a state, and the system evolves in time so that the next state of a vertex only depends on the states in its ...
- 288
Only top scored, non community-wiki answers of a minimum length are eligible