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.

17 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
0answers
170 views

Time Complexity of Simulating CA with TM

This question is a follow up to the question: Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines. To simulate a CA with a TM, I used a construction which placed a marker on ...
2
votes
0answers
61 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 $...
2
votes
0answers
95 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:...
2
votes
0answers
29 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 & ...
2
votes
0answers
40 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 ...
2
votes
0answers
534 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
0answers
17 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
0answers
17 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
35 views

Why does symmetric starting patterns end up in symmetric ending structures?

Why every symmetric starting structures in the "game of life" end up to be symmetric as well / disappear completely? For example: Becomes: A lot of examples can be made ...
0
votes
0answers
31 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 ...
0
votes
0answers
26 views

Simulating general expressions in rule 110

Good afternoon today i was thinking of some interesting programming challenges and i thought back to conways game of life and the full 8 bit computers that people have emulated using the game of life. ...
0
votes
0answers
118 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
35 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
0answers
46 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
32 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 ...
0
votes
0answers
30 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
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. ...