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 Feb 21, 2019
WEB OF SCIENCETM
checked on Feb 13, 2019
checked on Jan 18, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.