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.
85 questions
1
vote
1
answer
27
views
Detecting Hole Creation in a Cellular Automaton
I'm working on a cellular automaton related to Diffusion-Limited aggregation where the simulation runs on a grid. Each cell is either EMPTY or FULL.
Once a cell transitions from EMPTY to FULL (...
- 13
0
votes
1
answer
49
views
Conway's Game of Life to expand QR code
If you use a QR code as a seed for Conway's Game of Life, and have information for
A) How many steps you should run it for, and
B) The size of the new square (where to put the border after you are ...
1
vote
1
answer
47
views
How to motivate freshman students towards automatic groups?
I'm a new professor and working at a computer science college. I'm going to be responsible for giving a one-hour lecture to motivate my students to study automatic groups.
I'm very experienced as a ...
- 111
0
votes
0
answers
22
views
How to motivate freshman students towards automata groups? [duplicate]
I'm a new professor and working at a computer science college. I'm going to be responsible for giving a one-hour lecture to motivate my students to study automata groups.
I'm very experienced as a ...
- 111
0
votes
0
answers
37
views
Trying to model HIV using cellular automaton but can't replicate the results of some paper
There is this paper in which HIV is modelled using cellular automaton. I am trying to replicate this work but I am not getting the same results as the authors. In this paper the authors describe the ...
- 1
0
votes
0
answers
98
views
Is game of life an example to halting problem?
I am working on a solution that can say if an initial composition is going to live forever or eventually die without calculating each generation until it reaches a stable or an ever-repeating cycle in ...
- 101
1
vote
1
answer
29
views
Can Sutner's (1991) quadratic algorithm for testing reversibility of Cellular Automata be applied to 1-D CA with even sized neighborhoods?
Admittedly I haven't fully wrapped my head around the paper yet, but I'm curious if this algorithm can be adapted to say, a one dimensional cellular automata with two states, and an even sized ...
- 153
1
vote
0
answers
93
views
What is a "universal" cellular automaton exactly, what does it look like to compute "anything"?
About a Universal Computer, this wiki says:
A universal computer in a cellular automaton is a system that can compute anything that a Turing machine can compute (another term for this is Turing-...
- 2,295
0
votes
2
answers
139
views
Why is Rule 110 considered "weakly" universal?
My supposition is that this is was more or less an automatic designation based on the fact that Rule 110 requires an infinite "background tiling" of the 14-bit sequence ...
- 306
2
votes
1
answer
71
views
Strategy for searching for elementary cellular automata (cyclic boundary conditions) that repeat
I am looking for elementary cellular automata rules and initial conditions that give rise to interesting cycles (Cyclic boundary conditions, such that the leftmost entry is the neighbour of the ...
- 23
2
votes
1
answer
114
views
Cellular automata on the Eisenstein integers?
Is there any cellular automaton on the Eisenstein integers? By this I mean that the triangles formed by the Eisenstein integers are considered as cells and each triangle has three neighbours plus ...
- 123
0
votes
2
answers
48
views
Difference between this grammar
I was reading a book and there is a part in which they use this grammar
$$
X \rightarrow xY $$
$$
Y \rightarrow yZ
$$
$$ Z \rightarrow z$$
$$ Z \rightarrow \lambda $$
and other times they use this ...
1
vote
1
answer
68
views
What is the meaning of conservative dynamics in the context of Conway's Game of Life
While reading up about Conway's Game of Life, I often come across the term conservative or non-conservative dynamics. What exactly does these terms mean?
My guess is that a certain quantity (e.g., ...
- 121
0
votes
0
answers
16
views
Textbook request for Linear Cellular Automata, if possible with an abstract algebraic approach
I am a final semester pure math undergrad, and I became interested in Linear Cellular Automatas.I became interested after reading Klaus Sutner's article. In the article, a little abstract algebra is ...
- 111
5
votes
0
answers
80
views
Complexity of still life extentions in Game of Life
The game of life is one of the most famous cellular automata in 2D. It has a variety of objects, some of them are moving like gliders, some have an oscillating behavior and others do not change at all,...
- 51
0
votes
0
answers
95
views
calculate kolmogorov complexity in the game of life
In order to calculate the Kolmogorov complexity one has to "count" the minimum amount of operations it takes for a certain task(from here). Since the game of life (or cellular automata) ...
0
votes
1
answer
586
views
What are the differences/relationship between 2D Turing Machines and Cellular Automata
I have been reading up on 2D Turing machines on wolframscience and I am kind of confused about what exactly is the relationship between 2D Turing machines (like Paterson's worm and Langton's Ant) and ...
- 103
1
vote
1
answer
212
views
Had Conway's Game of Life or any C-A been demonstrated to generate non-repeating pattern?
As we know, Conway's Game of Life is Turing-complete. And Turing-complete systems can be used to calculate irrational numbers such as $\sqrt{2}$, $\pi$, $e$, etc. which have non-repeating digits.
So ...
- 352
2
votes
2
answers
242
views
Whats the signifgance of Conway's Game of Life?
I've seen Conway's game of life mentioned in different circles and it seems many people (myself included) have made an implementation of it at one point or another. Other than the fact that it is ...
- 175
3
votes
2
answers
264
views
Is it possible to reverse engineer cellular automata?
Given a sequence of states of a given cellular automata, is it possible to construct the rules of the automata & hence predict the next state? To be clear, initially the rules are NOT known but ...
- 131
2
votes
1
answer
103
views
Generalization of Cellular Automata
So in the little I know about formalization of cellular automata, it appears there are 4 major categories of cellular automata:
1-dimensional (cellular automata on the line)
2-dimensional (cellular ...
- 2,295
3
votes
1
answer
679
views
Does P = NP in Cellular Automata of Hyperbolic Spaces?
I read a few years ago in this book that NP problems are tractable in the space of cellular automata in the hyperbolic plane. What does this mean? Does P = NP ...
- 2,295
2
votes
1
answer
138
views
2d cellular automata Wolfram binary codes
This is a similar question to How 2d cellular automata rules works?
However, the answer there did not provide me what I am looking for. Specifically, I want to be able to render these 2d cellular ...
- 23
5
votes
1
answer
482
views
Conway's Game of Life: Is it really P-complete?
Wikipedia claims that the Game of Life is P-complete (or the decision problem version of it is; the function version, I suppose, would then be FP-complete).
Colloquially, P-complete and FP-complete ...
- 153
0
votes
0
answers
63
views
What type of cellular automata is this?
So, this is kind of a long shot, but does anybody here familiar with cellular automata know what type this is? In the game, it starts as a flat pink/red and then becomes this over the course of a few ...
- 1
1
vote
0
answers
20
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 ...
- 11
1
vote
2
answers
205
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
1
answer
322
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?
- 43
1
vote
1
answer
79
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 ...
- 133
1
vote
0
answers
21
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
- 111
0
votes
0
answers
242
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 ...
- 1
0
votes
0
answers
40
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 ...
- 101
0
votes
2
answers
127
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
0
answers
63
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 $...
user26358
1
vote
1
answer
82
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 ...
- 13
-3
votes
1
answer
83
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
0
answers
176
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:...
- 264
0
votes
0
answers
59
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 ...
- 131
0
votes
0
answers
37
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
0
answers
57
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 ...
- 121
2
votes
1
answer
66
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 $...
- 229
1
vote
1
answer
719
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 ...
- 119
0
votes
1
answer
109
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 ...
- 103
4
votes
2
answers
3k
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 ...
- 215
0
votes
0
answers
35
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 ...
- 216
0
votes
1
answer
52
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 ...
- 3
7
votes
1
answer
123
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 ...
- 4,159
1
vote
1
answer
97
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 ...
- 4,159
2
votes
1
answer
27
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 ...
- 4,159
2
votes
1
answer
60
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 ...
- 4,159