SEQUENTIAL CODES, LOSSLESS COMPRESSION OF INDIVIDUAL SEQUENCES, AND KOLMOGOROV COMPLEXITY

A general class of sequential codes for lossless compression of indivi dual sequences on a finite alphabet is defined, including many types o f codes that one would want to implement. The principal requirement fo r membership in the class is that the encoding and decoding operations be performable on a computer. The OPTA function for the class of code s is then considered, which is the function that assigns to each indiv idual sequence the infimum of the rates at which the sequence can be c ompressed oi er this class of sequential codes. Two results about the OPTA function are obtained: 1) it is shown that any sequential code in the class compresses some individual sequence at a rate strictly grea ter than the rate for that sequence given by the OPTA function; and 2) it is shown that the OPTA function takes a value strictly greater tha n that of the Kolmogorov complexity rate function for some individual sequences.