停止性問題を読んでも、意味が分からなかった Lisper のために、Lisp のコードで停止性を解説してみる。使用する Lisp としては、Scheme、Common Lisp、Emacs Lisp を検討したが、Emacs Lisp が一番よいと分かったので、Emacs Lisp を使う。 名前を使った概略 halt-p というプログラムは、入力としてプログラム p とデータ d を取る。Lisp なので、p も d も S 式である。halt-p は、p と d を検査し、p に d を与えたときに、停止するか否かを有限時間で判断する。停止するなら t、停止しないなら nil を返す。 machine というプログラムは、入力 x に対して以下のような動作をする。 (halt-p x x) が t なら、(machine x) を呼び出すことで同じ作業を繰り返す つまり、x に x 自