A Caltech Library Service

Two Theorems on Time Bounded Kolmogrov-Chaitin Complexity

Schweizer, David and Abu-Mostafa, Yaser (1985) Two Theorems on Time Bounded Kolmogrov-Chaitin Complexity. California Institute of Technology , Pasadena, CA. (Unpublished)

PDF (Adobe PDF (234KB))
See Usage Policy.


Use this Persistent URL to link to this item:


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).

Item Type:Report or Paper (Technical Report)
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1985.5205-tr-85
Persistent URL:
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26904
Deposited By: Imported from CaltechCSTR
Deposited On:30 Nov 2001
Last Modified:03 Oct 2019 03:19

Repository Staff Only: item control page