Michael Deveau, Department of Pure Mathematics, University of Waterloo
"Computability Theory and Some Applications"
In
this
thesis,
we
explore
various
areas
of
computability
theory,
ranging
from
applications
in
computable
structure
theory
primarily
focused
on
problems
about
computing
isomorphisms,
to
a
number
of
new
results
regarding
the
degree-theoretic
notion
of
the
bounded
Turing
hierarchy.
First,
in
joint
work
with
Csima,
Harrison-Trainor
and
Mahmoud,
the
set
of
degrees
that
are
computably
enumerable
in
and
above
$\mathbf{0}^{(\alpha)}$
are
shown
to
be
degrees
of
categoricity
of
a
structure,
where
$\alpha$
is
a
computable
limit
ordinal.
By
restricting
the
construction
to
a
particular
case,
we
are
able
to
produce
a
computable
prime
model
with
a
degree
of
categoricity
as
high
as
is
possible.
This
then
shows
that
a
particular
upper
bound
on
such
degrees
is
exact.
Second,
in
joint
work
with
Csima
and
Stephenson,
a
common
trick
in
computable
structure
theory
as
it
relates
to
degrees
of
categoricity
is
explored.
In
this
trick,
the
degree
of
an
isomorphism
between
computable
copies
of
a
rigid
structure
is
often
able
to
be
witnessed
by
the
clever
choice
of
a
computable
set
whose
image
or
preimage
through
the
isomorphism
actually
attains
the
degree
of
the
isomorphism
itself.
We
construct
a
pair
of
computable
copies
of
$(\omega,
<)$
where
this
trick
will
not
work,
examine
some
problems
with
decidability
of
the
structures
and
work
with
$(\omega^2,
<)$
to
resolve
them
by
proving
a
similar
result.
Next,
the
effectivization
of
Walker's
Cancellation
Theorem
in
group
theory
is
discussed
in
the
context
of
uniformity.
That
is,
if
we
have
an
indexed
collection
of
instances
of
sums
of
finitely
generated
abelian
groups
$A_i
\oplus
G_i
\cong
A_i
\oplus
H_i$
and
the
code
for
the
isomorphism
between
them,
then
we
wish
to
know
to
what
extent
we
can
give
a
single
procedure
that,
given
an
index
$i$,
produces
an
isomorphism
between
$G_i$
and
$H_i$.
Finally,
several
results
pertaining
to
the
bounded
Turing
degrees
(also
known
as
the
weak
truth-table
degrees)
and
the
bounded
jump
are
investigated.
We
investigate
some
open
problems
related
to
lowness
and
highness
as
it
appears
in
this
realm,
and
then
generalize
a
characterization
about
reductions
to
iterated
bounded
jumps
of
arbitrary
sets.
We
use
this
result
to
prove
the
non-triviality
of
the
hierarchy
of
successive
applications
of
the
bounded
jump
above
any
set.
MC 5403