The tag has no usage guidance.

learn more… | top users | synonyms

3
votes
0answers
414 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 ...
7
votes
2answers
128 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 ...
1
vote
2answers
23 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) ...
5
votes
1answer
181 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
16 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 ...
11
votes
3answers
184 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 ...
0
votes
0answers
19 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
29 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
18 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
23 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 ...
2
votes
0answers
15 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 ...
1
vote
1answer
90 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 ...
4
votes
4answers
885 views

Conway's game of life variations

Is there any known two-dimensional Conway's game of life variation where each cell can not be just on/off but able to hold more states, maybe 4 or 5?
1
vote
1answer
58 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 ...
0
votes
1answer
52 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 ...
4
votes
1answer
91 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
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
93 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
602 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 ...
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
120 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 ...
4
votes
1answer
113 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)$ ...
1
vote
2answers
126 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 ...
2
votes
1answer
54 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. ...
2
votes
2answers
155 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, ...
1
vote
2answers
100 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 ...
2
votes
1answer
99 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 ...
0
votes
1answer
37 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
101 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
58 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 ...
-2
votes
0answers
43 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
130 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
111 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
110 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
759 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 ...
11
votes
0answers
245 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 ...
6
votes
2answers
228 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 ...
1
vote
1answer
147 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?
0
votes
1answer
712 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 & ...
3
votes
1answer
346 views

Proving Turing Completeness by Simulating Rule 110

Something I've heard often is that Rule 110 is the `simplest' Turing-complete formalism. As a programming exercise in a language I am new to, I implemented a function that computes from an initial ...
2
votes
1answer
222 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 ...