Randomness and Universal Machines
No Thumbnail Available
Date
2005-12-09T01:13:26Z
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.