Martin-Löf reducibility and cost functions

Noam Greenberg, Joseph S. Miller, Andre Nies +1

Martin-Löf (ML)-reducibility compares $K$-trivial sets by examining the Martin-Löf random sequences that compute them. We show that every $K$-trivial set is computable from a c.e.\…