Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [cellular-automata]

For questions on cellular automata, a discrete model consisting of a regular grid of cells.

2
votes
1answer
49 views

Is Langton's Ant really Turing Complete

I recently watched a Numberphile video about Langton's Ant (and the extra footage). They mention that the ant always ends up creating a highway at some point in all the initial board configurations ...
3
votes
0answers
61 views

Infinitesimal Cellular Automaton

I thought about how a continuous (in time and space, but not in states) cellular automaton could look like. The most straightforward generalization which came to my mind is the following: Let $(X,*)$...
0
votes
0answers
39 views

Dimensionality of a Graph

In the past I have used stochastic cellular automata to evaluate chemical systems, with a 2D grid where each state corresponds to a chemical entity, the transitions are defined by certain chemical ...
0
votes
0answers
24 views

Absolute oscillator in Langton's Ant

We have a simple (or single) block of Langton's Ants colony which includes two ants looking in the same direction. Their positions can be interpreted as knight's walk. The distances between each next ...
1
vote
0answers
35 views

Open problems in Cellular Automata field

here there is a link on Wolfram about 20 open problems of CA theory. Has anyone of them been solved or tested? I'm searching for literature.
3
votes
1answer
67 views

What reversible cellular automaton rule emulates all 256 Wolfram rules?

On page 648 of A New Kind of Science, there's a definition of a "universal" cellular automaton, which can emulate Wolfram's 256 elementary cellular automata. Furthermore, it emulates them in a "cell-...
4
votes
0answers
80 views

Reflector in Conway's Game of Life on Triangular Tessellations

Back in 1994, Carter Bays reports in "Cellular Automata in the Triangular Tessellation" that there are at least 6 Games of Life (GL) living on triangular tessellations. A GL has at least one glider (...
0
votes
0answers
23 views

The distribution for infinite simple symmetric random walks

I've written a program that takes a 2d grid of ints and takes a time step by having an int distribute each "particle" it contains randomly in the surrounding cells of the grid (so if i have a point on ...
2
votes
0answers
91 views

Project ideas on Chaos theory, Cellular Automata, Fractals, Games, IA [closed]

I'm a computer science student and I need to find a final year project. What interests me the most is Chaos, IA, Games, Fractals, CA.. Something I liked was the chaos theory within sudoku. The ...
4
votes
1answer
105 views

Find minimal number of elements in matrix.

Consider a $A \in Mat_{n}(\{+1,-1\})$ (square matrix consisted of +1,-1). Now we can make and operation majority , i.e. $a_{i,j} = $ median of his neighborhoods(closest elements around him, i.e. ...
1
vote
1answer
36 views

Clustering computation in pair approximation model

Let's consider a square lattice of cells. Each cell can be either occupied by a species (1 or 2) or be empty (0). Each cell can be either in state 1, 2 or 0. In the pair approximation model, I ...
3
votes
0answers
102 views

Similarities of CA Rule 150 and Odd Collatz-function outputs

I made a "discovery" a couple of weeks ago in regards to the first iterates of (odd) numbers of the form $2^n-1$ where $n\in\mathbb{N}$. First iterates is a bit loose term here; what I mean is all of ...
4
votes
1answer
132 views

Contributing to a unsolved problem and writing a paper about it

How do I write a paper on the Collatz Conjecture without fooling or making an ass out of myself? Im not affiliated to any University at the moment (my past Uni was like 20 years ago, but I didnt ...
0
votes
0answers
182 views

Cellular Automata on the Collatz Conjecture

I have a Cellular Automaton that of any initial integer (initial condition of the automaton) generates states of Collatz sequences. The neighbourhood of the automaton is shaped like an L-tetromino (...
18
votes
2answers
363 views

How to translate mathematical intuition into a rigorous proof?

I've seen a lot of questions about how to develop mathematical intuition, but often I have the opposite problem. Several times I have run into a situation where I want to solve a math problem, and I ...
1
vote
0answers
32 views
0
votes
0answers
48 views

How to interpret wolfram rule 108 as a simplified populationmodel

I have made a Matlab-program as to iterate wolfram-rule 108 on any chosen begin situation. However my question is how this rule can be interpreted as a simplified version of a population model. (...
5
votes
1answer
137 views

Mandelbrot and Julia fractals for $z_{n+2} = z_{n+1}^2 + z_n^2 + c$

The Mandelbrot and Julia type fractals are very Well known. But such fractals follow from $$z_n = f(z_{n-1},c)$$ In other words a recursion that only depends on the previous value and a constant. (...
3
votes
1answer
47 views

Second-order Cellular Automaton definition

What does second-order term mean in a Cellular Automaton? I read on second-order cellular automaton (wikipedia) that a second-order has two time-states, but does the definition of an order mean the ...
2
votes
3answers
54 views

In the linked image, why does a pattern form, as opposed to random noise?

Image in question This image was generated line by line, with each pixel's value determined by a set of rules: If the pixel is on the edge, set to the same color as the previous pixel 1 away from ...
6
votes
1answer
124 views

Does Day and Night on a Klein bottle have a steady state?

Place a $m \times n$ ($m,n \ge 3$) square grid on a Klein bottle. On each square, we select an arbitrary non-mirror symmetric marker, and arrange them on the Klein bottle in some way. This arrangement ...
0
votes
1answer
64 views

Population Preserving Cellular Automata

Let's consider the class $CA$ of cellular automata where a cell is thought to exist in the $2$-dimensional grid ${\bf Z}\times{\bf Z}$, has binary states and the usual neighbourship relation of of ...
2
votes
1answer
70 views

How does a cellular automaton “know” when to halt?

I came across the (proven) claim that the cellular atomaton "rule $110$" is universal, meaning that it can do every calculation in principle. But to calculate a result, the automaton must "halt" ...
1
vote
0answers
43 views

Simplest universal cellular automaton

Is there more simple one-dimensional universal CA than Rule 110? One where next state of cell is determined not by 3 but by 2 cells?
1
vote
0answers
28 views

Average time bootstrap percolation

Presentation of the model: we consider the regular lattice created from $\mathbb{Z}^d$. At $t=0$, each site is said "active" independently with a probability $p$, "inactive" otherwise. At $t$, if a ...
0
votes
0answers
50 views

Invertibility of Cellular Automata over $A^G$ for locally finite G.

This is an exercise from "Cellular Automata and Groups" by T. Ceccherini-Silberstein and M. Coornaert. Let $G$ be a locally finite group and let $A$ be an arbitrary set. Let $\tau: A^G \rightarrow A^...
1
vote
0answers
79 views

Any good reference for start in Cellular Automata?

The question is as simple as the title. I want to know more about Cellular Automata, and his applications in Chemistry and Biology. I have read that, maybe, there is a relation of the topic with Graph ...
3
votes
1answer
117 views

How to show that the probability that $\mathbb{Z}^d$ is internally spanned is equal to 1? (bootstrap percolation)

Presentation of the model: we consider the regular lattice created from $\mathbb{Z}^d$. At $t=0$, each site is said "active" independently with a probability $p$, "inactive" otherwise. At $t$, if a ...
4
votes
1answer
51 views

Are there injective maps from a higher- to a lower-dimensional cellular automaton?

Suppose we have a cellular automaton on $\mathbb Z^n$ with cell values in the finite set $V$, with update function $u : V^{\mathbb Z^n} \to V^{\mathbb Z^n}$, and similarly another cellular automaton ...
1
vote
0answers
57 views

Chaos in discrete space and time systems. Definition, tests, etc?

I have been working with a cellular automata model and have been struggling to characterize its dynamics. It seems to be displaying aperiodic behaviour in a certain part of the parameter space, but I ...
3
votes
2answers
892 views

Expanding Nebula: Problem in Cellular Automata or Coding Theory

First post to Math Stackexchange. Recently I was posed with a mathematically intensive computer programming challenge that I am completely at a loss for solving. To give you some info on my math ...
3
votes
1answer
331 views

Real life application of Conway's Game of life

Does Conway's Game of Life has any real life application? I mean applications that are used today. If so, please add references, because I couldn't find anything, except for some hypothetical ...
7
votes
2answers
169 views

How can I prove that Game of Life's evolution function is continuous?

Conway's Game of Life is a cellular automaton, but also a discrete dynamical system. In all the papers, books, notes I have read on it, it is never never never shown that its evolution function is ...
1
vote
1answer
139 views

How do I find the rule number for a cellular automata rule?

I have been given a rule for a cellular automata (in which so long as one adjacent cell is living but not both the next generation lives), but I can't find any reference works on cellular automata ...
1
vote
0answers
38 views

What mathematical concept captures the idea of a one-way or unidirectional space or operation?

There are lots of places where we encounter one-way operations where there is a defined way "forward" but no way to really go "backwards". I can think of a number of examples but the so called "arrow ...
3
votes
0answers
86 views

Vice-versa Erdos conjecture

Erdos conjectured that, except $1, 4$ and $256$, no power of $2$ is a sum of distinct powers of $3$. A vice-versa conjecture may be: except $1$, $9$ and $81$ all powers of $3$ contains two ...
2
votes
1answer
165 views

Binary cellular automata and computable functions

1) Let's consider a set of all binary cellular automata on a finite (and finite dimensional) rectangular* grid. The state of a cell in the next generation is determined by the state of the cell ...
2
votes
0answers
50 views

Cellular bases of the symmetric group $KS_n$

Let $S_n$ be the symmetric group on the set $\{1,2,\ldots,n\}$ and $K$ a field of characterize $0$. The definition of cellular algebra refers to https://en.wikipedia.org/wiki/Cellular_algebra . I ...
3
votes
1answer
193 views

What methods are known to visualize the patterns of fractal sequences?

Trying to find ways of visualizing the patterns of a fractal sequence, I managed to convert a sequence to an elementary cellular automaton in which the first status (or step) of the automaton ...
1
vote
0answers
57 views

Calculate Density of Values in Cellular Automata

I am working with a special cellular automata that uses hexagonal cells rather than square cells, a hexagonal grid, rather than a square grid, and the set of complex numbers, rather than a finite set, ...
0
votes
1answer
1k views

What counts as a “Neighbor” in Conways' game of life?

I have looked everywhere but I cannot find an answer for this. Since I am bored, I am trying to create this game, but I can't seem to figure out what is considered a "Neighbor". Is it only directly ...
8
votes
2answers
334 views

Irrational numbers generated by a deterministic cellular automaton?

If we consider a simple 1D cellular automaton (acting on a binary string) and record a value at a fixed position in the string, we can interpret the recorded sequence as a binary number. Most simple ...
5
votes
1answer
221 views

Is there a possibility to determine/ estimate the topological entropy?

By $E$, denote the set of excited states $E=\left\{1,2,\ldots,e\right\}$ and by $R$ the set of refractory states $R=\left\{e+1,e+2,\ldots,e+r\right\}$. By $0$, denote the equilibrium state. The ...
2
votes
0answers
303 views

Why does this cellular automaton generate circular patterns?

I made a kind of cellular automaton game with the following rules. Each cell in a rectangular grid has a "water level" (a 32-bit floating-point number). In the next generation, water "flows" from each ...
1
vote
1answer
118 views

Free Gliders for Everyone?

According to Feynman's Lecture on Computation (Problem 5.1, p. 148 ) you can extract $E=kTN\log 2$ out of two copies of a random $N$ bit random tape. From this we can conclude that it takes the same ...
2
votes
0answers
75 views

Asynchronous XOR cellular automata and complexity

I've been experimenting a bit with what I think is the simplest possible CA-like rule that generates complex patterns and behaviors: https://eloquence.github.io/elixor/ Essentially, I define an ...
5
votes
2answers
2k views

what are the practical uses of “game of life” or “langton's Ant”

A few questions: Besides looking really cool, what are the practical uses of "game of life" or "langton's Ant"? I understand how agent-based modeling itself is a potentially useful methodoly, not how ...
1
vote
1answer
505 views

Alphabets of Turing Machine

I'm not completely sure about equivalence of two definitions of Turing machine. The first one states that Turing machine has a finite alphabet $\Sigma$, set of states and some rules. Turing machine ...
4
votes
1answer
112 views

How long before the prey can escape?

I've (sort of) come across the following problem in my research. The actual scenario is a little abstract to explain, so I'm rephrasing the problem in terms of a predator/prey scenario. I'm tagging ...
0
votes
1answer
82 views

Is there a theory for cellular automata propagating signals in straight lines?

Is there a theory explaining how a cellular automata can propagate signals in straight lines? For example, this video shows how some "signals" travel down at a diagonal, even though they are composed ...