問題4-15

｢4.1.5 プログラムとしてのデータ｣では、これまでに説明されてきた評価器は万能機械であるという視点について述べられています。プログラムそのものも、評価器にとってはデータなのだということで、非常に興味深く読み進めました。注釈19には、Turing機械についても触れられていますが、このあたりについては体系だって学んだことがないので、機会を作って勉強してみたいと思っています。
問題4-15は、Turingの停止問題に関するトピックが取り上げられています。｢プログラマの数学｣や｢やさしいコンピュータ科学｣に、計算不可能な問題や停止問題について述べられていたことを思い出したので、それを再読しました。
もし、(try try)が停止するならば、(halts? try try)は真を返すはずですが、そうすると、tryの中では(run-forever)されてしまい無限ループに陥ってしまいます。また、(try try)が停止しないのであれば、(halts? try try)はfalseになるはずですが、tryの中では'haltsが返され処理は停止します。この矛盾が生じたそもそもの原因は、halts?が書けると仮定したことなので、実際にはhalts?を書くことができないということになります。
背理法を使った証明は、読むことも書くことも、自分は全然慣れていないということを痛感した問題でした。