8 - Higher randomness

Summary

We present an overview of higher randomness and its recent developments. After an introduction, we provide in the second section some background on higher computability, presenting in particular $\Pi^1_1$ and $\Sigma^1_1$ sets from the viewpoint of the computability theorist. In the third section we give an overview of the different higher randomness classes: $\Delta^1_1$-randomness, $\Pi^1_1$-Martin-Löf randomness, higher weak-2 randomness, higher difference randomness, and $\Pi^1_1$-randomness. We then move on to study each of these classes, separating them and inspecting their respective lowness classes. We put more attention on $\Pi^1_1$-Martin-Löf randomness and $\Pi^1_1$-randomness: The former is the higher analogue of the most well-known and studied class in classical algorithmic randomness. We show in particular how to lift the main classical randomness theorems to the higher settings by putting continuity in higher reductions and relativisations. The latter presents, as we will see, many remarkable properties and does not have any analogue in classical randomness. Finally in the eighth section we study randomness along with a higher hierarchy of complexity of sets, motivated by the notion of higher weak-2 randomness. We show that this hierarchy collapses eventually.