KEMURIの最適化手法の検討

KEMURIの最適化手法を検討してみたいなと考えていたので、とりあえずどの文字をXORすれば目的の文字になるか?の一覧をグラフで可視化するところから始めてみました。この土日に考えていたことのアウトラインを紹介します。

XORの三角形

KEMURIでは"Hello, world!"に対する排他的論理和(XOR)の有限回の適用だけで、任意のプリンタブルなASCII文字を生成できます。排他的論理和の性質として、

A^B = C ⇒ A^C = B

というのがあるので、これを

という三角形で表現することを考えてみました。これは、「任意の頂点の記号から、別の頂点の記号を生成するには、前後の記号同士を結ぶ線分の対にある頂点の記号でXORをとればよい」という意味になります。また、この三角形は二つの記号が決まれば一意に定まります。

三角形の結合

KEMURIの文字生成のルールは、この三角形の有限集合となり、複数のXOR演算は三角形のいずれかの頂点を共有すします。たとえば、a^b^c = d は、

のように。

また、三角形は頂点同士を共有し合うことはありますが、辺を共有し合うことはありません。たとえば、上の図で c^d=e だからといって、bc間に辺を加え、空丸をeにする(あるいは他に頂点eを新しく作る)ことはできず、bceの三角形を独立して書き出さなければいけなくなります。でないと、最初に示したこの三角形の性質(=排他的論理和の性質)が維持できません。なので、頂点の共有の繰り返しにより、どこかに閉ループができたとしてもそれは四角形以上の多角形になります。

グラフの使い方

いま考えているイメージでは、このグラフができあがれば、任意の文字を生成するために必要な手続きが簡単に見つかるかずです。ある文字を作ろうとしたら、そこに近い初期文字("Hello, world!"のどれかひとつ)を決めて、最短パスを通る演算を施してあげればよいのです。

このグラフ(赤い頂点は初期文字)からは、

a = (H^e)^(l^,) = H^e^l^,

であることが分かります*1。これだけでは、あまりグラフ化するメリットが見えませんが、パスの途中に後で生成すべき文字がある場合は、それをduplicationによって複製しておくなどして最適化ができるかもしれません。また、"Hello, world!"を分解するコストを抑えたパスを見つけられる可能性もあります。KEMURIプログラムでの計算のほとんどは"Hello, world!"の分解であるといえますので、その効果は非常に大きいと思われます。

課題

排他的論理和は可換なので、交換法則が成り立ちます。なので、上の二つ目の図の場合、bとcを入れ替えることもできます。そのため、全規則のグラフを出来る限り連結しようとすると、その形は一意ではなく、膨大なパターンができます。とりあえず、優先順位をつけて作ってみようと思いますが、結構な作業になりそうです。

これって、GRINEdit使ってできないかなぁ。「これPla?」ならぬ「これGRI?」てところでしょうか。

*1:この規則は例であって、実際のものとは異なります