この文を書け

今日、2,3時間ほど自由な時間があったので、以前に読みかけて放置していた計算理論の本を
読みました。これが、面白い!
今日読んだのは、再帰定理に関する部分なのだけど、要するにこういうことだ。
そのプログラムの全文を出力するプログラムを書くことが出来る。
ちょっと考えてみると、例えばプログラムの内容が「ほげほげ」なら、それを出力するには
「『ほげほげ』を書け」と書き込まないといけない。
ということは、「『ほげほげ』を書け」がプログラムの内容なのだから、
「「『ほげほげ』を書け」を書け」と書き込まないといけない。。。。以下循環。
と、そのようなプログラムを書くことができなくなってしまう。論理的にそういうことは
プログラムできないのか?すなわち、
「この文を書け」
というプログラムは一見不可能にも見える。ところが、これをやってのけるのがコンピュータウィルスだ。


まさに、自分自身の複製を作ってあちこちに書き込むわけである。論理的に矛盾せずに、
自分自身を書く(もっというと自分自身のプログラムについて計算する)プログラムが可能であることを
主張するのが再帰定理とのことであった。
さて、どうやれば、自分自身のプログラムリストを出力するプログラムを書くことができるでしょう?
これは大変面白い数理的パズルだと思います。原理が面白かったので、実際に自分自身を出力する
プログラムをCで書いてみました。プログラミングに関しては素人なので、もっと工夫すると短いコードが
書けるのだと思いますが、、、もっとすっきりしたコードが書けたら是非教えてください。

#include “stdio.h”
#include “string.h”
int main(){
int i;char mprog[1000],*loc;
char prog[800]=” i=0;n loc=mprog;n while(*(prog+i)!=”){n if(*(prog+i)==’\\’){n *loc=’\\’;*(loc+1)=’\\’;loc=loc+2;n }else if(*(prog+i)==’\”‘){n *loc=’\\’;*(loc+1)=’\”‘;loc=loc+2;n }else if(*(prog+i)==’\%’){n *loc=’\\’;*(loc+1)=’\%’;loc=loc+2;n }else if(*(prog+i)==’\n’){n *loc=’\\’;*(loc+1)=’n’;loc=loc+2;n }else{n *loc=*(prog+i);loc=loc+1;n }n i++;n }n *loc=”;nprintf(“#include \”stdio.h\”\n#include \”string.h\”\nint main(){\n int i;char mprog[1000], *loc;\n char prog[800]=\”%s\”;\n%s\n”,mprog,prog);}n”;
i=0;
loc=mprog;
while(*(prog+i)!=”){
if(*(prog+i)==’\’){
*loc=’\’;*(loc+1)=’\’;loc=loc+2;
}else if(*(prog+i)=='”‘){
*loc=’\’;*(loc+1)='”‘;loc=loc+2;
}else if(*(prog+i)==’%’){
*loc=’\’;*(loc+1)=’%’;loc=loc+2;
}else if(*(prog+i)==’n’){
*loc=’\’;*(loc+1)=’n’;loc=loc+2;
}else{
*loc=*(prog+i);loc=loc+1;
}
i++;
}
*loc=”;
printf(“#include “stdio.h”n#include “string.h”nint main(){n int i;char mprog[1000], *loc;n char prog[800]=”%s”;n%sn”,mprog,prog);}

追記:
自分自身のプログラム全文を出力するプログラムのことを”quine”と呼ぶらしい。
各種言語で書いた、種々の”quine”が載っているページを見つけました。
http://www.nyx.net/~gthompso/quine.htm

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中