8 found
Sort by:
  1. George Barmpalias, Rod Downey & Keng Meng Ng (2011). Jump Inversions Inside Effectively Closed Sets and Applications to Randomness. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  2. Barbara F. Csima, Rod Downey & Keng Meng Ng (2011). Limits on Jump Inversion for Strong Reducibilities. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  3. David Diamondstone & Keng Meng Ng (2011). Strengthening Prompt Simplicity. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  4. George Barmpalias, Andrew E. M. Lewis & Keng Meng Ng (2010). The Importance of Π⁰₁ Classes in Effective Randomness. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Rod Downey & Keng Meng Ng (2010). Effective Packing Dimension and Traceability. 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)  
     
    My bibliography  
     
    Export citation  
  6. Keng Meng Ng (2009). On the Degrees of Diagonal Sets and the Failure of the Analogue of a Theorem of Martin. 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)  
     
    My bibliography  
     
    Export citation  
  7. Keng Meng Ng (2008). On Strongly Jump Traceable Reals. Annals of Pure and Applied Logic 154 (1):51-69.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  8. Keng Meng Ng (2008). On Very High Degrees. 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 (5 more)  
     
    My bibliography  
     
    Export citation