Working with strong reducibilities above totally ω-c.e. degrees

Abstract. We investigate the connections between the complexity of a c.e. set, as calibrated by its strength as an oracle for Turing computations of func-tions in the Ershov hierarchy, and how strong reducibilities allow us to compute such sets. For example, we prove that a c.e. degree is totally ω-c.e. iff every set in it is weak truth-table reducible to a hypersimple, or ranked, set. We also show that a c.e. degree is array computable iff every left-c.e. real of that degree is reducible in a computable Lipschitz way to a random left-c.e. real (an Ω-number). 1