The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
70 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
33 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
57 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
89 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
71 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
75 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
0answers
13 views

Is there a method of representing Neural Nets as fixed Length Bit strings?

Is there a method for representing neural nets as fixed length bit strings? If this is true then are there perhaps some elementary configurations like Stephen Wolfram's method for generating ...
0
votes
1answer
26 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
70 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
49 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 ...
0
votes
0answers
21 views

Pascal's triangle and Sierpinski triangle [duplicate]

Is there a formal proof that Pascale's triangle, coloring only the odd numbers, converges to a Sierpinski triangle? In other words: Is there any formal proof that the graph of Rule 90 Wolfram ...
1
vote
0answers
197 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
36 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
100 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
49 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
89 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
103 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
294 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 ...
9
votes
0answers
173 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 ...
5
votes
2answers
182 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
121 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
435 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
238 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
131 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 ...