自己出力プログラムと自己参照プログラム
自分自身を出力するプログラムを書いてみる事にする。 あたりまえだけど、プログラム全体を文字列とかリストにして、 プログラム中に埋め込むわけにはいかない。 でも全体は無理でも、 プログラム内の一部分だけなら文字列やリストにして利用することはできる。 そこで、プログラムを、 Aパート ... プログラムの一部分を、単に文字列とかリストにしたもの。 Bパート ... プログラム全体を出力する部分。 の2つに分けて考える。 Aパートは、Bパート(または、その一部分)をリテラルとして保持して、 Bパートがそれを利用して全体を出力するという役割分担になる。 Schemeの場合 簡単のために Schemeで考える(Lispでも動く)。 プログラムの構成は、大まかには、 (<Bパート> <Aパート>) みたいになる。 とりあえず、AパートはBパートそのものをリストにしていると考える。 するとAパート
計算できない問題・関数について
いくつかの問題 停止問題 プログラムを実行すると、 実行が終了して停止するか停止せずにいつまでも実行を続けるかの、 どちらかになる。 そこで、与えられたプログラムが停止するか、 いつまでも停止しないかを判定する、 という問題(プログラムの「停止問題」という)を考える。 (この問題をちゃんとした問題として扱うには、 プログラムがどう実行されるのかが 正確に(処理系依存とかのあいまいさ無しに)定義されている必要がある。 だから普通は、チューリングマシンみたいな できるだけ単純な道具立てを使って話をする。 でも、ここでは細かい事にはこだわらず、 「適当にどうにか定義してある」事にしておく。) 停止問題を解くプログラムを作りたいとする。 これは、コンパイラと比較すると判りやすいかもしれない。 コンパイラはプログラム(のソース)を受けとり、 実行コードを出力する。 停止問題を解くプログラムは、 プロ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
