2017/07/02 by Noam Greenberg, Greenberg, Noam, Joseph S. Miller +5 · 1 citation
Computer Science · Mathematics · #03D30 #03D32 #68Q30 #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Rough Sets and Fuzzy Logic #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1707.00258
openalex publication_date 2017/07/02 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
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. 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~Ω. This leads to a new characterisation of strong jump-traceability.