Questions tagged [cellular-automata]
A computational model composed of a grid of stateful cells and a set of rules describing when to change a cell's state.
60
questions
1
vote
0answers
16 views
Intuition behind cellular automaton mixed bulking function?
I'm reading the paper of Nicolas Ollinger on intrisically universal 1d cellular automata: https://arxiv.org/abs/0906.3213.
On page 3 (201), he gave the definition for mixed bulking quasi order. I'm ...
1
vote
2answers
48 views
How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?
Consider cellular automaton rules for a two-dimensional universe with two states, where a cell's new state can depend on its previous state and the states of the cells in its Moore neighborhood. Such ...
4
votes
1answer
173 views
Langton's Ant Periodic Behavior
I was wondering if there's any initial configuration which generates a pure periodic behavior for Langton's Ant?
1
vote
1answer
63 views
Does any algorithm exist for computing the state of a non-trivial cellular automaton after an arbitrary number of time steps?
If have a cellular automaton, can I see the state of the board after something like $10^{{10}^{10}}$ time steps? For trivial cases, this is possible - for example, a cellular automaton where the state ...
1
vote
0answers
16 views
Do all Cellular Automata have some kind of information boundary? Can all Cellular Automata be modelled with the Bekenstein Bound?
Since they are discrete models, do they have some kind of information boundary? Can all Cellular Automata models be related to the Bekenstein Bound?
https://en.wikipedia.org/wiki/Bekenstein_bound
0
votes
0answers
55 views
Do Stephen Wolfram and Gerard 't Hooft propose that literally every cellular automaton is a universe?
Both Stephen Wolfram and Nobel laureate Gerard 't Hooft think that the universe is a cellular automaton.
As far as I know, 't Hooft developed a series of frameworks to build different models of ...
0
votes
0answers
33 views
Why can't we generate the output of a cellular automata at time step t without first generating all the preceding states
Why can't we generate the output of cellular automata at time step t without first generating all the preceding states? Why can we do this for some functions? What features of a function does it ...
0
votes
2answers
75 views
Is there any model of Game of Life compatible with hypercomputation?
I found a question in Mathematics Stack Exchange which asks a very similar question
(https://math.stackexchange.com/questions/1023812/hypercomputation-higher-dimensional-variants-of-conways-game-of-...
2
votes
0answers
60 views
Finding the final state of the $1$ dimensional “split the twos” automata
This problem is from a coding competition ( Website Here ) in Mexico that does not provide solutions and has me stuck.
Consider the following automata:
Every state $B_k$ is an array of fixed length $...
1
vote
1answer
57 views
How to create a cellular automata rule to achieve a desired pattern?
Normally, to find the rule that is suitable to our need, we have to generate all possible rules and apply each rule on a seed and check whether a rule produces a desired pattern. This method is ...
-3
votes
1answer
74 views
Is it there any computer/cellular automaton/brain to compute logically impossible and incomputable things? [closed]
Is it there any computer or cellular automaton or model of the brain where they could compute logically impossible things and incomputable things?
For example, if we wanted to compute/simulate/think ...
2
votes
0answers
84 views
Cellular automata for 2d cloud simulation
I want to build a cellular automata that simulates a behaviour that looks like clouds, that is: infinite and random cycles, pieces can gather or break apart, just like the image below:
My question is:...
0
votes
0answers
45 views
Is it possible to simulate oracle machines on 1-dimensional cellular automata?
My instinctual response is that it is possible, but I can't see how to simulate the oracle tape on a 1-d CA.
If not, are they able to be simulated on n-dimensional CA? My thought is that the oracle ...
0
votes
0answers
29 views
Pairing as opposed to cellular automata
The rule is that an isolated lit square in a grid of squares must be paired in the x-direction (either immed. left or right of it) AND y-direction. That is, from surrounding cells, the closest lit or ...
2
votes
0answers
50 views
In what sense can a cellular automaton be Turing complete? [duplicate]
The rule 110 cellular automaton is known (or claimed) to be Turing complete. But what exactly does it mean?
I do know what Turing completeness mean. Roughly speaking a language is Turing complete if ...
1
vote
1answer
43 views
Algorithm to estimate the probability that a “0 and 1 matrix” fills up following the bootstrap percolation rules
Presentation of the model: we consider the regular lattice created from $\mathbb{Z}^2$ (It's no more, no less a square lattice).
At $t=0$, each site is said "active" independently with a probability $...
1
vote
1answer
339 views
How 2d cellular automata rules works?
How 2D Cellular Automata rules sequences works?
For example, in elementary cellular automata, when we look at the binary sequence of the rule number, we understand that first bit says if all neighbors ...
0
votes
1answer
86 views
Classes of outer totalistic cellular automata
I'm wondering if anyone knows of any place where the Wolfram classifications of many outer totalistic cellular automata have been catalogued. The classes of a few examples are given in A New Kind of ...
3
votes
1answer
1k views
Turing-completeness, Conway's Game of Life and Logical Gates
I was recently given an assignment at university asking me to discuss the universal computational capability of Conway's Game of Life.
I'm not required to actually build up a Universal Turing machine ...
0
votes
0answers
29 views
Binary arrays for cellular automata
Where can I download some interesting cellular arrays for Conway's Game of Life? Arrays such as the Gosper glider gun, etc? I can find the images easily enough, but are they available somewhere in ...
0
votes
1answer
45 views
Need introductory guide to cellular automata for geographic automata systems
I would like to work on urbanisation and I've read that cellular automata has potential use on model urban sprawl. However I need some kind of introductory to cellular automata in order to tackle an ...
6
votes
0answers
58 views
Is there any field that studies the equivalent of cellular automata, but for arbitrary graphs rather than 1D cells?
A cellular automaton consists of a sequence of cells, each with a state, and a globally symmetric transition rule based on the neighbors of a cell. They can be interpreted as graphs where each cell is ...
1
vote
1answer
73 views
Simple elementary cellular automata with high period?
I'm looking for a simple rewrite system which displays high period.
In order to do that, I've ran a brute-force search on every elementary cellular automata, for a few fixed memory lengths ...
2
votes
1answer
22 views
How to identify strongly confluent cellular automatas?
Lets represent a class of cellular automata as a finite, unidimensional bit array state : [Bit], plus a rewrite rule ...
2
votes
1answer
52 views
Is there any count-preserving cellular automata which tends do “10101010…”?
Suppose that I have a bit string of finite length. Is there any bit rewriting rule rewrire :: (Bit,Bit,Bit) -> (Bit,Bit,Bit), that doesn't change the total count ...
5
votes
1answer
117 views
What does Cellular Automata Pre-image problem actually means?
I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata.
In the 2nd page he lists three NP-Complete ...
3
votes
1answer
234 views
Complexity of $n \times \log n$ tiling problem
Is there a polynomial time algorithm for an $n \times \log n$ tiling problem?
For instance: Suppose $A$ is a finite alphabet. A tile is a $2 \times 2$ matrix of elements from $A$. A tiling is a ...
10
votes
1answer
414 views
Is the halting problem decidable for 3 symbol one dimensional cellular automata?
I've been trying to figure out if the halting problem is decidable for 3-symbol one-dimensional cellular automata.
Definition Let $f(w,i)$ denote the configuration of the system at time step $i$. ...
1
vote
2answers
223 views
Consistent Simulation of Cellular Automata on Infinite Grid
Let's say that you have an infinite grid of cells.
A program is run per cell, where you have read access to some finite number of cells (for the previous state in time), but you only have write ...
5
votes
1answer
291 views
How rule 110 would be proven to be universal if the tag system did not exist?
I was reading about Cellular Automata and I read in this question that
Matthew Cook proved that rule 110 is universal, and that his proof relied upon showing how rule 110 can simulate a tag system. ...
2
votes
1answer
144 views
Are Cellular Automata always computers?
I was reading on Complex Systems journal and found a paper where the author states that a cellular automaton can be viewed as a computer.
In the introduction part:
Cellular automata can be viewed ...
3
votes
1answer
149 views
Why some rules in Elementary Cellular Automata halt and others don't?
I was looking over stephen wolfram's work mainly about Elementary Cellular Automata, i see that for all rules with N steps {i.e 200 steps} they show the same pattern {i,e rule 90 running on 20 steps ...
2
votes
1answer
43 views
Is there a similar categorization to Elementary Cellular Automata?
Elementary cellular automata show different systems and fractals like rule 30, rule 90, and rule 110. I want to know if there is another classification or type which shows similar structures just like ...
3
votes
1answer
43 views
What is the relation between universality and chaotic behavior in Elementary Cellular Automata?
So i know that rule 110 from Elementary Cellular Automata is universal but i am wondering if we had other chaotic behaviors let's say there exists a system that shows nearly infinite chaotic behaviors ...
5
votes
1answer
962 views
What is the difference between computational model, model of computation and a computer?
I was browsing the forum where i came by this question, it says that rule 110 from {ECA} is a computation model.
What is the difference between a computation model and model of computation and how ...
0
votes
1answer
135 views
What is the relation between pure mathematics, applied mathematics and Cellular Automata?
I was reading about pure mathematics and I am wondering if there is a relation between it and Cellular Automata.
Broadly speaking, pure mathematics is mathematics that studies entirely abstract ...
2
votes
0answers
28 views
What is the relation between Universality and simulations of Cellular Automata structures?
Elementary Cellular Automata and Conway's Game of Life show interesting Cellular structures, suppose we have a computational model {a Cellular Auotmaton} that can simulate both CA types (ECA & ...
4
votes
2answers
117 views
How Cellular Automata is related to Automata Theory?
I have read about Automata Theory where it is about the study of abstract machines and automata.
And i know that an abstract machine takes the input, process it and create the output, just like ...
2
votes
0answers
39 views
What is the relation between Universality and Geometric shapes in cellular automata?
When wolfram described Elementary Cellular Automata, most of the rules appeared as triangle and lines.
Now, Rule 110 consists of triangles which is proved to be universal.
Is there a relation ...
6
votes
2answers
283 views
How to prove universality in complex systems?
I'm working on my graduation project for CS, which is about cellular automata. Recently, i was able to build a system where the input is transferred to multiple different structures at once. The ...
2
votes
1answer
338 views
Does solving mathematical equations with Cellular Automata structures means it is universal?
I'm working on a research about Elementary Cellular Automata (ECA), and i found a method to build a system that can solve mathematical equations by using a specific cellular automaton structure.
The ...
2
votes
1answer
88 views
Can a cellular automata structure simulates another cellular automata structure?
In Elementary Cellular Automata, rules can show one pattern, but i am wondering if there is something where a cellular automata structure can simulate another structure?
Is there a category for this ...
6
votes
2answers
325 views
Are Elementary Cellular Automata structures considered to be fractals?
I know that a fractal is a non ending pattern, like Pascal's triangle or Sierpinski's triangle, which are the same as Rule 90 from Elementary Cellular Automata.
But, what about the other rules from ...
5
votes
3answers
365 views
Are deterministic and nondeterministic Cellular Automata equivalent?
It seems that in CA context nondeterministic (ND) means probabilistic, not ND as in NFSMs. At least I haven't seen a paper or book which discusses NCAs, without talking about probabilistic CAs.
I ...
0
votes
0answers
70 views
Immutable data structures for 2d+ lattices
I would like to find an immutable/persistent data structure that allows efficient updating for 2d (or higher) lattices/arrays/matrices, and reasonable performance when appending in any direction. ...
1
vote
1answer
77 views
Which cellular automata rules are suitable for randomizing an input sequence?
S. Wolfram has in has book "A New Kind of Science" listed 256 simple rules of cellular automata. Which of these rules could via iteration essentially contribute to render an input sequence more random ...
5
votes
2answers
199 views
Is the number of inequivalent elementary cellular automata rules really 88?
Everywhere from Wolfram's "New Kind of Science" (p. 57) to Wikipedia they say that, out of all possible 256 (=2^8) elementary cellular automata rules, 88 are inequivalent (as defined in the Wikipedia ...
1
vote
1answer
92 views
How to synchronize a 2d cellular automaton in $\Theta(\sqrt{n} \log n)$ steps
Let's assume we have given a two dimensional cellular automaton with an initial configuration where alls cells are in an quiescent state, expect for one square of cells. Let $n$ be the number of cells ...
2
votes
0answers
516 views
How to simulate a cellular automaton via a Turing machine
It is rather easy to see that every cellular automaton can be simulated by a Turing machine: We can simulate a cellular automaton with an appropriate C program and every C program can be simulated by ...
1
vote
2answers
94 views
Cellular Automata Using Small Boards
I'm working on making patterns for a digital lava lamp (essentially, making interesting patterns using a 4x10 grid), and I've been looking into cellular automata. I tried implementing some variations ...
