We examine the randomness and triviality of reals using notions arising from martingales and prefix-free machines.

In the present paper we prove that the isolated differences of r. e. degrees are dense in the r. e. degrees.

We show that the intersection of the class of 2-REA degrees with that of the ω-r.e. degrees consists precisely of the class of d.r.e. degrees. We also include some applications and show that there is no natural generalization of this result to higher levels of the REA hierarchy.

We examine the effective categoricity of equivalence structures via Ershov's difference hierarchy. We explore various kinds of categoricity available by distinguishing three different notions of isomorphism available in this hierarchy. We prove several results relating our notions of categoricity to computable equivalence relations: for example, we show that, for such relations, computable categoricity is equivalent to our notion of weak ω-c.e. categoricity, and that $\Delta _2^0 $ -categoricity is equivalent to our notion of graph-ω-c.e. categoricity.

Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ⋃ c) ⋂ (b ⋃ c), a ⋃ c | b ⋃ c, and c < a ⋃ b.

We construct a $\Delta^0_2$ degree which fails to be computably enumerable in any computably enumerable set strictly below $\emptyset'$.

We construct a Δ 0 2 degree which fails to be computably enumerable in any computably enumerable set strictly below $\emptyset'$.

Examining various kinds of isolation phenomena in the Turing degrees, I show that there are, for every n>0, (n+1)-c.e. sets isolated in the n-CEA degrees by n-c.e. sets below them. For n≥1 such phenomena arise below any computably enumerable degree, and conjecture that this result holds densely in the c.e. degrees as well. Surprisingly, such isolation pairs also exist where the top set has high degree and the isolating set is low, although the complete situation for jump classes remains unknown.