ページへ戻る

− Links

 印刷 

GUIGUI01​/memo29 のバックアップ差分(No.4) :: OSASK計画

osaskwiki:GUIGUI01/memo29 のバックアップ差分(No.4)
« Prev[4]  Next »[5]
3: 2009-02-03 (火) 18:39:22 ソース[6] 4: 2009-02-04 (水) 11:34:34 ソース[7]
Line 27: Line 27:
-ちなみにこのアイデアも[[design008]]の独自性の「僕にはソフトウェアでやりたいことがまだ他にもたくさんある」の中の一つだ。まあ他のより現実的なテーマのほうを優先しているから、これに取り掛かれる日はこないだろうけど。 -ちなみにこのアイデアも[[design008]]の独自性の「僕にはソフトウェアでやりたいことがまだ他にもたくさんある」の中の一つだ。まあ他のより現実的なテーマのほうを優先しているから、これに取り掛かれる日はこないだろうけど。
-またFPGAのデータだって結局は二進数の列で表現可能なので、同じくランダムプログラミングで究極的に最適な回路を探すことができるはずだと僕は信じている。たとえばx86互換CPUだって、いきなり100世代後の最終形態が得られるかもしれない。 -また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までの整数の中でラプ素数がどのくらいの割合で存在するか。それが機能密度ということなんじゃないだろうか。僕はそんな気がする。
 +--この評価方法が従来の「同じような動作をするプログラムを作ってサイズを比較する」よりもいいところは、それぞれの実行ファイル形式に得意不得意があって、容易に比較できない場合でも、この方法なら比較的平等に比較可能だから。
* こめんと欄 * こめんと欄
#comment #comment
« Prev[4]  Next »[5]
ページ別名: 未設定
ページ作成: k-tan
サイト管理: lina

Links list

(This host) = http://osask.net

  1. (This host)/modules/osaskwiki/index.php?cmd=backup&pgid=271&age=4&action=nowdiff
  2. (This host)/modules/osaskwiki/index.php?cmd=backup&pgid=271&age=4&action=source
  3. (This host)/modules/osaskwiki/271.html
  4. (This host)/modules/osaskwiki/index.php?cmd=backup&pgid=271&action=diff&age=3
  5. (This host)/modules/osaskwiki/index.php?cmd=backup&pgid=271&action=diff&age=5
  6. (This host)/modules/osaskwiki/?cmd=backup&pgid=271&action=source&age=3
  7. (This host)/modules/osaskwiki/?cmd=backup&pgid=271&action=source&age=4
  8. (This host)/modules/osaskwiki/index.php?cmd=backup&pgid=271
  9. (This host)/modules/osaskwiki/index.php?cmd=backup&action=diff&pgid=271&age=1
  10. (This host)/modules/osaskwiki/index.php?cmd=backup&action=diff&pgid=271&age=2
  11. (This host)/modules/osaskwiki/index.php?cmd=backup&action=diff&pgid=271&age=3
  12. (This host)/modules/osaskwiki/index.php?cmd=backup&action=diff&pgid=271&age=5
  13. (This host)/modules/osaskwiki/index.php?cmd=backup&action=diff&pgid=271&age=6
  14. (This host)/modules/osaskwiki/index.php?cmd=backup&action=diff&pgid=271&age=Cur
  15. (This host)/userinfo.php?uid=3