Differences of halting probabilities

摘要

We study the differences of Martin-Lof random left-c.e. reals and show that for each pair of such reals a, β there exists a unique number r > 0 such that qa — β is a Martin-Loef random left-c.e. real for each positive rational q > r and a Martin-Lof random right-c.e. real for each positive rational q < r. Based on this result we develop a theory of differences of halting probabilities, which answers a number of questions about Martin-Loef random left-c.e. reals, including one of the few remaining open problems from the list of open questions in algorithmic randomness [21]. The halting probability of a prefix-free machine M restricted to a set X is the probability that the machine halts and outputs an element of X. Becher, Figueira, Grigorieff, and Miller asked whether Ω_U (X) is Martin-Lof random when U is universal and X is a ∏_1~0 set. We apply our theory of differences of halting probabilities to give a positive answer.