EveryK-trivial set is computable from an incomplete Martin-Löf random set, i.e., a Martin-Löf random set that does not compute the halting problem.

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. (...) sets are not dense [2]), however the problem for the computable Lipschitz degrees is more complex. (shrink)

This paper investigates indifferent sets for comeager classes in Cantor space focusing of the class of all 1-generic sets and the class of all weakly 1-generic sets. Jockusch and Posner showed that there exist 1-generic sets that have indifferent sets [10]. Figueira, Miller and Nies have studied indifferent sets for randomness and other notions [7]. We show that any comeager class in Cantor space contains a comeager class with a universal indifferent set. A forcing construction is used to show that (...) any 1-generic set, or weakly 1-generic set, has an indifferent set. Such an indifferent set can by computed by any set in GL2 which bounds the (weakly) 1-generic. We show by approximation arguments that some, but not all, ∆0 1-generic sets can compute an indifferent set 2 for themselves. We show that all ∆0 weakly 1-generic sets can compute 2 an indifferent set for themselves. Additional results on indifferent sets, including one of Miller, and two of Fitzgerald, are presented. (shrink)

There are two fundamental computably enumerable sets associated with any Kolmogorov complexity measure. These are the set of non-random strings and the overgraph. This paper investigates the computational power of these sets. It follows work done by Kummer, Muchnik and Positselsky, and Allender and co-authors. Muchnik and Positselsky asked whether there exists an optimal monotone machine whose overgraph is not tt-complete. This paper answers this question in the negative by proving that the overgraph of any optimal monotone machine, or any (...) optimal process machine, is tt-complete. The monotone results are shown for both descriptional complexity Km and KM, the complexity measure derived from algorithmic probability. A distinction is drawn between two definitions of process machines that exist in the literature. For one class of process machines, designated strict process machines, it is shown that there is a universal machine whose set of non-random strings is not tt-complete. (shrink)

Over the past seventy-five years, the UN has evolved significantly, often in response to geopolitical dynamics and new waves of thinking. In some respects, the UN has registered remarkable achievements, stimulating a wide range of multilateral treaties, promoting significant growth of human rights, and at times playing a central role in containing and preventing large-scale armed conflict. As part of the special issue on “The United Nations at Seventy-Five: Looking Back to Look Forward,” this essay argues that the organization has (...) been the most impactful in three areas: producing, shaping, and driving key ideas, particularly on development and rights; generating such effective operational agencies as UNICEF and the World Food Program; and, especially in the immediate post–Cold War period, addressing major conflict risks through the Security Council. Since then, however, the UN has struggled to meet emerging challenges on many fronts and been increasingly hampered by internal ossification and institutional sprawl as well as internecine dysfunction. The twenty-first century has confronted the UN with further challenges relating most notably to climate change; to risks arising from new technologies; and to the increasingly fraught relationships between China, Russia, and the United States. If the past seventy-five years can offer one lesson, it is that new thinking and new ideas will need to drive the organization to evolve still further and faster, or else risk irrelevance. (shrink)