Browsing by Author "TEUTSCH, Jason"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Immunity and Hyperimmunity for Generalized Random Strings
    (2007-05-17T09:35:39Z) STEPHAN, Frank; TEUTSCH, Jason
    We introduce generalizations of the Kolmogorov random strings, called minimal index sets. The set of Kolmogorov random strings are known to be immune but not hyperimmune. In contrast, minimal index sets are not only immune but also immune against high levels of the arithmetic hierarchy. We give optimal immunity results with respect to the arithmetic hierarchy and we consider the set MIN* as an intuitive counter-example. Of particular note here are the fact that there are three minimal index sets located in Pi-3 but not in Sigma-3 with distinct immunities and that certain immunity properties depend on the choice of Goedel numbering. We show that minimal index sets are not hyperimmune. As a consequence of this fact, we are able to construct a set which neither contains nor is disjoint from any arithmetic set, yet it is majorized by a recursive function and contains a minimal index set. Lastly, we present generalizations of the Kolmogorov random strings which, unlike the more familiar random strings, need not be Turing complete.
  • No Thumbnail Available
    Item
    Index Sets and Universal Numberings
    (2009-03-17T01:51:08Z) JAIN, Sanjay; STEPHAN, Frank; TEUTSCH, Jason
    This paper studies the Turing degrees of various properties defined for universal numberings, that is, for numberings which list all partial-recursive functions. In particular properties relating to the domain of the corresponding functions are investigated like the set DEQ of all pairs of indices of functions with the same domain, the set DMIN of all minimal indices of sets and DMIN* of all indices which are minimal with respect to equality of the domain modulo finitely many differences. A partial solution to a question of Schaefer is obtained by showing that for every universal numbering with the Kolmogorov property, the set DMIN* is Turing equivalent to the double jump of the halting problem. Furthermore, it is shown that the join of DEQ and the halting problem is Turing equivalent to the jump of the halting problem and that there are numberings for which DEQ itself has 1-generic Turing degree.