COMPUTING K-TRIVIAL SETS BY INCOMPLETE RANDOM SETS

Abstrakt

Every K-trivial set is computable from an incomplete Martin-Lof random set, i.e., a Martin-Lof random set that does not compute the halting problem.

Klíčová slova

• information-theory
• lowness properties
• pa