# Tagged Questions

The tag has no usage guidance.

83 views

### When do cellular automata on non-abelian groups not offer a computational speed up?

Suppose that $G$ is a finitely generated group and $A$ is a finite set. Then we shall give $A$ the discrete topology and $A^{G}$ the product topology; in particular $A^{G}$ is compact and totally ...
132 views

### Does there exist a polynomial time algorithm to determine whether an equation is a consequence of (x+y)*(y+z)=(x*y)+(y*z)?

Consider the identity $C$ $$(x+y)\times(y+z)=(x\times y)+(y\times z).$$ Is the problem of determining whether an identity is a consequence of $C$ in universal algebra a polynomial time problem? This ...
317 views

### Why don't the critters ever age?

So the two-dimensional reversible cellular automaton Critters (which you can simulate online at https://dmishin.github.io/js-revca/index.html#) on the Torus does not seem to follow the second law of ...
253 views

### Class of languages recognizable by single-tape 3-state TMs

I have for a while been curious about Turing Machines with exactly one tape and exactly 3 states (namely the start state $q_0$, the accept state $q_{accept}$, and the reject state $q_{reject}$). Note ...
68 views

### Is there a DCSL that cannot be recognized in O(n^2) steps by a deterministic LBA?

Is there a context sensitive language $L$ so that $L$ cannot be recognized by a deterministic linear bounded turing machine in $O(n^2)$ steps, but still can be recognized by a deterministic LBA? The ...
271 views

### Langton's ant questions

I'm a mathematician currently working on the Langton's ant conjecture, just for fun. I have some result but I don't know if they are meaningless. So that is why I'm asking. 1) Is there a mathematical ...
109 views

3k 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 ...
1k 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 ...
603 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 ...
337 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 looks ...
917 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 ...
182 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.: 111111.....
141 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 ...
342 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 ...
550 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. ...