Computuing \(K\)-trivial sets by incomplete random sets (Q2925324)

In algorithmic randomness, various definitions have been proposed and studied that make precise the intuitive notion of a set of a `random' or `typical' real number, Martin-Löf randomness being the paradigmatical example. Somewhat counter-intuitively, it turns out that some reals that are `random' are also `informative', in that non-computable, but computably enumerable reals can be computed from them. This motivates the question which noncomputable c.e. sets are computable from random sets. One would expect every such set to be in some sense `close to computable'. However, there are in fact random reals that solve the halting problem; once these are excluded by focusing on `incomplete' random sets, i.e. random sets that do not solve the halting problem, we get that all such reals are \(K\)-trivial, which roughly means that their initial segments carry no more information than their length in terms of prefix-free Chaitin complexity. By various results, \(K\)-trivial sets, though not necessarily computable, are indeed `close to computable'. Hence, one may now hope that this implication can be reversed, i.e. that \(K\)-trivial reals are computable from incomplete random sets, yielding a concise answer to the question which noncomputable c.e. sets are computable from random sets. It turns out that this is indeed the case in a quite strong sense: By the main theorem of the paper, there is a single incomplete Martin-Löf random set such that every \(K\)-trivial set is Turing-reducible to it. NEWLINENEWLINENEWLINEThe paper is, as the authors remark in the introduction, rather an `announcement' than a proof, giving sufficient information for an informed reader to construct a complete argument. The motivation and background of the problem are well explained, along with the various relevant results that were accumulated over time and could now finally be pieced together to lead to the main result. The paper contains virtually no proofs but points to the relevant sources. It will be accessible to someone with a basic background in computational randomness.