プログラムつながり

どこだか忘れてしまったが、どこかで見たパラドックスというか何というか。

「いかなる入力に対しても停止する」ことが証明できるようなチューリングマシンの全体を H とする。（論理体系としては、たとえば一階述語論理を使うことにしよう。）
まず、H は帰納的に可算である。実際、以下のアルゴリズムは H のすべての元を列挙する：

n = 0 とする。

n が何らかの証明の符号化になっていて、かつ、その証明が正しく、かつ、その証明の結論が「チューリングマシン M は必ず停止する」という命題になっているならば、M を出力する。（証明チェックは決定可能だから、このステップは停止する。）

n に 1 を加えて 2. に戻る。

一方で、H は帰納的に可算ではないことが以下のようにして示せる。もし H が帰納的に可算ならば、H を列挙するアルゴリズム A が存在する。ここで、入力 n に対して

A を実行し、H の n 番目の元 M を得る。

M に n を入力したときの出力に 1 を足したものを出力する。

という動作をするチューリングマシン P を考える。H の定義から M は必ず停止するので、どんな n を入力しても P は停止する。にも拘らず、P は H に含まれていない。なぜなら、どんな n に対しても、P と H の n 番目の元とでは n を入力したときの出力が異なるからである。このことは H の定義に矛盾する。