Martin–Löf reducibility and cost functions

Martin-Löf (ML)-reducibility compares the complexity of K -trivial sets of natural numbers by examining the Martin-Löf random sequences that compute them. One says that a K -trivial set A is ML-reducible to a K -trivial set B if every ML-random computing B also computes A . We show that every K -tri...

Full description

Saved in:
Bibliographic Details
Published in:Israel journal of mathematics 2024, Vol.260 (1), p.261-301
Main Authors: Greenberg, Noam, Miller, Joseph S., Nies, André, Turetsky, Dan
Format: Article
Language:English
Subjects:
Algebra
Analysis
Applications of Mathematics
Cost function
Group Theory and Generalizations
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Number theory
Sequences
Theoretical
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Martin-Löf (ML)-reducibility compares the complexity of K -trivial sets of natural numbers by examining the Martin-Löf random sequences that compute them. One says that a K -trivial set A is ML-reducible to a K -trivial set B if every ML-random computing B also computes A . 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 intended to capture ML-random sequences. We show that for every cost function there is a c.e. set that is ML-complete among the sets obeying it. We characterise the K -trivial sets computable from a fragment of the left-c.e. random real Ω given by a computable set of bit positions. This leads to a new characterisation of strong jump-traceability.
ISSN:0021-2172
1565-8511
DOI:10.1007/s11856-023-2565-x