Questions tagged [cellular-automata]
The cellular-automata tag has no usage guidance.
28
questions
4
votes
1
answer
172
views
Computation with cellular automata in practice
It is well known that certain cellular automata (CA) are computationally universal, such as Conway's game of life in 2 dimensions or the rule 110 in 1 dimension. As far as I know, they can emulate ...
7
votes
1
answer
144
views
Is the following restriction of cellular automata / tile assembly / CRN a known model?
Consider the following model: we work in the $d$-dimensional grid $\mathbb{N}^d$, and we have an alphabet $\Sigma$.
The initial cell $(0,\ldots,0)\in \mathbb{N}^d$ is marked with some letter $\Sigma$, ...
1
vote
0
answers
53
views
A proved computationally-irreductible function
In arXiv:1111.4121 and arXiv:1304.5247, Hervé Zwirn and Jean-Paul Delahaye propose a formal definition of computational irreducibility. Is there a (possibly artificial) function that can be proved to ...
6
votes
1
answer
160
views
What is the minimal class of subshifts for which conjugacy is known to be undecidable?
The question of whether two finite one directional shifts are conjugates is known to be decidable.
The same question for sofic shifts is famously open.
I have seen that some works manage to prove ...
2
votes
1
answer
644
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 ...
5
votes
3
answers
767
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.
...
4
votes
1
answer
91
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 ...
5
votes
0
answers
124
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
1
answer
177
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
1
answer
572
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
3
answers
3k
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
0
answers
92
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 ...
3
votes
1
answer
2k
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 ...
2
votes
0
answers
168
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 $...
8
votes
5
answers
1k
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
1
answer
174
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
0
answers
470
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-...
33
votes
4
answers
4k
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 ...
1
vote
0
answers
112
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
1
answer
172
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 ...
2
votes
2
answers
416
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 ...
-3
votes
1
answer
842
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 ...
5
votes
1
answer
1k
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
0
answers
198
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.....
6
votes
1
answer
422
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 ...
1
vote
0
answers
146
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
1
answer
380
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 ...
15
votes
0
answers
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 ...