Browse Prior Art Database

Two Theorems on Time Bounded Kolmogorov-Chaitin Complexity

IP.com Disclosure Number: IPCOM000127943D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 5 page(s) / 19K

Publishing Venue

Software Patent Institute

Related People

David Schweizer: AUTHOR [+4]

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 (Le are a proper fraction of all strings of a given length).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 34% of the total text.

Page 1 of 5

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Two Theorems on Time Bounded Kolmogorov-Chaitin Complexity

David Schweizer and Yaser Abu-Mostafa

Department of Computer Science California Institute of Technology

5205:TR:85 ,, November 1985

This work was supported by Caltech's Program in Advanced Technologies, sponsored by Aerojet General, General Motors, GTE, and TRW.

California Institute of Technology Two Theorems on Time Bounded Kolmogorov-Chaitin Complexity David Schweizer and Yaser Abu-Mostafa Computer Science 256-80 California Institute of Technology Pasadena, CA

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 (Le are a proper fraction of all strings of a given length).

Notation and Definitions

We will be working over the input alphabet

(Equation Omitted)

and we write # for the blank symbol. We write s to denote a string in E'" and A to denote the empty string. If s E E" (i.e. s is of length n) we write

(Equation Omitted)

. We take U to be a particular implementation of the Universal Turing Machine with input alphabet E and states

(Equation Omitted)

where qo is the start state, and ql is the halt state. U operates on encodings of Turing Machines. We write p(M) to denote the encoding of the Turing Machine M and p(M)w to denote the binary string w concatenated onto the encoding of M. Given p(M)w as input, U halts iff M halts on the

California Institute of Technology Page 1 Dec 31, 1985

Page 2 of 5

Two Theorems on Time Bounded Kolmogorov-Chaitin Complexity

input w, and leaves as output precisely what M leaves. U is further defined not to halt if its input is not a syntactically correct encoding of a Turing Machine. It is convenient to think of U as having an input tape, several work tapes, and an output tape; we remind the reader that this is a convenience which changes nothing, as mufti-tape machines are formally equivalent to single- tape machines. We call a string of the form p(M)w a program.. For fixed p(M), we refer to the various extensions of the encoding to full programs as instances of the encoding. (Note that p(M) _ p(M)a = the instance of p(M) with the empty string as input.) Note that U is a Turing Machine, and therefore has an encoding. Further, that encodin...