（勉強中）コルモゴロフ複雑性って何ですか？
お題
間違っていたら、きっと優しい人が指摘してくれると思う。
この記事を見た人が真に受けないようにお願いします。
よく分からないので、Rubyをベースに考えます。
かろうじて触ったことがあって、"[言語名] ゴルフ"でググってそれっぽいのが出てきたので･･･（※出来るとは言っていない）
とりあえず、以下のルールにします。
① Wikipedia記事では2進数ベースでしたが、16進数ベースにする。
② 出力された文字を、そのASCIIコードの16進数表記と同一視する。
③ プログラム本体も、そのASCIIコードの16進数表記と同一視する。
④ 与えられた文字列を出力する最短のコードを探す。
（その16進表記の「桁数」を K(x) と呼ぶ）
⑤ 制御記号とか難しいことを言わない。
⑥ 議論上ヤバそうだったら、16進数→2進数に直して議論を続行する。
この場合、"1"（0x31）を出力する最短のコードは
p 1
のはずです。"p 1"のコードは 0x702031 なので、
K("1") = K(0x31) = "p 1"の桁数 = 0x702031の桁数 = 6
となるのだと思います。
""とかについては、上手く解釈してください。これを付けないと自分で何を書いているのか分からなくなりそうだったんです。
目標となる文字列をそのまま入力に入れる方式の場合、pとかputsとか$><<とかを使えばいいので、ほぼ固定になります。
例えば、"a"（0x61）を出力する場合は、たぶん
$><<"a"
ですが、この場合の16進表記は、0x243e3c3c226122 です。その中の243e3c3c22__22の12桁分はどんな文字列相手でも（たぶん）変わりません。可能性としてあるのは、それよりも短くなるパターンのみのはずです。
したがって、
K("x") ≦ "x"の桁数 + 12
という式が成り立ちます。（Wikipedia記事の自明な上限の部分です）
※相手が数字の場合は、pメソッド（0x7020）を使えるので、
K("x") ≦ "x"の桁数 + 4
となります。
出力したい文字列によっては、K(x)の値が大幅に小さくなる場合があります。
例えば、"1000000000"（0x31303030303030303030）の場合、
p 10**9 （0x702031302a2a39）
と出来るので、
K("1000000000") = K(0x31303030303030303030) ≦ 14
であることが分かります。
※p 1e9 の出力は、1000000000.0 なので、今回は除くことにします。
ほかにも、
"nil"（0x6e696c）の場合は、
p p （0x702070）
という手段があるため、
K("nil") = K(0x6e696c) ≦ 6
となります。というか、これよりも短い出力法があるようには思えない（主観）ので、
K("nil") = K(0x6e696c) = 6
となるのだと思われます。
普通、出力したい文字列が長くなるほどK(x)の値も大きくなるのですが、たまにこのような短縮方法があったりするため、油断は出来ません。
さて、ある程度以上の長さであれば、様々なプログラムを試すことができるようになるはずです。もしかすると、K(x)の値にはある程度のところで頭打ちになる、つまり上記の「たまに」は実は「常に」だったりすることは無いのでしょうか？
ということで、Wikipediaの記事は「圧縮不可能な文字列」の話になります。
K(x) ≧ "x"の桁数
のとき、「圧縮不可能」と呼んでいるようです。
上の例だと、"1000000000"（0x31303030303030303030 ← 20桁）のときは圧縮可能で、"nil"（0x6e696c ← 6桁）のときには（たぶん）惜しくも圧縮不可能と呼ばれることになるはずです。
"x"の（16進コードの）桁数をnとします。このとき、0桁からn桁までのプログラムの総数を考えてみましょう。（ここでは動かないものも含めます）
例：n = 2 のとき（※1文字なのでプログラムとしては･･･）
"x"の16進コードは、0x0～0xFF までの通りあります。
同じように、nの一般例は、0x0～0xFFFF...Fの通りとなります。
それをそのままプログラム（の16進コード）だと思ってしまえばいいので、プログラムの総数は個と言えるでしょう。0桁からn-1桁までのプログラムの総数の場合は、
個です。
一方、"x"の16進コードが、ちょうどn桁になるものは何通りあるでしょうか？
例：n=2のとき
対象は、0x10～0xFF まであるので、通りあります。
一般例では、0x10...0～0xFF...F まであるので、通りとなります。･･･あっているでしょうか･･･。
ここから言えることは、
0桁～n-1桁のプログラムの総数 ＜ ちょうどn桁になる"x"の総数
ということです。「圧縮不可能」の定義には、K(x) = "x"の桁数 の場合も含むのでした。
したがって、ちょうどn桁になる"x"の中には必ず圧縮不可能なものが含まれるということが分かります。
別な見方をすると、K(x)の値は頭打ちにはならないということが言えます。
一旦ここまで
