  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.

Logic