title: What is the maximum theoretically possible compression rate?
body: <p>This is a theoretical question, so expect that many details here are not computable in practice or even in theory.</p>
  
  <p>Let's say I have a string <code>s</code> that I want to compress. The result should be a self-extracting binary (can be x86 assembler, but it can also be some other hypothetical Turing-complete low level language) which outputs <code>s</code>.</p>
  
  <p>Now, we can easily iterate through all possible such binaries and programs, ordered by size. Let <code>B_s</code> be the sub-list of these binaries who output <code>s</code> (of course <code>B_s</code> is uncomputable).</p>
  
  <p>As every set of positive integers must have a minimum, there must be a smallest program <code>b_min_s</code> in <code>B_s</code>.</p>
  
  <p>For what languages (i.e. set of strings) do we know something about the size of <code>b_min_s</code>? Maybe only an estimation. (I can construct some trivial examples where I can always even calculate <code>B_s</code> and also <code>b_min_s</code>, but I am interested in more interesting languages.)</p>