Compression of random binary data

[Christian Gollwitzer]

Am 23.10.17 um 12:13 schrieb Marko Rauhamaa:
> Thomas Jollans <tjol at tjol.eu>:
> 
>> On 2017-10-23 11:32, danceswithnumbers at gmail.com wrote:
>>> According to this website. This is an uncompressable stream.
>>>
>>> https://en.m.wikipedia.org/wiki/Incompressible_string
>>>
>>> 1234999988884321
>>
>> No, it's not. According to that article, that string is incompressible
>> by a particular algorithm. I can see no more general claims.
> 
> Here's a compression algorithm that manages to compress that string into
> a 0-bit string:
> 
>   * If the original string is 1234999988884321 (whatever that means),
>     return the empty bit string.
> 
>   * Otherwise, prepend a don't-care bit to the original string and return
>     the result of the concatenation.
> 

...and that's why there is the "Kolmogorov complexity". You need to 
append the decompression program to the data to show how much you really 
saved, which will turn out to be nothing compared to the "trivial 
decompressor"

	print "1234999988884321"

Christian