# New Directions In Cellular Automata

Abdulrhman Elnekiti

► To cite this version:

Abdulrhman Elnekiti. New Directions In Cellular Automata. 2017. hal-01520747v2

HAL Id: hal-01520747

https://hal.science/hal-01520747v2

Preprint submitted on 7 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# New Directions In Cellular Automata

## Abdulrhman Elnekiti

Department of Computer Science
University of Turkish Aeronautical Association
11 Bahcekapi, 06790 Etimesgut - Ankara, Turkey
Email: Abdulrhman.Elnekiti@stu.thk.edu.tr

We Propose A Novel Automaton Model which uses Arithmetic Operations as the Evolving Rules, each cell has the states of the Natural Numbers $k = \mathbb{N}$, a radius of $r = \frac{1}{2}$ and operates on an arbitrary input size. The Automaton reads an Arithmetic Expression as an input and outputs another Arithmetic Expression. In Addition, we simulate a variety of One Dimensional Cellular Automata Structures with different Dynamics including Elementary Cellular Automata.

### 1. History & Overview

A Cellular Automaton (CA) is a Discrete Dynamical System which consists of Identical Cells, each cell has a defined number of states and the cells evolve according to a local rule in a defined number of iterations. CA was introduced by Von Neumann and Ulam [1] to model natural growth processes like Seashell and Snowflakes [2].

Stephen Wolfram has explored One-Dimensional CA where each cell has the states of [1 or 0], known as Elementary Cellular Automata (ECA) [3]. We propose an Automaton model that shows a variety of structures based on a specific arithmetic expression formed as the input.

### 2. Formal Description

A One-Dimensional Cellular Automaton consists of a finite row of cells, we define a cell $c$ and the Right-Most Neighboring cell as $c+1$, a radius $r$ and the possible states for each cell as $k$. The Automaton can be described by $r = \frac{1}{2}$ and $k = \mathbb{N}$, where it depends on the current cell $c$ and the next cell to it $c+1$, and each cell has the states of the Natural Numbers.

**Transition Function** : Let $c(i, t)$ denote the state of the $i$th cell at time $t$, the cell state in the next time step is defined by $c(i, t + 1)$
using the transition function $\delta$ :

$$c(i, t + 1) = \delta[c(i, t), c(i + 1, t)] \quad (1)$$

$$\delta = |c(i, t) - c(i + 1, t)| \quad (2)$$

$$c(i, t + 1) = |c(i, t) - c(i + 1, t)| \quad (3)$$

**Input Formation.** Let $P$ denote the input, $P \subset \{\mathbb{N}, -\}(*)$ where $\mathbb{N}$ is the set of The Natural Numbers, $(-)$ is the Subtraction Operation and the Asterisk defines a repetition of the Sequence of the elements, i.e. $P = [2-0-1-4]$, $P = [2-0-1-5]$ or $P = [2-0-1-6]$, for a better interpretation we define $P$ by default as $P = [2-0-1-7-0-4-7-8-9-0-9-8-7-4-0-7-1-0-2]$.

<figure><img src="image_2.png" /><figcaption>**Figure 1.** The Input $P$ And the First Resulting Iteration Written Under It Using $\delta$</figcaption></figure>

The blue circles describe that the resulting cell of any Two Continuous Cells is placed under it.

2-0-1-7-0-4-7-8-9-0-9-8-7-4-0-7-1-0-2
2-1-6-7-4-3-1-1-9-9-1-1-3-4-7-6-1-2
1-5-1-3-1-2-0-8-0-8-0-2-1-3-1-5-1
4-4-2-2-1-2-8-8-8-8-2-1-2-2-4-4
0-2-0-1-1-6-0-0-0-6-1-1-0-2-0
2-2-1-0-5-6-0-0-6-5-0-1-2-2
0-1-1-5-1-6-0-6-1-5-1-1-0
1-0-4-4-5-6-6-5-4-4-0-1
1-4-0-1-1-0-1-1-0-4-1
3-4-1-0-1-1-0-1-4-3
1-3-1-1-0-1-1-3-1
2-2-0-1-1-0-2-2
0-2-1-0-1-2-0
2-1-1-1-1-2
1-0-0-0-1
1-0-0-1
1-0-1
1-1
0

<caption>**Figure 2.** The Complete Iterations Generated From The Input $P$ Using The Transition Function $\delta$</caption>
To show a complex structure in the automaton, we define a pattern $S$
that will be highlighted in the iterations. The pattern is defined as a
sequence of the Natural Numbers $N$ and the Subtraction Operation
$S \subset \{N, -\} (*)$, i.e. $S = [0-], S = [1-0], S = [1-0-1]... etc$

<figure><img src="image_3.png" /><figcaption>**Figure 3.** A Complex Structure Generated Using The Default Input $P$ And $S = [0-]$</figcaption></figure>

**3. Simulation of Elementary Cellular Automata**

In this section we will simulate different structures from ECA using
the Proposed Automaton. For each input of the following simulations,
it can be found in the appendices and will be referred to as *Simulation*
- 1 = (A.1) ... *Simulation* - 2 = (A.2) ... etc.

<figure><img src="image_4.png" /></figure>
<figure><img src="image_5.png" /><figcaption>**Figure 4.** A Comparison Between ECA Structures And Their Equivalent Simulations</figcaption></figure>

The figure shows a comparison between different structures of ECA on the left side as (a), (c) & (e), known also as Rule-90 [5], Rule-110 [6] & Rule-182 [7] respectively. Where on the right side (b), (d) & (f) shows the corresponding simulations using the proposed automaton.

**Properties Of The Automaton.** The Automaton can simulate multiple structures from ECA with the same input applied, i.e. Rule-90 shown in Figure 4. (a), it can be simulated using $P = (A.1)$ and $S = (1-)$ highlighted. For Rule-182 shown in Figure 4. (e), it can be simulated using the same input $P = (A.1)$ and $S = (0-)$ highlighted.

Another property is simulating Rule-110 which has been proven to be Turing-Complete [4] shown in Figure 4. (c), the corresponding simulation is Figure 4. (d) using $P = (A.2)$ and $S = (1-)$.
**Symmetric Vs Non-Symmetric Structures.** An interesting property of the automaton is transforming a Non-Symmetric structure to a Symmetric one based on the input modification.

This is done by combining the original input $P$ (where $P = P_{old}$) with the reverse of it described as $P_{new} = (P_{old})(Reverse(P_{old}))$, i.e. $P_{old} = [1-5]$ & $Reverse(P_{old}) = [5-1]$, which will give us $P_{new} = [1-5-5-1]$.

<figure><img src="image_6.png" /><figcaption>**Figure 5.** A Structure Generated Using $P_1 = (2-0-1-7-2-0-1-8)$ And $S = [0-]$</figcaption></figure>

**Figure 5.** is symmetric when $P_1$ is modified to include itself and the reverse of it as $P_{new} = (2-0-1-7-2-0-1-8) - (8-1-0-2-7-1-0-2)$, it is equivalent to $P_{new} = (2-0-1-7-2-0-1-8-8-1-0-2-7-1-0-2)$.

<figure><img src="image_7.png" /><figcaption>**Figure 6.** The Symmetric Structure Based On $P_{new}$ and $S = [0-]$</figcaption></figure>

While highlighting $S = [0-]$ shows a complex structure, other patterns
References

[1] J. von Neumann, *Theory of Self-Reproducing Automata* (A. W. Burks,ed.), Urbana, IL: University of Illinois Press, 1966.

[2] H. Meinhardt, *The Algorithmic Beauty of Sea Shells*, Springer, 1995.

[3] S. Wolfram, *A New Kind of Science*, Champaign, IL: Wolfram Media, Inc., 2002.

[4] Matthew Cook, "Universality in Elementary Cellular Automata," *Complex Systems Journal*, **15**(1), 2004 pp. 1–40.

[5] Eric W. Weisstein. "Rule 90" (September 12, 2002) http://mathworld.wolfram.com/Rule90.html

[6] Eric W. Weisstein. "Rule 110" (December 30, 2002) http://mathworld.wolfram.com/Rule110.html

[7] Eric W. Weisstein. "Rule 182" (December 30, 2002) http://mathworld.wolfram.com/Rule182.html