Two Theorems on Time Bounded Kolmogrov-Chaitin Complexity

Abstract

An obvious extension of the Kolmogorov﷓Chaitin notion of complexity is to require that the program which generates a string terminate within a prespecified time bound. We show that given a computable bound on the amount of time allowed for the production of a string from the program which generates it, there exist strings of arbitrarily low Kolmogorov﷓Chaitin complexity which appear maximally random. That is, given a notion of fast, we show that there are strings which are generated by extremely short programs, but which are not generated by any fast programs shorter than the strings themselves. We show by enumeration that if we consider generating strings from programs some constant number of bits shorter than the strings themselves then these apparently random strings are significant (i.e are a proper fraction of all strings of a given length).

Files

Additional details