Switch to: References

Add citations

You must login to add citations.
  1. A Bounded Jump for the Bounded Turing Degrees.Bernard Anderson & Barbara Csima - 2014 - Notre Dame Journal of Formal Logic 55 (2):245-264.
    We define the bounded jump of $A$ by $A^{b}=\{x\in \omega \mid \exists i\leq x[\varphi_{i}\downarrow \wedge\Phi_{x}^{A\upharpoonright \!\!\!\upharpoonright \varphi_{i}}\downarrow ]\}$ and let $A^{nb}$ denote the $n$th bounded jump. We demonstrate several properties of the bounded jump, including the fact that it is strictly increasing and order-preserving on the bounded Turing degrees. We show that the bounded jump is related to the Ershov hierarchy. Indeed, for $n\geq2$ we have $X\leq_{bT}\emptyset ^{nb}\iff X$ is $\omega^{n}$-c.e. $\iff X\leq_{1}\emptyset ^{nb}$, extending the classical result that $X\leq_{bT}\emptyset '\iff (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Bounded-low sets and the high/low hierarchy.Huishan Wu - 2020 - Archive for Mathematical Logic 59 (7-8):925-938.
    Anderson and Csima defined a bounded jump operator for bounded-Turing reduction, and studied its basic properties. Anderson et al. constructed a low bounded-high set and conjectured that such sets cannot be computably enumerable. Ng and Yu proved that bounded-high c.e. sets are Turing complete, thus answered the conjecture positively. Wu and Wu showed that bounded-low sets can be superhigh by constructing a Turing complete bounded-low c.e. set. In this paper, we continue the study of the comparison between the bounded-jump and (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Bounded low and high sets.Bernard A. Anderson, Barbara F. Csima & Karen M. Lange - 2017 - Archive for Mathematical Logic 56 (5-6):507-521.
    Anderson and Csima :245–264, 2014) defined a jump operator, the bounded jump, with respect to bounded Turing reducibility. They showed that the bounded jump is closely related to the Ershov hierarchy and that it satisfies an analogue of Shoenfield jump inversion. We show that there are high bounded low sets and low bounded high sets. Thus, the information coded in the bounded jump is quite different from that of the standard jump. We also consider whether the analogue of the Jump (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Effective Domination and the Bounded Jump.Keng Meng Ng & Hongyuan Yu - 2020 - Notre Dame Journal of Formal Logic 61 (2):203-225.
    We study the relationship between effective domination properties and the bounded jump. We answer two open questions about the bounded jump: We prove that the analogue of Sacks jump inversion fails for the bounded jump and the wtt-reducibility. We prove that no c.e. bounded high set can be low by showing that they all have to be Turing complete. We characterize the class of c.e. bounded high sets as being those sets computing the Halting problem via a reduction with use (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation