クイズ

先ほど、自転車の前輪がパンクしました。なお、先週は後輪がパンクしています。それはさておき。
とある方法で、自然数の濃度 = 実数の濃度を証明しました。以下に記述するので、矛盾点を指摘してください。

自然数の濃度をX, 実数の濃度をYとおく。
チューリング等価なプログラム全体の集合の濃度をZとおく。この時、Y <= Z <= Xを証明する。
まず、Y <= Zは比較的自明である。例えば、チューリング等価ではない言語として、x++とx--しか 存在しない言語を考えると、この言語によって記述されるプログラム全体の濃度は、明らかにYより大きい。というのは、ある命令の次に来る可能性のある命令が2種類、そこでプログラムが終了する可能性が1種類なので、少なくとも2 * 2 * 2 * ....(加算無限個続く)個のプログラムが存在する。よって、この簡単な言語よりも記述力の高い通常のプログラム言語によって記述されるプログラム全体の集合の濃度は、Yより大きい。
次に、Z <= Xを示す。チューリングマシンの停止問題は非決定的であるが、nステップで停止するかどうかの判定は決定的である。実際にnステップ走らせて、止まらなければ強制終了させればよい。そして、nステップで停止するプログラム全体の集合は、各ステップで実行されうる命令の数が高々有限なので(チューリングマシンは"有限"オートマトンによる実行を基本とする)、その濃度は多くともXである。よって、Z <= X + X + X + ...(加算無限個続く)であり、X^2 = Xより、Z <= Xがいえる。
これらより、 Y <= Z <= Xであり、かつ自明にX <= YなのでX = Yである。