Two Theorems on Time Bounded Kolmogrov-Chaitin Complexity

Schweizer, David and Abu-Mostafa, Yaser (1985) Two Theorems on Time Bounded Kolmogrov-Chaitin Complexity. Technical Report. California Institute of Technology. [CaltechCSTR:1985.5205-tr-85]

Full text available as:

Other (Adobe PDF (234KB))

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

EPrint Type:	Monograph (Technical Report)
Subjects:	All Records
ID Code:	291
Deposited By:	Caltech Library System
Deposited On:	30 November 2001
Record Number:	CaltechCSTR:1985.5205-tr-85
Official Persistent URL:	http://resolver.caltech.edu/CaltechCSTR:1985.5205-tr-85
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record