We propose and develop rate-distortion theory in the Kolmogorov
complexity setting. This gives the ultimate limits of lossy compression of
individual data objects, taking all effective regularities
of the data into account.