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.

Filter by
Sorted by
Tagged with
0 votes
2 answers
45 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 ...
user avatar
1 vote
1 answer
59 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., ...
user avatar
  • 21
0 votes
0 answers
12 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 ...
user avatar
5 votes
0 answers
65 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,...
user avatar
0 votes
0 answers
27 views

Calculate complexity of game of life(cellular automata) [duplicate]

I want to calculate the kolmogorov complexity of n evolution of a game of game of life(game of life is a kind of cellular automata). I’m not searching for the complexity of a certain pattern of cells ...
user avatar
0 votes
0 answers
53 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) ...
user avatar
0 votes
1 answer
79 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 ...
user avatar
1 vote
1 answer
133 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 ...
user avatar
  • 151
2 votes
2 answers
109 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 ...
user avatar
  • 175
3 votes
2 answers
80 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 ...
user avatar
  • 131
0 votes
0 answers
26 views

How does the railway model of computation get translated to motion on the heptagrid tiling of the hyperbolic plane?

I have been reading these, along with slowly chipping away at the two books Margenstern has produced: A universal cellular automaton in the hyperbolic plane A Universal Cellular Automaton on the ...
user avatar
  • 1,853
2 votes
1 answer
50 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 ...
user avatar
  • 1,853
3 votes
1 answer
566 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 ...
user avatar
  • 1,853
2 votes
1 answer
74 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 ...
user avatar
5 votes
1 answer
132 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 ...
user avatar
0 votes
0 answers
54 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 ...
user avatar
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 ...
user avatar
1 vote
2 answers
136 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 ...
user avatar
4 votes
1 answer
208 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?
user avatar
  • 43
1 vote
1 answer
74 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 ...
user avatar
1 vote
0 answers
19 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
user avatar
0 votes
0 answers
192 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 ...
user avatar
  • 1
0 votes
0 answers
38 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 ...
user avatar
0 votes
2 answers
98 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-...
user avatar
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 $...
user avatar
1 vote
1 answer
68 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 ...
user avatar
  • 13
-3 votes
1 answer
79 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 ...
user avatar
2 votes
0 answers
111 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:...
user avatar
  • 262
0 votes
0 answers
53 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 ...
user avatar
0 votes
0 answers
36 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 ...
user avatar
2 votes
0 answers
55 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 ...
user avatar
  • 121
2 votes
1 answer
55 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 $...
user avatar
  • 209
1 vote
1 answer
541 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 ...
user avatar
  • 119
0 votes
1 answer
92 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 ...
user avatar
4 votes
2 answers
2k 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 ...
user avatar
0 votes
0 answers
33 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 ...
user avatar
  • 216
0 votes
1 answer
46 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 ...
user avatar
7 votes
1 answer
97 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 ...
user avatar
  • 4,017
1 vote
1 answer
85 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 ...
user avatar
  • 4,017
2 votes
1 answer
24 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 ...
user avatar
  • 4,017
2 votes
1 answer
56 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 ...
user avatar
  • 4,017
5 votes
1 answer
183 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 ...
user avatar
3 votes
1 answer
291 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 ...
user avatar
10 votes
1 answer
489 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$. ...
user avatar
  • 1
1 vote
2 answers
371 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 ...
user avatar
  • 1,320
5 votes
1 answer
363 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. ...
user avatar
2 votes
1 answer
190 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 as ...
user avatar
  • 171
3 votes
1 answer
190 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 ...
user avatar
  • 49
2 votes
1 answer
52 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 ...
user avatar
3 votes
1 answer
47 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 ...
user avatar