Martin-L\"of reducibility and cost functions

MaRDI QIDQ6288540FDO

Authors Noam Greenberg, Joseph S. Miller, André Nies, Daniel Turetsky

Publication date 2 July 2017

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: Martin-L"of (ML)-reducibility compares $K$-trivial sets by examining the Martin-L"of random sequences that compute them. We show that every $K$-trivial set is computable from a c.e. set of the same ML-degree. We investigate the interplay between ML-reducibility and cost functions, which are used to both measure the number of changes in a computable approximation, and the type of null sets used to capture ML-random sequences. We show that for every cost function there is a c.e. set ML-above the sets obeying it (called an ML-complete set for the cost function). We characterise the $K$-trivial sets computable from a fragment of the left-c.e. random real~$Omega$. This leads to a new characterisation of strong jump-traceability.

This page was built for publication: Martin-L\"of reducibility and cost functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6288540)