Browse Prior Art Database

Two Theorems on Time Bounded Kolmogorov-Chaitin Complexity Disclosure Number: IPCOM000147861D
Original Publication Date: 1985-Nov-30
Included in the Prior Art Database: 2007-Mar-28
Document File: 5 page(s) / 252K

Publishing Venue

Software Patent Institute

Related People

Schweizer, David: AUTHOR [+3]


David Schweizer and Kaser Abu-Mostafa

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 35% of the total text.

Page 1 of 5

Two Theorems on Time Bounded Kolmogorov-Chaitin Complexity

David Schweizer and Kaser Abu-Mostafa

Department of Computer Science

California Institute of Technology

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 1985

[This page contains 1 picture or other non-text object]

Page 2 of 5

Two Theorems on Time Bounded Kolmogorov-Chaitin Complexity David Schweizer and Yaser Abu-Mostafa

Computer Science 256-80

California Institute of Technology
Pasadena, CA 91125


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

Notation and Definitions

We will be working over the input alphabet C = (0,
I), and we write # for the blank symbol.

We write s to denote a string in X* and X to denote the empty string. If s E Cn (i.e. s is of length
n) we write 1st = n.

We take U to be a particular implementation of the Universal Turing Machine with input

alphabet C and states {qo,ql,. . . ,qK), where qo is the start state, and ql is the halt state. U operates on encoding5 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 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 multi-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)X = 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 encoding can be incor...