Please use this identifier to cite or link to this item:
Title: On initial segment complexity and degrees of randomness
Authors: Miller, J.S.
Yu, L. 
Issue Date: Jun-2008
Citation: Miller, J.S., Yu, L. (2008-06). On initial segment complexity and degrees of randomness. Transactions of the American Mathematical Society 360 (6) : 3193-3210. ScholarBank@NUS Repository.
Abstract: One approach to understanding the fine structure of initial segment complexity was introduced by Downey, Hirschfeldt and LaForte. They define X ≤K Y to mean that (∀n) K(Xn) ≤ K(Yn) + O(1). The equivalence classes under this relation are the K-degrees. We prove that if X ⊕ Y is 1-random, then X and Y have no upper bound in the K-degrees (hence, no join). We also prove that n-randomness is closed upward in the K-degrees. Our main tool is another structure intended to measure the degree of randomness of real numbers: the vL-degrees. Unlike the K-degrees, many basic properties of the vL-degrees are easy to prove. We show that X ≤K Y implies X ≤vL Y , so some results can be transferred. The reverse implication is proved to fail. The same analysis is also done for ≤C, the analogue of ≤K for plain Kolmogorov complexity. Two other interesting results are included. First, we prove that for any Z ∈ 2ω, a 1-random real computable from a 1-Z-random real is automatically 1-Z-random. Second, we give a plain Kolmogorov complexity characterization of 1-randomness. This characterization is related to our proof that X ≤C Y implies X ≤vL Y . Copyright © 2008 American Mathematical Society.
Source Title: Transactions of the American Mathematical Society
ISSN: 00029947
DOI: 10.1090/S0002-9947-08-04395-X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 21, 2019


checked on Feb 13, 2019

Page view(s)

checked on Jan 18, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.