On the OPTA function for lossless compression of individual sequences via recursive sequential codes
John C. Kieffer, En‐hui Yang · 2002
The OPTA (optimum performance theoretically attainable) function for lossless compression of individual sequences is investigated. This function gives the optimum asymptotic rate in bits per source symbol at which each individual sequence can be losslessly compressed via sequential codes whose encoding and decoding operations can be described in terms of recursive functions. Two results are described: (1) no sequential code yields asymptotic rate equal to that of the OPTA function for every individual sequence, and (2) the OPTA function cannot be expressed in terms of Kolmogorov complexity.>