ABSTRACT
It is known that infinite binary sequences of constant Kolmogorov complexity are exactly the recursive ones. This chapter proposes some definitions, based on Kobayashi’s notion of compressibility, and compare them to both the standard resource-bounded Kolmogorov complexity of infinite strings, and the uniform complexity. Some nontrivial coincidences and disagreements are proved. Kolmogorov complexity measures the quantity of information contained in a finite string. It is usually defined as the size of a minimal program able to instruct a universal Turing machine to produce the string. Of course, for a fixed, individual string, its complexity is a fixed number. In general, for recursive monotonic functions all the classes between Kobayashi’s and Loveland’s definitions are again equivalent modulo constant factors. The technical details that made our definitions syntactically different are only relevant for “unreasonable” bounds.
