A _cellular automaton_ is pair $(X,R)$ where $X$ is a grid of some specific
boundary topology111These grids can have joined boundaries, fixed boundaries,
be bi-infinite, etc. etc. . and $R$ is the ‘rule’ that is applied successively
to the grid. Each row is coloured based on the state of the colours on the
previous row.

We will specifically look at the subclass of cellular automata known as
Elementary Cellular Automata, or ECAs. These were first introduced and studied
by Wolfram in [65].

######  Definition 6.1.2.

An _elementary cellular automaton_ , or ECA, is a cellular automaton
$(X,R_{n})$ where the rules in $R$ are derived from the binary representation
of $n$. An ECA’s rules for a cell at position $i$ on row $j$, written
$c_{i,j}$, is determined by the triple $(c_{i-1,j-1},c_{i,j-1},c_{i+1,j-1})$.
Thus, our rule set $R_{n}$ is given by a function
$r_{n}:\\{0,1\\}^{3}\rightarrow\\{0,1\\}$.

To acquire our rules for $R_{n}$ we first take the binary representation of
$n$, and then send each of our 8 possible inputs sequentially to each bit of
the binary representation of $n$, starting with the least significant bit.

To illustrate how this works, take $R_{30}$. We start with the 8-bit binary
representation of 30, 00011110, and then map the inputs to $r_{30}$ as per
table 6.1.

111 | 110 | 101 | 100 | 011 | 010 | 001 | 000
---|---|---|---|---|---|---|---
0 | 0 | 0 | 1 | 1 | 1 | 1 | 0
Table 6.1. Rule 30 Automaton Rules

If we let our grid be the full $\mathbb{Z}^{2}$ lattice, then for each row
$x\in\mathbb{Z}^{2}$, we can define
$R_{n}:\mathbb{Z}^{2}\rightarrow\mathbb{Z}^{2}$ as the successive application
of $r_{n}$ to every triple $(x(i-1),x(i),x(i+1))$, for each cell $x(i)\in x$.

###  6.2. Some Results about ECAs

We will define and discuss some background results for our work on ECAs and
tilings. With ECA’s already being an interesting and fertile area of study, we
will give some background theory to the results, and then demonstrate that
these results can also be realized as tiling problems by means of coding ECA’s
into prototile sets.

####  6.2.1. ECAs and Chaos

We will view ECAs as Discrete Time Dynamical Systems (DTDS) - that is, an
iterated system that has discrete time steps. We write these as above,
$(X,F)$, where $X$ is the _phase space_ , which is equipped with a distance
function $d$, and a _next state map_ $F:X\mapsto X$, continuous on $X$
according to the topology on $X$ induced by $d$. We also assume that such a
metric space $(X,d)$ is perfect - i.e. has no isolated points.

######  Definition 6.2.1 (Sensitivity).

A DTDS $(X,F)$ is _sensitive to initial conditions_ if and only if there
exists $\delta>0$ such that

$(\forall x\in X)\,(\forall\epsilon>0)\,(\exists y\in X)\,(\exists
n\in\mathbb{N})[d(x,y)<\epsilon\wedge d(F^{n}(x),F^{n}(y))\geq\delta]$

More intuitively, this definition states that the iterated map has the
property that there exist points arbitrarily close to some point $x\in X$ that
eventually separate away from $x$ by at least $\delta$.

We will need, for our definitions of chaos, definitions of the following
terms:

######  Definition 6.2.2.

A dynamical system $(X,F)$ has a _dense orbit_ if and only if

$(\exists x\in X)\,(\forall y\in X)\,(\forall\epsilon>0)\,(\exists
n\in\mathbb{N})\,[d(F^{n}(x),y)<\epsilon]$

######  Definition 6.2.3.

A dynamical system $(X,F)$ is _topologically transitive_ if and only if for
all non-empty open subsets $U,V$ of $X$,

$(\exists n\in\mathbb{N})\,[F^{n}(U)\cap V\neq\emptyset]$

For a perfect DTDS $(X,F)$, the existence of a dense orbit necessarily implies
topological transitivity. This is an important result in reference to the
1-dimensional dynamical systems we wish to represent in tilings later on - it
shows us that the barrier to achieving chaotic behaviour is reassuringly low,
which somewhat naturalises our results.

######  Definition 6.2.4.

A dynamical system $(X,F)$ has _dense periodic points_ if and only if the set
of all the periodic points given by

$Per(F)=\\{x\in X:(\exists k\in\omega)\,F^{k}(x)=x\\}$

is a dense subset of $X$. Specifically,

$(\forall x\in X)\,(\forall\epsilon>0)\,(\exists p\in
Per(F))\,[d(x,p)<\epsilon]$

Following on from these definitions, Devaney in [22] formulated the most well-
known definition of chaos as follows:

######  Definition 6.2.5 (Devaney Chaos).

The dynamical system $(X,F)$ is _chaotic_ if

  1. (1)

$F$ is topologically transitive,

  2. (2)

$F$ has dense periodic points,

  3. (3)

$F$ is sensitive to initial conditions.

Meanwhile, other formulations of chaos came about - the most notable for this
work is due to Knudson [43], which is nonperiodicity-free:

######  Definition 6.2.6 (Knudson Chaos).

The dynamical system $(X,F)$ is chaotic if

  1. (1)

$F$ has a dense orbit,

  2. (2)

$F$ is sensitive to initial conditions.

This formulation that came about when Knudson proved there existed a dynamical
system which is chaotic according to Devaney’s definition, but which the
restriction of the set to its periodic points was also Devaney Chaotic.

It will be useful later to consider similar restrictions, such as [59] that
demonstrates the following proposition:

######  Proposition 6.2.7 ([59, Prop. 1, p.353]).

Let $I$ be a (potentially infinite) interval - a 1-dimensional space - and
$F:I\mapsto I$ be a continuous, topologically transitive map. Then

  1. (1)

The periodic points of $F$ are dense in $I$,

  2. (2)

$F$ has sensitivity to initial conditions.

Thus, for 1-dimensional systems, topological transitivity is ‘enough’ for a
dynamical system to be chaotic. Given our ECAs are being considered as
essentially 1-dimensional DTDS it becomes clear that our requirements for such
a system to be chaotic are quite surprisingly minimal.

In order to fully describe this, we need notions of ‘permutivity’ for an ECA,
which we get from [13]:

######  Definition 6.2.8 (Permutivity).

A cellular automaton local rule $f$ is _permutive_ in $x_{i}$, for $-k\leq
i\leq k$, if and only if for any given sequence
$x_{-k},\ldots,x_{i-1},x_{i+1},\ldots,x_{k}\in X$ we have

$\\{f(x_{-k},\ldots,x_{i-1},x_{i},x_{i+1},\ldots,x_{k}):x_{i}\in X\\}=X$

We can refine this idea to leftmost (rightmost) as follows:

######  Definition 6.2.9 (Leftmost (Rightmost) Permutive).

A local CA rule $f$ is said to be _leftmost_ (_rightmost_) permutive if and
only if there is an integer $i$, $-k\leq i\leq 0$ ($0\leq i\leq k$) such that:

  1. (1)

$i\neq 0$,

  2. (2)

$f$ is permutive in the $i^{th}$ variable,

  3. (3)

$f$ does not depend on $x_{j}$ for $j<i$ ($j>i$).

As pointed out in [13], for ECAs this means that when an ECA is leftmost-
permutive, it follows that

$(\forall x_{i},x_{i+1})\,[f(0,x_{i},x_{i+1})\neq f(1,x_{i},x_{i+1})]$

namely, if two strings differ in the $x_{i-1}^{th}$ position, they differ in
the $x_{i}^{th}$ position under $f$. Likewise, when an ECA is rightmost-
permutive, the mirror argument follows, specifically

$(\forall x_{i-1},x_{i})\,[f(x_{i-1},x_{i},0)\neq f(x_{i-1},x_{i},1)]$

We can now use the following result from Cattaneo et al. (Cor. 3.3 in [13]):

######  Corollary 6.2.10 ([13, Cor. 3.2]).

Let $(\mathbb{Z}^{2},R_{n})$ be an ECA based on the local rule $r_{n}$. Then
the following are equivalent:

  1. (1)

$r_{n}$ is leftmost or rightmost permutive, or both.

  2. (2)

$r_{n}$ is Devaney Chaotic.

  3. (3)

$r_{n}$ is Knudson Chaotic

  4. (4)

$r_{n}$ is surjective and non-trivial.

By Table 1 and the analysis in Section 3.3 in [13], it becomes clear that
there exist a set of rules that exhibit chaotic behaviour, the most well known
of which is $R_{30}$, having been studied in some depth originally by Wolfram
in [65].

####  6.2.2. ECAs and Turing Universality

We now wish to extend results from earlier in this thesis to very small
dynamical systems, for which we will need the following definitions:

######  Definition 6.2.11.

A _cyclic tag system_ is a computational system consisting of the following
arrangement:

  * •

A set $P\subset 2^{<\omega}$ of _productions_.

  * •

A finite binary string $d=d_{0},d_{1},\ldots d_{j}$ called the _data string_.

  * •

A transformation map

$(i,d)\rightarrow(i+1(\mathrm{mod}\
n),(d_{1},d_{2},\ldots,d_{k})^{\frown}P^{d_{0}}_{i})$

where $i$ is a counter, $n=|P|$, and for all $i$:

$\displaystyle P^{0}_{i}$ $\displaystyle=\emptyset$ $\displaystyle P^{1}_{i}$
$\displaystyle=P_{i}$

Intuitively, a cyclic tag system operates as follows:

  1. (1)

If $d_{0}=0$, then we delete $d_{0}$ and do nothing.

  2. (2)

If $d_{0}=1$, then we delete $d_{0}$ and append the $i^{th}$ member of $P$,
$P_{i}$.

  3. (3)

If $d=\emptyset$ then we halt.

An example computation is as follows. Let $P=\\{101,110,10\\}$ and $d=11$, our
computation is as given in table 2.

$P_{i}$ | $d$
---|---
101 | 11
110 | 1101
11 | 101110
101 | 0111011
110 | 111011
11 | 11011110
101 | $\ldots$
Table 6.2. This table shows the development of a cyclic tag system for initial
$d$ of $11$ and $P_{i}$’s in sequence as given in the text. The development of
the contents of $d$ is given at each line.

It is proved in [15] that a cyclic tag system is Turing Universal - this was
done by showing a Universal Turing Machine can be coded into a 2-tag system,
and 2-tag systems can be coded into Cyclic tag systems. The proof is omitted
here, but a clear proof can be found in [46].

In 2004, Cook proved in [15] the following theorem:

######  Theorem 6.2.12 ([15, Sec 4]).

The ECA $R_{110}$ is Turing Universal.

This is done by combination of the following theorem and Lemmas:

######  Lemma 6.2.13 ([15, Sec 3]).

A cyclic tag system is Turing Complete.

This is a somewhat surprising result, owing to the very minimal nature of
cyclic tag systems, but the proof shows that by careful construction of the
production sets $P$ it is possible to emulate the tag systems, due to Post, of
a small number of states easily. The proof of this coding is fairly
straightforward, but is omitted here owing to length.

######  Lemma 6.2.14 ([15, Sec 4]).

A Cyclic Tag system can be implemented in a glider system.

  * Sketch of proof of 6.2.12.

Rule 110 has the ability to carry a state of 1’s and 0’s left and right
depending on careful setup of the strings - such patterns that shift
iteratively left and right down our ECA state are called ‘gliders’. A ‘glider
system’ is some arrangement of these gliders such that they then propagate
left and right. There are 5 glider types documented in [15], and these are
crafted into different arrangements of glider systems in order to achieve the
result we are interested - specifically, coding the $P$ and $d$ of any cyclic
tag system.

Figure 6.1. The schematic diagram for Cook’s encoding of Cyclic Tag Systems in
Rule 110, taken from [28]

By carefully implementing a glider system in the input row for an ECA, Cook
was able to code Turing Machine computations into the dynamics of $R_{110}$,
thereby showing this ECA to be Turing Universal.

An additional aside, which will be useful in our discussion of ECA tilings, is
that the halting state of some TM coded into $R_{110}$ is equivalent to
whether the dynamics of the system become aperiodic or remain periodic,
equivalent to halting or not halting, respectively. ∎

An overall schematic diagram can be found in Figure 6.1

However, we note that there are some cases where simply expecting aperiodicity
or continued periodicity is not sufficient. Take a TM that calculates some
non-repeating sequence, such as the Champernowne’s Constants used earlier in
this thesis. The output of this computation will necessarily be aperiodic in
any given tiling encoding of this computation.

Thus we have to resolve the issue surrounding this - if our tiling is going to
be aperiodic whether we have halted or not, then how can we tell if our
computation is running or if it has halted?

Firstly, we note that Rule 110 is not left or right permutive, so any tiling
will not naturally be aperiodic by the criteria in the previous section. We
next need to note that we can stratify these two notions of ‘aperiodicity’ by
means of a straightforward argument on the underlying mechanics of our
resultant tilings _in vicem_ of the Turing Machines and cyclic tag machines we
are representing.

We note that any non-repeating computation will actually be quasi-periodic by
our definition 4.1.9 \- a fact that follows when we observe that certain
strings, namely those representing states in our Turing Machine via the set of
productions $P$ in our cyclic tag system being recurrent in the tiling.

Thus, any aperiodic behaviour will be apparent from the fact that there will
be no sign of our Turing computational artefacts in the ECA following entering
the halt state. As such, it will either become periodic or aperiodic, but our
test for the occurrence of particular words that code these will fail.

The same carries forwards into our tiling by means of looking for particular
sequences of tiles - represented as finite tuples - in any resultant tiling.
Given this, we can safely work with ECA Rule 110 and not worry about ‘losing
track’ of the status of our computation.

###  6.3. Elementary Cellular Automata and Tilings

In this section we build on work from the author’s MSc thesis, [12], where we
proved the following theorem:

######  Theorem 6.3.1 ([12, Chap. 3]).

There exists a universal prototile schema consisting of 18 Wang tiles that
tiles the plane according to the rules of any given ECA.

  * Proof.

We note that we need to satisfy the following requirements:

  1. (1)

Encode each cell in a time-space diagram for a given ECA.

  2. (2)

Encode the relationships between each cell given by $R_{n}$.

  3. (3)

Show how bits can be copied across each other in the tiling in order to
emulate the action of $R_{n}$.

We first construct the prototile scheme that will code the action of our ECA
function given by $f_{n}:\\{0,1\\}^{3}\rightarrow\\{0,1\\}$, given by our rule
$R_{n}$. This scheme is as follows:

$b$$a$$c$$\begin{subarray}{c}\end{subarray}{f_{n}(a,b,c)}$

Thus, for each rule we get the following 8 prototiles, where we fill in the
specific outputs for each $f_{n}$ to get our _Rule prototiles_ :

$0$$0$$0$$\begin{subarray}{c}\end{subarray}{f_{n}(0,0,0)}$

$0$$0$$1$$\begin{subarray}{c}\end{subarray}{f_{n}(0,0,1)}$

$1$$0$$0$$\begin{subarray}{c}\end{subarray}{f_{n}(0,1,0)}$

$1$$0$$1$$\begin{subarray}{c}\end{subarray}{f_{n}(0,1,1)}$

$0$$1$$0$$\begin{subarray}{c}\end{subarray}{f_{n}(1,0,0)}$

$0$$1$$1$$\begin{subarray}{c}\end{subarray}{f_{n}(1,0,1)}$

$1$$1$$0$$\begin{subarray}{c}\end{subarray}{f_{n}(1,1,0)}$

$1$$1$$1$$\begin{subarray}{c}\end{subarray}{f_{n}(1,1,1)}$

We add to these _state swapping_ tiles that will take an output of $f_{n}$ and
‘swap’ this bit with the cell’s neighbours. We first fix the colour $B$ that
will act as ‘blank’, allowing us to line up the tiles above and below each
crossover of bits from the distributor tiles (see below):

$B$$0$$0$$(0,0)$

$(0,0)$$0$$0$$B$

$B$$0$$1$$(0,1)$

$(0,1)$$1$$0$$B$

$B$$1$$0$$(1,0)$

$(1,0)$$0$$1$$B$

$B$$1$$1$$(1,1)$

$(1,1)$$1$$1$$B$

We now need some _distributor tiles_ that will take an output state and
distribute this information left, right, and downwards:

$1^{f_{n}}$$1$$1$$1$

$0^{f_{n}}$$0$$0$$0$

Note that these tiles differentiate the upper quadrant as being specifically
from the output of $f_{n}$ so as to prevent trivial tilings of the plane using
just distributor prototiles. These tiles code exactly the cells from the
original time-space diagram.

We then note that each part of the action of some ECA rule $R_{n}$ is now
coded into our tiling:

  * –

Each cell is represented in any planar tiling due to the above prototile
constructions.

  * –

Each relationship coded by $f_{n}$ is represented as state swapping tiles
creating a space for some rule tile, which then has the output of $f_{n}$
distributed for this process to repeat.

  * –

We do not code the upper half-plane owing to our not-knowing the previous rows
of computation that took place before our input row.

Thus, we have fully represented in 18 prototiles, given by our 8 rule tiles, 8
state swapping, and 2 distributor prototiles.

The tiling process is as follows:

  1. (1)

Code the input into a series of distributor tiles.

     * –

We pad the input with infinitely many ‘0’s left and right to achieve a full
half-planar tiling.

  2. (2)

Place the relevant state swapping tiles between each of these.

  3. (3)

Tile each successive row using the correct tilings, in order to get successive
states of the ECA.

∎

Figure 6.2. A sample tiling of $S_{30}$. NB: Indicators $O^{f}$ and $1^{f}$
are omitted for clarity.

Figure 6.2 shows the tiling in action, coding the first few rows of ECA rule
30, with $R_{30}$ clearly coded with the connecting tiles showing how the
outputs interact with each other.

###  6.4. A 15 Prototile ECA Tiling

We present a tiling that codes any ECA in only 15 tiles, using an adapted
hexagon-based tiling. This particular tiling lends itself to our computable
trinary functions that form our $f_{n}$ ECA functions, and have not yet been
found in the literature.

######  Theorem 6.4.1 (C. 2019).

For any ECA of Rule $n$ there exists a prototile set $S_{n}$ of size 15 such
that any tiling of the plane $T$ by $S_{n}$ codes each iteration of the ECA
starting from the string coded by the first row.

  * Proof.

Broadly speaking, we require three things from our tiling of ECA rules - for a
given rule $R_{n}$:

  1. (1)

Encoding of each input and output of the $f_{n}$ for our rule $R_{n}$.

  2. (2)

Handling of the ‘transfer of bits’ from one represented cell to the cells
lower left, lower centre, and lower right.

  3. (3)

Fixing of upper half-plane boundary.

For the purposes of this proof, we work on tiling the lower half-plane, with
the lower border of the upper half-plane having colour $I$. This means that we
do not have to worry about the pre-images of the inverse function $f^{-1}$
which can not be unique or even be a ‘Garden of Eden’, meaning it is a
configuration that has no pre-image. Thus simplifying the way in which we tile
the plane by omitting these in the upper half plane, essentially fixing it
with colour $I$.

We first present the base tiling we are going to use - horizontally aligned
hexagons with diamond lozenges filling the gaps between them, as so:

We present two tile schemas that we will make use of can be carried out to
obtain a tile set $S_{n}$ for each ECA Rule $R_{n}$.

Firstly, we give a schema for the hexagon tiles that will code the actual rule
action. For $a,b,c,f_{n}(a,b,c)\in\\{0,1\\}$ we define our tile schema:

$a$$b$$c$$f_{n}(a,b,c)$

where $f_{n}$ is the operation of applying rule $n$ to the three input bits
$a,b,c$. Note, if required we can use similar notation to the 4-tuple codes we
used for Wang tiles - specifically: $\langle a,b,c,f_{n}(a,b,c)\rangle$

We can see that for $a,b,c\in\\{0,1\\}$ there are 8 prototiles that we can
define as our basis for each ECA tiling. These are as follows:

$1$$1$$1$$f_{n}(1,1,1)$$1$$1$$0$$f_{n}(1,1,0)$$1$$0$$1$$f_{n}(1,0,1)$$1$$0$$0$$f_{n}(1,0,0)$$0$$1$$1$$f_{n}(0,1,1)$$0$$1$$0$$f_{n}(0,1,0)$$0$$0$$1$$f_{n}(0,0,1)$$0$$0$$0$$f_{n}(0,0,0)$

We next define our diamond lozenges as being tiles that are vertically and
horizontally quadrisected and use the following tile schema, for
$s,t\in\\{0,1\\}$:

$s$$t$$t$$s$

This gives us our 4 connecting lozenges as follows:

0000011010011111

These connecting lozenges are required owing to a property of ECAs - namely,
for some string $\sigma\in\\{0,1\\}^{<\omega}$, any bit $b_{i}\in\sigma$ is
needed to calculate the bits
$b^{\prime}_{i-1},b^{\prime}_{i},b^{\prime}_{i+1}\in\sigma^{\prime}$. As such,
these lozenges achieve the required ‘crossover’ of these bits. These act in
principle precisely the same as the ‘state swapping tile’ in our previous
theorem 6.3.1.

We will also need the following 3 ‘I’ tiles to make our tiling ‘neat’ and to
define the first row of out tiling:

$I$$I$$I$$0$$I$$I$$I$$1$II

This will give us a flat edge for the top of the tiling, where we can now see
that a tiling of the plane, with no gaps can be achieved, as shown in this
diagram:

We can thus define the tiling algorithm for some ECA as follows:

  1. (1)

Take the input for our ECA and code this using the ‘I’ tiles.

     * –

Pad the input with $\langle I,I,I,0\rangle$ tiles as needed left and right to
fill the left and right halves of our lower half-plane.

     * –

Ensure that the half-lozenge ‘I’-tiles are placed between the upper gaps
between these hexagons.

  2. (2)

Place the correct corresponding lozenge tiles between the hexagon tiles.

  3. (3)

Place the now-defined hexagon tiles under each hexagon such that the upper 3
sides correspond to the lozenges on the upper left and upper right, and the
hexagon immediately above.

  4. (4)

Go to 2.

Given this algorithm and this tile set, we can code any ECA by choosing the
prescribed outputs from $f_{n}(x,y,z)$ from our rule $n$. Given this setup, we
can see that our tiling gives a tiling of the half-plane without any holes,
and such that it imitates the behaviour of any ECA.

∎

As an illustrated example, the full prototile set for Rule 30 can be found in
figure 6.3

$1$$1$$1$$0$$1$$1$$0$$0$$1$$0$$1$$0$$1$$0$$0$$1$$0$$1$$1$$1$$0$$1$$0$$1$$0$$0$$1$$1$$0$$0$$0$$0$0000011010011111$I$$I$$I$$0$$I$$I$$I$$1$II
Figure 6.3. A 15 prototile set of tiles that encodes the behaviour of the Rule
30 ECA in the lower half-plane.

Our proof of this theorem is unusual as it makes use of a non-standard planar
tiling made up of hexagon and lozenge tiles - something that the author has
not seen at all in the literature. This particular prototile arrangement lends
itself to 3-ary iterated functions and dynamical systems slightly better than
Wang tiles. Hence, they are included in this thesis as objects for potential
further consideration.

######  Corollary 6.4.2 (C. 2019).

There are chaotic ECA prototile sets of size 15.

  * Proof.

This is immediate from the known properties of Rule 30, 90, etc. given in [13]
\- specifically, we can simply code these ECAs into prototiles using the
scheme above and obtain a fixed-size prototile set that can code the required
behaviour on a given input, such an input being given by an initial row of
‘I’-tiles from our original construction. ∎

######  Corollary 6.4.3 (C. 2019).

There are Turing Complete prototile sets of size 15.

  * Proof.

This corollary is immediate from the Turing completeness of Rule 110 [15] and
the theorem 6.4.1 by the same argument given for 1. We note that we have to
perform the following steps to obtain the result. Given a Turing Machine with
index $e$ and a given input $x$:

    1. (1)

Convert $\varphi_{e}$ to a cyclic tag system, to get $Tag_{e}$.

    2. (2)

For $\varphi_{e}(x)$ we take $Tag_{e}$ and code this and $x$ into a single row
input for our ECA.

    3. (3)

Code this into the initial row ‘I’-tiles from our construction.

With this done, we can allow our tiling to proceed row by row, and note that
this codes each successive stage of the computation $\varphi_{e}(x)$ via the
mapping above. ∎

$I$$I$$I$$I$$I$$I$$I$$I$$I$$I$$I$$I$$I$$I$$I$$0$$I$$I$$I$$0$$I$$I$$I$$1$$I$$I$$I$$0$$I$$I$$I$$0$0000011010010000$0$$0$$0$$0$$0$$0$$1$$1$$0$$1$$0$$1$$1$$0$$0$$1$$0$$0$$0$$0$0110111111111001$0$$0$$1$$1$$0$$1$$1$$1$$1$$1$$1$$0$$1$$1$$0$$0$$1$$0$$0$$1$1111100100000110
Figure 6.4. Example few rows of a hexagon and lozenge tiling of Rule 30.

We include in figure 6.4 as a worked example of the initial few stages and
columns of a Rule 30 ECA Hexagon and Lozenge tiling, demonstrating the
function of the initializer tiles, the ECA hexagons, and the connecting
lozenge tiles to demonstrate how an ECA can be encoded into a tiling of the
plane.

######  Conjecture 6.4.4 (C. 2019).

There exist ECA prototile sets of 8 tiles.

By [39] these cannot be formed from Wang tiles - this would mean that there is
an aperiodic prototile set of fewer than 8 tiles, which they proved to not be
the case. As such, a tiling of 8 tiles must be some other planar repeating
tessellation with colours applied to different edges or areas in order to
represent a prototile set of 8 tiles.

##  Chapter 7 Conclusion

> Nevertheless, I repeat; we are only at the beginning. I am only a beginner.
> I was successful in digging up buried monuments from the substrata of the
> mind. But where I have discovered a few temples, others may discover a
> continent.
>
> S. Freud,
> in an interview with G. S. Viereck.

Here we give an overview of the conclusions from the work presented in this
thesis, and give summary of some of the open questions arising from this
research.

###  7.1. Conclusions from Results

In Chapter 3 we presented our first results concerning the relationship
between computability and tiling problems. We extended results due to Harel in
[37] to the general Domino Problem for infinite prototile sets. These results
follow the general intuition due to Berger in [5] that the Domino Problem for
finite prototile sets is $\Sigma^{0}_{1}$/$\Pi^{0}_{1}$ complete, so expecting
that $TILE/\neg TILE$ is equivalent to $\Sigma^{1}_{1}$/$\Pi^{1}_{1}$ does fit
the general intuition regarding this class of tiling problems.

We next discussed, in chapter 4 the question of whether tilings from a given
prototile set are periodic or aperiodic. From this outset we found a rather
unusual set for which the problems of (a)periodicity for infinite prototile
sets are complete - $(\Pi^{1}_{1}\wedge\Sigma^{1}_{1})$ \- which is a rare
class of problems. Indeed, it is entirely possible that this may be weakened
in subsequent work to one side of this conjunction.

The fact that $ATile_{FIN}\in\Pi^{0}_{1}$ is surprising, given we did not even
have a proven existence of such prototile sets until the mid-60’s. However, we
state the conjecture (below) that $PTile_{FIN}$ is unlikely to be arithmetical
owing to the requirement to quantify over all possible tilings for a given
prototile set, despite its bound on lengths of their possible periodicity
vectors.

The Weihrauch reductions presented in Chapter 5 are the first that we know of
concerning tiling problems. They directly use material from previous chapters
in order to show that the Domino Problems we have defined and studied are all
bounded above by the closed choice principle for Baire Space, with some
equivalences also being found. These give further detail to our picture of the
computability aspects of Domino Problems, fleshing out the overall picture
beyond the conventional view.

Finally, our results in Chapter 6 paint a picture regarding how to code
tilings of 3-ary functions, using ECAs as our example. This is, sometimes, a
more natural formulation of a problem, and as such the presentation of this
hexagon-lozenge tiling may be useful outside of this particular class of
automaton coding into prototile sets.

###  7.2. Open Problems and Further Work

There remain some interesting open problems that arise both from the
literature surrounding this thesis, and from results in the thesis itself.

From [39] we have the following conjecture:

######  Conjecture 7.2.1.

All the aperiodic Wang prototile sets generated by Kari’s method are _minimal
aperiodic_.

This result holds for all given prototile sets derived and demonstrated in the
literature, but we did not make any progress regarding the resolution of this
problem. It does, however, make a lot of sense, and would be a good result to
complete the picture painted by Rao et al. .

Recall $PTile_{FIN}$ is the set of finite prototile sets for whom all tilings
are periodic, we stated the following conjecture:

######  Conjecture 7.2.2.

$PTile_{FIN}$ is not arithmetical.

This is motivated by the need to at some point quantify over the entire class
of tilings for some finite prototile set $S$ in order to assert that $S\in
PTile_{FIN}$, and this need seems unavoidable. However this is not something
we have yet been able to show in general. The possible vectors are bounded,
which may belie some clever trick for making $PTile_{FIN}$ arithmetical, but
this is thus far elusive.

Lastly, recall that $ATile_{FIN}\in\Pi^{0}_{1}$, it would seem natural to
derive some notion of measure on a prototile set’s tilings, in order to derive
the following conjecture - an analogue of Kucera’s key result (see [23] for an
exposition):

######  Conjecture 7.2.3 (C. 2019).

For a notion of positive measure on $\mathcal{S}$-tilings, for some prototile
set $\mathcal{S}$, if a tiling $T$ has positive measure:

  * •

$T$ is aperiodic.

  * •

$T$ encodes some Martin-Löf Random.

However, the work to identify a suitable notion of measure was not yet
undertaken. We suspect that this can be achieved by means of analysis on the
‘colour density’ for coloured edges/Want tile quadrants.

It is also worth noting that the following conjecture is unresolved:

######  Conjecture 7.2.4.

The tiling method due to Socolar in [47] does indeed lead to total planar
aperiodic tilings.

It is our strong opinion that this is true by means of an application of WKL
to some additional machinery added to the construction that is presented.
However, the details have not yet been worked out to see if this can be
achieved.

Finally, we have our conjecture from chapter 6:

######  Conjecture 7.2.5.

There exist ECA prototile sets of 8 tiles.

As noted there, this cannot be formed of Wang tiles, but there is likely some
way of cutting a planar representation of a given ECA into a regular single
prototile per part of each rule. Shapes for this result would probably
resemble interlocking tilings that look like a double conjoined ‘H’, as
detailed in [32].

Finally, we note that the work in Chapter 5 on Weihrauch reducibility for
tiling problems as principles has the capability to be taken much further. We
alluded to one, for which we gave a definition of $WIPT$, accompanied by the
following estimate of $C_{\omega^{\omega}}\leq_{W}C_{2^{\omega}}\star
C_{\omega}\star WIPT$.

Indeed, we consider that there are many further applications for tiling
problems, in particular for dimensionality $\geq 2$ and for non-Euclidian
planar tilings.

A good starting point for the latter is the result due to Beauquier, Muller,
and Schupp in [4]. Here, they showed that a tiling problem known as “the Bar
Problem” - the question of whether a plane that has holes in it can be covered
with $(1\times n)$ ‘bars’ - is $NP$-complete in the Euclidian plane, however
in the hyperbolic plane it becomes polynomial time.

Overall, we hope that we have demonstrated some interesting results regarding
tiling problems, and laid down some framework and exposition that encourages
future results.

## References

  * [1] Helen Au-Yang and Jacques H.H. Perk, _Quasicrystals—the impact of N.G. de Bruijn_ , Indagationes Mathematicae 24 (2013), no. 4, 996–1017.
  * [2] Joan Bagaria, _C(n)-cardinals_ , Archive for Mathematical Logic 51 (2012), no. 3, 213–240.
  * [3] Joan Bagaria, Carles Casacuberta, A. R. D. Mathias, and Jiří Rosický, _Definable orthogonality classes in accessible categories are small_ , Journal of the European Mathematical Society 17 (2015), no. 3, 549–589.
  * [4] Danièl Beauquier, David E. Muller, and Paul E. Schupp, _The bar problem—a simple tiling problem which is $np$-complete on the Euclidean tessellation by squares but which is polynomial time on the hyperbolic tessellations by 4g-gons, $g\geq 2$_, 1999, pp. 29–36.
  * [5] R. Berger, _The undecidability of the domino problem_ , Memoirs ; No 1/66, American Mathematical Society, 1966.
  * [6] Peter Van Emde Boas, _The convenience of tilings_ , In Complexity, Logic, and Recursion Theory, Marcel Dekker Inc, 1997, pp. 331–363.
  * [7] Vasco Brattka, Matthew de Brecht, and Arno Pauly, _Closed choice and a uniform low basis theorem_ , (2010).
  * [8] by same author, _Closed choice and a uniform low basis theorem_ , Annals of Pure and Applied Logic 163 (2012), no. 8, 986–1008.
  * [9] Vasco Brattka and Guido Gherardi, _Weihrauch degrees, omniscience principles and weak computability_ , (2009).
  * [10] by same author, _Effective choice and boundedness principles in computable analysis_ , The Bulletin of Symbolic Logic 17 (2011), no. 1, 73–117.
  * [11] Vasco Brattka and Arno Pauly, _On the algebraic structure of Weihrauch degrees_ , Log. Methods Comput. Sci. 14 (2016), no. 4, Paper No. 4, 36\. MR 3868998
  * [12] Mark Carney, _Computable and enumerable tilings_ , Master’s thesis, University of Leeds, 2014.
  * [13] Gianpiero Cattaneo, Michele Finelli, and Luciano Margara, _Investigating topological chaos by elementary cellular automata dynamics_ , Theor. Comput. Sci. 244 (2000), no. 1-2, 219–241.
  * [14] E. A. Cichon, _A short proof of two recently discovered independence results using recursion theoretic methods_ , Proceedings of the American Mathematical Society 87 (1983), no. 4, 704–704.
  * [15] Matthew Cook, _Universality in elementary cellular automata_ , Complex Systems 15 (2004).
  * [16] S.B. Cooper, _Computability theory_ , Chapman Hall/CRC Mathematics Series, Taylor & Francis, 2003.
  * [17] Karel Culik, _An aperiodic set of 13 Wang tiles_ , Discrete Mathematics 160 (1996), no. 1, 245 – 251.
  * [18] Martin Davis, _The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions_ , Dover Publications, Inc., New York, NY, USA, 2004.
  * [19] N.G. de Bruijn, _Algebraic theory of Penrose’s non-periodic tilings of the plane. I_ , Indagationes Mathematicae (Proceedings) 84 (1981), no. 1, 39 – 52.
  * [20] by same author, _Algebraic theory of Penrose’s non-periodic tilings of the plane. II_ , Indagationes Mathematicae (Proceedings) 84 (1981), no. 1, 53 – 66.
  * [21] Jean-Charles Delvenne and Vincent D. Blondel, _Quasi-periodic configurations and undecidable dynamics for tilings, infinite words and turing machines_ , Theoretical Computer Science 319 (2004), no. 1, 127 – 143, Combinatorics of the Discrete Plane and Tilings.
  * [22] Robert L. Devaney, _An introduction to chaotic dynamical systems_ , 2nd ed. ed., Addison-Wesley Redwood City, Calif, 1989 (English).
  * [23] Rod Downey and Denis Hirschfeldt, _Algorithmic randomness and complexity_ , Springer-Verlag, Berlin, Heidelberg, 2010.
  * [24] Bruno Durand, _Tilings and quasiperiodicity_ , Theoretical Computer Science 221 (1999), no. 1–2, 61–75.
  * [25] Bruno Durand, Leonid A. Levin, and Alexander Shen, _Complex tilings_ , Journal of Symbolic Logic 73 (2008), no. 2, 593–613.
  * [26] Bruno Durand, Andrei Romashchenko, and Alexander Shen, _Fixed point theorem and aperiodic tilings_ , The Logic in Computer Science Column by Yuri Gurevich 97 (2010), 126–136.
  * [27] Eugenia Fuchs, _Behind the intuition of tilings_ , VIGRE 2009 Proceedings.
  * [28] Juarez Martínez Genaro, _Rule 110 and Turing Universality - webpage from UWE_ , https://uncomp.uwe.ac.uk/genaro/rule110/ctsRule110.html, Accessed: 2017-03-25.
  * [29] Guido Gherardi and Alberto Marcone, _How incomputable is the separable Hahn-Banach theorem?_ , Notre Dame J. Form. Log. 50 (2009), no. 4, 393–425 (2010). MR 2598871
  * [30] R. L. Goodstein, _On the restricted ordinal theorem_ , Journal of Symbolic Logic 9 (1944), no. 2, 33–41.
  * [31] E.R. Griffor, _Handbook of computability theory_ , Studies in Logic and the Foundations of Mathematics, Elsevier Science, 1999.
  * [32] Branko Grünbaum and G C Shephard, _Tilings and patterns_ , W. H. Freeman & Co., New York, NY, USA, 1986.
  * [33] Petra Gummelt, _Penrose tilings as coverings of congruent decagons_ , Geometriae Dedicata 62 (1996), no. 1, 1–17.
  * [34] Kurt Gödel, _Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme_ , Monatshefte für Mathematik und Physik 38 (1931), no. 1, 173–198.
  * [35] David Harel, _Recurring dominoes: Making the highly undecidable highly understandable (preliminary report)_ , Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory (London, UK, UK), Springer-Verlag, 1983, pp. 177–194.
  * [36] by same author, _Dynamic logic_ , pp. 497–604, Springer Netherlands, Dordrecht, 1984\.
  * [37] by same author, _Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness_ , J. ACM 33 (1986), no. 1, 224–248.
  * [38] Denis R Hirschfeldt, _Slicing the truth: On the computable and reverse mathematics of combinatorial principles_ , World Scientific Publishing Co., jul 2014.
  * [39] Emmanuel Jeandel and Michael Rao, _An aperiodic set of 11 Wang tiles_ , June 2015, working paper or preprint.
  * [40] Jarkko Kari, _A small aperiodic set of Wang tiles_ , Discrete Math. 160 (1996), no. 1-3, 259–264.
  * [41] Richard Kaye, _The mathematics of logic: A guide to completeness theorems and their applications_ , Cambridge University Press, 2007.
  * [42] Laurie Kirby and Jeff Paris, _Accessible independence results for Peano arithmetic_ , Bulletin of the London Mathematical Society 14 (1982), no. 4, 285–293.
  * [43] Carsten Knudsen, _Chaos without nonperiodicity_ , The American Mathematical Monthly 101 (1994), no. 6, 563–565.
  * [44] Leonid A. Levin, _Aperiodic tilings: Breaking translational symmetry_ , The Computer Journal 48 (2005), no. 6, 642–645.
  * [45] A. L. Mackay, _What has the Penrose tiling to do with the icosahedral phases? geometrical aspects of the icosahedral quasicrystal problem_ , Journal of Microscopy 146 (1987), no. 3, 233–243.
  * [46] Turlough Neary and Damien Woods, _P-completeness of cellular automaton rule 110_ , Automata, Languages and Programming (Berlin, Heidelberg) (Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, eds.), Springer Berlin Heidelberg, 2006, pp. 132–143.
  * [47] George Y. Onoda, Paul J. Steinhardt, David P. DiVincenzo, and Joshua E. S. Socolar, _Growing perfect quasicrystals_ , Phys. Rev. Lett. 60 (1988), 2653–2656.
  * [48] R. Penrose, _Pentaplexity a class of non-periodic tilings of the plane_ , The Mathematical Intelligencer 2 (1979), no. 1, 32–37.
  * [49] Pavel Pudlk, _Logical foundations of mathematics and computational complexity: A gentle introduction_ , Springer Publishing Company, Incorporated, 2013.
  * [50] Gerald E. Sacks, _Higher recursion theory_ , Perspectives in Logic, Cambridge University Press, 2017.
  * [51] Daniel Schechtman, _Quasi-periodic crystals—the long road from discovery to acceptance_ , Rambam Maimonides Medical Journal 4 (2013), no. 1.
  * [52] Dong Shi, Zoe Budrikis, Aaron Stein, Sophie A. Morley, Peter D. Olmsted, Gavin Burnell, and Christopher H. Marrows, _Frustration and thermalization in an artificial magnetic quasicrystal_ , Nature Physics 14 (2017), no. 3, 309–314.
  * [53] Stephen Simpson, _Medvedev degrees of 2-dimensional subshifts of finite type_ , Ergodic Theory and Dynamical Systems 34 (2007).
  * [54] Alex Smith, _Universality of Wolfram’s 2, 3 Turing Machine_ , https://www.wolframscience.com/prizes/tm23/TM23Proof.pdf, Accessed: 2018-10-13.
  * [55] Robert I. Soare, _Recursively enumerable sets and degrees_ , Springer-Verlag, Berlin, Heidelberg, 1987.
  * [56] Joshua E.S. Socolar and Joan M. Taylor, _An aperiodic hexagonal tile_ , Journal of Combinatorial Theory, Series A 118 (2011), no. 8, 2207–2231.
  * [57] P. Subramanian, A. J. Archer, E. Knobloch, and A. M. Rucklidge, _Three-dimensional icosahedral phase field quasicrystal_ , Phys. Rev. Lett. 117 (2016), 075501.
  * [58] Alan M. Turing, _On computable numbers, with an application to the Entscheidungsproblem_ , Proceedings of the London Mathematical Society 2 (1936), no. 42, 230–265.
  * [59] Michel Vellekoop and Raoul Berglund, _On intervals, transitivity = choas_ , The American Mathematical Monthly 101 (1994), no. 4, 353–355.
  * [60] Hao Wang, _Proving theorems by pattern recognition, ii_ , pp. 159–192, Springer Netherlands, Dordrecht, 1990.
  * [61] Klaus Weihrauch, _A simple introduction to computable analysis_ , 1995.
  * [62] by same author, _On computable metric spaces Tietze-Urysohn extension is computable_ , Computability and Complexity in Analysis (Berlin, Heidelberg) (Jens Blanck, Vasco Brattka, and Peter Hertling, eds.), Springer Berlin Heidelberg, 2001, pp. 357–368.
  * [63] Eric W. Weisstein, _Cellular Automaton. from Mathworld – a wolfram web resource_ , http://mathworld.wolfram.com/CellularAutomaton.html, Accessed: 2019-03-25.
  * [64] Linda Brown Westrick, _Seas of squares with sizes from a $\Pi^{0}_{1}$ set_, Israel Journal of Mathematics 222 (2017), no. 1, 431–462.
  * [65] Stephen Wolfram, _A new kind of science_ , Wolfram Media Inc., Champaign, Ilinois, US, United States, 2002.

## Index

  * $(x,y)$-Universal Turing Machine Definition 2.3.6
  * $\neg TILE$ equivalence to $WELL$ Theorem 3.4.4
  * 1-reducible Definition 1.2.21
  * aperiodic tiling Definition 4.1.2
  * $b$-tree Definition 3.2.4
  * basis Definition 1.5.3
  * cellular automaton Definition 6.1.1
  * characteristic function Definition 1.2.12
  * choice chains §5.2
  * choice function §5.2
  * choice principle §5.2
  * $ChooseTiling$ Definition 5.3.2
  * $ChooseWeakPatchTiling$ Definition 5.4.2
  * $CIPT$ Definition 5.4.6
  * circumparameter Definition 2.1.8
  * clopen §1.3.1
  * closed choice Definition 5.2.6, Definition 5.2.6
  * compact choice Definition 5.2.1
  * complete tiling 1st item
  * compositional product Definition 5.4.5
  * Computability Theory §1.2
  * computability theory §1.2.3
  * computable Definition 1.2.13, Definition 1.2.5
  * computable prototile sets Definition 3.1.1
  * computable relation Definition 1.2.1
  * computable tile sets Definition 3.1.1
  * computably enumerable §1.2.3, Definition 1.2.14
  * concatenation §1.3
  * constructive ordinal Definition 1.4.7
  * converges Definition 2.1.7
  * cyclic tag system Definition 6.2.11
  * dense orbit Definition 6.2.2
  * dense periodic points Definition 6.2.4
  * Devaney chaos Definition 6.2.5
  * diagonalization §1.2.4
  * disjoint union of prototile sets Definition 4.2.6
  * DNR §1.2.4
  * domino problem Definition 2.2.1
  * Domino Problem for Wang Tiles Principle Definition 5.5.1
  * edge meets 1st item
  * elementary cellular automaton Definition 6.1.2
  * extendible nodes Definition 1.5.2
  * extension theorem Theorem 2.1.13
  * finitely branching Definition 1.3.2
  * fixed point Theorem 1.2.20
  * halting problem Definition 1.2.6
  * Hausdorff distance Definition 2.1.4
  * height §1.4.4
  * immediate successor §1.3.1
  * index set Definition 1.2.30
  * infinite path 1st item
  * initial segment §1.3
  * initial substring §1.3
  * inparameter Definition 2.1.9
  * $k$-tree Definition 3.2.4
  * Knudson chaos Definition 6.2.6
  * left/rightmost permutive Definition 6.2.9
  * $m$-reducible Definition 1.2.21
  * macro tile Definition 4.1.3
  * match criteria 2nd item
  * megatile Definition 4.4.3
  * naming system item 1
  * natural enumeration Proof.
  * next state map §6.2.1
  * oracle Definition 1.2.24
  * oracle Turing machine Definition 1.2.24
  * order isomorphic 3rd item
  * order type 4th item
  * ordinal 5th item
  * ordinal notations Definition 1.4.3
  * partial tiling 2nd item
  * patch Definition 2.1.5
  * pattern §4.1.2
  * periodic tiling Definition 4.1.1
  * permutive Definition 6.2.8
  * permutivity Definition 6.2.8
  * phase space §6.2.1
  * Post’s Set Definition 1.2.18
  * properly extended §1.4.5
  * prototile 1st item
  * quasi-periodic §4.1.2
  * realizer 1st item
  * realizer reducibility §5.1.1
  * recurring domino problem Definition 3.2.1
  * representation item 2
  * represented space Definition 5.1.1
  * Rice’s theorem Theorem 1.2.31
  * schema tile Definition 2.3.3
  * self-similar prototile set Definition 4.1.5
  * sequence number Definition 1.4.21
  * Skolem function Definition 1.2.3
  * Skolem/Herbrand normal form Definition 1.2.3
  * $SNT$ equivalence to $WELL$ Theorem 3.4.7
  * strongly not tiling §3.4.2
  * strongly Weihrauch reducible Definition 5.1.5
  * $TILE$ Definition 3.3.1
  * tile Definition 2.1.1
  * $TILE$ equivalence to $ILL$ Theorem 3.4.1
  * tiles over Definition 2.1.6
  * tilings §2.1.1
  * topological sensitivity Definition 6.2.1
  * topologically transitive Definition 6.2.3
  * total tiling Definition 2.2.4
  * Total Wang tilings Definition 2.2.4
  * totally ordered set 1st item
  * tree Definition 1.3.1
  * Turing degree 2nd item
  * Turing Machine §1.2.1, Definition 1.2.4
  * Turing reducibility §1.2.6
  * Turing reducible Definition 1.2.25
  * Universal Turing Machine Definition 1.2.7
  * Wang tiles Definition 2.2.2, Definition 2.2.2
  * weakly computable Definition 5.2.4
  * weakly tiling §3.4.2
  * Weihrauch reducibility Definition 5.1.5
  * well-founded Definition 1.4.8
  * well-ordered set 2nd item
  * well-ordering Definition 1.4.16
  * wild card Definition 5.4.1
  * $WTILE$ equivalence to $ILL$ Theorem 3.4.9
  * $\Pi^{0}_{1}$ Classes Definition 1.3.4