Computability, Traceability and Beyond

Abstract

This thesis is concerned with the interaction between computability and randomness. In the first part, we study the notion of traceability. This combinatorial notion has an increasing influence in the study of algorithmic randomness. We prove a separation result about the bounds on jump traceability, and show that the index set of the strongly jump traceable computably enumerable (c.e.) sets is PI superscript (0) subscript (4)-complete. This shows that the problem of deciding if a c.e. set is strongly jump traceable, is as hard as it can be. We define a strengthening of strong jump traceability, called hyper jump traceability, and prove some interesting results about this new class. Despite the fact that the hyper jump traceable sets have their origins in algorithmic randomness, we are able to show that they are natural examples of several Turing degree theoretic properties. For instance, we show that the hyper jump traceable sets are the first example of a lowness class with no promptly simple members. We also study the dual highness notions obtained from strong jump traceability, and explore their degree theoretic properties. In the second part we investigate the degree theoretic aspects of different classes arising in algorithmic randomness. We show that every PA degree is the join of two random degrees. We also study the Turing degrees with effective packing dimension one. In particular, we show that these degrees are not as well-behaved as they were initially conjectured. We define a weak notion of Martin-Lof randomness, and characterize the c.e. degrees which contain such randoms. This is the first time a class of random reals is characterized using multiple permitting arguments - the latter arose in classical degree theory in connection with lattice embeddings. Lastly we investigate the sets which are low for Demuth randomness, and show that every such set is hyperimmunefree. In the third part we explore the structure of the c.e. Turing degrees. We investigate which c.e. degrees can be split into smaller ones with low complexity. For instance we construct a c.e. degree which cannot be split into two superlow c.e. degrees. This highlights the fact that the low and superlow c.e. degrees are very di erent. We also prove some results about cupping classes: we show that the low2- cuppable sets are exactly the c.e. traceable-cuppable sets. We refute a conjecture of Li on the cuppable sets, by constructing a cuppable c.e. set which can only be cupped with high sets. We present some results on strong tabular reducibilities. In particular, we show that the truth table analogue and the weak truth table analogue of two classical jump inversion theorems fail. Finally, we study the Turing degrees of diagonal sets. We answer a question of Kummer and show that the semi-maximal and semi-hyperhypersimple degrees do not coincide.