Browsing by Author "FIGUEIRA, Santiago"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Lowness Properties and Approximations of the Jump
    (2005-11-10) FIGUEIRA, Santiago; NIES, Andre; STEPHAN, Frank
    We study and compare two combinatorial lowness notions: strong jump-traceability and well-approximability of the jump, by strengthening the notion of jump-traceability and super-lowness for sets of natural numbers. A computable non-decreasing unbounded function h is called an order function. Informally, a set A is strongly jump-traceable if for each order function h, for each input e one may effectively enumerate a set T_e of possible values for the jump J^A(e) and the number of values enumerated is at most h(e). A' is well-approximable if can be effectively approximated with less than h(x) changes at input x, for each order function h. We prove that there is a strongly jump-traceable set which is not computable, and that if A' is well-approximable then A is strongly jump-traceable. For r.e. sets, the converse holds as well. We characterize jump-traceability and the corresponding strong variant in terms of Kolmogorov complexity, and we investigate other properties of these lowness ...
  • No Thumbnail Available
    Item
    Randomness and Universal Machines
    (2005-12-09T01:13:26Z) FIGUEIRA, Santiago; STEPHAN, Frank; WU, Guohua
    The present work investigates several questions from a recent survey of Miller and Nies related to Chaitin's Omega numbers and their dependence on the underlying universal machine. It is shown that there are universal machines for which Omega(U) is just the sum over 2^{1-H(x)} for all strings x. Define that Omega(U,X) is the sum over 2^{-|p|} for all p where U(p) is defined and a member of X. Then there exists such a universal machine U and a co-r.e. set X such Omega(U,X) is neither left-r.e. nor Martin-Loef random. Furthermore, one of the open problems of Miller and Nies is answered completely by showing that there is a sequence U_n of universal machines such that the truth-table degrees of the Omega(U_n) form an antichain. Finally it is shown that the members of hyperimmune-free Turing degree of a given Pi-0-1-class are not low for Omega unless this class contains a recursive set.