Questions tagged [cellular-automata]

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

Filter by
Sorted by
Tagged with
3
votes
0answers
38 views

barriers/membranes in Conway's Game of Life

Has anyone working on Conway's Game of Life found a way to create barriers which divide zones, ideally between a potentially chaotic "outside" and a structured inside, which could then ...
4
votes
2answers
104 views

On the growth rate of Conway's game of life.

I'm reading a book in which Conway's game of life is mentioned: the author states that it can be proved that the growth rate cannot be exponential but it's at most quadratic. Can someone suggest me ...
0
votes
1answer
70 views

how universal is Conway's game of life? is it reasonable to expect that a technological alien civilization would recognize, say, a glider?

This is a philosophical one, so apologies if it's not appropriate. I can think of several reasons that Conway's Game of Life would be rediscovered by any mathematically inclined biological life forms. ...
0
votes
0answers
18 views

Inversible turing complete cellular automata are easily inversible so why we can't inverse any inversible programme with them?

From what i've read: inverse of inversible cellular automata is also cellular automata (i wanted to prove that but sadly i'm 40 years late), so easily inversible; and inversible turing complet ...
11
votes
2answers
326 views

What is the maximum "alive density" of cells in Conway's Game of Life when played on a torus?

I've read that Conway's Game of Life (CGOL) can have unbounded growth from a finite initial number of alive cells (e.g. a glider gun). However, if CGOL is played on a torus, space (the number of cells)...
114
votes
7answers
10k views

Is black hole pattern possible in Conway's Game of Life that eats/clears everything?

Is black hole pattern possible in Conway's Game of Life that eats/clears the infinite universe plane ? Formally, is there a pattern that satifies following requirements? The pattern has finite size. ...
1
vote
0answers
27 views

Periodic columns in asymmetrical 1D cellular automata?

Does anyone know of or is able to track down a 2-color, 1-D cellular automaton admitting an aperiodic initial configuration and a ruleset that is asymmetrical, and which has at least one (but not ...
2
votes
1answer
62 views

how many unique patterns can be made on a 4x4 grid accounting for rotational symmetry?

I was working with higher range Margolus cellular automata neighborhoods and i ran into a problem, how many patterns you can make in a 4x4 square grid if you consider rotationally symmetric patterns ...
1
vote
0answers
144 views

Is Rule 30 Turing complete?

Rule 30 is a well-known ECA. Wikipedia has a fine introduction to that topic if you're unfamiliar. Here's a 60-second version of the mechanism: Let $s_0 \leftarrow 1$. Let $s_{i+1} \leftarrow s_{i}00$...
16
votes
2answers
419 views

Infection spread on a torus chessboard

In one of his books, Peter Winkler includes the following problem: A disease is spreading on a $n\times n$ chessboard as follows: if a healthy cell is neighboring at least 2 infected cells, it becomes ...
2
votes
1answer
108 views

Dimension of the Cantor set in the context of cellular automata

I'm reading the book "Cellular Automata and Complexity" by Wolfram. On page 426 he gives a very intuitive picture showing why any cellular automaton state $\{0,1\}^\infty$, can be uniquely ...
1
vote
0answers
35 views

Can information transmission be proven in a Rule 30 ECA?

(This is hopefully a clearer version of an earlier post of mine.) I have been spending lots of time on the open challenge of proving the aperiodicity of the central column of a rule 30 cellular ...
0
votes
2answers
372 views

how can I prove that if I have a regular language L, that L' is a regular language

how can I prove that if I have a regular language L and I create a new language L' where L' = (L but with last letter repeated) (i.e. if ab is in language L then abb is in language L') that L' is a ...
1
vote
0answers
96 views

Are there impossible patterns in Conway's game of life?

Given a grid representing a state in Conway's game of life, if there is no pattern that leads to this state, this means that there exists a forbidden $N\times N$ pattern for some $N$. If so what is ...
1
vote
1answer
64 views

Cyclic cellular automaton with 3-neighborhood

Consider a 2D cyclic cellular automaton with randomized starting states and the usual von Neumann 4-neighborhood ruleset. It is well-known that this CA produces a stable and periodic state after a ...
0
votes
1answer
28 views

Doubt about developing the summation $\sum_{n=2}^{\infty}(n-1) \cdot 3^{2n-2}(1-\varepsilon )^{2n}$.

In the book "Contours, Convex Sets and Cellular Automata" (Andrei Toom), I've found the following: [...] the probability that there is no percolation does not exceed $\sum_{n=2}^{\infty}(n-...
1
vote
0answers
105 views

Random processes on coloured graphs

Let a random process on a $k$-coloured graph be any set of rules that determine how nodes change their colour probabilistically from time step to time step, depending only on the colours of their ...
0
votes
0answers
33 views

Using the rule stated below, is there a way I can plant trees on a 2D plane such that there are no trees in the first k diagonals? [duplicate]

This question was part of the problem set for PROMYS Europe 2020, a maths (or math, just in case I made anyone unhappy) camp held at Oxford every year. It was the one which I couldn't do, and I am ...
3
votes
3answers
211 views

How to create a non-square 2D grid with spherical topology.

When programming Conway's Game of life on my computer. A problem arises; how to deal with the borders on the board? Do the cells at the border have to take into consideration less neighbours than the ...
1
vote
0answers
74 views

is it possible to embed a fractal inside another fractal

I have been looking at one-dimensional (1D) cellular automata (CAs) which generate two-dimensional (2D) fractal patterns. Among the 256 1D elementary CAs, I tried to list down the fractal generating ...
3
votes
1answer
112 views

A basic transition automaton of ECA 30

I am reading this thesis, which on page no 14 talks about modeling. It also says in page no 15 that: The automata we construct to model the basic transition scan words over $\Sigma^2$, where $\...
2
votes
1answer
60 views

Elementary cellular automaton showing eventually periodic behavior after large number of iterations.

In this video: Cellular Automata and Rule 30 Stephen Wolfram talks about such an elementary cellular automaton at 17:01. Does anybody have an idea which one exactly he could be talking about?
1
vote
0answers
39 views

What is a periodic pattern in 1D Cellular Automata

What is a periodic pattern in 1D cellular automata? I have this 3-color, code 1599 rule and I can see that a certain generation can be grouped together by their similar or foreseeable pattern, then ...
1
vote
1answer
184 views

Is there any 3D patterns, if we are to stack up each generation of "Conway's game of life" on top of each other?

1D Cellular Automata do not show any interesting patterns if we look at each state only one at a time in Succession, but if we put each state below each other, we can see patterns emerging. In the ...
11
votes
0answers
1k views

Fractal Pattern from Queen's Move Construction

This question relates to the OEIS sequence A279212. Fill an array by antidiagonals upwards; in the top left cell enter $a(0)=1$; thereafter, in the $n$-th cell, enter the sum of the entries of those ...
2
votes
2answers
85 views

Name of these Sierpinski-like fractals?

A Sierpinski triangle can be created by Starting with a row consisting of a single 1 Each row below is horizontally offset by a half-cell Each cell is the sum-mod-2 of the two cells above it Now ...
1
vote
1answer
54 views

How does On/Off Reversal work in Life-Like Cellular Automata

I've recently been made aware of the concept of on-off rule reversal in life-like cellular automata. I understand the algorithm for calculating the rule reversal from a given rule. But I don't ...
2
votes
1answer
77 views

Are there any symmetries in rules of Life-Like Cellular Automata?

Life-like cellular automata have $2^{18}$ different possible rulesets, and I would like to test hypotheses/search through them all, however that's a lot of rulesets to test a simulation on, so I'm ...
0
votes
1answer
65 views

Prove that a recurrence for Rule 30 is: B2=MOD(A1+B1+(1+B1)*C1,2)

Prove that Rule 30 satisfies the recurrence: $$T(1, k) = [k = N]$$ $$T(n,k)=(T(n-1,k-1)+T(n-1,k)+(T(n-1,k)+1) T(n-1,+1+k)) \bmod 2$$ where [ ] is the Iverson bracket. ...
1
vote
1answer
82 views

Finding Life-Like Cellular Automata Rules and Initial States with Guaranteed Still End States

My goal is to find all rulesets of life-like cellular automata and initial states that, when simulated in a toroidal grid (although non-toroidal would be interesting as well) of arbitrary finite ...
0
votes
1answer
31 views

Trouble understanding proof in "Aperiodicity in One-Dimensional Cellular Automata" paper by Erica Jen

From the proof of page 7 in https://digital.library.unt.edu/ark:/67531/metadc1443182/m2/1/high_res_d/7230855.pdf (page 10 of the PDF): The fact that $R$ is injective in its $(i+1)$-th component (...
6
votes
0answers
108 views

Noether's theorem in SmoothLife?

Conway's Game of Life, being discretized in both space and time domains, has no locally conserved quantities. SmoothLife, however, is a generalization of the Game of Life to a continuous and spatially-...
1
vote
0answers
64 views

Simplest set of replacement rules which can include mathematical logic?

Things like the various Type Theories appear to be based on replacement rules of one kind or another. This got me thinking, what would be the simplest set of replacement rules (maybe even just one ...
2
votes
0answers
129 views

Are Cellular Automata models compatible with the Holographic Principle?

Cellular Automata are discrete models which have a regular finite dimensional grid of cells, each in one of a finite number of states, such as on and off. There are various scientists that have ...
3
votes
1answer
275 views

Cell state probabilities for a probabilistic version of Conway's Game of Life

I am given a version of Conway's Game of Life where each cell can be in any of 3 states: Dead (D), Alive (A) or Dying (X). The following transition rules exist: An Alive cell next to a Dying cell ...
0
votes
0answers
64 views

About Tegmark's mathematical universe

I'm not sure anyone else than Tegmark himself can answer this, but why not give it a try. Would Tegmark consider a cellular automata a mathematical structure? If nature is mathematical, isn't it also ...
4
votes
1answer
1k 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
104 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,*)$...
3
votes
0answers
173 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
183 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-...
5
votes
0answers
211 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 (GoL) living on triangular tessellations. A GoL has at least one glider (...
2
votes
0answers
214 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 ...
5
votes
1answer
114 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
48 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
186 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
191 views

Contributing to a unsolved problem and writing a paper about it [closed]

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 ...
1
vote
1answer
597 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
508 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 ...
0
votes
0answers
67 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
222 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. (...