Two Theorems on Time Bounded Kolmogrov-Chaitin Complexity

An obvious extension of the KolmogorovChaitin 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 KolmogorovChaitin 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)