4 ms·

I don't understand how omega can be be incompressible. Compression, from the information theory perspective, allows me to send the string Digits #10000 to #1

by ced 15y ago

I don't understand how omega can be be incompressible. Compression, from the information theory perspective, allows me to send the string Digits #10000 to #100000 of the decimal representation of omega. which any competent human could "decompress" into the corresponding digit sequence (inasmuch as it's computable)

gjm11 15y ago
The bit in parentheses is why your argument doesn't show that omega isn't incompressible: it very emphatically isn't computable.
- ced 15y ago
  Yeah, but compression is all about communicating information. If I don't have the information that I want to communicate, it's weird to claim that it's incompressible. Are the lost works of Shakespeare incompressible because we can't know what they contained? That's a meaningless statement to me. Besides, some of the bits are known, and thus, they are clearly compressible.
andrewcooke 15y ago
you're right that the isolated assertion is not at all sensible, but the wider context is that you are considering all possible algorithms and the sequences that they generate, and looking for some way of compressing as many of those as possible. you should read one of chaitin's books for a better idea (they're generally "accessible", but at some point you just give up trying to make complete sense of it all...) in other words, you are choosing your compression for one particular algorithm (the one that generates omega - you could go further and say it's 1 for omega and 0 for everything else). this is a common problem in arguments about compressibility (if we're only trying to compress beethoven's ninth then i can do that in one bit too) - you have to be talking in an "average" or statistical sense for things to be useful. having said that, the exact nature of what they're saying is still not clear to me (ie it's not clear exactly how the details of the argument work out, or how this eventually ties back to http://en.wikipedia.org/wiki/Shannons_source_coding_theorem http://en.wikipedia.org/wiki/Shannons_source_coding_theorem).
- andrewcooke 15y ago
  i think another replier here may also be correct that chaitin, in particular, includes the length of the decompression code. unfortunately i can't delete my answer for some reason (too old i guess).
  - ced 15y ago
    No, I think that your answer made the most sense. The length of the decompression code is a constant, whereas Omega has an infinity of digits, so it doesn't matter.
Natsu 15y ago
That's not quite fair because you have to include the size of your decompression routine with the description. Also, there's the whole "not computable" part.
khafra 15y ago
When he says "compress," he means "losslessly." A compression which doesn't actually allow you to compute any of the original data is pretty lossy.

by ced 15y ago

gjm11 15y ago

The bit in parentheses is why your argument doesn't show that omega isn't incompressible: it very emphatically isn't computable.

ced 15y ago
Yeah, but compression is all about communicating information. If I don't have the information that I want to communicate, it's weird to claim that it's incompressible. Are the lost works of Shakespeare incompressible because we can't know what they contained? That's a meaningless statement to me. Besides, some of the bits are known, and thus, they are clearly compressible.

andrewcooke 15y ago

you're right that the isolated assertion is not at all sensible, but the wider context is that you are considering all possible algorithms and the sequences that they generate, and looking for some way of compressing as many of those as possible. you should read one of chaitin's books for a better idea (they're generally "accessible", but at some point you just give up trying to make complete sense of it all...) in other words, you are choosing your compression for one particular algorithm (the one that generates omega - you could go further and say it's 1 for omega and 0 for everything else). this is a common problem in arguments about compressibility (if we're only trying to compress beethoven's ninth then i can do that in one bit too) - you have to be talking in an "average" or statistical sense for things to be useful. having said that, the exact nature of what they're saying is still not clear to me (ie it's not clear exactly how the details of the argument work out, or how this eventually ties back to http://en.wikipedia.org/wiki/Shannons_source_coding_theorem http://en.wikipedia.org/wiki/Shannons_source_coding_theorem).

andrewcooke 15y ago
i think another replier here may also be correct that chaitin, in particular, includes the length of the decompression code. unfortunately i can't delete my answer for some reason (too old i guess).
- ced 15y ago
  No, I think that your answer made the most sense. The length of the decompression code is a constant, whereas Omega has an infinity of digits, so it doesn't matter.

Natsu 15y ago

That's not quite fair because you have to include the size of your decompression routine with the description. Also, there's the whole "not computable" part.

khafra 15y ago

When he says "compress," he means "losslessly." A compression which doesn't actually allow you to compute any of the original data is pretty lossy.