Please use this identifier to cite or link to this item:
|Title:||On initial segment complexity and degrees of randomness|
|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. https://doi.org/10.1090/S0002-9947-08-04395-X|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 20, 2018
WEB OF SCIENCETM
checked on Apr 10, 2018
checked on May 18, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.