This book is concerned with the theory of computability and complexity over the real
numbers. This theory was initiated by Turing, Grzegorczyk, Lacombe, Banach and Mazur …

We report on some recent work centered on attempts to understand when one set is more
random than another. We look at various methods of calibration by initial segment …

One approach to understanding the fine structure of initial segment complexity was
introduced by Downey, Hirschfeldt and LaForte. They define $ X\leq _K Y $ to mean that …

It is time for a new paper about open questions in the currently very active area of
randomness and computability. Ambos-Spies and Kučera presented such a paper in 1999 …

In this paper, we define new notions of randomness based on the difference hierarchy. We
consider various ways in which a real can avoid all effectively given tests consisting of $ n …

As a natural example of a 1-random real, Chaitin proposed the halting probability Ω of a
universal prefix-free machine. We can relativize this example by considering a universal …

If x= x1x2⋯ xn⋯ is a random sequence, then the sequence y= 0x10x2⋯ 0xn⋯ is clearly not
random; however, y seems to be “about half random”. L. Staiger [Kolmogorov complexity …

Algorithmic randomness Page 1 70 COMMUNICATIONS OF THE ACM | MAY 2019 | VOL. 62 |
NO. 5 review articles IMA GE B Y DUKENOD CLASSICAL PROBABILITY THEORY gives all …

Suppose we are given a computably enumerable object. We are interested in the strength of
oracles that can compute an object that approximates this ce object. It turns out that in many …

We call A weakly low for K if there is ac such that KA (σ)≥ K (σ)− c for infinitely many σ; in
other words, there are infinitely many strings that A does not help compress. We prove that A …