The tag has no wiki summary.

learn more… | top users | synonyms

-4
votes
0answers
35 views

Cellular neural networks [on hold]

What is the effect of the template A in the cellular neural network? What is the difference between using local rules and learning to enforce the CNN to give the desired output? How do I use a ...
3
votes
0answers
106 views

Meta Game of Life

Apparently, Game of Life has been implemented in Game of Life. For example: https://www.youtube.com/watch?v=xP5-iIeKXE8 The device used here is called the "OTCA Metapixel", and supports all ...
1
vote
0answers
92 views

Finding a cellular automaton that reproduces a finite-sized spacetime patch with reduced coloration

Note: This question is an extension of: Computational complexity of finding a (1D deterministic) CA that achieves a desired spacetime history "patch" after $t$ iterations, which Marzio De ...
2
votes
1answer
128 views

Computational complexity of finding a (1D deterministic) CA that achieves a desired spacetime history “patch” after $t$ iterations

Question description: Consider the problem of finding a minimum $n$-color $k$-state one-dimensional cellular automata (minimizing $k$ for some fixed value of $n$ or vice versa), with communication ...
26
votes
4answers
2k views

Does a noisy version of Conway's game of life support universal computation?

Quoting Wikipedia, "[Conway's Game of Life] has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life." Do such ...
2
votes
1answer
264 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 ...
-3
votes
1answer
318 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
211 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 ...
2
votes
1answer
488 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
153 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
123 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
305 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
406 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
329 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
876 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 ...