The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
15 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
29 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 ...
0
votes
0answers
19 views

What is an automata network?

I've tried Wikipedia and Google as first steps, but while I've found some interesting papers and articles, and a couple expensive textbooks, I've yet to find a clear definition of an automata network ...
1
vote
2answers
25 views

Give a regular expression

Let Σ be {0, 1} Give a regular expression generating words over Σ containing an even number of 1’s or with a length which is multiple of 3. i came up with this solution: ε ( ((0*(10*10*)) + ((0+1) (...
7
votes
2answers
134 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 ...
0
votes
0answers
17 views

Preventing cars from leaving a crossroad in a cellular automata traffic simulation

I'm writing a traffic simulation using cellular automata based on this paper It states that the rule in the middle of the crossroad always stays the same (184), but that the cell after the crossroad ...
5
votes
1answer
184 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 ...
0
votes
0answers
21 views

Plotting the fundamental diagram of traffic flow

I have a traffic simulation and I don't understand how I can plot the fundamental diagram (flow rate vs density). I simulate the traffic as follows: I have a matrix that has as many columns as the ...
1
vote
0answers
33 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 ...
0
votes
0answers
19 views

Cellular automata orphan

Suppose we have 2-dimensional automata, with local rule(Moore neighbourhood): 0 if $a+b+c+d+f+e+g+h+i \leq 4$ 1 if $a+b+c+d+f+e+g+h+i \geq 5$ How to find orphan?
1
vote
1answer
107 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 ...
0
votes
0answers
26 views

Elementary Cellular Automata Rule 232

Rule 232 can be expresses as: $c_n=1$, iff $c_{n-1}+c_n+c_{n+1}\geq2$ {$c_n=0$ otherwise) Figured out its Wolfram number(rule), that would be as mentioned in topic - 232 Here is link for cloud....
2
votes
0answers
18 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 ...
2
votes
1answer
114 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 ...
1
vote
1answer
68 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
92 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
54 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 ...
0
votes
1answer
72 views

Watrous’s definition of Quantum Cellular Automata

I need some help understanding the second-to-last and final equations of the introduction to quantum cellular automata included below. My specific questions: What does it mean when the capital Pi ...
5
votes
0answers
73 views

Conway's Game OF Life maximum periods on a set x by x game board.

I have taken interest in Conway's Game of Life and want to know if you guys can help me with a mathematical problem :) That is what this website is for right? You need to be familiar with the rules ...
0
votes
2answers
97 views

online courses and books covering the theory of cellular automata

i would like to learn the theory cellular automata and know more about the research being done in this field and the links with other related fields such as artificial inteligence, computabilty and ...
1
vote
1answer
683 views

What do 2-dimensional cellular automata rules actually mean?

There is a certain 2d cellular automata I am particularly interested in. It is called "rule 52928". It's used by Wolfram | Alpha on the loading screen. But what exactly does the rule mean? Is it an ...
1
vote
0answers
65 views

Why are the $T^{3n}\mu$ Bernoulli-shifts, too? Can you clarify this?

Preliminaries: Definition of Bernoulli-shift Let $X=\left\{0,1,2\right\}^{\mathbb{Z}^d}$ and $\mathcal{B}$ the Borel-$\sigma$-Algebra on it. Moreover, let $\mu_{p_0,p_1,p_2}$ denote a Bernoulli-...
0
votes
0answers
26 views

Why does follow that $\eta_n\to 0$ in distribution as $n\to\infty$?

Following setting: Consider $\left\{0,1,2\right\}^{\mathbb{Z}}$. And on it the following dynamics: A site $x\in \mathbb{Z}$ represents a cell which can be 1, 2 or 0. A 1 becomes a 2 in the next time ...
0
votes
1answer
63 views

Proof of the Curtis-Hedlund Theorem: Why is there a function $\mu\colon A^S\to A$ such that $\tau(x)(1_G)=\mu(x_{|S})$ for all $x\in A^G$?

Here is the Curtis-Hedlund Theorem and its proof [the sets $V(\cdot,\cdot)$ used in this proof are explained below.]: My problem is I am not sure that I have understand that correctly. So I ...
4
votes
1answer
123 views

Is cellular automata something that is studied in mathematics departments?

I am interested in studying cellular automata but am unsure if I should be looking at CS or mathematics graduate departments. Symbolic dynamics seems to have some tie to cellular automata but I haven'...
4
votes
1answer
117 views

Good data structure for hyperbolic tiling

Say you're doing something computational where each data point is a tile in a (not necessarily Euclidean) 2-dimensional tiling, for instance, a Life-like cellular automata. You might want a data ...
0
votes
1answer
32 views

recursive automata, or recursion mod 2.

Consider the list of length $m$ $(1,0,\dots 0)$ we call this list $l_1$, we now define a sequence of lists recursively, where $l_1$ is the previous list, and if $l_n$ is the list $(a_1,a_2\dots a_n)$ ...
2
votes
1answer
58 views

Have $3$-dimensional cellular automata been studied at all?

Recently, I have become interested in the Game of Life and other similar cellular automata. I notice how these cellular automata operate in a square tiling on $2$-space, and it seems as if similar ...
5
votes
1answer
74 views

Writing in 1993, a researcher noted that it is hard to prove things about a cellular automata model - has this changed?

Leah Edelstein-Keshet in her 1993 article Cellular automata approaches to biological modelling writes: We do not believe that CA should be viewed as a replacement for rigorous mathematical models. ...
1
vote
2answers
102 views

Rigid spaceships in Conway's Game of Life

(1) Is it true that there are no rigid spaceships in Conway's Game of Life, i.e. spaceships with period 1 i.e. spaceships of constant shape (only allowed to rotate) of non-zero translational velocity? ...
2
votes
1answer
101 views

Are there cellular automata with “long range” rules?

Common cellular automata have rules that only check cells' immediate neighbours, in the current, immediate step. Have CA been explored that have rules that are "longer range" (spatially and temporally)...
2
votes
2answers
160 views

Garden of Eden States in Cellular Automata

I am just beginning to study cellular automata and I am having trouble understanding the so called Garden of Eden states. How can a deterministic algorithm wind up in a state that has no pre-image, ...
0
votes
1answer
38 views

Functions & Cellular automata

Let x = number of live neighbors of a cell $$f(x)=\left\{\begin{matrix} live & \textrm{if}\ x = 3\\ live & \textrm{if}\ x = 4\\ dead & \textrm{otherwise}\\ \end{matrix}\right.$$ $$f(1) ...
2
votes
0answers
102 views

Cellular Automata Method to Reach Equilibrium on a Network of Numbers

Here's a puzzle that I'm curious if anyone can attack with a simple method without resorting to simulation. I can tell you the answer (well, an answer) from running some programs. But I'm writing a ...
2
votes
1answer
60 views

Cellular Automata: Does there exist an initial group of cells in a square lattice which never zeroes out completely?

Fix a positive integer $k$. Given an infinite grid of squares, each of them is assigned a nonnegative integer value. Furthermore, only finitely many of these values are nonzero. Call this state ...
10
votes
3answers
193 views

Conway's Game of Life

Is there a mathematical way to directly calculate iteration n from the first iteration skipping calculating the iterations in between in Conway's Game of Life? I would assume, if it is possible, it ...
1
vote
2answers
134 views

The Relation of Cellular Automata to Languages

In Conway's Game of Life, would a cell be considered a deterministic finite automata? Is there a language for the automata, and would it be a regular language? In probabilistic cellular automata, are ...
3
votes
0answers
429 views

Modern Mathematical Theory for Neural Networks, Cellular Automata, Neuroscience

Is it possible for someone to do research on subjects like neural networks, cellular automata, or neuroscience as an applied mathematician? I have in mind the theoretical development of these fields,...
-2
votes
0answers
44 views

When is a cellular automaton “bidirectional”? [duplicate]

From this paper. "A (bi-directional, deterministic) cellular automaton is a triplet $A = (S;N;\delta)$, where $S$ is an non-empty state set, $N$ is the neighborhood system, and $\delta$ is the local ...
3
votes
2answers
132 views

When is a cellular automaton “bidirectional”?

From this paper. "A (bi-directional, deterministic) cellular automaton is a triplet $A = (S;N;\delta)$, where $S$ is an non-empty state set, $N$ is the neighborhood system, and $\delta$ is the local ...
1
vote
0answers
68 views

Amoebas and computation

Today I found out about amoeba based computing and optic computing in a popular math book In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation by William J. Cook. Searching ...
1
vote
1answer
112 views

Does Conway's Game of Life have attracting cycles (or equilibria)?

Is there a sequence $\:\langle S_0,S_1,S_2,...,S_{n-1},S_n\rangle\:$ of generations for Conway's Game of Life such that [$\hspace{.01 in}S_0 = S_n$ $\:$ and $\:$ $S_0$ has at least one live cell $\:$ ...
1
vote
2answers
112 views

Implications of the Period 43 stable reflector

Mike Playle has found the long-sought stable reflector in Life. It can recover from a reflection in 43 steps, which makes all oscillators of period 43 and above possible. What major things have been ...
2
votes
2answers
795 views

Are axioms and rules of inference interchangeable?

There is an equivalence between cellular automata and formal systems, you can code one into the other and vice versa. But in the the cellular automata (CA) the rules of inference are fixed and are ...
1
vote
0answers
133 views

Random spreading

Given an infinite grid of squares, some marked alive (which stay alive forever,) some marked dead at any time(like Conway's game of life) and 1 alive at the beginning, there is an algorithm. It starts ...
6
votes
2answers
232 views

Can SAT instances be solved using cellular automata?

I'm a high school student, and I have to write a 4000-word research paper on mathematics (as part of the IB Diploma Programme). Among my potential topics were cellular automata and the Boolean ...
11
votes
0answers
255 views

What turmite runs the longest before becoming predictable?

When looking at 2D Turing machines, many of them eventually become predictable. For example, Langton's Ant, the champion 2-color 1-state turmite, develops a highway after 10,000 steps. Predictable ...
0
votes
1answer
736 views

circuit in Conway’s Game of Life

Let's assume that the bits in the Moore neighborhood are numbere as follows: $$\begin{array}{lll} a_4 & a_3 & a_2 & a_{11}\\ a_5 & {\large a_0} & a_1 & a_{10} \\ a_6 & ...
1
vote
1answer
148 views

Moore neighborhood on a two-dimensional Cartesian lattice

How many distinct cellular automata rules are there that use the Moore neighborhood on a two-dimensional Cartesian lattice if we allow three bits (eight states) per site?
2
votes
1answer
225 views

2 dimensional cellular automaton for prime twins?

Is there a 'simple' 2 dimensional cellular automaton to generate all prime twins ? With 'simple' I mean not too many states per cell and not so many rules. Thus a universal turing machine equivalent ...