GUIGUI01​/memo29 のバックアップソース(No.3) :: OSASK計画

• 差分^[1] を表示
• 現在との差分^[2] を表示
• GUIGUI01/memo29^[3] へ行く。

* ぐいぐい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世代後の最終形態が得られるかもしれない。

* こめんと欄
#comment

• GUIGUI01/memo29 のバックアップ一覧^[6]
• GUIGUI01/memo29 のバックアップソース(No. All)
  • 1: 2009-02-03 (火) 13:33:24^[7]
  • 2: 2009-02-03 (火) 14:05:56^[8]
  • 3: 2009-02-03 (火) 18:39:22
  • 4: 2009-02-04 (水) 11:34:34^[9]
  • 5: 2009-02-04 (水) 11:34:34^[10]
  • 6: 2009-11-17 (火) 12:08:46^[11]
  • 現: 2024-01-08 (月) 12:58:42^[12] k-tan^[13]