The tag has no usage guidance.

learn more… | top users | synonyms

4
votes
1answer
78 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
35 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
56 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 ...
4
votes
0answers
56 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
55 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
171 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
61 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
24 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
57 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
96 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 ...
2
votes
1answer
76 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
31 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
46 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
65 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
88 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
90 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 ...
2
votes
2answers
127 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
32 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
91 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
57 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 ...
1
vote
2answers
98 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
0answers
327 views

Modern mathematical theory on Neural Networks, Cellular Automata, Neuroscience

Is it possible for someone to do research on Neural Networks/Cellular Automaton/Neuroscience as an applied mathematician, for its theoretical development, especially based on some modern mathematics, ...
-2
votes
0answers
42 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
121 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
65 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
103 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
106 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
548 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
131 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
207 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 ...
10
votes
0answers
212 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
617 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
138 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
187 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 ...
3
votes
1answer
307 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 ...