Keng Meng Ng

collaborators

3 papers

math.LO2024

Finite final segments of the d.c.e. Turing degrees

Steffen Lempp, Yiqun Liu, Yong Liu +3

We prove that every finite distributive lattice is isomorphic to a final segment of the d.c.e. Turing degrees (i.e., the degrees of differences of computably enumerable sets). As a…

math.LO2022

Limit Complexities, Minimal Descriptions, and $n$ -Randomness

Rodney Downey, Lu Liu, Keng Meng Ng +1

Let $K$ denote prefix-free Kolmogorov Complexity, and $K^{A}$ denote it relative to an oracle $A$ . We show that for any $n$ , $K^{\emptyset^{(n)}}$ is definable purely in terms of the…

math.LO2014

An analogy between cardinal characteristics and highness properties of oracles

Jörg Brendle, Andrew Brooke-Taylor, Keng Meng Ng +1

We present an analogy between cardinal characteristics from set theory and highness properties from computability theory, which specify a sense in which a Turing oracle is computat…

Finite final segments of the d.c.e. Turing degrees

Limit Complexities, Minimal Descriptions, and n-Randomness

An analogy between cardinal characteristics and highness properties of oracles

Limit Complexities, Minimal Descriptions, and $n$ -Randomness