We prove that there exists a noncomputable c.e. real which is low for weak 2-randomness, a definition of randomness due to Kurtz, and that all reals which are low for weak 2-randomness are low for Martin-Löf randomness.

We call A weakly low for K if there is a c such that $K^A(\sigma)\geq K(\sigma)-c$ for infinitely many σ; in other words, there are infinitely many strings that A does not help compress. We prove that A is weakly low for K if and only if Chaitin's Ω is A-random. This has consequences in the K-degrees and the low for K (i.e., low for random) degrees. Furthermore, we prove that the initial segment prefix-free complexity of 2-random reals is infinitely (...) often maximal. This had previously been proved for plain Kolmogorov complexity. (shrink)

I first seriously contemplated writing a book on degree theory in 1976 while I was visiting the University of Illinois at Chicago Circle. There was, at that time, some interest in ann-series book about degree theory, and through the encouragement of Bob Soare, I decided to make a proposal to write such a book. Degree theory had, at that time, matured to the point where the local structure results which had been the mainstay of the earlier papers in the area (...) were finding a steadily increasing number of applications to global degree theory. Michael Yates was the first to realize that the time had come for a systematic study of the interaction between local and global degree theory, and his papers had a considerable influence on the content of this book. During the time that the book was being written and rewritten, there was an explosion in the number of global theorems about the degrees which were proved as applications of local theorems. The global results, in turn, pointed the way to new local theorems which were needed in order to make further progress. I have tried to update the book continuously, in order to be able to present some of the more recent results. It is my hope to introduce the reader to some of the fascinat ing combinatorial methods of Recursion Theory while simultaneously showing how to use these methods to prove some beautiful global theorems about the degrees. (shrink)

The interplay between computability and randomness has been an active area of research in recent years, reflected by ample funding in the USA, numerous workshops, and publications on the subject. The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the complexity aspect. However, computability theoretic tools can also be used to introduce mathematical counterparts for the intuitive notion of randomness of a set. Recent research shows that, conversely, concepts (...) and methods originating from randomness enrich computability theory.The book covers topics such as lowness and highness properties, Kolmogorov complexity, betting strategies and higher computability. Both the basics and recent research results are desribed, providing a very readable introduction to the exciting interface of computability and randomness for graduates and researchers in computability theory, theoretical computer science, and measure theory. (shrink)

Van Lambalgen's Theorem plays an important role in algorithmic randomness, especially when studying relative randomness. In this paper we extend van Lambalgen's Theorem by considering the join of infinitely many reals which are random relative to each other. In addition, we study computability of the reals in the range of Omega operators. It is known that $\Omega^{\phi'}$ is high. We extend this result to that $\Omega^{\phi^{(n)}}$ is $\textrm{high}_n$ . We also prove that there exists A such that, for each n (...) , the real $\Omega^A_M$ is $\textrm{high}_n$ for some universal Turing machine M by using the extended van Lambalgen's Theorem. (shrink)

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 [1]. All the question in it have been solved, except for one: is KL-randomness different from Martin-Löf randomness? This question is discussed in Section 6.Not all the questions are necessarily hard—some simply have not been tried seriously. When we think a question is a major one, and therefore likely to be hard, (...) we indicate this by the symbol ▶, the criterion being that it is of considerable interest and has been tried by a number of researchers. Some questions are close contenders here; these are marked by ▷. With few exceptions, the questions are precise. They mostly have a yes/no answer. However, there are often more general questions of an intuitive or even philosophical nature behind. We give an outline, indicating the more general questions.All sets will be sets of natural numbers, unless otherwise stated. These sets are identified with infinite strings over {0, 1}. Other terms used in the literature are sequence and real. (shrink)