> Also, what is the difference between the statements "no program can compress every string" and "not every string can be compressed by some program".

The first is true, and you can show this with the pidgeon hole principle. The second isn't true. The reason for this is that you can put different information in each program.

To use the example from recursive below:

> You could do it like this: If the first bit is a 0, remove it.

There's a program that'll work for half of the strings. For the other half, you could use the program "If the first bit is a 1, remove it.".

At most half of them.

You could do it like this: If the first bit is a 0, remove it.

It could never be more than half, by the pigeon hole principle.