Chaitin's halting probability and the compression of strings using oracles

Chaitin's halting probability and the compression of strings using oracles

George Barmpalias and Andrew E.M. Lewis

Summary

If a computer is given access to an oracle---the characteristic function of a set whose membership relation may or may not be algorithmically calculable---this may dramatically affect its ability to compress information and to determine structure in strings which might otherwise appear random. This leads to the basic question, ``given an oracle $A$, how many oracles can compress information at most as well as $A$?''

This question can be formalized using Kolmogorov complexity. We say that $B\leq_{LK} A$ if there exists a constant $c$ such that $K^A(\sigma) < K^B(\sigma) +c$ for all strings $\sigma$, where $K^X$ denotes the prefix-free Kolmogorov complexity relative to oracle $X$. The formal counterpart to the previous question now is, ``what is the cardinality of the set of $\leq_{LK}$-predecessors of $A$?''

We completely determine the number of oracles that compress at most as well as any given oracle $A$, by answering a question of Miller which also appears in Nies' book; the class of $\leq_{LK}$-predecessors of a set $A$ is countable if and only if Chaitin's halting probability $\Omega$ is Martin-Löf random relative to $A$.