Computing K-Trivial Sets by Incomplete Random Sets

2013/05/23 by Laurent Bienvenu, Bienvenu, Laurent, Adam R. Day +11
Computer Science · #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.1305.5514

openalex publication_date 2013/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Every K-trivial set is computable from an incomplete Martin-Löf random set, i.e., a Martin-Löf random set that does not compute 0'.

Related

• Density, forcing, and the covering problem
• Martin-Löf reducibility and cost functions
• Pointed computations and Martin-Löf randomness
• Van Lambalgen's theorem fails for some computable measure
• Limit Complexities, Minimal Descriptions, and n-Randomness