# 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
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 ...
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 \$...
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:...
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 & ...
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 ...
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 ...
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 ...
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
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...