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.

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”.

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 (...) down the tree. The (obvious) problems with locality are then resolved by placing an isomorphic copy of the entire priority tree below each strategy (yielding a self-similar tree). This part of the construction could be replaced by an application of the Recursion Theorem, but shows how to achieve the same effect with a more direct construction. (shrink)

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”.