"Similarly, if you start with a 10 kilobyte text file, and 7zip compresses it down to 2 kilobytes, no amount of time spent trying to further compress the file using other compression programs will ever get that file down to 1 byte." (Emphasis added.)
This claim seems too strong. Do you mean that an arbitrary compression algorithm is unlikely to compress the file to one byte?
Taking what's written at face value, if I assume that every compression I apply monotonically decreases the size of the file, then I need only find a large enough sequence of compressions and compose them to compress my file to one byte. This is of course silly, since the composition is just a huge highly specialized compression program optimized for this instance, but I can spend enough time to make it happen.
The second comment is fair. I think when I first read this, I ignored the bit about 7zip and understood the sentence as claiming "no Turing machine takes an input smaller than one byte and prints out a 10kb file".
Aren't programs for Turing machines specified as marks on an infinite tape?
I was interpreting 100-bit program as one where up to 100 cells on the tape have marks in them (and there's only one kind of mark, so a cell can only have a mark or not). Maybe I've got the wrong picture though. I haven't studied Turing machines in much depth.
Yes. That includes both the case where the length is specified outside the program, and the case where we use a prefix-free encoding. Actually I'm not sure what you're asking here - why wouldn't prepending 0 to a program change its behavior in whatever Universal Turing Machine you used? If the first bit always has to be 1, it might as well be omitted.
"Similarly, if you start with a 10 kilobyte text file, and 7zip compresses it down to 2 kilobytes, no amount of time spent trying to further compress the file using other compression programs will ever get that file down to 1 byte." (Emphasis added.)
This claim seems too strong. Do you mean that an arbitrary compression algorithm is unlikely to compress the file to one byte?
Taking what's written at face value, if I assume that every compression I apply monotonically decreases the size of the file, then I need only find a large enough sequence of compressions and compose them to compress my file to one byte. This is of course silly, since the composition is just a huge highly specialized compression program optimized for this instance, but I can spend enough time to make it happen.
I only assumed the sequence was monotonic.
The second comment is fair. I think when I first read this, I ignored the bit about 7zip and understood the sentence as claiming "no Turing machine takes an input smaller than one byte and prints out a 10kb file".
No individual compressor can monotonically decrease file sizes.
And we count the string of .rar.7z.zip.rar... in your filename into the total size of your file.
Not 2^100?
Aren't programs for Turing machines specified as marks on an infinite tape?
I was interpreting 100-bit program as one where up to 100 cells on the tape have marks in them (and there's only one kind of mark, so a cell can only have a mark or not). Maybe I've got the wrong picture though. I haven't studied Turing machines in much depth.
Yes. That includes both the case where the length is specified outside the program, and the case where we use a prefix-free encoding. Actually I'm not sure what you're asking here - why wouldn't prepending 0 to a program change its behavior in whatever Universal Turing Machine you used? If the first bit always has to be 1, it might as well be omitted.
Is there a difference between any particular 99-bit program and a 100-bit program with a 0 as the first bit?
2^100 + 2^99 + 2^98... + 1 = 2^101 - 1.