On Strings with Trivial Kolmogorov Complexity
    Download PDF
George Barmpalias. On Strings with Trivial Kolmogorov Complexity. International Journal of Software and Informatics, 2011,5(4):579~593
Hits: 2360
Download times: 1640
Fund:Barmpalias was supported by a research fund for international young scientists No.611501-10168and an International Young Scientist Fellowship number 2010-Y2GB03 from the Chinese Academyof Sciences. Partial support was also obtained by the Grand project: Network Algorithms andDigital Information of the Institute of Software, Chinese Academy of Sciences.
Abstract:The Kolmogorov complexity of a string is the length of the shortest program that generates it. A binary string is said to have trivial Kolmogorov complexity if its complexity is at most the complexity of its length. Intuitively, such strings carry no more information than the information that is inevitably coded into their length (which is the same as the information coded into a sequence of 0s of the same length). We study the set of these trivial sequences from a computational perspective, and with respect to plain and prefix-free Kolmogorov complexity. This work parallels the well known study of the set of nonrandom strings (which was initiated by Kolmogorov and developed by Kummer, Muchnik, Stephan, Allender and others) and points to several directions for further research.
keywords:Kolmogorov complexity  K-trivial  C-trivial  strings  completness  truth table degrees
View Full Text  View/Add Comment  Download reader



Top Paper  |  FAQ  |  Guest Editors  |  Email Alert  |  Links  |  Copyright  |  Contact Us

© Copyright by Institute of Software, the Chinese Academy of Sciences

京公网安备 11040202500065号