Martin-L\"of reducibility and cost functions

arXiv1707.00258MaRDI QIDQ6288540FDOQ6288540

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

Publication date: 2 July 2017

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.

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)

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)