Switch to: References

Citations of:

The Ershov Hierarchy

In S. B. Cooper & Andrea Sorbi (eds.), Computability in Context: Computation and Logic in the Real World. World Scientific (2011)

Add citations

You must login to add citations.
  1. Avoiding uniformity in the Δ 2 0 enumeration degrees.Liliana Badillo & Charles M. Harris - 2014 - Annals of Pure and Applied Logic 165 (9):1355-1379.
    Defining a class of sets to be uniform Δ02 if it is derived from a binary {0,1}{0,1}-valued function f≤TKf≤TK, we show that, for any C⊆DeC⊆De induced by such a class, there exists a high Δ02 degree c which is incomparable with every degree b ϵ Ce \ {0e, 0'e}. We show how this result can be applied to quite general subclasses of the Ershov Hierarchy and we also prove, as a direct corollary, that every nonzero low degree caps with both (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • A classification of low c.e. sets and the Ershov hierarchy.Marat Faizrahmanov - forthcoming - Mathematical Logic Quarterly.
    In this paper, we prove several results about the Turing jumps of low c.e. sets. We show that only Δ‐levels of the Ershov Hierarchy can properly contain the Turing jumps of c.e. sets and that there exists an arbitrarily large computable ordinal with a normal notation such that the corresponding Δ‐level is proper for the Turing jump of some c.e. set. Next, we generalize the notion of jump traceability to the jump traceability with ‐ and ‐bound for every infinite computable (...)
    Download  
     
    Export citation  
     
    Bookmark