Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

5
votes
0answers
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 ...
6
votes
1answer
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 ...
4
votes
1answer
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 ...
9
votes
3answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
0answers
109 views

A variant of the tiling problem

A classic tiling problem with Wang tiles has the form: Given $n$ tiles $T=\{t_1,...,t_n\}$ and some constraints $H,V\subseteq T\times T$, is there a way to tile a $w\times h$ rectangular grid with $...
1
vote
1answer
49 views

Data Mining of self-replicators

My current (very limited) understanding of the creative process that leads to the design of self-replicators is that any particular self-replicator, like Universal Constructor, Langton's loop or ...
8
votes
5answers
562 views

Are there any schools with researchers interested in cellular automata?

I have been working on an independant project focusing on cellular automata and was wondering if this might be something that I could continue on in graduate school somewhere. I've seen some ...
0
votes
1answer
144 views

Where is the proof of universality of Rule110 in Stephen Wolfram's book?

I have Stephen Wolfram's book A New Kind Of Science. And I want to find the proof of the universality of Rule 110. I couldn't find the clue in the contents page since it only shows 12 chapters and no ...
3
votes
0answers
208 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 life-...
1
vote
0answers
108 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
151 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 ...
29
votes
4answers
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 ...
3
votes
2answers
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 ...
-3
votes
1answer
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 ...
2
votes
2answers
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 ...
4
votes
1answer
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 ...
2
votes
0answers
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.....
1
vote
0answers
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 ...
4
votes
1answer
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 ...
5
votes
2answers
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. ...
6
votes
1answer
365 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 ...
15
votes
0answers
1k 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 ...