ビジービーバー関数BB(n)は、任意の自然数nについてその値が定まると言っていいのだろうか?
例えば連続体仮説でよく知られるように、"可算無限濃度より大きく、連続体濃度より小さい濃度の個数"
の値はZFCのモデルのとり方によって変わり、連続体仮説が真となるモデルなら0、そうでないなら0以外となる。
BB(n)の値も、自然数のモデルのとり方によって変わってしまうことはないか。
"自然数論(ペアノ算術)における妥当な論理式を枚挙し、矛盾を導出したら停止するチューリング機械M"
を構成すると、 これが停止する <=> 自然数論は矛盾 となるから、
自然数論が無矛盾ならこの機械は停止しないはずである。
一方で、自然数論が無矛盾なら自己の無矛盾性は証明できないから、Mが停止しないことを証明できない。
一階述語論理の完全性より、恒真ならば証明可能なので、停止することも停止しないことも証明不能なら
停止するモデルと停止しないモデルの2つがありえる、ということになる。
(一階述語論理の完全性と呼ばれるものは、ゲーデルの第一不完全性定理で言うところの完全性(任意の論理式に
ついて、その肯定か否定のどちらかが証明可能)とは全く意味が異なることに注意)
そもそもチューリング機械Aが停止するとは、"Aがnステップ目で停止状態"を意味する論理式H_A(n)に対し、
∃n (H_A(n))が真であることだと言える。
∃n (H_M(n))が成り立つモデルと成り立たないモデルがあるとはどういうことか。
単純に、∃n (H_M(n))が成り立つ自然数論のモデルはより多くの自然数を含んでいる、ということである。
(集合論で言うところの、巨大基数公理が成り立つモデルのほうが、そうでないモデルよりたくさんの
集合を含んでいることに似ている)