The cellular-automata tag has no wiki summary.
2
votes
1answer
173 views
Langton's ant highway conjecture and undecidability
I was recently reading about Langton's ant and the related conjecture which states that for every initial configuration, the ant eventually starts building a 'highway'.
I also read that it has been ...
-4
votes
1answer
196 views
Minimal Turing Machine implementation / Von Neumann UC [closed]
I've written a small python program which implements a Turing Machine with a finite tape. It has a tape, a head, a state register and a set of transfer functions ("the program"). The difference to a ...
2
votes
2answers
161 views
Difference between Stencil -structures and Cellular Automata Category-theoretically?
Definitions
Stencil =
"For a given point, a stencil is a pre-determined set of nearest
neighbors (possibly including itself)."
(source)
Wikipedia's definition (source) =
It ...
1
vote
1answer
331 views
Initial conditions for universal Rule 110
In A New Kind of Science, Wolfram proves that the Rule 110 cellular automaton can emulate a cyclic tag system, and is therefore a universal computer.
I was wondering what specific initial conditions ...
2
votes
0answers
135 views
Particle collisions for universal computation
Proof of universality of Game of Life is straightforward (CAFAQ):
(two annihilating glider streams with gaps (ie. 0s) are colliding, one is "data" and the second is all glider filled, ie.: ...
1
vote
0answers
111 views
Density of black cells in rule 110 cellular automata [closed]
Is there a way to compute the limit of the ratio (number of black cells)/(number of white cells), in the rule 110 or rule 30 automaton? With initial state = 1 black cell.
Simulation of first 120000 ...
4
votes
1answer
278 views
Quantum cellular automata
This questions is cross-posted from MathOverflow
A little background: As far as I know there is no standard definition of a quantum cellular automaton in the literature. Different authors use ...
5
votes
2answers
315 views
Isolation in Turing-complete reversible cellular automata
I don't know much about the terminology and the results on cellular automata, but I would like to ask a question about an conjecture I thought.
Consider Turing-complete reversible cellular automata.
...
6
votes
1answer
313 views
On 1-dimensional cellular automata
I'm interested in linear 2-state cellular automata (with local rules only) that could compute the majority function. Say the state of a cell is either 0 or 1. Is it possible to have a cellular ...
13
votes
0answers
765 views
Can a Penrose tile cellular automaton be Turing-complete?
This question was based on an incorrect premise ... see Colin's comment below. Forget it.
This was inspired by the discussion on this Math Overflow question. First, I need to define our terms.
In a ...
