アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

264

8

章 不可能なプログラム

プログラムが決して終了しないときだけです。すなわち、

#evaluate

は結果を返さずに、永久にルー

プする必要があるのです。

おそらく実際には、ruby does_it_say_no.rb < does_it_say_no.rbは永久にループすることな

く、ホストマシンの有限なメモリを使い尽くして、rubyをクラッシュさせるでしょう

†

。これは

プログラムの外部にあるリソース制約であって、プログラム自体の性質ではありません。必要

なだけメモリを追加し続けることによって、原理上、計算を無限に実行することができます。

停止しないプログラムをRuby で書くのに、これは必要以上に複雑なやり方に見えるかもしれませ

ん。

while true do end

とすれば、同じことがずっと簡単にできるためです。

ところが、does_it_say_no.rbの振る舞いを考えることによって、システムの具体的な機能とは無関

係に、停止しないプログラムが万能性にとって避けられない結果であることがわかりました。ここでの

議論は万能性以外のRubyの能力に依存していないため、同じ考え方をチューリングマシンやラムダ計

算、その他の万能システムにも当てはめることができます。自分自身を評価できるほど強力な言語を

使って仕事をしているなら、たとえそれ以外の言語能力について知らなくても、

#evaluate

と同等な

ものを使うことで、決して停止しないプログラムを構築できるということです。

具体的に言うと、停止しないプロ ...