Among other problems, how do you know when you have found the shortest possible way of expressing something in ones and zeroes?

You don't. That's uncomputable in the general case, and in most nontrivial special cases as well. You can, however, put upper bounds on it.