University of Leeds

School of Mathematics

Submitted in accordance with the requirements for the degree of

Doctor of Philosophy

October 2019

Intellectual Property Statement

> The candidate confirms that the work submitted is his own and that
> appropriate credit has been given where reference has been made to the work
> of others.
>
> This copy has been supplied on the understanding that it is copyright
> material and that no quotation from the thesis may be published without
> proper acknowledgement.
>
> The right of to be identified as Author of this work has been asserted by
> him in accordance with the Copyright, Designs and Patents Act 1988.
>
> © October 2019 The University of Leeds and

Abstract

In this thesis we will present and discuss various results pertaining to
tiling problems and mathematical logic, specifically computability theory.

We focus on Wang prototiles, as defined in [32]. We begin by studying Domino
Problems, and do not restrict ourselves to the usual problems concerning
finite sets of prototiles. We first consider two domino problems: whether a
given set of prototiles $S$ has total planar tilings, which we denote $TILE$,
or whether it has infinite connected but not necessarily total tilings,
$WTILE$ (short for ‘weakly tile’). We show that both
$TILE\equiv_{m}ILL\equiv_{m}WTILE$, and thereby both $TILE$ and $WTILE$ are
$\Sigma^{1}_{1}$-complete. We also show that the opposite problems, $\neg
TILE$ and $SNT$ (short for ‘Strongly Not Tile’) are such that $\neg
TILE\equiv_{m}WELL\equiv_{m}SNT$ and so both $\neg TILE$ and $SNT$ are both
$\Pi^{1}_{1}$-complete.

Next we give some consideration to the problem of whether a given (infinite)
set of prototiles is periodic or aperiodic. We study the sets $PTile$ of
periodic tilings, and $ATile$ of aperiodic tilings. We then show that both of
these sets are complete for the class of problems of the form
$(\Sigma^{1}_{1}\wedge\Pi^{1}_{1})$. We also present results for finite
versions of these tiling problems.

We then move on to consider the Weihrauch reducibility for a general total
tiling principle $CT$ as well as weaker principles of tiling, and show that
there exist Weihrauch equivalences to closed choice on Baire space,
$C_{\omega^{\omega}}$. We also show that all Domino Problems that tile some
infinite connected region are Weihrauch reducible to $C_{\omega^{\omega}}$.

Finally, we give a prototile set of 15 prototiles that can encode any
Elementary Cellular Automaton (ECA). We make use of an unusual tile set, based
on hexagons and lozenges that we have not see in the literature before, in
order to achieve this.

Dedicated to Prof. S. Barry Cooper

Acknowledgements

I wish to thank my supervisors Dr. Paul Shafer and Prof. Michael Rathjen, both
of whom have guided and inspired me along this journey. In particular, Dr.
Shafer’s regular engagement and inspiring passion for computability, logic,
and mathematics, matched with his rigorous approach and choice quality coffee,
has been one of the most profound privileges to work with. The generosity of
time, expertise, and guidance from both of my supervisors has made this Ph.D.
possible.

I am grateful to my colleagues and friends in the Logic Group at the
University of Leeds for their support in answering questions and commenting on
ideas, in particular: Giovanni Solda, Emanuele Frittaion, Alberto Marcone,
Marta Fiori Carones, John Truss, Stan Wainer, Andrew Brooke-Taylor, Charles
Harris, Anton Freund, Martin Krombholz, Bjarki Geir Benediktsson, John Howe,
Jakob Vidmar, Richard Matthews, Rosario Mennuni, James Gay, James Riley, Anja
Komatar, Cong Chen, Richard Whyman, Sarah Sigley, Cesare Gallozzi, and Petra
Staynova. Of note is Emanuele Frittaion, whose observation regarding Weihrauch
degrees after a seminar I gave spawned the work in Chapter 5, and Andrew
Brooke-Taylor for the references on Vopěnka’s Principle in Chapter 4.

My thanks to the University of Leeds and the School of Mathematics for their
hosting me, and to the EPSRC for their financial assistance. It has been
gratefully received.

My thanks to my parents Pauline and Richard, my brother Edward, and my family
- in particular my mum, who has lingered through several conversations I am
certain she was not expecting to understand all of. My love and thanks to you
all for supporting me in many ways.

I acknowledge the plentiful support of my friends and colleagues in the
technology scene, including the participants at Leeds Hackspace, DC151, and
DC11331, and the DEFCON and BSides family. I honour the marvellous work of the
baristas of Leeds.

Lastly, my thanks to my first supervisor on this Ph.D., Prof. S. Barry Cooper,
to whom this thesis is dedicated. Without you, Barry, I would not have been so
encouraged and prepared to undertake this task in the beginning.

Cheers, Barry, and thank you, my friends.

###### Contents

  1. 1 Computability, Trees, and Preliminary Concepts
    1. 1.1 Preliminaries
    2. 1.2 Computability
      1. 1.2.1 Turing Machines
      2. 1.2.2 Enumeration in Stages
      3. 1.2.3 Core Background to Computability Theory
      4. 1.2.4 Conventional theorems in Computability
      5. 1.2.5 Computable Notions of Reducibility
      6. 1.2.6 Turing Reducibility and the Jump Operator
    3. 1.3 Computable Trees
      1. 1.3.1 Trees and $\Pi^{0}_{1}$ Classes
    4. 1.4 Kleene’s $\mathcal{O}$ and $\Pi^{1}_{1}$-Completeness
      1. 1.4.1 Ordinal Notations and Kleene’s $\mathcal{O}$
      2. 1.4.2 Kleene’s $\mathcal{O}$
      3. 1.4.3 Kleene’s $\mathcal{O}$, and Well-foundedness
      4. 1.4.4 Recursive Ordinals and well-founded Relations
      5. 1.4.5 $\mathcal{O}$, Well-foundedness, and $\Pi^{1}_{1}$ Sets
    5. 1.5 Trees, Ordinals, and the Arithmetical and Analytic Hierarchies
      1. 1.5.1 Fundamental Results
      2. 1.5.2 Trees and Analytic Sets
  2. 2 Tilings - Concepts and Results
    1. 2.1 Tilings of the Plane
      1. 2.1.1 Preliminaries of Tilings
      2. 2.1.2 The Extension Theorem
    2. 2.2 The Domino Problem
      1. 2.2.1 Wang Tiles
    3. 2.3 Undecidability of the Domino Problem
      1. 2.3.1 Universal Turing Machine and TM Tilings
    4. 2.4 Implications of TM Tilings
  3. 3 $\Sigma^{1}_{1}$-Complete Tilings
    1. 3.1 Computable Trees and Computable Tilings
    2. 3.2 $\Pi^{1}_{1}$ Properties of Tilings
      1. 3.2.1 Harel’s $\Pi^{1}_{1}$ Tilings
    3. 3.3 Domino Problems for Infinite Computable Sets of Prototiles
      1. 3.3.1 Filter for Computable Trees
    4. 3.4 $\Pi^{1}_{1}$ and $\Sigma^{1}_{1}$ Domino Problems
      1. 3.4.1 Equivalences to $TILE$
      2. 3.4.2 Further Equivalences for $WELL$ and $ILL$
      3. 3.4.3 Discussion of these Results
  4. 4 Aperiodicity, Tilings, and Logical Complexity
    1. 4.1 Aperiodic Tilings and $\Sigma^{1}_{1}$/$\Pi^{1}_{1}$ Sets
      1. 4.1.1 Definitions of Periodic and Aperiodic Tilings
      2. 4.1.2 Overview of Aperiodicity
    2. 4.2 Periodicity and Aperiodicity of $ILL$
      1. 4.2.1 Periodicity and Aperiodicity of $WELL$
    3. 4.3 Completeness of $PTile$ and $ATile$
    4. 4.4 Aperiodicity and Periodicity for Finite Prototile Sets
  5. 5 Weihrauch Reducibility and Tiling Problems
    1. 5.1 Weihrauch Reducibility
      1. 5.1.1 Core Concepts in Weihrauch Reducibility
    2. 5.2 Weihrauch Reducibility and Choice Principles
    3. 5.3 Weihrauch Reducibility and Tiling Problems
    4. 5.4 Weihrauch Reductions for Weak Planar Tilings
      1. 5.4.1 Weihrauch Equivalence for $CWPT$
      2. 5.4.2 Weihrauch Reducibility for Other Weak Tiling Principles
    5. 5.5 General Weihrauch Reducibility for Wang Domino Problems
      1. 5.5.1 Further Weak Tiling Problems
  6. 6 Small ECA Tilings
    1. 6.1 Elementary Cellular Automata
      1. 6.1.1 Elementary Cellular Automata
    2. 6.2 Some Results about ECAs
      1. 6.2.1 ECAs and Chaos
      2. 6.2.2 ECAs and Turing Universality
    3. 6.3 Elementary Cellular Automata and Tilings
    4. 6.4 A 15 Prototile ECA Tiling
  7. 7 Conclusion
    1. 7.1 Conclusions from Results
    2. 7.2 Open Problems and Further Work

###### List of Figures

  1. 2.1 Edge Conditions in the von Neumann Neighbourhood surrounding a Wang tile.
  2. 3.1 Overall shape of our tiling construction in the proof of 3.4.1.
  3. 3.2 Tile Path Construction
  4. 3.3 Weakly Tiling Path Construction
  5. 4.1 A Penrose Tiling - generated online at https://misc.0o0o.org/penrose/
  6. 4.2 A set of 13 aperiodic Wang prototiles due to Culik [17].
  7. 4.3 A set of 11 aperiodic Wang prototiles due to Jeandel and Rao [39].
  8. 4.4 $PTile$ for $e\in ILL$ Construction
  9. 4.5 Overall shape of our tiling construction in the proof of 3.4.1.
  10. 6.1 The schematic diagram for Cook’s encoding of Cyclic Tag Systems in Rule 110, taken from [28]
  11. 6.2 A sample tiling of $S_{30}$. NB: Indicators $O^{f}$ and $1^{f}$ are omitted for clarity.
  12. 6.3 A 15 prototile set of tiles that encodes the behaviour of the Rule 30 ECA in the lower half-plane.
  13. 6.4 Example few rows of a hexagon and lozenge tiling of Rule 30.

###### List of Tables

  1. Glossary of Sets and Constructions
  2. 6.1 Rule 30 Automaton Rules
  3. 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.

## Introduction

In this thesis we will explore the connections between tiling problems and
logic, specifically in relation to, and through the lens of, computability
theory.

### Background to the Thesis

Broadly speaking, the tiling problems we study fall into two categories, for
given prototile set $S$:

  1. (1)

Domino Problems - the question of whether $S$ tiles the plane.

  2. (2)

Tiling Properties - do all/any $S$-tilings have some specific property, e.g.
are they all periodic or aperiodic?

We will construct well defined versions of both of these problems, and study
their relationships to various areas of computability theory.

This thesis builds on results that the author first presented in their MSc
dissertation [12] as part of their MSc Mathematics at the University of Leeds.
In that work, we presented some ways to code various results in computability,
as well as elementary cellular automata, into sets of Wang prototiles.

In building on these results, we explore with much more depth the ways in
which the classes of tiling problems listed above relate to various aspects of
computability. We ask questions along the following lines:

  * •

What are the computable parts of a given tiling problem?

  * •

How do tiling problems fit into existing computability hierarchies?

We also present improved versions of the Elementary Cellular Automata tilings
using an original tile schema that we have constructed for this purpose.

#### Motivations

There are some very interesting results in the literature regarding tiling
problems and logic, and in general the aim is to determine both what
conditions can be met by some given prototile set, and conversely whether
there exist prototile sets that exhibit particular properties that are of
interest.

We will look at both finite and infinite sets of prototiles and determine
results for both of these classes of possible tiling problems. Specifically,
we are interested in formulating answers to the question:

“What is the relative difficulty for a given problem about tile sets and
tilings?”

This question, as the literature belies, is far from a foregone conclusion.
The construction of a prototile set is intrinsically linked to the various
patterns and behaviours of that set’s tilings in the plane.

Given the well-studied logical strength of other combinatorial principles, we
hope to expand the logical and mathematical vocabulary in this respect for
tiling problems.

#### Computability and Tiling Problems

In 1964 (see [32]) Wang proved that if a prototile set of Wang tiles -
diagonally quadrisected square tiles - can tile any arbitrarily large finite
portion of the plane, then it can tile the whole plane. This is a fairly
straightforward compactness argument, and does indeed use König’s lemma (cited
as ‘König’s Infinity Lemma’ in [32]) to achieve the result, which we present
in Chapter 2, Theorem 2.2.5.

Following on from this work, Wang continued to ask interesting questions
regarding tiling problems. Indeed, many of the interesting results regarding
tilings spawns from a conjecture due to Hao Wang in the early 60’s:

######  Conjecture 0.0.1.

It is necessary, as well as sufficient, that if a set of prototiles $S$ is
periodic, it tiles the plane.

Seeking an answer to this question, Berger in [5] formulated the first set of
aperiodic Wang tiles - a prototile set consisting of 20,426 tiles that has
only aperiodic tilings of the plane. This completely disproved Wang’s
conjecture, and demonstrated that periodicity is sufficient, but not necessary
for a prototile set to tile the plane - thereby negating the conjecture.

Berger’s refutation of Wang’s conjecture was surprising, and laid the
groundwork for further results in creating aperiodic prototile sets for a
decade - the most well known of which are probably Penrose tilings. A summary
of this work is given at the start of Chapter 4.

In addition to creating the first aperiodic prototile sets, Berger was also
the first to formulate the connection between Wang tilings and Turing
Machines. The ultimate result was that the domino problem for finite sets of
Wang prototiles, namely

“Does a finite set of Wang prototiles $S$ tile the plane?”

and the halting problem

“Does a given Turing Machine $M$ halt on given input $x$?”

are equivalent, and these formed the central results of his thesis.

This equivalence was highly motivational for the current work we have
regarding prototile sets and mathematical logic, as we can include the Domino
Problem class of tiling problems for finite sets of prototiles as having the
normal form of some $\Sigma^{0}_{1}$ formula - or the negation of one, if we
desire an infinite planar tiling.

### The Current Literature on Tiling Problems and Logic

Firstly, we will summarise results in the literature that relate areas of
logic to theorems and ideas about tiles, tilings, and prototile set properties
and constructions.

Although Berger showed early on that Wang tiles are related to the
undecidability of the Halting Problem, developments of using and studying
tilings in mathematical logic is comparatively recent.

Beginning with Harel in [35], who showed how problems of ‘high
undecidability’, i.e. problems in $\Pi^{1}_{1}$, can be expressed as tiling
problems. This is achieved in the plane by means of a set of carefully
constructed Wang prototiles. Harel then built on this work in [37] developing
more full relationships between prototile sets and theorems about
well/illfounded trees. Indeed, [35] is cited by many texts in the field of
Dynamic Logic - with Harel providing a chapter on this in the Handbook of
Philosophical Logic [36].

In ‘On the Convenience of Tilings’ [6], van Emde Boas showed how various
complexity classes are captured in specific tiling boundary results. Starting
with an effective formulation of Turing Machines as prototile sets, van Emde
Boas shows that a Wang prototile set that is unbounded vertically and
horizontally is NP-complete, owing to the fact that a Turing Tape is realized
left to right, whilst successive stages of a computation are realized
vertically. Similarly, van Emde Boas continued by showing that a ‘corridor’
tiling - a tiling that is of bounded width but unbounded height - is complete
for PSPACE.

Following Durand’s work on tilings and quasiperiodicity in [24], the work of
Durand, Levin, and Shen [25] showed that for every prototile set admits either
no tiling or some tiling with $\mathcal{O}(n)$ Kolmogorov complexity of its
$(n\times n)$-squares. Thatis to say, the string taken to describe any given
square in the tiling has a complexity linearly related to the size of the
square. This work was a continuation of their study of computational
complexity paradigms and how they relate to tile sets and their planar
tilings.

In Durand, Romashenko, and Shen [26], we find a significant development in the
underlying theory of tilings - the existence of fixed point-based tilings.
This work married up the work on Wang tiles with the previous work by Penrose
and Amman on aperiodic Penrose tilings - see [32, Chapters 10,11] for full
presentations and discussions of these earlier works.

With these results in hand, recent work on $\Pi^{0}_{1}$ sets and tilings by
Brown-Westrick in [64] utilised these self-similar Turing Machine tilings from
[26] in order to show that effectively closed subshifts of the distinct square
shift are all sofic [64, Theorem 1, 2].

The study of tilings has, naturally from the above, been found and utilised in
symbolic dynamics. A full introduction is found in the aforementioned Harel
[36], with some interesting results being found recently in the work of
Delvenne and Blondel [21] where it is shown that by means of tiling problems,
an analogue of Rice’s theorem for computable functions is possible, giving
that certain properties of dynamical systems are undecidable. As an extension
to this result (Theorem 1 in [21]), it is shown that topological entropy (as
defined in [21, Sec. 4.3, p.140]) is undecidable for Turing Machines and
tilings alike. Simpson in [53] also gave the following insight into tiling
problems and their relation to mathematical logic, writing in [53] that:

> “In the study of 2-dimensional subshifts of finite type, it has been useful
> to note that they are essentially the same thing as _tiling problems_ in the
> sense of Wang [ in [60]].”

Indeed, Levin’s address, given as the Kolmogorov Lecture in 2005 at the
University of London - see [44] \- gave some detail on the use of enumerable
tilings in order to prove that $2$-adic shifts and reflections can be enforced
by a prototile set.

It is interesting to note that [21] makes use of the notion of _quasi-
periodicity_ \- the property that every pattern $u$ of the tiling, there
exists a $k$ such that any given $(k\times k)$ patch of tiles contains $u$.
This notion is an interesting interim property that bridges the gap between
fully periodic and fully aperiodic - see section 4.1.2 for further details.

Adjacent to this work in mathematical logic, papers by Kari [40] and later
Culik [17] showed how theorems about cellular automata that compute non-
repeating reals can be converted into prototile sets to give very small sets
of aperiodic prototiles. This work was generalised by Jeandel and Rao in [39]
to give the smallest possible set of aperiodic Wang prototiles, with a very
small size of 11 prototiles to achieve this. They also proved through various
means - both mathematically and with computational assistance - that this
prototile set was smallest possible, and also had the property that if we were
to remove any single tile from the prototile set, we no longer have tilings of
the plane. Thereby, this prototile set either tiles aperiodically or fails to
tile at all.

Having given this outline of the general view of tiling problems with respect
to mathematical logic and related fields, we are now in a position to outline
our contribution to this field.

### Outline of the Thesis and Main Results

Here we give an overview of the outline of the thesis, the main points in each
chapter, and an account of the original work we are presenting in this volume.

#### Overview and Outline of the Thesis

In chapter 1 we give a full background to the underlying mathematical logic
and machinery we will use throughout the thesis. We give many definitions and
present theorems generally without proofs, indicating sources along the way
should they be necessary to the reader. We introduce precise definitions of
Turing Machines as well as basic computability results that will be used later
on. We also define various notions of reducibility in preparation for our work
in Chapter 3.

We also give the background theory of computable trees as computable subsets
of Baire space and Cantor space that form the backbone of many of our results
in later chapters. We also give background results concerning the
$\Pi^{1}_{1}$-completeness of Kleene’s $\mathcal{O}$ which we shall use in
later chapters. We finish this chapter with overview material for how
computable trees, ordinals, and the arithmetical and analytic hierarchies hang
together mathematically.

In chapter 2 we give an overview of core results regarding tilings and
prototile sets. We give proofs of the Extension Theorem and state formally the
first of our core tiling problems - the Domino Problem. We then give a proof
of the undecidability of the Domino Problem by means of the computable
conversion of any Turing Machine into a set of prototiles in such a way that
their tilings tiling the plane iff the given Turing Machine on input $x$ does
not halt.

We introduce here the notion of a tile schema - a way of describing specific
placement of colours from chosen colour sets. This allows us to describe
(infinite) prototile sets by means of carefully chosen colour sets and schema
tile construction such that the resultant product of combining these gives
prototile sets whose tilings carry the specific properties we are looking for.
Though this method may seem convoluted prima facie, we hope to demonstrate
that this technique leads in fact to quite straightforward proofs for
translating various principles and concepts into the combinatorial properties
of a prototile set.

We round off this chapter by noticing some interesting corollaries and
propositions arising from this fact that are of similar ilk to other results
in mathematical logic - principally the fact that there exist prototile sets
such that their domino problem is undecidable by Peano Arithmetic.

In chapter 3 we state the first run of our main results - $\Pi^{1}_{1}$\- and
$\Sigma^{1}_{1}$-completeness of specific domino problems. We consider domino
problems that require all tilings to be total, as well as domino problems that
do not require total tilings, but instead only require an infinite connected
patch of the plane to be tiled. To prove these results of $\Pi^{1}_{1}$ and
$\Sigma^{1}_{1}$ completeness, we utilise the completeness for these classes
due to wellfounded and illfounded trees. We construct tile schemas for each,
and then demonstrate the completeness by means of $m$-reductions between our
classes of prototile sets and ill-/well-founded trees.

With Chapter 4 we depart from domino problems, and instead consider the
problems regarding whether or not the tilings for a given prototile set are
all periodic, all aperiodic, or some mixture of the two. We state the
fundamental results, with background references provided for this rather
interesting class of problems.

We demonstrate that these notions are simultaneously $\Pi^{1}_{1}$ and
$\Sigma^{1}_{1}$, as well as prove that, in fact, the questions of periodicity
and aperiodicity for infinite sets of prototiles are both complete for the
class of problems of the form $(\Pi^{1}_{1}\wedge\Sigma^{1}_{1})$. We also
show that the set of all finite prototile sets whose tilings are aperiodic is
$\Pi^{0}_{1}$, which is a surprising result.

Chapter 5 is an extension of this notion of computable reductions into the
realm of Weihrauch reducibility. We give a feature rich presentation of the
definitions and notions of Weihrauch reducibility, and state some core
results. We then give intuitions for the core concepts in this theory, and
proceed to derive Weihrauch equivalences between domino problems and closed
choice on Baire space.

Intuitively these results are motivated by realisation that all Wang tilings
can be given by ‘tiling trees’, first defined by Wang, for which closed choice
realizers in Baire space can locate the infinite paths through, and from which
we can recover a tiling of the plane. We can also consider that, given a non-
deterministic prototile set - that is, for any prototile in the set there
exist multiple possibilities for matching tiles in a given tiling - then
having some choice principle in play is a natural conclusion. We give some
exact results by means of Weihrauch equivalences.

The proposal for a new way of coding Elementary Cellular Automata (ECAs) into
prototile sets is the subject of Chapter 6. Here, we demonstrate that for the
3-ary functions defining the behaviour of ECAs is naturally coded by a hexagon
and lozenge based construction. With the requisite tiles to neaten up the
upper edge of our tiling, we have a prototile set consisting of 15 tiles that
very naturally give a way to represent the behaviour of ECAs in tilings of the
half-plane by means of coding the first ‘input’ row, and then making it such
that the subsequent tilings of each row are exactly given by the underlying
function of the given ECA.

We also show that such a prototile set is necessarily then chaotic and Turing
Complete given correct choices for the ECA rule that we encode - Rule 30 and
Rule 100 respectively for these results. Thus we have a nice and very small
prototile set that carries with it a lot of possible mathematical capability.

Finally, we complete the thesis with an overview in Chapter 7 of the various
open problems that we have found along the way - both in the literature and in
the course of our research. We also aim to indicate the possible avenues for
extending the results in this thesis further.

#### Summary of Original Work

In this thesis, the following items are our original contributions:

  * •

Our proof of theorem 2.3.2 is inspired by the form in [6], but is reshaped to
match the structure of our later proofs. The observations leading up to
corollary 2.4.5 have not been found in the literature, but are relatively
straightforward to derive.

  * •

The results given in Chapter 3 are all original unless stated otherwise.
Specifically, our main results are:

    * –

Lemma 3.3.3

    * –

Theorem 3.4.1

    * –

Theorem 3.4.4

    * –

Theorem 3.4.7

    * –

Theorem 3.4.9

  * •

The results concerning $ATile$, $PTile$, $ATile_{FIN}$ and $PTile_{FIN}$ in
Chapter 4 are all original:

    * –

Theorem 4.2.1

    * –

Theorem 4.2.2

    * –

Theorem 4.2.8

    * –

Theorem 4.2.9

    * –

Theorem 4.3.1

    * –

Theorem 4.3.2

    * –

Corollary 4.3.3

    * –

Theorem 4.4.5

    * –

Theorem 4.4.6

  * •

The Weihrauch reductions for tiling problems in Chapter 5 are original:

    * –

Theorem 5.3.3

    * –

Theorem 5.4.3

    * –

Theorem 5.4.7

    * –

Theorem 5.5.2

  * •

The main result in Chapter 6 is also original: Theorem 6.4.1

## Glossary of Sets and Constructions

We give a table that details all of the major sets and operators that are used
in this thesis, for convenience and for reference.

Name |  Description |  Thesis Ref.
---|---|---
$m$-reducibility |  Given two sets $A$ and $B$, $A$ is $m$-reducible to $B$, written $A\leq_{m}B$, if there exists some computable function $f:\omega\rightarrow\omega$ such that for all $x\in\omega$, $x\in A\iff f(x)\in B$ |  1.2.21
Weihrauch Reducibility |  Given two operators $f$ and $g$ on represented spaces, we say $f\leq_{W}g$, if there exist computable $H,K:\subseteq\omega^{\omega}\rightarrow\omega^{\omega}$ such that for any realizer $G\vdash g$, $F=K\langle id_{\omega^{\omega}},GH\rangle$ is a realizer for $f$. |  5.1.5
$WELL$ |  The set of all indices $e$ such that $\varphi_{e}$ is the characteristic function of a well-founded tree $T\subseteq\omega^{<\omega}$. |  3.4.3
$ILL$ |  The set of all indices $e$ such that $\varphi_{e}$ is the characteristic function of an ill-founded tree $T\subseteq\omega^{<\omega}$. |  3.3.2
$TILE$ |  The set of all indices $e$ such that $\varphi_{e}$ is the characteristic function of an infinite Wang prototile set whose tilings are total in the plane. |  3.3.1
$WTILE$ |  The set of all indices $e$ such that $\varphi_{e}$ is the characteristic function of an infinite Wang prototile set whose tilings are infinite, connected, but not necessarily total in the plane. |  3.4.5
$SNT$ |  The set of all indices $e$ such that $\varphi_{e}$ is the characteristic function of an infinite Wang prototile set whose connected tilings are all finite. |  3.4.6
$ATile$ |  Set of all $e$ such that $\varphi_{e}$ is the characteristic function for a set of prototiles who planar tilings are all total and aperiodic. |  4.1.2
$PTile$ |  Set of all $e$ such that $\varphi_{e}$ is the characteristic function for a set of prototiles who planar tilings are all total and periodic. |  4.1.1
$ATile_{FIN}$ |  Set of all $e$ such that $\varphi_{e}$ is the characteristic function for a _finite_ set of prototiles who planar tilings are all total and aperiodic. |  4.4.2
$PTile_{FIN}$ |  Set of all $e$ such that $\varphi_{e}$ is the characteristic function for a _finite_ set of prototiles who planar tilings are all total and periodic. |  4.4.1
AIT |  The construction found in the proof of theorem 3.4.1 that creates an aperiodic prototile set given an ill-founded tree. |  4.2.7
PIT |  The construction found in the proof of theorem 4.2.2 that creates an aperiodic prototile set given an ill-founded tree. |  4.2.7
$CT$ |  The operator that takes some set of Wang prototiles as input and returns a total tiling of the plane. |  5.3.2
$CWPT$ |  An operator that takes a set of Wang prototiles and returns a connected planar, but not necessarily total tiling. |  5.4.2
$CIPT$ |  An operator that takes a prototile set $S$ that has total planar tilings, and returns an infinite ‘slice’ of this tiling as a tiling of an infintie region of $\mathbb{Z}^{2}$. |  5.4.6
$WIPT$ |  An operator that takes a set of prototiles and return a tiling that has an infinite patch tiled within it, but we do not know where it is. |  5.5.3
$DPW$ |  The $DPW$ operator takes some set of prototiles and return a tiling that has an infinite connected patch within it. |  5.5.1
$C_{\omega^{\omega}}$ |  Closed choice on Baire space - equivalent to finding a path through an ill-founded Baire space tree. |  5.2.6
$C_{2^{\omega}}$ |  Closed choice on Cantor space - equivalent to Weak König’s Lemma. |  Sec 5.5.1
$C_{\omega}$ |  closed choice on the natural numbers - this takes a function $f:\omega\rightarrow\omega$ such that $range(f)\neq\omega$, and returns some point $n\notin range(f)$. |  Sec. 5.5.1

##  Chapter 1 Computability, Trees, and Preliminary Concepts

> The Analytical Engine has no pretensions whatever to originate anything. It
> can do whatever we know how to order it to perform…But it is likely to exert
> an indirect and reciprocal influence on science itself.
>
> Ada Lovelace,
> in a Letter to Charles Babbage

In this chapter we will present the background theory for the rest of this
volume. We will give definitions, theorems, and select proofs to lay the
logical and mathematical groundwork for later chapters.

###  1.1. Preliminaries

We will use the following standard notation throughout this work:

######  Definition 1.1.1.

We shall make use of the standard logical notation:

  * •

$\forall x$ and $\exists x$ for ‘for all $x$’ and ‘there exists $x$’
respectively.

  * •

$x\wedge y$ and $x\vee y$ for logical ‘$x$ AND $y$’ and ‘$x$ OR $y$’
respectively.

  * •

In general, variables and constants will be in lower case Roman lettering:
$a,b,c,x,y,z,\ldots$

  * •

Lower case Roman letters such as $f,g,h,s,t,\ldots$ can also be used for
function names.

  * •

In general, sets will be in upper case Roman lettering: $X,Y,Z,\ldots$

  * •

We shall use $A\rightarrow B$ to denote logical implication.

  * •

We shall use $A\cap B$ and $A\cup B$ to denote set intersection and union of
$A$ and $B$.

  * •

We shall use $A\setminus B$ to denote the set $A$ with any elements found in
$B$ removed, the standard set-minus.

  * •

Greek letters $\alpha,\beta,\gamma,\ldots$ shall be used primarily for
ordinals, with the exception of $\varphi$ which is used for Turing Machines.

  * •

We shall use $\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}$ to mean the natural
numbers, integers, rationals, and reals respectively.

  * •

For a given set $A$, let $\mathcal{P}(A)$ denote the _powerset_ of $A$ \- the
set of all subsets of $A$.

  * •

Unless otherwise indicated, our computable functions will be of the form
$f:\omega\rightarrow\omega$.

######  Definition 1.1.2 (Cantor Pairing Function).

We shall use the standard Cantor pairing function to represent ordered pairs
$\langle x,y\rangle$ as follows:

$\langle x,y\rangle=\frac{(x+y)(x+y+1)}{2}+y$

We will shorten the notation for ordered $n$-tuples as $\langle
x_{1},x_{2},\ldots,x_{n}\rangle$, with $\langle x,y,z\rangle=\langle\langle
x,y\rangle,z\rangle$, and so forth. We fix this coding for the duration of
this thesis, which will serve our definition of ‘computable’ later.

We denote the set of natural numbers by its ordinal notation $\omega$,
allowing for $\mathbb{N}$ to be used where it will avoid confusion.

###  1.2. Computability

We will use standard definitions, using [16] as our main reference text.

######  Definition 1.2.1.

Let a _computable relation_ $R_{e}\subseteq\omega\times\omega)$ be a
computable relation such that for some Turing Machine $e$,

$R(x,y)\iff(\exists y)\varphi_{e}(x)=y$

######  Definition 1.2.2 (First Layer of the Arithmetical Hierarchy).

We define the following notation for logical complexity of formulas as
follows:

  * •

If for all $x\in\omega$ we have

$x\in A\iff(\exists y)R(x,y)$

for a computable relation $R$, then we say that $A$ is a $\Sigma^{0}_{1}$ set,
or $A\in\Sigma^{0}_{1}$.

  * •

If for all $x\in\omega$ we have

$x\in A\iff(\forall y)R(x,y)$

for a computable relation $R$, then we say that $A$ is a $\Pi^{0}_{1}$ set, or
$A\in\Pi^{0}_{1}$.

  * •

If $A\in\Sigma^{0}_{1}\cap\Pi^{0}_{1}$ then we say that $A$ is
$\Delta^{0}_{1}$, or write $A\in\Delta^{0}_{1}$.

Note that we rely on alternating existential/universal quantifiers, called
_prenex normal form_ , in the structure of our formulae to properly ascertain
which layer of any hierarchy we are at. Given this arithmetical hierarchy, we
will later denote the ‘analytic’ (also called ‘inductive’) hierarchy in the
same way, with a superscript of $1$ \- $\Pi^{1}_{1}$, $\Sigma^{1}_{1}$, and
$\Delta^{1}_{1}$. We will also find the following definition useful:

######  Definition 1.2.3 (Skolem/Herbrand Normal Form).

In the simplest form that we require in this thesis, a function is in Skolem
(Herbrand) normal form if all of the existentially (universally) quantified
terms are replaced by functions that take the preceding universally
(existentially) quantified variable as input.

We always begin with formulae in prenex normal form. An example of
Skolemisation is taking

$\forall x\,\exists y\,\forall z\,[P(x,y,z)]$

and producing

$\forall x\,\forall z\,[P(x,f(x),z)]$

for some _Skolem function_ $f$. Likewise, Herbrandization is taking some
formula

$\exists x\,\forall y\,\exists z\,[P(x,y,z)]$

and producing some

$\exists x\,\exists z\,[P(x,g(x),z)]$

for some _Herbrand function_ $g$.

####  1.2.1. Turing Machines

We define a Turing Machine as follows:

######  Definition 1.2.4.

A _Turing Machine_ (abbreviated to ‘TM’) consists of a bi-infinite row of
cells called the ‘tape’, upon which are written symbols according to a
‘program’ $P$ held in the TM ‘head’ that moves sequentially along the tape. A
program is a set of 5-tuples of the following form:

$(s,q,s^{\prime},q^{\prime},\\{L,R\\})$

where $s$ and $q$ are respectively the current symbol and state, $s^{\prime}$
is the symbol to be written in place of $s$, and $q^{\prime}$ is the next
internal state for the TM to switch to. The final item instructs the head to
move left or right, denoted $L$ or $R$ respectively.

Before a TM is run, we set the input in symbols on the tape, set the head at
position 0, and set the internal state to the starting state denoted $q_{0}$.
We then allow the TM to operate along the input on the tape according to its
program $P$.

Let us denote $\varphi_{e}(x)$ as the $e^{\text{th}}$ TM, under some chosen,
effective enumeration of all possible Turing Machines, acting on input $x$. We
say that our computation halts if we reach the reserved halting state, after
which no more computation is performed. If such a computation halts, whatever
is on the tape when it halts is considered the output. If the $e^{\text{th}}$
TM halts on input $x$ with output $y$, we write this
$\varphi_{e}(x)\downarrow=y$. Where $\varphi_{e}(x)$ does not halt, we write
$\varphi_{e}(x)\uparrow$.

######  Definition 1.2.5.

A function $f:\omega\rightarrow\omega$ is _computable_ if there exists some
$e$ s.t. $f=\varphi_{e}$.

######  Definition 1.2.6 (Halting Problem).

For any given TM $\varphi_{e}$ and some input $x$, is there a decidable method
of determining if $\varphi_{e}(x)$ halts?

######  Definition 1.2.7.

There exists a Turing machine $U$ \- the _Universal Turing Machine_ \- which
if given input $(e,n)$ can simulate $\varphi_{e}(n)$. That is to say,
$\varphi_{U}(e,n)=\varphi_{e}(n)$.

Alan Turing introduced these concepts in [58], and determined that it the
Halting Problem was in fact _undecidable_ , meaning that there is no universal
Turing Machine that can decide it.

####  1.2.2. Enumeration in Stages

Given the discrete way in which we formulate Turing Machines, it is natural to
press ‘stop’ every now and again and see how our computation might be going.
To do this, we can talk of successive stages of a computation, and the current
configuration of the Turing Machine’s tape at that particular point.

######  Definition 1.2.8.

For any TM $\varphi_{e}$:

  * •

Let $\varphi_{e,s}(x)$ denote the computation $\varphi_{e}(x)$ carried out up
to stage $s$.

  * •

Let $C_{e,s}$ denote the bi-infinite sequence corresponding to the tape
configuration of $\varphi_{e}(x)$ at stage $s$ of the computation.

######  Theorem 1.2.9 ([16, Thm. 5.2.10]).

For any computation $\varphi_{e}(x)$,

$\varphi_{e}(x)\downarrow\iff(\exists s)\varphi_{e,s}(x)\text{ is in the HALT
state}$

  * Proof.

If our computation has halted, then it has managed to reach the ‘HALT’ state
in the program. This necessarily means that a finite number of steps has been
carried out before we halt. Thus, $s$ exists. ∎

This gives the following corollary immediately:

######  Corollary 1.2.10 ([16, E. 5.2.14]).

For any $e$, $\\{x:(\exists s)\varphi_{e,s}(x)\downarrow\\}$ is a
$\Sigma^{0}_{1}$ set.

####  1.2.3. Core Background to Computability Theory

Computability Theory arose out of the work of Gödel, Church, Turing, Kleene,
Péter, and Post - their foundational papers are collected in [18]. A core
thematic idea arising out of this study, originally called ‘Recursion theory’,
was the Church-Turing Thesis defined as follows in [16, p.42]:

######  Definition 1.2.11 (Church-Turing Thesis).

For a given function $f$:

$f\text{ is effectively computable }\iff f\text{ is recursive }\iff f\text{ is
Turing computable.}$

This states that any algorithm we can come up with can be performed on a
Turing Machine. As Cooper points out in section 2.5 in [16], this gives us the
security that our intuition for computability is matched with relevant details
when it is needed.

We can extend idea of what is computable to sets and trees, which we can
initiate with the following definitions.

######  Definition 1.2.12.

Let $\chi_{A}$ denote the _characteristic function_ of a set
$A\subseteq\omega$.

######  Definition 1.2.13.

A set $A$ is _computable_ if the characteristic function $\chi_{A}$ is
computable.

That is to say that a set $A\subseteq\omega$ is computable if there exists $e$
such that for each $x\in\omega$

$\varphi_{e}(x)=\begin{cases}0&x\notin A\\\ 1&x\in A\end{cases}$

We can also define what it is for a set to be _computably enumerable_ :

######  Definition 1.2.14 (Computably Enumerable Sets).

We say that a set $A$ is _computably enumerable_ , or _c.e._ , if
$A=\emptyset$ or for some computable $f$,

$A=range(f)=\\{f(0),f(1),f(2),\ldots\\}$

There is an early result due to Post (see [16, p.72]):

######  Theorem 1.2.15 ([16, Thm. 5.1.5]).

If $A\subseteq\omega$ is computable, then $A$ is c.e.

  * Proof.

Let $A$ be computable. Then we have a computable characteristic function
$\chi_{A}$ that can decide for any $x\in\omega$ the question “$x\in A$?”,
meaning there is a code $i$ such that $\varphi_{i}=\chi_{A}$.

Given this $i$, we construct a Turing Machine that contains the machine given
by $i$ and recursively answers the questions “$0\in A$?”, “$1\in A$?”,
$\ldots$ in succession. For each positive answer to “$x\in A$?” we enumerate
$x$ into $A$, giving our result. ∎

In a similar way, we can prove other basic results, such as:

######  Theorem 1.2.16 ([16, Thm. 5.1.7]).

$A$ is computable if and only if both $A$ and $\overline{A}$ are c.e.

  * Proof.

($\rightarrow$) This follows from 1.2.15 above.
($\leftarrow$) If both $A$ and $\overline{A}$ are computably enumerable by
computable functions $f$ and $g$ respectively, then we can construct
$\chi_{A}$ by means of a TM that for all $x\in\omega$ computes both $f(x)$ and
$g(x)$. Clearly one of these will give an answer, as both sets are c.e., and
so $\chi_{A}$ is computable. ∎

However, the inverse arguments fail, which is where computability theory
starts to get much more interesting.

######  Theorem 1.2.17 ([16, Thm. 5.3.1]).

There exists a computably enumerable set that is is not computable.

We first define Post’s Set:

######  Definition 1.2.18 (Post’s Set).

Let $K=\\{e:\varphi_{e}(e)\downarrow\\}$.

  * Proof.

We first note that Post’s set $K$ is $\Sigma^{0}_{1}$, and thereby computably
enumerable, as

$e\in K\iff e\in W_{e}\iff\exists s\,\varphi_{e,s}(e)\downarrow.$

However, to see that $K$ is not computable, it suffices to show that
$\overline{K}$ is not computably enumerable. To see this, let $\overline{K}$
be computably enumerable for contradiction. Then $K=W_{i}$ for some
$i\in\omega$, giving

$x\in W_{i}\iff x\in\overline{K}\iff x\notin K\iff x\notin W_{x}$

For $x=e$ this forces a contradiction by forcing different answers for
“$j\in\overline{K}$”? and “$j\in W_{j}$?” for all $j\in\omega$. ∎

####  1.2.4. Conventional theorems in Computability

There are two standard, and very important theorems in computability - the
$s$-$m$-$n$ theorem, and the recursion theorem, which we will give brief
exposition and proofs of. These statements and proofs are based on [16] and
[55].

######  Theorem 1.2.19 ($s$-$m$-$n$ Theorem, [16, Thm. 4.2.6]).

For every $m,n\geq 1$ there exists a 1-1 computable function $s^{m}_{n}$ of
$m+1$ variables, such that for all $x,y_{1},y_{2},\ldots y_{m}$:

$\varphi^{(n)}_{s^{m}_{n}(x,y_{1},y_{2},\ldots,y_{m})}=\lambda
z_{1},z_{2},\ldots,z_{n}[\varphi^{m+n}_{x}(y_{1},\ldots,y_{m},z_{1},\ldots,z_{n})]$

Here, the notation of $\varphi_{x}^{y}$ denotes the machine with index $x$
that takes $y$-many inputs. This theorem is the only time we shall use this
notation in this thesis - later, the subscript shall be used to denote Oracle
sets.

Note, here we use the standard $\lambda$-notation for the substitution of
$z_{1},z_{2},\ldots$ into our computable function. The notation of $m$ and $n$
in $s^{m}_{n}$ denote the number of parameters into the computable function
$s$.

  * Proof sketch.

For $m=n=1$, let the TM $\varphi_{s^{1}_{1}(x,y)}(z)$ obtain $\varphi_{x}$,
and then apply $\varphi_{x}(y,z)$. Such an $s=s^{1}_{1}$ is computable, as it
is some effective procedure on $x$ and $y$. If it is not 1-1, then we can make
it so by ‘padding’ the process, and then letting the resultant $s^{\prime}$ be
s.t. $\varphi_{s(x,y)}=\varphi_{s^{\prime}(x,y)}$, ordering our inputs
$\langle x,y\rangle$ using a standard pairing function. ∎

######  Theorem 1.2.20 (Kleene’s Recursion Theorem, [16, Thm. 4.4.1]).

For every computable function $f$ there exists an $n$ \- called the _fixed
point_ of $f$ \- s.t.

$\varphi_{n}=\varphi_{f(n)}$

  * Proof.

Define the ‘diagonal’ function $d(u)$ as follows:

$\varphi_{d(u)}=\begin{cases}\varphi_{\varphi_{u}(u)}&\text{if
}\varphi_{u}(u)\downarrow\\\ \uparrow&\text{otherwise}\end{cases}$

Note that by 1.2.19, $d(u)$ is 1-1 and total. $d$ is also independent of the
$f$ that we are interested in.

For such a given $f$, let $i$ be the index given by

$\varphi_{i}=f\circ d$

Claim: We claim that $n=d(i)$ is some fixed point for $f$.

Note that, $f$ gives that $\varphi_{i}$ is total (as $d$ is total, above), so
$\varphi_{d(i)}=\varphi_{\varphi_{i}(i)}$. Thus our result follows from the
following equivalences:

$\varphi_{n}=\varphi_{d(i)}=\varphi_{\varphi_{i}(i)}=\varphi_{fd(i)}=\varphi_{f(n)}$

∎

In the previous proof, we constructed a function we described as _diagonal_.
Let _diagonalization_ , the construction of a diagonal function, be as
follows: let $e$ be the index of $\varphi_{e}$, which we diagonalise $e$ by
running $\varphi_{e}(e)$.

This technique was first introduced by Gödel in [34] to give us unprovable
statements, and was later used by Turing in [58] in relation to proving the
non-computability of the halting problem. The set of _Diagonally Non-
Recursive_ functions, or _DNR_ , is composed of all the computable functions
$f$ such that $f(e)\neq\varphi_{e}(e)$ for all $e$, and is the subject of
current study in modern mathematical logic. A thorough introduction and
treatment can be found in [38].

We can also note that the numbers for which $\varphi_{n}=\varphi_{f(n)}$ need
not be unique for any given $f$.

####  1.2.5. Computable Notions of Reducibility

In speaking about computability, we often want to relativise two sets between
each other. To do this, we will need the following definitions. We will begin
with a more basic form of reducibility, called $m$-reducibility. This is
defined in [16] as follows:

######  Definition 1.2.21 ($m$-Reducibility).

Given set $A$ and $B$, we say that $A$ is _$m$ -reducible_ to $B$, written
$A\leq_{m}B$, if there is a computable function $f:\omega\rightarrow\omega$
such that for all $x\in\omega$:

$x\in A\iff f(x)\in B$

If our function $f$ is injective, we say that $A$ is _1-reducible_ to $B$,
written $A\leq_{1}B$.

Although $m$-reducibility was introduced _after_ Turing reducibility (see
1.2.25 below), it is a slightly easier-to-formulate version of reducibility
between two sets. Cooper in [16, p.103] gives the intuition for
$m$-reducibility as $A$ being in some sense “at least as computable” as $B$.

From the definition 1.2.21 above, we can derive that

$A\leq_{m}B\iff\overline{A}\leq_{m}\overline{B}$

which follows from the fact that $A=f^{-1}(B)$, and following from a general
fact about pre-images we get that $\overline{A}=f^{-1}(\overline{B})$

Additionally, we can prove relatively straightforward theorems that give a
good flavour of how theorems around $m$-reducibility are carried out:

######  Theorem 1.2.22 ([16, Thm. 7.1.2]).

The ordering $\leq_{m}$ is:

  1. (1)

reflexive.

  2. (2)

transitive.

  3. (3)

if $A\leq_{m}B$ and $B$ is computable, then $A$ is computable.

  4. (4)

if $A\leq_{m}B$ and $B$ is c.e., then $A$ is c.e.

  * Proof.
  * 1\. - Reflexive Clearly $A\leq_{m}A$ as for all $x$, $f(x)=x$ is computable. ∎
2\. - Transitive Let $A\leq_{m}B$ be given by $f$, and $B\leq_{m}C$ be given
by $g$. We can get $A\leq_{m}C$ by

$x\in A\iff f(x)\in B\iff g(f(x))\in C$

so $A\leq_{m}C$ by $g\circ f$. ∎
For the next two proofs, let $A\leq_{m}B$ by a computable $f$.
3\. If $B$ is computable, then $\chi_{A}=\chi_{B}\circ f$, which is
computable. ∎
4\. Let $B\in\Sigma^{0}_{1}$, with

$x\in B\iff\exists yR(x,y)$

for a computable relation $R$. Then

$x\in A\iff\exists yR(f(x),y)$

giving us immediately that $A\in\Sigma^{0}_{1}$ also. ∎

Following on from these normal forms, we can prove that not just computable
sets are $\Sigma^{0}_{1}$, but also computably enumerable sets are
$\Sigma^{0}_{1}$ complete. This important intuition will be complimented by
successive results in later sections.

######  Theorem 1.2.23 ([16, Thm. 5.1.5]).

The following are equivalent:

  1. (1)

$A$ is c.e.,

  2. (2)

$A\in\Sigma^{0}_{1}$.

  * Proof.
  * $1\rightarrow 2$ Let $A$ be c.e. - if $A=\emptyset$, then $x\in A\iff\exists x(x=x+1)$. Let $A=range(f)$ for some computable function $f$. Then

$x\in A\iff\exists s(f(s)=x)$

where $f$ is now a computable relation between $s$ and $x$.
$2\rightarrow 1$ Let $A\in\Sigma^{0}_{1}$ such that there is a computable $R$
giving

$\exists yR(x,y)\iff x\in A$

we then construct a TM $e$ such that on input $y$, it will search through all
possible $x\in\omega$ and $R(x,y)$ (computable) with the following outcomes:

$\varphi_{e}(y)=\begin{cases}x&\text{if }R(x,y)\\\
\uparrow&\text{otherwise}\end{cases}$

Thus, $(\exists x)\varphi_{e}(y)=x\iff x\in A$ with $A$ also being c.e. ∎

####  1.2.6. Turing Reducibility and the Jump Operator

Although $m$-reducibility is incredibly useful, we can generalise it to a
notion of _Turing reducibility_ by means of the following definitions - first
proposed by Turing in 1939, but following the outline in [16].

######  Definition 1.2.24 (Oracle Turing Machines).

We define an _oracle Turing machine_ to be a normal Turing machine, but with
access to an extra tape - called the _oracle_ \- and makes use of _query
quadruples_ $(q_{i},S_{k},q_{j},q_{k})$ that allow the Turing machine to
behave as follows. Let $\varphi_{e}^{A}(x)$ be the $e^{th}$ TM on input $x$
and oracle $A$:

  * •

The TM computes as before until it encounters a query quadruple.

  * •

The TM, then in state $q_{i}$, will read the current value on the work tape,
call it $n$, and then query the oracle tape to ask $\text{is }n\in A?$.

  * •

Depending on the output of the query, the TM will then:

    * –

State $q_{j}$ if $n\in A$.

    * –

State $q_{k}$ if $n\notin A$.

Note, this definition does not require our oracle sets to be computable nor
enumerable - just that they are there. In fact, it is explicitly why oracle
Turing Machines were introduced - in order to analyse questions like “is the
halting problem all there is?” Essentially, we can now ask “What can we
compute knowing the characteristic function of a, not necessarily computable,
set $A$?” This breakthrough from Turing allowed us to reason about problems
‘beyond’ the halting problem, by talking about _Turing reducibility_.

######  Definition 1.2.25 (Turing Reducibility).

We say that a set $A$ is _Turing reducible_ to a set $B$, written $A\leq_{T}B$
if for some $e$,

$\chi_{A}=\varphi_{e}^{B}$

.

It is worth noting, however, that Turing reducibility is finer than
$m$-reducibility, as evidenced by the following result:

######  Theorem 1.2.26 ([16, Thm. 4.2.6]).

There exists $A$ and $B$ s.t. $A\leq_{T}B$ but $A\nleq_{m}B$.

  * Proof.

Consider $C$ a non-computable computably enumerable set, with $\overline{C}$
its compliment. It is clear that

$C\leq_{T}\overline{C}$

but as $C$ is non-computable, we also have that

$C\nleq_{m}\overline{C}$

∎

The outcome of Turing’s work was the Turing hierarchy, which is defined by
taking successive ‘jumps’ which we define as follows.

######  Definition 1.2.27.

Let $A,B$ be given sets:

  * •

We write $A\equiv_{T}B$ if $A\leq_{T}B$ and $B\leq_{T}A$.

  * •

We define the _Turing degree_ \- also called the _degree of unsolvability_ \-
for some $A\subseteq\omega$ to be

$deg(A)=_{def}\\{X\subseteq\omega:X\equiv_{T}A\\}$

  * •

We can write $\boldsymbol{\mathcal{D}}$ for the collection of all such
degrees, and can define the partial ordering $\leq$ on
$\boldsymbol{\mathcal{D}}$ induced by $\leq_{T}$ as:

$deg(B)\leq deg(A)\Longleftrightarrow_{def}B\leq_{T}A$

It follows from this and some other results that three is in fact a partial
order on $\mathcal{D}$, however this is beyond the scope of this thesis.
Returning to Post’s set, $K$, we state the following theorems - omitting
proofs that can be found in [16].

######  Definition 1.2.28.

For $n,e\in\omega$, let $HALT={(n,e):\varphi_{e}(n)\downarrow}$.

######  Theorem 1.2.29 ([16, Thm. 5.3.1]).

$HALT\leq_{T}K$

Thus, $K$ is incomputable, and so things that $K$ reduces to are also
necessarily incomputable. We also need the following idea of _index sets_.

######  Definition 1.2.30.

Let $\mathcal{A}$ be a set of partial computable functions - or of computably
enumerable sets. The _index set_ of $\mathcal{A}$ is then the set $A$ of all
the indices of elements of $\mathcal{A}$.

######  Theorem 1.2.31 (Rice’s Theorem, [16, Thm. 7.1.11]).

If $A$ is an index set - with $A\neq\emptyset$ and $A\neq\omega$ \- then
$K\leq_{m}A$ or $K\leq_{m}\overline{A}$.

This result gives us the following corollary:

######  Corollary 1.2.32 ([16, Cor. 7.1.12]).

Every non-trivial index set is incomputable.

This gives us a window into the core intuition behind Rice’s important result
on computable functions - that every non-trivial semantic property is
fundamentally undecidable, by means of $m$-reducibility of $K$ into index
sets.

###  1.3. Computable Trees

We denote Cantor space by $2^{\omega}$, and Baire space by $\omega^{\omega}$.
For any alphabet $\Sigma$, we denote the set of strings
$\sigma=(\sigma(0),\sigma(1),\ldots,\sigma(n-1))$ of length $n$ by
$\Sigma^{n}$. We denote the set of arbitrary length finite strings by
$\Sigma^{<\omega}$, and similarly for Cantor space we use $2^{<\omega}$, and
for Baire space we shall use $\omega^{<\omega}$.

Let $|\sigma|$ denote the length of the string $\sigma\in\Sigma^{<\omega}$. We
denote the initial segment of $\sigma$ of length $n$ by $\sigma\upharpoonright
n$. For $\sigma$ and $\tau$, where $|\sigma|=i$ and $|\tau|=j$, we write
$\sigma^{\frown}\tau$ for the string
$(\sigma(0),\sigma(1),\ldots\sigma(i-1),\tau(0),\tau(1),\ldots,\tau(j-1))$,
which we call the _concatenation_ of $\sigma$ and $\tau$. We write
$\tau\prec\sigma$ if $\tau$ is an _initial segment_ , or _initial substring_ ,
of $\sigma$ \- that is, there is some $n<|\sigma|$ such that for all $0\leq
i\leq n$ it holds that $\tau(i)=\sigma(i)$.

####  1.3.1. Trees and $\Pi^{0}_{1}$ Classes

The source for this section is Cenzer’s chapter titled “$\Pi^{0}_{1}$ Classes
in Computability Theory” in [31].

######  Definition 1.3.1.

A _tree_ is a set $T\subset\Sigma^{<\omega}$ that is closed under initial
segments. That is, for all $\tau\in\Sigma^{<\omega}$ such that
$|\tau|\leq|\sigma|$ it is true that $\forall\sigma\in
T\,(\tau\prec\sigma\rightarrow\tau\in T)$.

We say that $\sigma$ is a successor to some $\tau\in T$ if there exists some
$s\in\Sigma^{<\omega}$ s.t. $\sigma=\tau^{\frown}s$. If $\sigma\in T$ is a
successor of some $\tau\in T$ and $|\sigma|=|\tau|+1$ we say that $\sigma$ is
an _immediate successor_ of $\tau$.

######  Definition 1.3.2.

We say that a tree $T$ is _finitely branching_ if for every $\tau\in T$ there
are finitely many immediate successors in $T$.

For every $T\subset 2^{<\omega}$ or $T\subset\Sigma^{<\omega}$ (for a finite
alphabet $\Sigma$), $T$ can only be finitely branching.

######  Definition 1.3.3.

We will make use of the following definitions for paths through a tree $T$:

  * •

An _infinite path_ through $T$ is a sequence $(x(0),x(1),\ldots)$ such that
$x\upharpoonright n\in T$ for all $n\in\omega$.

  * •

Denote by $[T]$ the set of infinite paths through $T$.

We also state what it is for a set to be a $\Pi^{0}_{1}$ class, which is
congruent with earlier definitions of $\Pi^{0}_{1}$ sets we stated earlier.

######  Definition 1.3.4.

  * •

A formula is $\Delta_{0}$ if it is a primitive recursive function.

  * •

A set $X\subset\omega^{\omega}$ is a $\Pi^{0}_{1}$ class if there is a
$\Delta_{0}$ formula $\varphi(n,x)$ in the language of first order arithmetic
such that $x\in X\iff(\forall n)\varphi(n,x)$.

A definition of Primitive Recursive Functions as well as other definitions we
use here can be found in Cooper [16, Sec. 2.1 p.12].

The $\Pi^{0}_{1}$ classes may be described topologically as effectively closed
subsets of the product space $\omega^{\omega}$. Early results in the study of
$\Pi^{0}_{1}$ classes were carried out by Kleene, who proved the Kleene basis
theorem in 1943. Further work was carried out by Kreisel, Shoenfield, Jockush,
Soare, et al. .

The topology on Baire space, $\omega^{\omega}$ is determined by a basis of
intervals given by $I(\sigma)=\\{x:\sigma\prec x\\}$. A subset
$P\subset\omega^{\omega}$ is closed iff $P=[T]$ for some tree $T$, hence our
description of $\Pi^{0}_{1}$ classes as effectively closed subsets of Baire
space.

Note that each interval given by $I$ is also closed, thus we can describe the
intervals as _clopen_. Note also that for Cantor space, $2^{\omega}$, the
clopen sets are just the finite unions of intervals.

Given these definitions we can state the core intuition for a $\Pi^{0}_{1}$
class as a tree in terms of some fixed initial segment $\sigma$ for which the
$\Pi^{0}_{1}$ class is the set of points that are all possible extensions of
$\sigma$ \- the cone of extensions above this fixed initial segment.

We now wish to formalise the relationship between $\Pi^{0}_{1}$ classes and
trees by means of the following Lemma:

######  Lemma 1.3.5 ([31, p.41,Lem. 1.1]).

For any class $P\subset\omega^{\omega}$, the following are equivalent:

  1. (1)

$P=[T]$ for some computable tree $T\subset\omega^{<\omega}$.

  2. (2)

$P=[T]$ for some primitive recursive tree $T$.

  3. (3)

$P=\\{x:\forall n(R(n,x))\\}$ for some computable relation $R_{e}$,

  4. (4)

$P=[T]$ for some $\Pi^{0}_{1}$ tree $T\subset\omega^{<\omega}$.

Recall our definitions of computable relation (definition LABEL:def:ArithH)
and tree (definition 1.3.1) above.

  * Proof.

A proof of this can be found in [31, p.41]. ∎

Armed with this characterisation, we can equate the enumeration of computable
trees with effectively enumerated $\Pi^{0}_{1}$ classes, as demonstrated in
the following lemma.

######  Lemma 1.3.6 ([31, p.41,Lem. 1.2]).

There is a uniformly recursive sequence $T_{e}$ of primitive recursive trees
such that, for every $\Pi^{0}_{1}$ class $P$, there is some $e$ such that it
holds that

$P=[T_{e}]$

  * Proof.

Let $\pi_{0},\pi_{1},\ldots$ be a recursive enumeration of the primitive
recursive functions such that $\pi_{i}:\omega\rightarrow\\{0,1\\}$. Define the
$e^{th}$ such tree by

$\sigma\in
T_{e}\iff(\forall\tau\preceq\sigma)\pi_{e}(\langle\tau\rangle_{n})=1$

where $\langle\tau\rangle_{n}=\langle
n,(\tau(0),\tau(1),\ldots,\tau(n-1))\rangle$.

$T_{e}$ is a tree, and if $T$ is a primitive recursive tree with
characteristic function $\pi_{e}$, then $T=T_{e}$. By lemma 1.3.5, every
$\Pi^{0}_{1}$ class is thereby equal to one of the $[T_{e}]$. ∎

###  1.4. Kleene’s $\mathcal{O}$ and $\Pi^{1}_{1}$-Completeness

In this section we will outline results that give the relationship between
well-founded trees and $\Sigma^{1}_{1}$-completeness. Our preliminary
definitions are as follows.

Unless otherwise stated, the material in this section is based on [16] and
[50].

######  Definition 1.4.1 (Ordinal).

We define ordinals as follows:

  * •

A _totally ordered set_ is a set $A$ with a relation $\leq$ such that the
following hold:

    * –

(Reflexivity) $\forall a\in A(a\leq a)$

    * –

(Antisymmetry) $(a\leq b\wedge b\leq a)\rightarrow a=b$

    * –

(Transitivity) $(a\leq b\wedge b\leq c)\rightarrow a\leq c$

    * –

(Comparability) $\forall a,b\in A(a\leq b\vee b\leq a)$

  * •

A _well-ordered set_ is a totally ordered set $A$ together with a relation
$\leq$ such that every subset $S\subseteq A$ has a least element.

  * •

Two sets $A,B\subseteq\omega$ are said to be _order isomorphic_ iff there
exists a bijection $f:A\rightarrow B$ between $A$ and $B$ such that for all
$a_{1},a_{2}\in A$

$a_{1}\leq a_{2}\iff f(a_{1})\leq f(a_{2})$

  * •

Two well-ordered sets $A,B\subseteq\omega$ have the same _order type_ iff they
are order isomorphic.

  * •

An _ordinal number_ or _ordinal_ (in the language due to Cantor) is just an
order type of some well-ordered set.

NB \- later, in definition 1.4.16, we will formalise the difference between a
totally-ordered and well-ordered set. Specifically that the well-foundedness
of such as set forces the relation to be irreflexive and connected.

######  Definition 1.4.2 (Ord).

We denote the set of all ordinals - that is, the set of every possible order
type - as Ord.

We now have all the basic machinery we need to describe the computable, or
recursive ordinals.

####  1.4.1. Ordinal Notations and Kleene’s $\mathcal{O}$

The aim of Kleene’s construction is to analyse the structure of the computable
ordinals, by means of creating representations of each as natural numbers.

The resulting theory identified that the computable ordinals form an initial
segment of Ord, sitting strictly below the least non-computable ordinal, which
we shall call the _Church-Kleene ordinal_ , denoted $\omega_{1}^{CK}$.

We will begin this journey into categorising and enumerating the computable
ordinals by first defining a way of formulating _notations_ for the ordinals.
The core idea here is that we can construct things that represent ordinals -
including successor ordinals and limit ordinals - but in a way that can be
more easily manipulated and understood for our present purposes.

######  Definition 1.4.3 (Ordinal Notation Ordering).

We first define the ordering $<_{\mathcal{O}}$:

  * •

If $x$ and $y$ are both notations for constructive ordinals, then let
$x<_{\mathcal{O}}y$ be for “$x$ is less than $y$ according to the ordering of
notations.”

  * •

Given an ordinal can have two different notations, $<_{\mathcal{O}}$ is not
linear.

We can regard $x<_{\mathcal{O}}y$ as a set of ordered pairs - thus it is the
closure of a finite set $X$ under some $\Sigma^{1}_{1}$-closure condition
$A(X)$ we we define below.

######  Definition 1.4.4.

Let $X$ be a finite set, the closure condition $A(X)$ has three clauses:

  1. (1)

$\forall u,v(\langle u,v\rangle\in X\rightarrow\langle v,2^{v}\rangle\in X)$
(Successors)

  2. (2)

$\forall
n(\varphi_{e}(n)\downarrow\wedge\langle\varphi_{e}(n),\varphi_{e}(n+1)\rangle\in
X)\rightarrow\forall n(\langle\varphi_{e}(n),3\cdot 5^{e}\rangle\in X)$
(Limits)

  3. (3)

$\forall u,v,w(\langle u,v\rangle,\langle v,w\rangle\in X\rightarrow\langle
u,w\rangle\in X)$ (Transitivity)

Thus, there is some least $X$ such that $\langle 1,2\rangle\in X$, with
$A(X)$. We let $<_{\mathcal{O}}$ be this least such $X$.

####  1.4.2. Kleene’s $\mathcal{O}$

We can now define Kleene’s $\mathcal{O}$ as follows:

######  Definition 1.4.5 (Kleene’s $\mathcal{O}$).

Let $\mathcal{O}$ denote the set of notations for constructive ordinals.
$\mathcal{O}$ forms the field of $<_{\mathcal{O}}$.

We will use the following definition of notations, noting that they are all
defined recursively for future purposes.

######  Definition 1.4.6.

Let the function $|\cdot|:\mathcal{O}\rightarrow\text{{Ord}}$ be defined by
transfinite recursion on $<_{\mathcal{O}}$ as follows:

$\displaystyle|1|$ $\displaystyle=0$ $\displaystyle|2^{u}|$
$\displaystyle=|u|+1$ $\displaystyle|3\cdot 5^{e}|$
$\displaystyle=\lim_{n\to\infty}|\varphi_{e}(n)|$

We can now define all of the constructive ordinals in the following manner.

######  Definition 1.4.7 (Constructive Ordinals).

An ordinal $\delta\in\text{{Ord}}$ is a _constructive ordinal_ if $\delta=u$
for some $u\in\mathcal{O}$.

####  1.4.3. Kleene’s $\mathcal{O}$, and Well-foundedness

We define well-foundedness as follows:

######  Definition 1.4.8 (Well-founded relations).

A binary relation $R$ is _well-founded_ if there is no $f$ s.t.

$\forall x(R(f(x+1),f(x))$

We are now ready for the following theorem:

######  Theorem 1.4.9 ([50, Thm. 2.2]).

  1. (1)

$<_{\mathcal{O}}$ and $\mathcal{O}$ are $\Pi^{1}_{1}$

  2. (2)

$<_{\mathcal{O}}$ is a well-founded partial ordering.

  3. (3)

For $v\in\mathcal{O}$, the restriction of $<_{\mathcal{O}}$ to
$\\{u|u<_{\mathcal{O}}v\\}$ is linear.

Our proof comes directly from [50].

  * Proof.

1\. A full proof of 1. can be found in [50, p.9]
2\. The following _natural enumeration_ of $<_{\mathcal{O}}$ is equivalent to
a redefinition of $<_{\mathcal{O}}$ by means of transfinite recursion on
ordinals, as follows:

    * –

Stage 0: enumerate $1<_{\mathcal{O}}2$.

    * –

Stage $\delta+1$: enumerate all $v<_{\mathcal{O}}2^{v}$ and
$u<_{\mathcal{O}}2^{v}$ if $u<_{\mathcal{O}}v$ was enumerated at stage
$\delta$.

    * –

Stage $\lambda$ (limit): enumerate $\varphi_{e}(n)<_{\mathcal{O}}3\cdot 5^{e}$
and $u<_{\mathcal{O}}3\cdot 5^{e}$, if not enumerated at some earlier stage,
if for each $n$ it holds that $\varphi_{e}(n)<_{\mathcal{O}}\varphi_{e}(n+1)$
was enumerated at an earlier stage, and if for some
$n,u<_{\mathcal{O}}\varphi_{e}(n)$ was also enumerated at an earlier stage.

By induction on each stage $\gamma$, a pair enumerated at some stage $\gamma$
belongs to $<_{\mathcal{O}}$. On the other hand, the set of all pairs
enumerated into $<_{\mathcal{O}}$ is a solution of $A(X)$, and so contains
$<_{\mathcal{O}}$.

By induction on $u<_{\mathcal{O}}v$ and $v<_{\mathcal{O}}w$, then
$u<_{\mathcal{O}}v$ is enumerated at an earlier stage than
$v<_{\mathcal{O}}w$. It then follows that $<_{\mathcal{O}}$ is well-founded,
else there would otherwise be a descending infinite sequence of ordinals.

3\. We prove this by induction on $<_{\mathcal{O}}$. Assume
$u_{1},u_{2}<_{\mathcal{O}}v$, we check that one of the following hold:

    * –

$u_{1}<_{\mathcal{O}}u_{2}$,

    * –

$u_{1}=u_{2}$, or

    * –

$u_{2}<_{\mathcal{O}}u_{1}$.

If $v=2^{u}$, then (1) above implies that $u_{1},u_{2}\leq_{\mathcal{O}}u$ and
our result follows by induction. Else, if $v=3\cdot 5^{e}$, then we apply (2)
to get the result. ∎

We can now prove the following facts about ordinal notations and their
addition:

######  Definition 1.4.10.

  * •

Let $+_{\mathcal{O}}$ be such that if $a,b\in\mathcal{O}$, then
$a+_{\mathcal{O}}b\in\mathcal{O}$ and

$|a+_{\mathcal{O}}b|=|a|+|b|$

  * •

Let $h$ be a recursive function such that

$\varphi_{h(e,a,d)}\simeq\varphi_{e}(a,\varphi_{d}(n))$

  * •

Let $I$ be a recursive function such that

$\displaystyle a$ $\displaystyle\text{ if }b=1$
$\displaystyle\varphi_{I(e)}(a,b)\simeq 2^{\varphi_{e}(a,m)}$
$\displaystyle\text{ if }b=2^{m}$ $\displaystyle 3\cdot 5^{h(e,a,d)}$
$\displaystyle\text{ if }b=3\cdot 5^{d}$ $\displaystyle 7$ otherwise

It is worth noting that, because our breaking up of $\mathcal{O}$ into
notations for zero, successors, and limits is effective, $I$ above is
recursive, even though $<_{\mathcal{O}}$ is non-recursive. Also, the clause
for $I(e)$ is sensible even if $a,b\notin\mathcal{O}$.

######  Theorem 1.4.11 (Kleene, [50, Thm. 3.4]).

The recursive function $+_{\mathcal{O}}$ has the following properties. For all
$a$, and $b$:

  1. (1)

$a,b\in\mathcal{O}\iff a+_{\mathcal{O}}b\in\mathcal{O}$.

  2. (2)

$a,b\in\mathcal{O}\Rightarrow|a+_{\mathcal{O}}b|=|a|+|b|$.

  3. (3)

$a,b\in\mathcal{O}\wedge b\neq 1\Rightarrow
a<_{\mathcal{O}}(a+_{\mathcal{O}}b)$.

  4. (4)

$a\in\mathcal{O}\wedge
c<_{\mathcal{O}}b\iff(a+_{\mathcal{O}}c)<_{\mathcal{O}}(a+_{\mathcal{O}}b)$.

  5. (5)

$a\in\mathcal{O}\wedge
b=c\in\mathcal{O}\iff(a+_{\mathcal{O}}b)=(a+_{\mathcal{O}}c)$.

  * Proof.

Can be found in Sacks [50] I.3.4 p.13. ∎

Due to our computable approach, and the fact that our notations for ordinals
are, in particular, very computable, we can get theorems such as the
following:

######  Definition 1.4.12.

Denote by $W_{e}$ the $e^{th}$ computably enumerable subset of $\omega$, the
domain of $\varphi_{e}$.

The intuition here is that $W_{e}$ is the ‘set of inputs that $\varphi_{e}$
halts on’ - which is why we use the domain of $\varphi_{e}$ in our definition.

######  Theorem 1.4.13 (Kleene, [50, Thm. 3.5]).

There exists a computable function $p$ such that for all $b\in\mathcal{O}$,

$W_{p(b)}=\\{a:a\leq_{\mathcal{O}}b\\}$

  * Proof.

The required properties of $p$ are as follows:

$\displaystyle W_{p(1)}$ $\displaystyle=\emptyset$ (1.1) $\displaystyle
W_{p(2^{a})}$ $\displaystyle=\\{a\\}\cup W_{p(a)}$ $\displaystyle W_{p(3\cdot
5^{d})}$
$\displaystyle=\bigcup\limits_{n\in\omega}\\{W_{p(\varphi_{d}(n))}:\varphi_{d}(n)\downarrow\\}$

By induction on $<_{\mathcal{O}}$ we get that any $p$ that satisfies all of
1.1 will also satisfy our theorem. As such, we want to show the existence of
such a computable $p$, specifically by means of effective transfinite
recursion on $p$. Let $e_{0}$ be any Gödel number for some TM, and let $i$ and
$j$ be computable functions such that:

$\displaystyle W_{e_{0}}$ $\displaystyle=\emptyset$ (1.2) $\displaystyle
W_{i(e,a)}$ $\displaystyle=\\{a\\}\cup W_{\varphi_{e}(a)}$ $\displaystyle
W_{j(e,d)}$
$\displaystyle=\bigcup\limits_{n\in\omega}\\{W_{\varphi_{e}(\varphi_{d}(n))}:n<\omega\\}$

In 1.2, it is intended that when $\varphi_{e}(a)\uparrow$, that
$W_{\varphi_{e}(a)}=W_{\varphi_{e}(\varphi_{d}(n))}=\emptyset$. We can now
obtain a recursive $I$ (similar to 1.4.10 above) such that:

$\displaystyle e_{0}$ $\displaystyle\text{ if }b=1$
$\displaystyle\varphi_{I(e)}(b)\simeq i(e,a)$ $\displaystyle\text{ if
}b=2^{a}$ $\displaystyle j(e,d)$ $\displaystyle\text{ if }b=3\cdot 5^{d}$
$\displaystyle 0$ otherwise

By theorem 1.2.20, the fixed point theorem, $I$ necessarily has a fixed point
$c$ where $\varphi_{I(c)}\simeq\varphi_{c}$. Let $p(b)$ be $\varphi_{c}(b)$.
Then

$\displaystyle e_{0}$ $\displaystyle\text{ if }b=1$ $\displaystyle
p(b)=i(e,a)$ $\displaystyle\text{ if }b=2^{a}$ $\displaystyle j(e,d)$
$\displaystyle\text{ if }b=3\cdot 5^{d}$ $\displaystyle 0$ otherwise

Given $i$ and $j$ are both computable and total, we get that
1.2$\rightarrow$1.1. ∎

We are also able to obtain the existence of similar recursive functions:

######  Theorem 1.4.14 (Kleene, [50, Thm. 3.5]).

There exists a recursive function $q$ such that for all $b\in\mathcal{O}$,

$W_{q(b)}=\\{\langle x,y\rangle:x<_{\mathcal{O}}y<_{\mathcal{O}}b\\}$

  * Proof.

Essentially the same as for the proof of theorem 1.4.13, with the modification
that we adjust the definition 1.1 and 1.2 preserve all of the pairs $\langle
x,y\rangle$ s.t. $x<_{\mathcal{O}}y<_{\mathcal{O}}a$ in our recursive
definition of $i$. ∎

####  1.4.4. Recursive Ordinals and well-founded Relations

We can now show that every c.e. subset of $\mathcal{O}$ is bounded in a
“highly effective manner.”[50, p.15]

######  Theorem 1.4.15 ([50, Lem. 4.1]).

There exists a computable $g$ such that for all $e$:

  1. (1)

$g(e)\in\mathcal{O}\iff W_{e}\subseteq\mathcal{O}$,

  2. (2)

$g(e)\in\mathcal{O}\Rightarrow|a|<|g(e)|\text{ for all }a\in W_{e}$.

  * Proof.

A proof can be found in Sacks [50] p.16. ∎

We now formalize our definition 1.4.1.

######  Definition 1.4.16.

A binary relation $R(x,y)$ is a _well-ordering_ if it is:

  1. (1)

(Connected) $(\forall x,y)(R(x,y)\vee R(y,x)\vee x=y)$

  2. (2)

(Transitive) $(\forall x,y,z)(R(x,y)\wedge R(y,z)\rightarrow R(x,z))$

  3. (3)

(well-founded) if $S\neq\emptyset$, $S$ is a subset of the field of $R$, then
$\exists y\in S$ such that $(\forall x\in S)\neg R(x,y)$
Note, that 3. implies:

  4. (4)

(Irreflexive) $(\exists x)\neg R(x,x)$

  5. (5)

(Antisymmetric) $(\forall x,y)(R(x,y)\rightarrow R(y,x))$

Given the well-foundedness of a well-ordering relation, we can define the
_height_ of $R$ as follows:

######  Definition 1.4.17.

  * •

Let $R$ be a well-founded binary relation, then it has a height, denoted by
$|R|$, measured by some ordinal.

  * •

Let $\beta$ be an ordinal variable. $\mu\beta$ is then the “least $\beta$ such
that…”

  * •

$|x|=\mu\beta\,[R(y,x)\rightarrow|y|<\beta]$

  * •

$|R|=\mu\beta\,\forall x\,[x\in\text{ field of }R\rightarrow|x|<\beta]$

We can also enumerate computable relations:

######  Definition 1.4.18.

Let $R_{e}$ denote $R_{e}(x,y)\iff\varphi_{e}(x,y)$.

Thus, we can enumerate all computable relations. We shall let

$\textbf{Rel}=\\{R_{e}:e<\omega\\}$

######  Lemma 1.4.19 ([50, Lem. 4.3]).

There exists a computable $f$ such that, for all $e$:

  * •

$R_{e}\text{ is well-founded }\iff f(e)\in\mathcal{O}$, and

  * •

$R_{e}\text{ is well-founded }\rightarrow|R_{e}|\leq|f(e)|$

This lemma gives rise to the following theorem due to Kleene and Markwald:

######  Theorem 1.4.20 (Kleene-Markwald, [50, Thm. 4.4]).

The computable ordinals are equal to the constructive ordinals.

  * Proof.

A proof can be found in Sacks [50] p. 18. ∎

####  1.4.5. $\mathcal{O}$, Well-foundedness, and $\Pi^{1}_{1}$ Sets

In this subsection, we will build on our theory and present the ordinal
analysis of $\Pi^{1}_{1}$ Sets.

######  Definition 1.4.21.

Let $\overline{f}(x)=\\{\langle i,f(i)\rangle:i<x\\}$, essentially that, for
$p_{i}$ being the $i^{th}$ prime, $p_{0}=2$:

$\overline{f}(x)=\prod\limits_{i<x}p_{i}^{1+f(i)}$

If $y=\overline{f}(x)$ for some $f$ and $x$, we say that $y$ is a _sequence
number_.

This $\overline{f}(x)$ can be thought of as the code for the graph of
$f\upharpoonright x$ \- essentially, it is the code for the sequence $\langle
f(0),f(1),\ldots,f(x-1)\rangle$, with $f(0)=1$. We can denote the length of
$x$ as $len(\overline{f}(x))$. We can thus view $y$ as $\langle
y_{0},y_{1},\ldots,y_{len(y)-1}\rangle$.

If $y$ and $z$ are both sequence numbers, then we say that ‘$y$ is _properly
extended_ by $z$’, written $y\prec_{seq}z$ if $len(y)<len(z)$ and for all
$i<len(y)$ we have that $y_{i}=z_{i}$.

######  Definition 1.4.22.

Let Seq denote the set of all sequence numbers.

Seq is a computable set, and $\prec_{seq}$ is a computable, antisymmetric,
transitive binary relation. We can think of $(\textbf{Seq},\prec_{seq})$ as
presenting Baire space, $\omega^{\omega}$ as a tree - which is why it is
useful in the study of $\Pi^{1}_{1}$ sets.

We denote $S_{R}(y)$ to be the restriction of $(\textbf{Seq},\prec_{seq})$ to
the sequence numbers $\overline{f}(x)$ such that

$S_{R}(y)=\forall i<x[\neg R(\overline{f}(i),y)]$

The following proposition begins our connection between well-foundedness and
formulae in the normal form $\Pi^{1}_{1}$:

######  Proposition 1.4.23 ([50, Prop. 5.3]).

$\forall f\exists x(R(\overline{f}(x),y))\iff S_{R}(y)\text{ is well-
founded.}$

  * Proof.

Fix some $y$. $\neg(\forall x\,\exists x\,R(\overline{f}(x),y)$ if and only if
there is some $f$ such that $\forall x\,\neg R(\overline{f}(x),y)$ if and only
if there is some $f$ such that $f(0)>f(1)>f(2)>\ldots$ in an infinite
descending sequence $S_{R}(y)$ if and only if $S_{R}(y)$ is not well-founded.
∎

We can now continue our analysis with the following normalisation of
$\Pi^{1}_{1}$ predicates and theorems. We note that for any computable
relation $R_{1}(f,x,y)$ we can find $e$ such that $\varphi_{e}^{f}(x,y)=0\iff
R_{1}(f,x,y)$. Using this, we can prove the following, denoting by $WF$ the
set of all well-founded trees - we now show the following lemma:

######  Lemma 1.4.24 ([50, Sec. 5.2]).

For each $\Pi^{1}_{1}$ set P,

$P\leq_{m}WF$

  * Proof.

Let some $B\in\Pi^{1}_{1}$. By the above, there is some computable $R$ such
that for all $y$,

$y\in B\iff\forall f\,\exists x\,R(\overline{f}(x),y)$

By proposition 1.4.23, we get

$y\in B\iff S_{R}(y)\text{ is well-founded.}$

∎

We can thus extend this lemma to a result due to Kleene:

######  Theorem 1.4.25 (Kleene, [50, Thm. 5.4]).

For each $\Pi^{1}_{1}$ set $P$,

$P\leq_{m}\mathcal{O}$

  * Proof.

Let $B\in\Pi^{1}_{1}$. As for 1.4.24, we have that there is some computable
$R$ such that for all $y$,

$y\in B\iff\forall f\,\exists x\,R(\overline{f}(x),y)$

and again by 1.4.23, we get

$y\in B\iff S_{R}(y)\text{ is well-founded.}$

Given the $S_{R}(y)$ is computable uniformly in $y$ \- that is, we only
require one TM with which to carry our the computation - we have that there
exists a computable function $g$ such that $S_{R}(y)=R_{g(y)}$. Let $f$ be as
in lemma 1.4.19, then

$y\in B\iff f(g(y))\in\mathcal{O}$

∎

This gives us the following useful corollary:

######  Corollary 1.4.26 ([50, Cor. 5.5]).

$\mathcal{O}\notin\Sigma^{1}_{1}$

  * Proof.

This proof is structurally similar to one that a complete c.e. subset of
$\omega$ is not computable.

We first note that for any set $S$ such that for some $A\in\Sigma^{1}_{1}$, if
$S\leq_{m}A$, then $S$ must also be $\Sigma^{1}_{1}$. So, by 1.4.23, we have
that if $\mathcal{O}$ were $\Sigma^{1}_{1}$, then every $\Pi^{1}_{1}$ set
would also be $\Sigma^{1}_{1}$.

Thus it suffices that we can find some $A\in\Pi^{1}_{1}$ such that
$A\notin\Sigma^{1}_{1}$. Define $Q(y)$ to be $\forall f\,\exists
x\,\varphi_{y}^{f\upharpoonright x}(y)$. Suppose $(\neg Q(y)\in\Pi^{1}_{1})$,
then $\neg Q(y)$ is equivalent to the statement that there exists $e$,
$\forall f\,\exists x\,\varphi_{e}^{f\upharpoonright x}(y)$. So $\neg Q(y)\iff
Q(y)$. ∎

We can now prove the result due to Spector about the
$\Sigma^{1}_{1}$-boundedness of $\mathcal{O}$:

######  Theorem 1.4.27 (Spector, 1955 - [50, Cor. 5.6]).

Let $X\subseteq\mathcal{O}$ and $X\in\Sigma^{1}_{1}$. There exists some
$b\in\mathcal{O}$ such that $\forall x\in X\,(|x|\leq|b|)$.

  * Proof.

As for the proof of 1.4.25, we can replace $\mathcal{O}$ with $B$ and find a
computable function $t$ such that for all $y$,

$y\in\mathcal{O}\iff R_{t(y)}\text{ is well-founded}$

Let our $Q(y)$ be

$\exists z\,[z\in X\wedge\exists f\,\forall
u,v\,(R_{t(y)}(u,v)\rightarrow\langle f(u),f(v)\rangle\in W_{q(z)})]$

where $W_{q(z)}$ is as per 1.4.14. $Q(y)\in\Sigma^{1}_{1}$. If $Q(y)$ holds
then we have $R_{t(y)}$ must be well-founded.

Suppose that $b$ does not exist, then if $R_{t(y)}$ is well-founded, then by
1.4.19 there is some $z\in X\subseteq\mathcal{O}$ such that $|R_{t(y)}|<|z|$,
and thereby $Q(y)$ holds. But $y\in\mathcal{O}$ is $\Sigma^{1}_{1}$,
contradicting 1.4.26. ∎

We can thus get the following corollary:

######  Corollary 1.4.28 ([50, Ex. 5.7]).

The set of all well-founded computable trees is $\Pi^{1}_{1}$ complete.

It should be noted that in later chapters, 1.4.24 and 1.4.28 will be
particularly useful, as it will form the basis for our theorems that relate
the well-foundedness of trees to tilings of the plane using infinite prototile
sets (see Chap. 2 for definitions of these terms).

###  1.5. Trees, Ordinals, and the Arithmetical and Analytic Hierarchies

We have outlined in previous sections various definitions that will be used in
our work in later chapters. There are some deep and illuminating connections
between these objects, which we hope to outline and illustrate in this
section. Unless otherwise stated, all results can be found in [31] and [16].

####  1.5.1. Fundamental Results

Our formulation of König’s lemma comes from [49] and [41].

######  Lemma 1.5.1 (König’s Lemma, [41, Thm. 3.13]).

Every infinite finitely branching tree has an infinite branch.

  * Proof.

We prove this for $T$, a binary tree. For a string $\sigma$ with $|\sigma|=n$,
let

$T_{\sigma}=\\{\tau\in T:\tau\upharpoonright
n=\sigma\\}\cup\\{\sigma\upharpoonright k:k<n\\}$

We shall call $T_{\sigma}$ the _subtree of $T$ below $\sigma$_. Though it is
easy to check that $T$ is a tree, it may or not be infinite.

We want $\gamma\in T$ such that the tree $T_{\gamma}$ below $\gamma$ is
infinite. Let this be our induction hypothesis. Suppose we have some $\gamma$,
with $|\gamma|=n$ and $T_{\gamma}$ is infinite. Since our tree $T$ is binary,
we have

$T_{\gamma}=\\{\tau\in
T:\tau\upharpoonright(n+1)=\gamma^{\frown}0\\}\cup\\{\tau\in
T:\tau\upharpoonright(n+1)=\gamma^{\frown}1\\}\cup\\{\gamma\upharpoonright
k:k\leq n\\}$

The third of these sets is clearly finite, so one of the first two -
corresponding to ’0’ and ’1’respectively - must be infinite, by our induction
hypothesis.

If the first of these is infinite, we set $\gamma(n+1)=\gamma^{\frown}0$, and
so we have

$T_{\gamma(n+1)}=\\{\tau\in
T:\tau\upharpoonright(n+1)=\gamma^{\frown}0\\}\cup\\{\gamma^{\frown}0\\}\cup\\{\gamma\upharpoonright
k:k\leq n\\}$

which is infinite. In the other case, we do the same for
$\gamma(n+1)=\gamma^{\frown}1$, which gives us the same infinite tree
$T_{\gamma(n+1)}$ as before.

In both cases, we have defined $\gamma(n+1)$ and proved our induction
hypothesis for $n+1$.

∎

This lemma is rather famous throughout the mathematical œuvre - indeed, in
other reference texts such as [32], this theorem features in reference to the
compactness of Wang tiles as “König’s Infinity Lemma”. This is something we
shall later make use of in proving this result in chapter 2.

König’s Lemma applied to trees with a bound on the number of children for each
node, then we say that this is _Weak König’s Lemma_ (WKL). WKL is a very
important principle studied in reverse mathematics, such as a compactness
principle for Cantor space. This is not, however, within the scope of this
thesis to study or present.

####  1.5.2. Trees and Analytic Sets

We start by defining the extendible nodes of a tree:

######  Definition 1.5.2.

For a tree $T$, we define the set of _extendible nodes_ $Ext(T)$ by

$\sigma\in Ext(T)\iff(\exists x)(x\in[T]\wedge\sigma\prec x)$

This definition allows us to collect all of the initial segments of the points
$x$ that lie in some tree $T$. Our aim is to use this set to establish
$Ext(T)$ as a basis for trees whose sets of paths are $\Pi^{0}_{1}$ sets. By
this, we mean that any extension in $Ext(T)$ is a $\Pi^{0}_{1}$ set. We first
establish what a basis is:

######  Definition 1.5.3.

Let $\Theta\subseteq\mathcal{P}(\omega^{\omega})$ be a collection of
subclasses of $\omega^{\omega}$. A set $\Gamma\subset\omega^{\omega}$ is a
_basis_ if every class $C\in\Theta$, there is some $x\in C$ such that
$x\in\Gamma$.

This gives us natural formulation for ‘basis theorems’, such as the following
extracted from [31, p.52].

######  Theorem 1.5.4 ([31, Remark p.51]).

The class $\Delta^{0}_{0}$ of computable functions is a basis for the family
of open subclasses of Baire space.

However, we will present the following result - the Kleene Basis theorem.

######  Theorem 1.5.5 (Kleene Basis Theorem, [31, Thm. 3.1]).

For any tree $T$ such that a $\Pi^{0}_{1}$ class $P=[T]\neq\emptyset$, $P$
contains a member that is computable in $Ext(T)$.

  * Proof.

The infinite path $x$ through $T$ can be computably defined by letting $x(0)$
be the least $n$ such that the sequence $(n)\in Ext(T)$. We continue the
construction by letting, for every $k$, $x(k+1)$ be the least $n$ such that
$(x(0),x(1),\ldots,x(k),n)\in Ext(T)$. ∎

We can also prove the following result:

######  Theorem 1.5.6 ([31, Thm. 3.3]).

For any recursive tree $T\subset\omega^{<\omega}$, $Ext(T)$ is a
$\Sigma^{1}_{1}$ set.

  * Proof.

This follows from the following characterisation:

$\sigma\in Ext(T)\iff(\exists x)(\forall n>|\sigma|)(x\upharpoonright n\in
T\wedge\sigma\prec x\upharpoonright n)$

∎

These results solidify the fundamental link that we will use later,
specifically that the well- or ill-foundedness of a tree
$T\subset\omega^{<\omega}$ is complete to $\Pi^{1}_{1}$ and $\Sigma^{1}_{1}$
formulae. This is a fact that is central to our results in chapter 3 and
beyond.

##  Chapter 2 Tilings - Concepts and Results

> It is the shape that matters.
>
> Samuel Beckett
> to Harold Hobson

This chapter presents previous results to do with the mathematical study of
tiling problems. We present more general results first, and then focus on
tiling problems for Wang prototiles that will occupy the rest of our study in
this thesis.

###  2.1. Tilings of the Plane

In this chapter, we will give an overview of the notation, history, and
important results concerning tiling problems. Unless otherwise indicated, we
will use [32] and [27] as our primary resources for material in this chapter.

####  2.1.1. Preliminaries of Tilings

We will use the following definitions of tilings in this thesis. Note we
restrict ourselves to tilings on the plane $\mathbb{R}^{2}$.

######  Definition 2.1.1 (Tiles).

A _tile_ is a closed polygon that covers some finite potion of the plane.

Topologically, each tile is a closed subset of the plane, and is homeomorphic
to a disc. As such, we can define _tilings_ as follows:

######  Definition 2.1.2 (Tilings).

Tilings will generally take the following forms:

  * •

Tiles form a _complete tiling_ if the union of these subsets is the full
plane.

  * •

Tiles form a _partial tiling_ if there are points in the plane that are not
contained in any subset.

For complete tilings, each point $p\in\mathbb{R}^{2}$ will find itself in one
of two situations. Either we have that:

  1. (1)

$p$ is to the interior of at most one tile, or

  2. (2)

$p$ is on the edge join of two tiles.

As a consequence of this, tiles in a complete tiling have pairwise disjoint
interiors, and there are no gaps between the tiles in the tiling.

To make it easier to consider the relationship between a tiling and the tiles
that constitute it, we can define sets of prototiles as follows:

######  Definition 2.1.3 (Prototile Sets).

For a given tiling $\mathcal{T}$,

  * •

A _prototile_ set $\mathcal{S}\subset\mathcal{T}$ is a set of tiles such that
for every tile $t\in\mathcal{T}$ there is an $s\in\mathcal{S}$ that is
congruent to $t$.

  * •

A prototile set $\mathcal{S}$ is called _minimal_ if for all
$s_{i},s_{j}\in\mathcal{S}$,

$s_{i}\text{ is congruent to }s_{j}\iff s_{i}=s_{j}$

Later in this thesis we will consider only _minimal tilings_ , where we have
substituted geometric requirements with a regular polygonal lattice with edge
conditions. But for now, we will proceed with all the above definitions.

####  2.1.2. The Extension Theorem

The Extension Theorem is a compactness-like argument that is an important
result from the literature, a version of which will become very useful later
in this volume.

We will start with some definitions for related and useful concepts we will
use in theorem 2.1.13. For this section we will assume that all prototile sets
are finite, although we will relax this requirement for our further work in
tiling problems later in this volume.

######  Definition 2.1.4.

Given a tiling $\mathcal{T}$, $t_{i},t_{j}\in\mathcal{T}$, the _Hausdorff
distance_ $h(t_{i},t_{j})$ between two tiles is defined as

$h(t_{1},t_{2})=\max\left\\{\sup_{a\in t_{1}}\inf_{b\in t_{2}}\left\lVert
a-b\right\rVert,\sup_{b\in t_{2}}\inf_{a\in t_{1}}\left\lVert
a-b\right\rVert\right\\}$

From this definition it follows that where for some tiles
$t_{1},t_{2}\in\mathcal{T}$, we have that $h(t_{1},t_{2})=0\implies
t_{1}=t_{2}$.

######  Definition 2.1.5 (Patch Tiling).

A _patch_ is the union of a number of tiles covering some non-total portion of
the plane $R\subset\mathbb{R}^{2}$.

The usual intuition for patch tilings is that they are finite portions of the
plane, however we will also use this wording to denote infinite connected
regions of the plane that are not total. Where the context requires we will
talk of ‘infinite patches’ and ‘finite patches’, but generally speaking, we
use this looser definition of ‘patch tiling’ than is generally used in the
literature.

######  Definition 2.1.6.

We say that a set of prototiles $\mathcal{S}$ _tiles over_ a finite subset $X$
of the plane if there is a finite patch tiling $P_{\mathcal{S}}$ such that for
all $x\in X$, $x\subset P_{\mathcal{S}}$, with each $t\in P_{\mathcal{S}}$
congruent to some $s\in\mathcal{S}$.

Where we have finite patches as a bounded tiling, these are then also
topologically equivalent to a disc.

######  Definition 2.1.7.

A sequence of tiles $t_{1},t_{2},t_{3},\ldots$ _converges_ to a limit tile $t$
if $\lim_{i\to\infty}h(t_{i},t)=0$.

######  Definition 2.1.8 (Circumparameter).

$U$ is a _circumparameter_ of a prototile set $\mathcal{S}$ if for every
$t\in\mathcal{S}$, $t$ is contained in some disc of radius $U$.

######  Definition 2.1.9 (Inparameter).

Analogously we have that $u$ is an _inparameter_ of $\mathcal{S}$ if for each
$t\in\mathcal{S}$, there exists a disc of radius $u$ that can be wholly
inscribed within $t$.

Now that we have covered the base definitions we require for this section, we
will proceed to prove some general theorems in the theory of tilings. Our aim
here is to state the geometric and topological arguments that are commonly
used to analyse general properties of tilings derived from finite prototile
sets. We begin with the following lemmas:

######  Lemma 2.1.10 (Bolzano-Weierstrass Theorem).

Let $S$ be a closed bounded area in $\mathbb{R}^{2}$, and let
$z_{1},z_{2},z_{3},\ldots$ be a sequence of points in $S$. There is a
subsequence of $z_{i_{1}},z_{i_{2}},\ldots$ that converges to some point $z\in
S$.

Note, such a limit $z$ need not be unique.

  * Proof.

Let $z_{i}$ for $i\in\omega$ be our sequence $z_{1},z_{2},z_{3},\ldots$, and
let $S_{0}$ be a bounded region in $\mathbb{R}^{2}$.

First we bisect $S_{0}$. By pigeonhole principle, we have that at least one of
these pieces contains infinitely many $z_{i}$. Call this piece $S_{1}$, and
repeat the subdivision infinitely. The same density must apply to at least one
of any subdivided region, so we can choose a sequence of pieces $S_{2}$,
$S-3$, …containing infinitely-many $z_{i}$ in each subsequent piece.

From our eventual infinite sequence $S_{0},S_{1},S_{2},\ldots$ we can choose
any sequence of points, with each successive $z_{i}$ coming from $S_{i}$.
These points converge closer to some limit point $z$. ∎

######  Theorem 2.1.11 (Selection Theorem, [32, p.154]).

Let $t_{1},t_{2},\ldots$ be an infinite sequence of tiles such that all
$t_{i}$ are congruent - by translation and rotation - to (bounded) $t$, that
is fixed. If every $t_{i}$ contains point $p$, then the sequence contains a
convergent subsequence whose limit tile $t^{\prime}$ is congruent to $t$, with
$p\in t$.

  * Proof.

Choose $t_{n}\cong t_{0}$ for each $n\in\omega$. As such, each point $p\in
t_{n}$ identifies some point $q_{n}\in T$. By 2.1.10, there is a convergent
subsequence $q_{i_{1}},q_{i_{2}},\ldots\rightarrow q$ inside $t$.

Intuitively, this limit point $q$ is taken from a point $p$ that is ‘common’
to all tiles where they translated, but _not_ rotated, and placed over each
other. When separated out, this is our sequence of $q_{i}$’s, where each tile
is labelled spiralling out from our $t_{0}$ \- much like the ‘snake’ proof in
classical set theory.

If we position this $t$ such that $q$ is over the coordinate
$(0,0)\in\mathbb{R}^{2}$, then we can notice that all of our translations are
rotated about $q$. So the position of each tile is the translation $q-q_{i}$
followed by some rotation $\alpha_{i_{n}}$ (mod $2\pi$).

As such, by using the same reasoning in lemma 2.1.10, we can we can gather a
subsequence of rotation angles $\alpha_{i_{1}},\alpha_{i_{2}},\ldots$ which
converges (modulo $2\pi$). Let $\alpha$ be the limit of this sequence, and so
$t_{i_{1}},t_{i_{2}},\ldots\rightarrow t^{\prime}$, which is a copy of $t$
rotated by $\alpha$ and with $q$ coincident with $p$. ∎

Note, this theorem will fail if such a $p$ does not exist, for example. That
said, we will use the following special case later:

######  Corollary 2.1.12 ([32, p.154]).

Let $t_{0},t_{1},t_{2},\ldots$ converge to some $t$, if $d(t_{i},t)\rightarrow
0$ as $i\rightarrow\infty$. Then $t$ is congruent to $t_{0}$.

We can now prove the Extension Theorem, which is a fundamental, general result
about tilings.

######  Theorem 2.1.13 (Tiling Extension Theorem, [32, Thm. 3.8.1]).

Let $\mathcal{S}$ be a finite set of prototiles - each of which is a closed
topological disc. If $\mathcal{S}$ tiles over arbitrarily large discs, then
there exist $\mathcal{S}$-tilings of the plane.

The proof will follow the one found in [32, p.151].

  * Proof.

Let $\mathcal{S}$ be a finite set of prototiles, and let $U$ be the common
circumparameter, and $u$ be the common inparameter. Consider the lattice
$\Lambda$ of all points who regular Cartesian coordinates are $(nu,mu)$ for
$m,n\in\mathbb{Z}$. $\Lambda$ therefore has some point in each prototile in
$\mathcal{S}$. Let $L_{0},L_{1},L_{2},\ldots$ be the full sequence of these
points, spiralling out from some chosen $L_{0}$, say $(0,0)$.

For any positive $r\in\mathbb{N}$, let $D(L_{0},r)$ be the disc of radius $r$
centred on the point $L_{0}$. Let $P(r)$ be the finite patch of tiles from
$\mathcal{S}$ that covers $D(L_{0},r)$. When $r$ is large enough for
$D(L_{0},r)$ to contain some $L_{s}$, let $t_{rs}$ denote the tile of $P(r)$
that covers $L_{s}$. If, however, $L_{s}$ lies on an edge or a vertex point,
then we can choose any tile in $P(r)$ that is incident to $L_{s}$.

By the Selection Theorem (2.1.11) we have that, given $\mathcal{S}$ is finite,
the sequence $t_{0},t_{1},t_{2},\ldots$ has a subsequence
$t^{\prime}_{0},t^{\prime}_{1},\ldots$ of tiles that are congruent to
$t^{\prime}_{0}$. This sequence will also contain an infinite subsequence
$S_{0}=t^{\prime}_{i_{0}},t^{\prime}_{i_{1}},\ldots$ that is convergent, and
whose limit tile $t^{\prime}_{0}$ will also contain $L_{0}$.

We now consider the sequence of tiles $t_{r1}$ containing $L_{1}$, restricting
attention to values of $r$ that correspond to tiles in $S_{0}$. We can carry
out the same line of argument as we just did to acquire $S_{1}$ of tiles all
congruent to $t_{1}$, containing $L_{1}$, and convergent to a limit tile
$t^{\prime}_{1}$.

Let $\mathcal{T}=\\{t^{\prime}_{0},t^{\prime}_{1},t^{\prime}_{2},\ldots\\}$,
deleting any duplicates as necessary in our selection. Ultimately, we want to
show that $\mathcal{T}$ forms an $\mathcal{S}$-tiling of the plane. To show
this, let $p$ be any point of the plane. We want to show that $p$ belongs to
at least one $t^{\prime}_{i}$, but does not belong to the interior of any
other $t^{\prime}_{j}$.

Let $D(p,u)$ be the disc centred at $p$, of circumparameter radius $u$. Let
$L_{m}$ be the point of $\Lambda$ in $D(p,u)$ with greatest index. We want to
restrict our attention to the sequence of finite patches $P(r)$ as $r$ ranges
through value corresponding to the subsequences $S_{m}$, specifically
$\mathcal{T}_{r}=\\{t_{r0},t_{r1},t_{r2},\ldots t_{rm}\\}$.

As $r\rightarrow\infty$, $\mathcal{T}_{r}$ converges to the set
$\mathcal{T}^{\prime}=\\{t^{\prime}_{0},t^{\prime}_{1},\ldots\\}$. Since all
of the tiles in $\mathcal{T}_{r}$ have disjoint interiors, and all contain
$p$, the same is true of each member of $\mathcal{T}^{\prime}$. Thus,
$\mathcal{T}$ is an $\mathcal{S}$-tiling of the plane. ∎

###  2.2. The Domino Problem

Whilst theorem 2.1.13 gives us a notion of compactness that we can express
through tiles, we then come to a more general question about tilings, known as
the ‘Domino Problem’.

######  Definition 2.2.1 (the Domino Problem).

For any given set of prototiles $S$, does there exist an $S$-tiling of the
plane?

By theorem 2.1.13 we know that if we can extend any finite patch $S$-tiling,
we can get a tiling of the plane, but the Domino Problem asks us to consider
whether there is any finite patch that cannot be tiled.

When considering the Domino Problem for various sets of tiles, it is possible
to modulate various requirements on how we cover the plane. For example, we
might not consider trivial sub-tilings of some $S^{\prime}\subset S$, or we
might permit ‘small’ holes that are strictly smaller than any polygon $t\in
S$, such that we can consider them ‘small enough’ in the limit.

Given this definition, it is common to consider these conditions on a Domino
Problem for some prototile set, unless explicitly indicated otherwise. Given a
set of prototiles $S$:

  * •

We will _not_ require that $\forall t\in S$, $t$ is used at least once in each
$S$-tiling of the plane.

    * –

This requirement is sometimes used to prevent trivial sub-tilings of the plane
of some $S^{\prime}\subset S$, mentioned above. However, when we come to
dealing with encoding a Turing Machine into prototile a set, we need to allow
that our TM will not enter every state on every input.

  * •

We will require that, for lattice regular polygonal tilings such as Wang tiles
(defined in 2.2.2) we do not admit rotations of the tiles.

    * –

Although this increases our prototile sets significantly, it make our later
more functional definitions much more straightforward.

  * •

That our tilings are complete tilings.

Though we will make use predominantly of lattice-based tilings in this thesis,
we wish to prevent gap from occurring in our tilings. As such, our resultant
tilings can be thought of as total functions over the plane via coverings
given by mapping each point in the lattice to a copy of a prototile.

These requirements can serve as to simplify our tilings, definitions, and
constructions of prototiles. As noted, although the number of prototiles will
increase, the complexity of our tiling functions will significantly reduce.

However, in this thesis, we will attempt to make our tilings as ‘free’ as
possible. Although this gives us slightly larger prototile sets, it serves to
give us some better insight into the equivalence between the logical
complexity of some statement, the computable trees arising from these
statements, and the computable prototile sets that code paths of these
computable trees into planar tilings.

####  2.2.1. Wang Tiles

To properly analyse the Domino Problem, we wish to reduce the complexity of
our tilings to some ‘bare minimum’, in line with the requirements above. As
such we will make use of Wang tiles, first introduced by Hao Wang in [60],
which we define as follows:

######  Definition 2.2.2 (Wang Tiles).

Let _Wang tiles_ be square tiles, diagonally quadrisected, such that ordered
4-tuples of the form $\langle l,u,r,b\rangle$ can be represented by:

$u$$l$$r$$b$

Where $l,u,r,b$ each stand for left, upper, right, and bottom respectively.

We keep our previous definitions of ‘prototiles’, ‘prototile sets’, and
‘tilings’. Given this prototile definition, we will need to consider what
happens when the edges of our tiles are to meet. Given a set $\mathcal{S}$ of
Wang prototiles:

######  Definition 2.2.3.

Given two Wang tiles $w,u\in\mathcal{S}$, such that $w=\langle
l_{w},u_{w},r_{w},b_{w}\rangle$ and $u=\langle
l_{u},u_{u},r_{u},b_{u}\rangle$:

  * •

The _edge meets_ between these tiles are the comparisons between meeting
edges, where one of the following applies:

    * –

$l_{w}$ is next to $r_{u}$,

    * –

$u_{w}$ is next to $b_{u}$,

    * –

$r_{w}$ is next to $l_{u}$,

    * –

$b_{w}$ is next to $u_{u}$

  * •

The _match criteria_ for Wang tiles are the requirements that for any edge
meet, the edge symbols match. Explicitly, one of the following holds:

    * –

if $l_{w}$ is next to $r_{u}$, then $l_{w}=r_{u}$

    * –

if $u_{w}$ is next to $b_{u}$, then $u_{w}=b_{u}$

    * –

if $r_{w}$ is next to $l_{u}$, then $r_{w}=l_{u}$

    * –

if $b_{w}$ is next to $u_{u}$, then $b_{w}=u_{u}$

$\cdot$$\cdot$$\cdot$$u$$\cdot$$\cdot$$l$$\cdot$$u$$l$$r$$b$$\cdot$$r$$\cdot$$\cdot$$b$$\cdot$$\cdot$$\cdot$
Figure 2.1. Edge Conditions in the von Neumann Neighbourhood surrounding a
Wang tile.

Intuitively we use the von Neumann neighbourhood surrounding the tile as the
basis for our matching and placement conditions for each Wang prototile. This
means that we only ever consider the 4-place valency for each tile and for
each position in our $\mathbb{Z}^{2}$ lattice following the rules we stated
above. When we come to code cellular automata, we will still only consider the
von Neumann neighbourhood over the usual Moore neighbourhood.

From this construction of Wang tiles, we can now envisage our tilings as
projection functions

$f_{\mathcal{S}}:\mathbb{Z}^{2}\rightarrow\mathcal{S}$

This characterisation will be useful when we explore computable tilings later
in this thesis. Thus, the following definition is natural:

######  Definition 2.2.4.

Given a set of Wang prototiles $\mathcal{S}$, we say that an
$\mathcal{S}$-tiling of the plane is a _total tiling_ if for
$f:\mathbb{Z}^{2}\rightarrow\mathcal{S}$, and $f$ enforces the edge-meet
criteria for the von Neumann neighbourhood of every point in $\mathbb{Z}^{2}$.

Given for every point $(x,y)\in\mathbb{Z}^{2}$ there is some $s\in\mathcal{S}$
such that $f(x,y)=s$ and $f$ ensures that $s$ observes and meets all of the
match criteria for its neighbours in the plane.

Our notion of a ‘total Wang tile tiling’ is indeed a direct analogue for
complete tilings we defined earlier. The slight change in terminology is to
facilitate the intuition we will use later in this thesis that a complete
tiling generated by a computable function must be total on $\mathbb{Z}^{2}$,
and so is in this sense a total function. Thereby, total functions give total
tilings, and total tilings must come from total functions.

Thus, a total tiling from a Wang prototile set is analogous to a complete
tiling we considered previously. When we consider computable sets of Wang
prototiles, this definition will be equivalent to a computable function
$\varphi_{e}$ being total.

Wang proved a version of the Extension Theorem for Wang tiles - known as
_Wang’s theorem_. Our statement and proof are taken from [32, p.600].

######  Theorem 2.2.5 ([32, p.600]).

Let $\mathcal{S}$ be a finite set of Wang prototiles. If it is possible, of
arbitrarily large values of $n$, to assemble $n\times n$ blocks of tiles
satisfying the edge-matching conditions, then there is an $\mathcal{S}$-tiling
of the plane.

We should reiterate that we only admit _translations_ of Wang prototiles - we
do not permit rotations of Wang prototiles into tilings of the plane. If we
did, this theorem would be immediate from the Extension theorem, theorem
2.1.13. Additionally the proof will make explicit use of the face that
$\mathcal{S}$ is a finite set of prototiles.

  * Proof.

Given a set of prototiles $\mathcal{S}$, with $|\mathcal{S}|=r$. We can
construct a graph-theoretic tree in the following manner. We start with a
single root node $n^{0}$. Level 1 is formed of $n^{1}_{1},\ldots,n^{1}_{r}$
corresponding to each of the tiles in $\mathcal{S}$. Similarly at each level
$k$, we add nodes $n^{k}_{1},\ldots,n^{k}_{r_{k}}$ corresponding to adding a
ring of tiles around each of the previous blocks.

We then form the tree by joining all of level 1 nodes to the root node. For
any level $k$, we connect any of the $n^{k}$ to the nodes in $n^{k+1}$; if,
for any $n^{k}_{i}$, $n^{k+1}_{j}$ contains the block represented by
$n^{k}_{i}$, and the tiles on the outer edge of block $n^{k+1}_{j}$ match all
the edge-matching criteria for the exterior of the tiles represented in
$n^{k}_{i}$ are met by the inner edge criteria $n^{k+1}_{j}$. If this holds,
then $n^{k}_{i}\text{ and }n^{k+1}_{j}$ are connected.

Each successive block can be thought of as an extension of the previous block
by an outer ‘square ring’ of tiles from $\mathcal{S}$ that surround the
outside of the block.

Thus, we can reduce the question of an $\mathcal{S}$-tiling now to whether
each level $k$ is connected to each $k+1$. If the answer is in the negative,
then there exists some $n$ such that there can be no patch of Wang tiles
greater than $n\times n$ that can be extended to a full planar tiling.

If the answer is in the positive, then we have created a finitely branching
infinite tree. By König’s Lemma, there is necessarily an infinite path through
our tree. By this construction, this path corresponds to an
$\mathcal{S}$-tiling of the plane. ∎

It is worth noting that although König’s Lemma is utilised in this proof, this
is not necessary. Given our sets of prototiles are always finite, we only
actually require Weak König’s Lemma - that an infinite bounded-branching tree
necessarily has an infinite path - for this proof with some modification of
our tiling tree as follows.

  * Alternative Tree Construction for proof of 2.2.5.

Take some finite prototile set $S$, and consider each each point on
$\mathbb{Z}^{2}$ by spiralling out from the centre point $(0,0)$ as before for
the proof of theorem 2.1.13. We can construct a tree based on the valid tiles
that could be placed at each successive point based on the 1 or 2 edge
criteria defined by previously placed tiles.

This tree is bounded by the size $S$, which is finite, thereby restricting the
branching of our tree. A total planar tiling also corresponds to a path
through this tree by the following observations:

    * –

Each level on our tree corresponds to a point in $\mathbb{Z}^{2}$.

    * –

All edge-meet criteria are met by the construction of each branch.

Thus if our tree is infinite, there must be an infinite path by WKL, meaning
there is a total planar tiling. ∎

Later in this thesis, we will entertain weaker notions of tiling the plane,
and will draw more equivalences with properties and principles on trees in
both Baire space and Cantor space.

###  2.3. Undecidability of the Domino Problem

One of Hao Wang’s students, Robert Berger, proved in [5] the undecidability of
the Domino Problem for finite sets of Wang prototiles. Whilst Berger’s
original created a prototile set of over 6,000 tiles, we present an updated
proof where sets of ‘universal Turing Machine prototiles’ number in the few
hundred.

######  Definition 2.3.1.

For a set $\mathcal{S}$ of prototiles, we denote “There exists a complete
$\mathcal{S}$-tiling of the plane” by $Tile(\mathcal{S})$.

Note that $Tile(S)$ immediately has a $\Sigma^{0}_{1}$ normal form as the
existence of an infinite sequence $s\in S^{\omega}$, such that $s$ is a
sequence of tiles that covers each point in the lower-right quarter plane in
$\mathbb{Z}^{2}$, thereby giving a total tiling of this quarter plane.

However, given we can extend any $S$ with tiles that fill in the other three
quarter-planes, we can convert this $s$ to a total planar tiling.

######  Theorem 2.3.2 ([5, Thm. 3-3]).

The Domino Problem for finite Wang prototile sets is
$\Sigma^{0}_{1}$-complete.

We will prove this by showing that for any Turing Machine $\varphi_{e}$ there
exists a set of prototiles $\mathcal{S}_{e}$ such that

$\varphi_{e}(x)\downarrow\iff\neg Tile(\mathcal{S}_{e})$

In order to do this, we will need the following machinery:

######  Definition 2.3.3.

A _schema tile_ is a prototile that determines a set of prototiles for given
sets of colours. That is, it determines the position of colours taken from one
or more sets of colours.

######  Example 2.3.4 (Schema Tile Example).

Let $A=\\{a_{1},a_{2}\\}$ and $B=\\{b_{1}\\}$ be sets of colours. Let $t$ be
the schema tile, with $i\neq j$:

$b_{i}$$a_{i}$$a_{j}$$b_{i}$

The prototile set $\mathcal{S}$ generated by $t$ will consist of the following
tiles:

$b_{1}$$a_{1}$$a_{2}$$b_{1}$

$b_{1}$$a_{2}$$a_{1}$$b_{1}$

It is worth observing that this resultant prototile set can give total planar
tilings.

Thus, we can talk about the following progression:

$\text{schema tile}+\text{colours}\Rightarrow\text{prototile
sets}\Rightarrow\text{planar tilings}$

By careful control of our schema tiles, we can establish the overall ‘shape’
or ‘behaviour’ of our prototile sets, which in turn controls some desirable
feature or features of our classes of planar tilings.

The following proof is after [6] and [12], however it has been restructured in
order to match the structure of proofs later in this thesis.

  * Proof of 2.3.2.

We construct the following schema tiles with which we can emulate Turing
Machines. Let $s\in\Sigma$ be colours representing symbols, $q_{i}\in Q$ be
colours representing machine states, and $(s,q)\in\Sigma\times Q$ be colours
corresponding to each symbol matched with each state. Let $B$ be a
distinguished colour representing ‘blank’, and $H$ be distinguished colour
representing the halting state.

Symbol tiles

$s$$B$$B$$s$

Head State tiles

$s$$q$$B$$(s,q)$

$s$$B$$q$$(s,q)$

Computational tiles For $s,s^{\prime}\in\Sigma$ and $q,q^{\prime}\in Q$,
permitting $s=s^{\prime}$ and $q=q^{\prime}$,

$(s,q)$$B$$q^{\prime}$$s^{\prime}$

$(s,q)$$q^{\prime}$$B$$s^{\prime}$

Halting tile

$s$$B$$H$$s^{\prime}$

Let $\varphi_{e}$ be some Turing Machine composed of 5-tuples, and let
$\varphi_{e}(x)$ be the computation that we wish to represent in our planar
tilings.

We first take every symbol in our Turing program, and represent each one by
some $s\in\Sigma$. We then code each symbol in the tape by a symbol tile. The
‘blank’ representing colour $B$ serves to line up our rows into
representations of configurations $c_{i}$ for $i\in\omega$. We now colour all
of the symbol tiles with each $s\in\Sigma$, and put these into
$\mathcal{S}_{e}$.

Next, we need to assign each of the states in $e$ to a state $q\in Q$, and we
are then ready to add the Head State and Computation prototiles to
$\mathcal{S}_{e}$. To do this, we take each $s\in\Sigma$, and each $q\in Q$,
and assign colours for each ‘TM state’ $(s,q)$. The Head State tiles will
accept a state from $q$ from left or right, and will merge this information
into the bottom quadrant of the prototile.

Next, we need to look to all of the 5-tuples
$(s,q,s^{\prime},q^{\prime},\\{L,R\\})\in e$. For each $(s,q)$ taken from
$\Sigma\times Q$, we look to see which of these form the first two positions
of a 5-tuple. We then create a prototile for $\mathcal{S}_{e}$ of the form of
this tuple based off the schema, placing the exit state $q^{\prime}$ on the
left or right according to the last position of the 5-tuple.

_E.g._ let $(1,a,1,a,L)$ and $(1,b,0,a,R)$ be valid 5-tuples from some given
$\varphi_{e}$. We can represent them in $\mathcal{S}_{e}$ by means of the
computation schema tiles as follows (respectively left and right):

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

$(1,b)$$B$$a$$0$

Given this we colour all the necessary computation tiles - except for any
5-tuple that enters the halting state, which we will deal with below) - remove
any unnecessary head state tiles, and add all these to the symbol tiles in
$\mathcal{S}_{e}$.

In order to complete the representation of $\varphi_{e}$, we need to add the
halting states. These are distinctive, 5-tuples, and for any given halting
5-tuple $(s,q,s^{\prime},HALT,\\{L,R\\})$, we represent these as:

$(s,q)$$B$$H$$s^{\prime}$

In order to fully represent our computation $\varphi_{e}(x)$ we perform the
following steps:

    1. (1)

We first take the representation of $x$ in symbols from $\Sigma$ \- let this
be a string of symbols $s_{0},s_{1},\ldots,s_{k}$, where $k=|x|$.

    2. (2)

We take $s_{0}$, the initial state of our TM $q_{0}$, and place the following
tile in the first position at co-ordinate $(0,0)$:

$s_{0}$$q_{0}$$B$$(s_{0},q_{0})$

    3. (3)

We then place the respective symbol tiles for $s_{1},\ldots,s_{k}$ to the
right of this tile on what will become the representation of the first
configuration $c_{0}$ of $\varphi_{e}(x)$. We can also continue tiling this
entire bi-infinite row according to the symbols on the rest of the TM tape.

       * –

We will later use the index on each configuration $c_{i}$ to map to the lower
quadrants of every even row of tiles $r_{2i}$ for checking later.

    4. (4)

We now continue the computation by continuing the tiling - given the
prototiles in use code each part of the computation, each row can be read off
as a successive stage of the computation.

    5. (5)

the Halting tiles are designed that they will block the tiling from tiling the
plane to the right any further.

We can check the following facts about our tiling computation:

    * –

Given our TM is not a non-deterministic TM, there will be only one choice for
each computation prototile on each row.

    * –

Each row $r_{2i}$ will correspond to some configuration $c_{i}$ in our
computation, with the tape configuration being readable from the top quadrants
of each tile on the row.

    * –

Given our first row setup, there will not be more than one TM head performing
the computation.

Thus, our tiling problem $Tile(\mathcal{S}_{e}(x))$ is also represented by the
problem

$\exists s\,\\{r_{2s}\in\mathcal{S}_{e}(x)\text{ has a hole}\\}$

which is in turn equivalent to the statement $\exists
s\,\varphi_{e,s}(x)\downarrow$. As such, the Domino Problem for finite Wang
prototile sets is $\Sigma^{0}_{1}$-complete. ∎

######  Corollary 2.3.5 ([5, Cor. 4-1, p.36]).

The Domino Problem is undecidable.

  * Proof.

By 2.3.2, it is clear that there exists a class of prototile sets
corresponding to each TM enumerated by some $e$. By our construction,

$\neg Tile(\mathcal{S}_{e}(x))\iff\varphi_{e}(x)\downarrow$

Thus, given the Halting Problem is undecidable, then the question of whether
or not the corresponding $\mathcal{S}_{e}$-tilings tile the plane or not is
also undecidable. ∎

The above re-proof of this classic result due to Berger is intended to
illustrate our proof method in later chapters.

The original proof uses much more machinery, and a large set of prototiles for
a Universal Turing Machine. This simplification makes plain the equivalence
much more immediately, and lays a groundwork for our later results.

We will use this equivalence in the rest of this volume when we define
_computable prototile sets_ and _computable tilings_ in the next chapter.

####  2.3.1. Universal Turing Machine and TM Tilings

Let Universal Turing Machines (UTMs) be minimal Turing Machine symbol and
state sets, such that they can effectively emulate a Turing Machine of any
size.

######  Definition 2.3.6.

Let a _$(x,y)$ -Universal Turing Machine_ $\psi$, denoted $(x,y)$-UTM, be a
Turing Machine that uses precisely $x$ active non-halting states, and $y$-many
symbols on the tape, such that $\psi$ is Turing Complete.

As such, we can think of them as being a pre-coded minimum requirement for any
Turing Machine to operate. Let $\mathcal{S}_{UTM}$ denote a ‘library’ of all
possible states and symbols given by some UTM of a given number of states and
symbols.

Due to the succinctness of our construction, it is reasonable to ask “how big
would a Turing prototile library be?”. By colouring for all possible states,
symbols, and state-symbol combinations we can get the following theorem:

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

There exists a set, called the _library_ , of prototiles $\mathcal{S}$ with
$|\mathcal{S}|=625$, such that for every $\varphi_{e}$ there exists a set of
prototiles $P_{e}\subset\mathcal{S}$ such that $P_{e}$ is a finite set of
prototiles that represents $\varphi_{e}$ selected from $\mathcal{S}$.

The proof of this can be found in [12], and involves colouring a full library
of Turing tiles with the states and symbols of a $(2,5)-UTM$, known universal
Universal Turing Machine.

Indeed, if we take Smith’s as-yet unpublished proof that a $(2,3)$-TM is
universal, [54], then we can get the following theorem:

######  Theorem 2.3.8 (C. 2019).

There is a library set of Turing Machine encoding prototiles of size 105.

The proof comes from generating colours from a set of states $|\Sigma|=2$ and
a set of symbols $|Q|=3$, obtaining $|\Sigma\times Q|=6$, and then applying
these colours to our Turing Tile schemas, and then counting all possible
compositions.

###  2.4. Implications of TM Tilings

There are some interesting implications that arise out of the fact that every
Turing Machine has a representation in tiles. We state the following processes
and theorems from [14], assuming that the definitions of Primitive Recursive
Arithmetic (PRA) and Peano Arithmetic (PA) are already known:

######  Definition 2.4.1 ([14, Process 1]).

  1. (1)

Given some $n\in\omega$, write this number as the sum of powers of $x$
(base-$x$ notation).

  2. (2)

Increase the base of the representation by 1.

  3. (3)

Subtract one from this new representation.

  4. (4)

Return to 2 and repeat this procedure.

######  Definition 2.4.2 ([14, Process 2]).

Same as 2.4.1, except that on step 1 we write $n$ as _pure base_
representation, that is we write $n$ in base $x$, and then continue this
process for all the exponents.

The difference between these two definitions is that process 1 (definition
2.4.1) will admit for $n=244$ a representation of $3^{5}+1$, whilst 2.4.2 will
go further to $3^{3+2}+1$. After one iteration of 2.4.1 we get
$(3^{5}+1):\rightarrow 4^{5}$, whereas 2.4.2 will give us
$(3^{3+2}+1):\rightarrow 4^{4+2}$.

The algorithm in 2.4.2 is due to Goodstein in 1944 in [30]. [14] gives short,
elegant proof of the following famous results originally due to Kirby and
Paris [42]:

######  Theorem 2.4.3 ([14, Thorem 1]).

For any $n\in\omega$ and base $x$, 2.4.1 terminates, but this fact is not
provable in PRA.

######  Theorem 2.4.4 ([14, Thorem 2]).

For any $n\in\omega$ and base $x$, 2.4.2 terminates, but this fact is not
provable in PA.

Denote by $ProvRec(PA)$ the Provably Recursive functions of PA. Cichon’s [14]
proof of 2.4.4 relies on demonstrating that some machine $\varphi_{Good}$ that
computes 2.4.2 is such that

$\varphi_{Good}\notin ProvRec(PA)$

Given this fact, it is necessarily true that

$PA\nvdash\forall n,x\,\exists s\,\varphi_{Good,s}(n,x)\downarrow=0$

Let $S_{Good}$ denote the Turing Machine tiling generated by the process
outlined in the proof of theorem 2.3.2. We get the following corollary:

######  Corollary 2.4.5 (C. 2019).

It is necessarily the case that for all $n,x$ there exists an $s$ such that
the row $r_{2s}$ has a hole, and so $\forall n,x\,[\neg Tile(S_{Good}(n,x))]$,
however by [14] it is necessarily true that

$PA\nvdash\forall n,x\,[\neg Tile(S_{Good}(n,x))]$

It is perhaps unexpected _prima facie_ that the Domino Problem would have the
means to defy provability of mathematically strong theories such as PA.
However, the long established relationships between tilings and computability
cement that there exists sets of Wang prototiles that have interesting proof
theoretic outcomes.

##  Chapter 3 $\Sigma^{1}_{1}$-Complete Tilings

> I could be bounded in a nutshell and count myself king of infinite space.
>
> Hamlet

In this chapter we present our main results that concern infinite sets of Wang
prototiles, and relate these to problems on infinite trees in Baire space.
Previous work in tilings has generally considered finite sets of prototiles -
and this is a natural assumption to make about things that we ostensibly only
consider to be of finitely-many possibilities.

The difference, as we shall see, is that by allowing our tilings as functions
$f:\mathbb{Z}^{2}\rightarrow\mathcal{S}$ to range over infinite prototiles,
the original Domino Problem 2.2.1 becomes equivalent, after careful
construction, to whether a tree corresponding to our tiling is well-founded or
ill-founded. As we found that finite sets of prototiles are equivalent to the
Halting Problem, so we construct this new equivalence in this chapter.

We then extend this result to a variation of the Domino Problem - the problem
of ‘weakly tiling’ the plane, as well as an analogous notion of ‘strongly not
tiling’ the plane.

###  3.1. Computable Trees and Computable Tilings

In the section that follows, we will need the following in order to prove
theorem 3.4.1. First, we define what we mean by computable tilings. Recall
that we represent by $\langle l,u,r,b\rangle$ the Wang prototile

$u$$l$$r$$b$

We define a computable set of Wang prototiles as follows:

######  Definition 3.1.1.

Let $X\subset\omega$, and $\mathcal{S}$ be a set of Wang prototiles.

  * •

Let $X_{\mathcal{S}}=\\{\langle c_{l},c_{u},c_{r},c_{b}\rangle:\langle
c_{l},c_{u},c_{r},c_{b}\rangle\text{ codes some prototile in }\mathcal{S}\\}$.

  * •

We say that $\mathcal{S}$ is _computable_ if $X_{\mathcal{S}}$ is computable.

  * •

We say that an $\mathcal{S}$-tiling of the plane is computable if
$f_{\mathcal{S}}:\mathbb{Z}^{2}\rightarrow\mathcal{S}$ is computable.

  * •

We say that $\mathcal{S}$ is _total_ if for every point
$(x,y)\in\mathbb{Z}^{2}$ and a tiling function
$f:\mathbb{Z}^{2}\rightarrow\mathcal{S}$, $f$ is total on $\mathbb{Z}^{2}$,
all edge conditions are met for any $\mathcal{S}$-tiling.

###  3.2. $\Pi^{1}_{1}$ Properties of Tilings

In this section we will cover previous work on the $\Pi^{1}_{1}$ nature of
specified Domino Problems that inquire about the properties of tile
occurrences in planar tilings.

####  3.2.1. Harel’s $\Pi^{1}_{1}$ Tilings

David Harel in [37] was interested in translations between various kinds of
computable trees. The core idea is to formulate correspondences between
finitely branching and countably infinitely branching trees and infinitely
branching tress, one-to-one, such that the paths along the latter become
“$\varphi$-abiding” paths of the former, for $\varphi$ being some property of
infinite paths.

Harel in [37] proposes the following problem relating to Wang prototile sets:

######  Definition 3.2.1 (Recurring Tile Problem).

Given a set of prototiles $\mathcal{S}$, for $t\in\mathcal{S}$, does $t$ occur
infinitely often in a tiling of the lattice $\mathbb{Z}^{2}$?

This is a variation on the standard Domino problems that we have considered so
far. Rather than ask “do there exist planar tilings?” we ask “do any planar
tilings have a given property?” The property in this case is a weaker question
than “are all $S$-tilings periodic or aperiodic?” - something we will come to
discuss later in this thesis.

Harel in [37] goes on to prove the following theorem:

######  Theorem 3.2.2 ([37], Theorem 6.3).

The Recurring Tile Problem is $\Sigma^{1}_{1}$-complete.

We first require the following definition and lemmas from [37]:

######  Definition 3.2.3.

A class $A$ is _$\Sigma^{1}_{1}$ -hard_ if there is a computable way of
converting any $\Sigma^{1}_{1}$ formula into some member of $A$.

######  Definition 3.2.4.

A tree $T$ is an $\omega$-tree if $T\subseteq\omega^{<\omega}$. A $k$-tree is
a tree $T\subseteq\\{0,1,\ldots,k-1\\}^{<\omega}$ for some finite
$k\in\omega$. If such a _$k$ -tree_ $T$ is bounded by some $b\in\omega$ then
it is a _$b$ -tree_. We say that a _recurrence_ in a $b$-tree is the
repetition of some specific $i\in\\{0,\ldots,k-1\\}$ along an infinite path.

For graph-theoretic trees, this is equivalent to some of the non-leaf nodes
being marked, and a recurrence being infinitely many marked nodes along some
infinite path in the tree.

######  Lemma 3.2.5 ([37], p.230).

The set $A$ of computable well-founded $\omega$-trees is computably isomorphic
to the set $B$ of computable marked recurrence-free $b$-trees.

This lemma then sets the scene for the following theorem:

######  Theorem 3.2.6 ([37], Lemma 6.1).

Let $A$ be the set of computable well-founded $\omega$-trees, and let $C$ be
the set of enumerated notation for all Non-deterministic Turing Machines
(NTMs). Then

$A\equiv_{1}C$

Recalling our definition of 1-reducibility in definition 1.2.21, and let
$A\equiv_{1}B$ iff $A\leq_{1}B$ and $B\leq_{1}A$. A proof of this is found in
[37]. From here we get:

######  Corollary 3.2.7 ([37], Corollary 6.2).

$C$ is $\Pi^{1}_{1}$ complete.

The intuition behind these results is to set the stage that the question:

C1: “for a given NTM $U$, does $U$ re-enter its starting state $q_{0}$
infinitely often?”

is a $\Sigma^{1}_{1}$ link to our Recurring Tile Problem above (RTP). The
proof of 3.2.2 thus proceeds as follows:

  * Proof of 3.2.2.

To first see that RTP is $\Sigma^{1}_{1}$, let $\mathcal{S}$ and some
$t\in\mathcal{S}$ be given. Construct and NTM $M$ that begins on a blank tape
by initially constructing a blank tiling of $\mathbb{Z}^{2}$. At each step,
$M$ iterates over the $\mathbb{Z}^{2}$ lattice in a spiral pattern,
considering each point in turn. Non-deterministically, $M$ tries to tile each
position with some tile from $\mathcal{S}$. $M$ rejects if the edge conditions
fail to match, and signals a successful use of the tile $t$ by re-entering its
starting state $q_{0}$. Otherwise, $M$ will never re-enter $q_{0}$. Thus, $M$
has the property C1 iff $t$ occurs infinitely often in the
$\mathcal{S}$-tiling.

The rest of the proof is showing that RTP is $\Sigma^{1}_{1}$-hard. This is
done through the following three claims. First, define R2 as follows:

R2 - Given $\mathcal{S}$ and $t\in\mathcal{S}$, can $\mathcal{S}$ tile the
positive quadrant of $\mathbb{Z}^{2}$ with $t$ occurring infinitely often and
with the borderlines coloured white?

######  Claim 3.2.8.

R2 is $\Sigma^{1}_{1}$-hard.

  * Proof of 3.2.8.

We sketch the following proof of this claim. By theorem 3.2.6 we have that for
an NTM $M$ that computes from the right, the question of whether it enters its
initial $q_{0}$ infinitely often will be a $\Sigma^{1}_{1}$-hard problem, as
it will be equivalent to the well-foundedness of some $\omega$-tree.

We then construct a tile set from a scheme such that for each $M$, the tile
set we build from $M$ has the property R2 iff $M$ has the property above.

Let $M$ be given, reserving $B$ as the ‘blank’ symbol, and let $p,q$ be
states, and $s,t$ be tape symbols, all in NTM quintuples as defined in chapter
1. Our prototile set $\mathcal{S}$ will consist of tiles generated by the
schema defined in the proof of theorem 2.3.2.

Given our translation of $M$ into tiles preserves the recurrent properties of
$M$, if $M$ enters its starting state $q_{0}$ infinitely often, then the tile
representing this will occur infinitely often in the tiling, so $\mathcal{S}$
satisfies R2, with the white borders guaranteed by substituting the blank
colour $B$ for plain white quadrants in our prototiles. ∎

We modify R2 to the following statement:

R3 - Given $\mathcal{S}$ and $t\in\mathcal{S}$, can $\mathcal{S}$ tile the
positive quadrant of $\mathbb{Z}^{2}$ with $t$ occurring infinitely often?

######  Claim 3.2.9.

R3 is $\Sigma^{1}_{1}$-hard.

  * Proof of 3.2.9.

Note that the border requirement in the previous claim was intended to force
the initial starting state tile giving $q_{0}$ to appear in the right place.
Consider the following machine problem:

C2 - Given NTM $M$, is there some tape configuration and state such that the
following computation does not halt and re-enters $q_{0}$ from the right onto
a blank tape cell infinitely often?

C2 is $\Sigma^{1}_{1}$-hard by theorem 3.2.6 and the observation that a
machine can be run from any starting tape configuration and state. We now
adjust our schema prototiles as follows in order to produce prototiles for our
$\mathcal{S}$ as follows:

For all symbols $s\in\Sigma$:

$s$$\rightarrow$$\rightarrow$$s$

$s$$\leftarrow$$\leftarrow$$s$

For symbols $s,s^{\prime}\in\Sigma$ and $q_{i},q_{j}\in Q$:

$s$${\rightarrow\atop q_{i}}$$\leftarrow$$(s,q_{i})$

$s$$\rightarrow$${\leftarrow\atop q_{i}}$$(s,q_{i})$

$(s,q_{i})$${\rightarrow\atop q_{j}}$$\rightarrow$$s^{\prime}$

$(s,q_{i})$$\leftarrow$${\leftarrow\atop q_{j}}$$s^{\prime}$

Fix $t$ to be

B$\rightarrow$${\leftarrow\atop q_{0}}$$(B,q_{0})$

The addition of the arrows forces patterns of the form

$\cdots\rightarrow\rightarrow\leftarrow\leftarrow\cdots$

This is intended to force only one state to appear on each row in our NTM
tiling. Thus $t$ occurring just once forces exactly one state per row, and so
$(\mathcal{S},t)$ satisfies R3 iff $M$ satisfies C2. ∎

To complete our proof, we need to extend these tilings out from one quadrant
to full planar tilings. First, note that our NTM tapes are bi-infinite two way
tapes, so we can extend our
$\cdots\rightarrow\rightarrow\leftarrow\leftarrow\cdots$ pattern to the left
half of the plane easily.

Extending to the upper half-plane is trickier. Note that there is nothing that
requires $M$ to have infinite computations in the forwards or backwards
directions by default. We can fix the backwards direction by requiring that
$M$ will return repeatedly into some state $q_{i}$, requiring that $q_{i}\neq
q_{0}$.

Likewise, we can prevent $\mathcal{S}$ from having $t$ appear infinitely often