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

274

8

章 不可能なプログラム

puts output

でもなぜ、このプログラムは必ず停止するのでしょうか。簡単な構文上の理由によるものでないのは

間違いありません。解説してみると「

IO#read

は必ず

String

を返し、

String#length

は必ず非負

の

Integer

を返します。そして、非負の

Integer

に対して

-(1)

を繰り返すと、必ず最終的には

#zero?

メソッドが

true

を返すオブジェクトを生成するためです」となります。この推論の連鎖はも

ろく、小さな変更に対して非常に敏感です。もしループ内の

n = n - 1

が

n = n - 2

に代わると、

プログラムは入力の長さが偶数のときにのみ停止します。停止性チェッカーがこのようなRubyと数に

関する事実をすべて知っているのはもちろんのこと、この種のプログラムについて正確な判定を下すた

めに、どのように事実をつなぎ合わせればよいかを知っているとしたら、それはかなり巨大で複雑なも

のになってしまうでしょう。

根本的な難しさは、プログラムを実際に動かすことなく、プログラムがやることを予測しよう

としているところにあります。

#evaluate

を使ってプログラムを実行することで、プログラ

ムが停止するかどうかを確かめたくなりますが、それだとまずいことが起こります。プログラ

ムが停止しなかった場合、

#evaluate

は永久に実行し続け、どれだけ待っても

#halts?

か

ら答えが返らないためです。信頼できる停止性検出アルゴリズムのためには、単にプログラ

ムを ...