18 found
Order:
  1.  3
    Universal Computably Enumerable Equivalence Relations.Uri Andrews, Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Luca San Mauro & Andrea Sorbi - 2014 - Journal of Symbolic Logic 79 (1):60-88.
  2.  2
    On Δ 2 0 -Categoricity of Equivalence Relations.Rod Downey, Alexander G. Melnikov & Keng Meng Ng - 2015 - Annals of Pure and Applied Logic 166 (9):851-880.
  3.  7
    Abelian P -Groups and the Halting Problem.Rodney Downey, Alexander G. Melnikov & Keng Meng Ng - 2016 - Annals of Pure and Applied Logic 167 (11):1123-1138.
  4.  19
    The Importance of Π⁰₁ Classes in Effective Randomness.George Barmpalias, Andrew E. M. Lewis & Keng Meng Ng - 2010 - Journal of Symbolic Logic 75 (1):387-400.
    We prove a number of results in effective randomness, using methods in which $\Pi _{1}^{0}$ classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  5.  1
    The Importance of Π1 0 Classes in Effective Randomness.George Barmpalias, Andrew E. M. Lewis & Keng Meng Ng - 2010 - Journal of Symbolic Logic 75 (1):387-400.
    We prove a number of results in effective randomness, using methods in which Π⁰₁ classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  6.  2
    Splitting Into Degrees with Low Computational Strength.Rod Downey & Keng Meng Ng - forthcoming - Annals of Pure and Applied Logic.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  7. On Strongly Jump Traceable Reals.Keng Meng Ng - 2008 - Annals of Pure and Applied Logic 154 (1):51-69.
    In this paper we show that there is no minimal bound for jump traceability. In particular, there is no single order function such that strong jump traceability is equivalent to jump traceability for that order. The uniformity of the proof method allows us to adapt the technique to showing that the index set of the c.e. strongly jump traceables is image-complete.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  8.  16
    Limits on Jump Inversion for Strong Reducibilities.Barbara F. Csima, Rod Downey & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (4):1287-1296.
    We show that Sacks' and Shoenfield's analogs of jump inversion fail for both tt- and wtt-reducibilities in a strong way. In particular we show that there is a ${\mathrm{\Delta }}_{2}^{0}$ set B > tt ∅′ such that there is no c.e. set A with A′ ≡ wtt B. We also show that there is a ${\mathrm{\Sigma }}_{2}^{0}$ set C > tt ∅′ such that there is no ${\mathrm{\Delta }}_{2}^{0}$ set D with D′ ≡ wtt C.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  9.  7
    Effective Packing Dimension and Traceability.Rod Downey & Keng Meng Ng - 2010 - Notre Dame Journal of Formal Logic 51 (2):279-290.
    We study the Turing degrees which contain a real of effective packing dimension one. Downey and Greenberg showed that a c.e. degree has effective packing dimension one if and only if it is not c.e. traceable. In this paper, we show that this characterization fails in general. We construct a real $A\leq_T\emptyset''$ which is hyperimmune-free and not c.e. traceable such that every real $\alpha\leq_T A$ has effective packing dimension 0. We construct a real $B\leq_T\emptyset'$ which is not c.e. traceable such (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  10.  3
    On Very High Degrees.Keng Meng Ng - 2008 - Journal of Symbolic Logic 73 (1):309-342.
    In this paper we show that there is a pair of superhigh r.e. degree that forms a minimal pair. An analysis of the proof shows that a critical ingredient is the growth rates of certain order functions. This leads us to investigate certain high r.e. degrees, which resemble ∅′ very closely in terms of ∅′-jump traceability. In particular, we will construct an ultrahigh degree which is cappable.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  11.  17
    On the Degrees of Diagonal Sets and the Failure of the Analogue of a Theorem of Martin.Keng Meng Ng - 2009 - Notre Dame Journal of Formal Logic 50 (4):469-493.
    Semi-hyperhypersimple c.e. sets, also known as diagonals, were introduced by Kummer. He showed that by considering an analogue of hyperhypersimplicity, one could characterize the sets which are the Halting problem relative to arbitrary computable numberings. One could also consider half of splittings of maximal or hyperhypersimple sets and get another variant of maximality and hyperhypersimplicity, which are closely related to the study of automorphisms of the c.e. sets. We investigate the Turing degrees of these classes of c.e. sets. In particular, (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  12.  12
    Strengthening Prompt Simplicity.David Diamondstone & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (3):946 - 972.
    We introduce a natural strengthening of prompt simplicity which we call strong promptness, and study its relationship with existing lowness classes. This notion provides a ≤ wtt version of superlow cuppability. We show that every strongly prompt c.e. set is superlow cuppable. Unfortunately, strong promptness is not a Turing degree notion, and so cannot characterize the sets which are superlow cuppable. However, it is a wtt-degree notion, and we show that it characterizes the degrees which satisfy a wtt-degree notion very (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  13.  1
    A Friedberg Enumeration of Equivalence Structures.Rodney G. Downey, Alexander G. Melnikov & Keng Meng Ng - 2017 - Journal of Mathematical Logic 17 (2):1750008.
    We solve a problem posed by Goncharov and Knight 639–681, 757]). More specifically, we produce an effective Friedberg enumeration of computable equivalence structures, up to isomorphism. We also prove that there exists an effective Friedberg enumeration of all isomorphism types of infinite computable equivalence structures.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  14.  7
    Jump Inversions Inside Effectively Closed Sets and Applications to Randomness.George Barmpalias, Rod Downey & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (2):491 - 518.
    We study inversions of the jump operator on ${\mathrm{\Pi }}_{1}^{0}$ classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0′ sets which are not 2-random. Both of the classes coincide with the degrees above 0′ which are not 0′-dominated. A (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  15.  1
    Complexity of Equivalence Relations and Preorders From Computability Theory.Egor Ianovski, Russell Miller, Keng Meng Ng & André Nies - 2014 - Journal of Symbolic Logic 79 (3):859-881.
  16. The Importance of $\Pi _1^0$ Classes in Effective Randomness. The Journal of Symbolic Logic, Vol. 75.George Barmpalias, Andrew E. M. Lewis, Keng Meng Ng & Frank Stephan - 2012 - Bulletin of Symbolic Logic 18 (3):409-412.
  17. Ω-Change Randomness and Weak Demuth Randomness.Johanna N. Y. Franklin & Keng Meng Ng - 2014 - Journal of Symbolic Logic 79 (3):776-791.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  18. Lowness for Effective Hausdorff Dimension.Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Daniel D. Turetsky & Rebecca Weber - 2014 - Journal of Mathematical Logic 14 (2):1450011.