Martin's conjecture is an attempt to classify the behavior of all definable functions on the Turing degrees under strong set theoretic hypotheses. Very roughly it says that every such function is either eventually constant, eventually equal to the identity function or eventually equal to a transfinite iterate of the Turing jump. It is typically divided into two parts: the first part states that every function is either eventually constant or eventually above the identity function and the second part states that every function which is above the identity is eventually equal to a transfinite iterate of the jump. If true, it would provide an explanation for the unique role of the Turing jump in computability theory and rule out many types of constructions on the Turing degrees.

In this thesis we will introduce a few tools which we use to prove several cases of Martin's conjecture. It turns out that both these tools and these results on Martin's conjecture have some interesting consequences both for Martin's conjecture and for a few related topics.

The main tool that we introduce is a basis theorem for perfect sets, improving a theorem due to Groszek and Slaman. We also introduce a general framework for proving certain special cases of Martin's conjecture which unifies a few pre-existing proofs. We will use these tools to prove three main results about Martin's conjecture: that it holds for regressive functions on the hyperarithmetic degrees (answering a question of Slaman and Steel), that part 1 holds for order preserving functions on the Turing degrees, and that part 1 holds for a class of functions that we introduce, called measure preserving functions.

This last result has several interesting consequences for the study of Martin's conjecture. In particular, it shows that part 1 of Martin's conjecture is equivalent to a statement about the Rudin-Keisler order on ultrafilters on the Turing degrees. This suggests several possible strategies for working on part 1 of Martin's conjecture, which we will discuss.

The basis theorem that we use to prove these results also has some applications outside of Martin's conjecture. We will use it to prove a few theorems related to Sacks' question about whether it is provable in ZFC that every locally countable partial order of size continuum embeds into the Turing degrees. We will show that in a certain extension of ZF (which is incompatible with ZFC), this holds for all partial orders of height two, but not for all partial orders of height three. We will also present an obstacle to embedding height three partial orders into the Turing degrees in ZFC which shows that one of the most natural ways of trying to do so cannot work.

We will end the thesis with a list of open questions related to Martin's conjecture, which we hope will stimulate further research.

We investigate the problem of what equivalence relations from recursion theory are universal countable Borel equivalence relations. While this question is interesting in its own right, it has also been a particularly rich source of connections between recursion theory, countable Borel equivalence relations, and Borel combinatorics. Tools developed by this investigation have proved very applicable to other problems in these fields.

In Chapter 2, we prove a model universality theorem, and introduce several themes of the thesis. A corollary of this first theorem is that polynomial time Turing equivalence is a universal countable Borel equivalence relation.

Slaman and Steel have shown that arithmetic equivalence is a universal countable Borel equivalence relation. In Chapter 3, we combine this fact with the existence of a cone measure for arithmetic equivalence to prove several structural results about universal countable Borel equivalence relations in general. We show that universality for Borel reductions coincides with universality for Borel embeddings, and a universal countable Borel equivalence relation is always universal on some nullset with respect to any Borel probability measure. We also settle questions of Thomas, and Jackson, Kechris, and Louveau by showing that a smooth disjoint union of non-universal countable Borel equivalence relations is non-universal. This result can be significantly strengthened by assuming a conjecture of Martin which states that every Turing invariant function is equivalent to a uniformly Turing invariant function on a Turing cone.

In Chapter 4, we investigate uniformity of homomorphisms among equivalence relations from recursion theory. We pose several open questions in this context, and investigate the implications of the uniformity that they imply. We introduce the concept of a Borel metric on a countable Borel equivalence relation, and show that this concept is closely connected to a weakening of the notion of a uniform homomorphism. Using this language of metrics and the machinery of Slaman and Steel for proving the universality of arithmetic equivalence, we construct an example of a homomorphism between equivalence relations coarser than Turing equivalence which is not uniform on any pointed perfect set. This is the first example of a nonuniform homomorphism in this sort of recursion-theoretic context, and it places some limits on how abstract a proof of Martin's conjecture could be.

In Chapter 5, we turn to the question of whether recursive isomorphism is a universal countable Borel equivalence relation. Improving prior results of Dougherty and Kechris and Andretta, Camerlo, and Hjorth, we show that recursive isomorphism on $3^\omega$ is a universal countable Borel equivalence relation. We isolate a question of Borel combinatorics for which a positive answer would imply that recursive isomorphism on $2^\omega$ is universal. We show that this question is equivalent to the problem of whether $\omega$ many 2-regular Borel graphs on the same space can be simultaneously Borel 3-colored so that there are no monochromatic points. We then show that this question has an affirmative answer if and only if many-one equivalence on $2^\omega$ is a uniformly universal countable Borel equivalence relation. Thus, we have an exact combinatorial calibration of the difficulty of this universality problem.

In Chapter 6, we consider the question of whether there exist disjoint Borel complete sections for every pair of aperiodic countable Borel equivalence relations. We show that this question is very robust, and has many equivalent formulations. A positive answer to this question would positively answer the combinatorial question of the previous paragraph, while a negative answer would settle several open questions of Borel combinatorics. We also show that this question is true in both the measure and category context, in all its equivalent forms. One application of this fact is that every Borel bipartite 3-regular graph has measurable and Baire measurable edge colorings with 4 colors. This is a descriptive analogue of a special case of Vizing's theorem on edge colorings from classical combinatorics. Finally, we see that recursive isomorphism on $2^\omega$ is measure universal. Thus, purely measure-theoretic tools cannot be used to prove that it is not universal.

A generic computation of a subset A of the natural numbers consists of a computation which correctly computes most of the bits of A and never incorrectly computes any bits of A, but which does not necessarily give an answer for every input. This concept derives its motivation from a recent trend in complexity theory to study the complexity of a problem in terms of how difficult it is to compute the majority of size n instances of the problem, and not in terms of how difficult it is to compute the most difficult size n instances of the problem.

When considered from a purely recursion-theoretic point of view, generic computability proves to be somewhat counterintuitive. It can be shown to be, in some sense, as nontransitive as possible, and not only do minimal pairs not exist in this context, but even finite minimal sets of reals can be shown to not exist.

If we modify the definition of generic computation to make it transitive, we are naturally confronted with a deduction procedure in which the oracles, like the computations, are not required to be total. For this reason, “generic reduction” is defined in an inherently Pi11 manner. While studying generic reduction, we show that it is Pi11-complete, and we also present a characterization of the hyperarithmetic reals in terms of generic reduction.

Finally, we increase the level of abstraction, studying transitive and nontransitive deduction procedures with partial oracles. We provide a framework for discussing such reductions, we mention how various known results in recursion theory can be fit into this framework, and we discuss a number of seemingly trivial reductions, showing how subtle variations in the definitions can impact the produced reduction.

We examine the Carlson-Simpson Lemma (VW(k,l)), which is the combinatorial core of the Dual Ramsey Theorem, from the perspective of Reverse Mathematics. Our results include the following:

Working in the system BSigma_2^0, we carry out the construction of a failure of the ordered version of the Carlson-Simpson Lemma OVW(k,l), which was introduced in a paper by Miller and Solomon. This observation implies that we can construct such a recursive counterexample in the model of SRT_2^2 that was discussed in a recent paper by Chong, Slaman and Yang. It follows that SRT_2^2 does not prove OVW(k,l) over RCA_0.

We also show that the strength of the principle VW(k,l) is independent of the number of colors l being used.

By proving that VW(k,l) is not conservative over RCA_0 for arithmetical sentences, we conclude that VW(k,l) is not provable from any theory that is conservative over RCA_0 for arithmetical sentences.

Part 1: Computability in Ordinal Ranks

We analyze the computable part of three classical hierarchies from analysis and set theory. All results are expressed in the notation of Ash and Knight.

In the differentiability hierarchy

defined by Kechris and Woodin, the rank of a

differentiable function is an ordinal less than omega_1 which

measures how complex it is to verify differentiability for that

function. We show that for each recursive ordinal alpha>0, the

set of Turing indices of computable C[0,1] functions that are differentiable with rank at most alpha is Pi_{2alpha+1}-complete.

In the hierarchy defined by the transfinite process of Denjoy integration, the rank of a Denjoy-integrable function f is defined as the ordinal alpha1, the set of indices of computable C[0,1] functions of the form int f, where f has rank at most alpha, is Sigma_{2alpha}-complete.

Finally, we give a new proof that for any recursive ordinal alpha>1, the set of indices for computable trees in 2^{

The major contribution of Part 1 is a general theorem which lies at the core of all three results. We introduce the limsup rank which assigns an ordinal to each well-founded tree in Baire space. Trees of limsup rank alpha are seen to correspond in a computable way to objects of rank alpha in each of the three contexts discussed above. For each recursive ordinal alpha>0, the theorem provides a one-one reduction from emptyset_{(2 alpha)} to the set of Turing indices of trees of limsup rank at most alpha, where emptyset_{(alpha)} is the canonical Sigma_alpha complete set.

Part 2: Computability in Symbolic Dynamics

We consider various questions in the intersection of computability theory as applied to subshifts. In particular, we consider three subshift invariants: entropy, Medvedev degree, and effective dimension spectrum. The last one is a new invariant. We explore these invariants in the context of important examples of subshifts: density-r subshifts, shifts of finite type, subshifts consisting of shift-complex sequences, and Medvedev subshifts.

Building on the work of Hochman & Meyerovitch, Myers, Robinson and Simpson, we show that the entropy and the Medevedev degree are independent invariants. To do this we construct subshifts with every combination of entropy and Medvedev degree that is not immediately prohibited, in both one and two dimensions. When the entropy is right-r.e. and the Medvedev degree is Pi^0_1, the subshifts we produce are Pi^0_1 in the one-dimensional case, and shifts of finite type in the two-dimensional case. When the entropy is in [0,1), we accomplish this using an alphabet with only two symbols.

We introduce the dimension spectrum of a subshift X as {dim(x) : x in X}, where dim is the effective dimension, and work towards a characterization of the possible dimension spectra. By a result of Simpson, every dimension spectrum has a top element. Conditions are given under which the dimension spectrum of X is the interval [0,ent(X)], and examples are given where the dimension spectrum is bounded away from 0.

We show that the dimension spectrum of a one-dimensional minimal subshift has a least element, and find the dimension spectrum of the minimal subshift from Bruin 2000.

From the original definition of a set whose jump is as simple as possible (A' =_T 0'), to more recent definitions involving randomness, notions of lowness appear throughout recursion theory. In that spirit, a non-recursive set A will be said to be low for speed if for any recursive set R and any computation of R from A, there is an oracle-free computation of R that is no more than polynomial-time slower than the A-computation.

We will construct such an r.e. set and discuss some properties of these sets. We will show that promptly simple r.e. sets cannot be low for speed, and also that there are non-prompt sets that are not low for speed. We conclude by showing that generic sets are low for speed if and only if P = NP.

We investigate the Martin-L�of random sample paths of Brownian motion, applying techniques from algorithmic randomness to Brownian motion, an active area of research in probability theory.

In Chapter 2, we investigate many classical results about one dimensional Brownian motion in the context of Martin-L�of randomness. We show that many results which are known to hold almost surely for the Brownian motion process - including results concerning the modulus of continuity, points of increase, time inversion, and law of large numbers - hold for every Martin-L�of random sample path. We also show that scaling invariance and the strong Markov property hold for every Martin-L�of random path, with suitable effectivization.

In Chapter 3, we investigate the zero set of one-dimensional Brownian motion. We prove that the set of zeroes is characterized by having high effective dimension. We also demonstrate that, although the zeroes are highly noncomputable in the sense of effective dimension, many of them are layerwise computable from a Brownian path.

In Chapter 4, we give a new proof that the solution to the Dirichlet problem in the plane is computable. It is a well-known result of Kakutani that the solution to the Dirichlet problem can be found using expected hitting times of Brownian paths to the boundary. We show that the hitting times of Martin-L�of random Brownian paths on a computable boundary are layerwise computable in the path, and thus the expected value of the hitting times is computable, and so the solution to the Dirichlet problem is computable.

In Chapter 5, we further investigate planar Martin-L�of random Brownian motion. We demonstrate that a Martin-L�of random planar Brownian path only hits points such that the path is not random relative to those points (except the origin), which implies that a Martin-L�of random planar path has area zero and that every point except the origin is hit by only measure 0 many paths. We also show that every Martin-L�of random planar Brownian path has points of uncountable multiplicity.

We investigate structures of size at most continuum using various techniques originating from computable structure theory and continuous logic. Our approach, which we are naming ``computable continuous structure theory", allows the fine-grained tools of computable structure theory to be generalized to apply to a wide class of separable completely-metrizable structures, such as Hilbert spaces, the p-adic integers, and many others. We can generalize many ideas, such as effective Scott families and effective type-omitting, to this wider class of structures. Since our logic respects the underlying topology of the space under consideration, it is in some sense more natural for structures with a metrizable topology which is not discrete.

In this dissertation we investigate two questions in the subject of algorithmic randomness. The first question we address is "Given a real, is there a probability measure for which the real is not an atom, but relative to which the real is algorithmically random?" This question was originally studied by Reimann and Slaman with respect to Martin-Lof randomness, and this research continues their investigation by considering the question with respect to stronger notions of randomness and by providing metamathematical analysis of Reimann and Slaman's methods.

The second question we investigate is "What are the first-order consequences of the existence of 2-random reals?" Conidis and Slaman showed that the consequences lie somewhere between IΣ₁ and BΣ₂, but left open the question of further classification. We show that the existence of 2-random reals does not imply BΣ₂, and thus the consequences lie strictly between IΣ₁ and BΣ₂. Furthermore, by utilizing the methods in this proof we are able to construct a κ-like model in which BΣ₂ fails and thereby answer an open question posed by Kaye in 1995.

A split of an r.e. set A is a pair of disjoint r.e. sets whose union is A. We investigate information theoretic properties of r.e. sets and properties of their enumerations, and whether these properties are preserved under splittings. The first part is involved with dynamic notions. An r.e. set is speedable if for every computable function, there exists a finite algorithm enumerating membership faster, by the desired computable factor, on infinitely many integers. Remmel (1986) asked whether every speedable set could be split into two speedable sets. Jahn published a proof, answering their question positively. However, his proof was seen to be incorrect and we construct a speedable set that cannot be split into speedable sets, answering their question negatively. We also prove additional splitting results related to speedability.

The second part is involved with effectively closed sets. We introduce the notion of being recursively avoiding and prove several results.