GUIGUI01​/memo29

ぐいぐい01に関するメモ-29

• (by K, 2009.02.03)
• メモのうち重要な部分をそのうちまとめてまともなページを作る

(41) くだらない夢

• .g01ではソースファイルはともかくとして、生成されるバイナリファイルが驚異的に小さいわけだけど、これは逆に言うと機能密度が高いとも言える。そうなると、僕が幼いときに思いついた（というかこんなものは誰でも考えるくだらないことだけど）ランダムプログラミングというものがほんの少しだけ「可能」へ近づく。結局.g01程度ではまだまだ到底現実的ではないんだけど。
• ランダムプログラミングという言葉は今この場で思いついただけなので、本当はもっと違った言い方があるのかもしれない。もし知っていたらこめんと欄で教えてほしい。
• ええとたとえばシグネチャを除いて4バイトのプログラムというものを考えよう（＝つまりシグネチャ込みなら合計6バイト）。これは、

  47 01 ?? ?? ?? ??

• の形式で必ず表せるはずだ。そして?? ?? ?? ??の部分を乱数で勝手に決めてみて、もしそのプログラムがきちんと動いたら、その6バイトはプログラムとして成立する。まあ実際にはうまく動くのはごくごくわずかで99.99%以上がプログラムとしてはまともに動かないと思う。
• こうして乱数を大量に発生させるか、もしくは（たぶんこのほうが効率的だけど）????????を00000000～ffffffffまで総当りで全部やれば、6バイトで記述可能なすべてのプログラムを「発見」できるはずだ。これを??の数が1バイトから1KBまでやるとすれば、まあ量子コンピュータを使わない限り宇宙の終焉までにこの作業が終わることは多分ないけど、でも1026バイト以下で記述可能な全ての.g01プログラムを得られることになる。
• そしてその中から希望の動作をするプログラムのうちで最短のものを探せば、人間は全くプログラミングの知識が無くても、最も最適化されたプログラムを得ることができるというわけである。どんな天才的なプログラマが挑んでも、この結果に勝つことはできない（引き分けにならできるけど）。・・・これはサイズ最適化しかできていないと思うかもしれないがそうではない。目的の動作をするプログラムは、検索するプログラムサイズに幅を持たせれば多分複数見つかるだろうから、その中でもっとも動作が高速なものを見つければ、速度最適化もできるわけだ。
• Linuxやwin32のように、容易にプログラムが長くなる実行ファイル形式（というかAPIのせい？）だと、この1KB程度では動作可能なプログラムがほとんど見つからないため、2KBや3KBくらいまで探さないと.g01の1KB相当の結果すら得られない。これは検索時間が自乗、三乗倍かかるということであって、ただでさえ途方も無いのに、もっと現実性が失われる。
• この目的のためには、ランダムもしくは総当りによって何らかの圧縮ファイルを生成し、それを展開してみて、展開に成功したら、それがプログラムとして成立するかをチェックするほうがいいのかもしれない。というのは、圧縮後のほうが小さいから。また圧縮にせよ非圧縮にせよ、あるビット列が続いたらそれはCPUの命令として無効命令だからそれ以降をどんなビット列にしても意味ないとか、もしくは圧縮データ列として展開不能になるなど、そういうことがありうると思うので、総当りの場合には枝狩りが可能だと思う。これで刈り取れる枝はかなりの量に上ると思うけど、それでもやっぱり検索空間はあまりに広すぎて、結局量子コンピュータが無い限り非現実的だろう。

• http://k.osask.jp/wiki/?boyaki_a/00135 の(2)に書いた部分の最適化をこのアルゴリズムでやると究極だけど、でもやっぱり計算量が多すぎて現実的ではないだろう。

• ちなみに数年先にやりたいと思っている.g02では更に機能密度が上がるので（といってもせいぜい数%くらいの差しかないだろうけど）、さらにランダムプログラミング向きかもしれない。

• この記事をOsaskWikiに書くべきか、もし書くとしたらGUIGUI01/memoがいいのか、それともdesignのほうなのか、それともくだらないからosaskdotのほうに書くべきか、実は結構悩んだ（笑）。

• （追記）
• これは普通の最適プログラムの求め方とは全く違う。普通は目的どおり動くプログラムをまず与えて、そこから不要な部分を削ったり、ループアンロールしたり、ある部分をごっそりと交換するなど、いわゆる局所最適化を可能な限り施して、完了とする。これは現実的な時間内で最適化が終わる。
• でも僕とかは（たぶんI.Tak.さんも）この程度の最適化では到底満足できない。結局普通のアルゴリズムで出てくるプログラムなんてガラクタ級でしかない。僕たちが自分でアセンブラで書いたものには全く追いつかない。僕たちが納得できるのは、本当に全ての可能性を全探索して「これが最善です」といえるものだけなのだ。こういうことをしてくれるのなら、僕だってコンピュータに頭を下げていい。というか僕らはアセンブラで「本気で」プログラムを書くとき、こういう全探索を（相当に雑な枝狩りをやりつつ）頭の中でやっている気がする。だからものすごく疲れる。
• なんというか人間は、自分のプログラムスキルに応じて最適化ということを考えるのかもしれない。やっぱり自分の能力と同等かそれ以上のものを出してくれないと、最適化の意味がない。だから僕などはあまりに現実性が無いと知りつつも、こんなランダムプログラミングみたいなことを考えずにはいられない。そしてもしプログラムをする時間がたくさんあれば、自分の思いつく限りの枝狩りアルゴリズムを総動員して、現状では何バイトまでなら現実的な時間内に全探索できるものなのか試してみたいとまで思う。結局役に立つサイズでは使用不可能なアルゴリズムだと分かっているのに、それでも一度はやってみたいと思ってしまうのだ。それほど僕はこのアルゴリズムを夢見ないではいられない。
• もし任意の言語で適当にプログラムを作りさえすれば、あとは自動的にコンピュータがそれと全く同じ動作の最適なプログラムを全探索で現実的な時間内に（1ヶ月くらいなら待てる）見つけてくれるというのなら、僕はすぐにアセンブラの知識なんて全部忘れてもいいと本気で思っている。それでjavaでもrubyでも、その他どんな高級言語でもいいけど、そういうものに喜んで乗り換えるだろう。
• ちなみにこの最適化プログラムができたら、真っ先にやるべきは最適化プログラムの最適化だ。
• ちなみにこのアイデアもdesign008の独自性の「僕にはソフトウェアでやりたいことがまだ他にもたくさんある」の中の一つだ。まあ他のより現実的なテーマのほうを優先しているから、これに取り掛かれる日はこないだろうけど。
• またFPGAのデータだって結局は二進数の列で表現可能なので、同じくランダムプログラミングで究極的に最適な回路を探すことができるはずだと僕は信じている。たとえばx86互換CPUだって、いきなり100世代後の最終形態が得られるかもしれない。

• （2009.02.04追記）
• 実は全ての正常に動作する.g01ファイルに対して以下のことが必ず成立する。

  ファイルの末尾に C3 ?? ?? ?? ?? ?? ... を追加しても動作は全く変わらない。?? ?? ...は任意のバイト列。
  （註）メモリの消費量などは変わるかもしれないが、この追加によって悪くなることはあってもよくなることはない。

• もしよかったら適当なプログラムで試してみてほしい。バイナリエディタで上記のバイト列を足しても、ファイルサイズが変わる程度でそのほかに違いを見出すことはできないだろう。
• 一方、x86はリトルエンディアンを採用しているアーキテクチャなので、0x12345678をメモリに書き込むと、 78 56 34 12 となる。これにより、.g01プログラム 47 01 78 56 34 12 は整数0x12345678すなわち305419896に対応付けることもできるだろう。
• さて、それでたとえば0xC3ABCDという整数に対応するのは 47 01 CD AB C3 というプログラムになるのだが、単なる整数であるこの数値が24bit整数であるという保証はどこにもなくもしかしたら32bit整数かもしれない。そうすると 47 01 CD AB C3 00 が対応するプログラムになるはずだ。いやいや64bitかもしれない。そしたら 47 01 CD AB C3 00 00 00 00 00 が対応するプログラムということになる。こういう不確定さはこの後の議論では厄介な問題になる（というか一つの整数を全て尽くすだけで全ての正常に動作する.g01ファイルを全探索したいのだ）。
• しかしもしこの 47 01 CD AB というプログラムが正常に動作するプログラムであれば、C3がついていても、またさらに余計な00がいくつ付いていようと、正常なプログラムに違いはないはずだし、動作も同じになるはずだ。そうであれば整数0xC3ABCDは一番短い形式である 47 01 CD AB を表すことにしたらいいと思う。ちなみにこのプログラムは正常に動作しないので、整数0xC3ABCDは.g01ランダムプログラムとしては成立していない。
• このルールにすると.g01に対応付けられるすべての整数の最上位は必ずC3である。だからそれ以外の数値を探索する必要はない。また単に数値を大きくしていくだけで、全てのサイズの.g01ファイルの可能性を探索できることになる。
• 次に言葉を定義しよう。整数はたくさんあるが、その中で.g01ランダムプログラムとして正常に動作するプログラムに対応するものを、.g01ラプ数ということにしよう。たとえば 47 01 00 は正常に動作するプログラムだから（ただ正常終了するだけ）、0xc300は.g01ラプ数である。同様に0xc39000や0xc3c300も同じ実行結果を返す.g01ラプ数である。さてこのように同じアルゴリズムで同じ実行結果を返す.g01ラプ数は無数にあるわけだが、その中で一番小さいものを.g01ラプ素数ということにしよう。一番小さいものはもちろんプログラムサイズも一番小さい。そして整数0xc300は.g01ラプ素数である。いやそれどころか最初の.g01ラプ素数でもある。
• さて僕たちが全探索で見つけたいと思っているのもまさにこの.g01ラプ素数だけである。全探索していればいろんなアルゴリズムでいろんなバイト数の"hello, world\n"出力プログラムが現れると思うが、アルゴリズムが同じで中にNOPがいくつか入っただけの違いとか、プログラムの末尾に使わないバイト列が付いているようなそういう瑣末で雑多な違いに煩わされたくはないのだ。しかしそれは.g01ラプ素数ではないから、もし素数しか見なくていいのなら、こういうことに煩わされることはなくなる。
• さてそれで、今まで僕は機能密度という言葉をかなりいい加減に使ってきたけれど、このラプ素数という概念を使えばもう少し厳密に定義できるような気がする。たとえば256^65536までの整数の中でラプ素数がどのくらいの割合で存在するか。それが機能密度ということなんじゃないだろうか。僕はそんな気がする。
  • この評価方法が従来の「同じような動作をするプログラムを作ってサイズを比較する」よりもいいところは、それぞれの実行ファイル形式やAPIに得意不得意があって容易に比較できない場合でも、この方法なら比較的平等に比較可能だから。

こめんと欄

• IRCでの話から： これってこれみたいな話だよね。 http://ja.wikipedia.org/wiki/無限の猿定理 僕もそう思う。 -- K 2009-02-04 (水) 22:22:50
• ただしちょっと違うところもあって、それはこのページでは「ランダム」だけで話をしているために、「無限の」時間をかければ「ほとんど確実に」そうなる、というレベルで話が終わっていますが、僕は整数0から（というか0xc300から）総当たりで全検索するのを基本にすえているので、必ず有限の時間で解は見つかります（その解が確実に存在して、そのバイト数の上界が決まっていれば）。というより、何番目以内に見つかるか、つまり見つける時間の上限すら予言可能です。 -- K 2009-02-04 (水) 22:36:24
• まあどっちにしても実用的な時間で終わらないこと変わりはないので、そんなに偉そうに言うことじゃないですが。 -- K 2009-02-04 (水) 22:43:58