4 found
Order:
  1.  10
    ∑5-Completeness of Index Sets Arising From the Lattice of Recursively Enumerable Sets.Michael A. Jahn - 1996 - Annals of Pure and Applied Logic 80 (1):55-67.
    We extend the techniques of Jahn to show the index set of the major subsets to be ∑5-complete. This was a question left open in Lempp and its solution involves a level-4 construction. We also show how the measuring of e-states arises naturally out of our iterated-trees approach to breaking up requirements.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  35
    Implicit Measurements of Dynamic Complexity Properties and Splittings of Speedable Sets.Michael A. Jahn - 1999 - Journal of Symbolic Logic 64 (3):1037-1064.
    We prove that any speedable computably enumerable set may be split into a disjoint pair of speedable computably enumerable sets. This solves a longstanding question of J.B. Remmel concerning the behavior of computably enumerable sets in Blum's machine independent complexity theory. We specify dynamic requirements and implement a novel way of detecting speedability-by embedding the relevant measurements into the substage structure of the tree construction. Technical difficulties in satisfying the dynamic requirements lead us to implement "local" strategies that only look (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  3.  8
    < I> Σ_< Sub> 5-Completeness of Index Sets Arising From the Recursively Enumerable Turing Degrees.Michael A. Jahn - 1996 - Annals of Pure and Applied Logic 79 (2):109-137.
    We employ techniques related to Lempp and Lerman's “iterated trees of strategies” to directly measure a Σ5-predicate and use this in showing the index set of the cuppable r.e. sets to be Σ5-complete. We also show how certain technical devices arise naturally out of the iterated-trees context, in particular, links arise as manifestations of a generalized notion of “stage”.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  4.  6
    Σ5-Completeness of Index Sets Arising From the Recursively Enumerable Turing Degrees.Michael A. Jahn - 1996 - Annals of Pure and Applied Logic 79 (2):109-137.
    We employ techniques related to Lempp and Lerman's “iterated trees of strategies” to directly measure a Σ5-predicate and use this in showing the index set of the cuppable r.e. sets to be Σ5-complete. We also show how certain technical devices arise naturally out of the iterated-trees context, in particular, links arise as manifestations of a generalized notion of “stage”.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark