0086132人目の素数さん
2017/12/16(土) 19:31:17.51ID:uVM5P2Vx>>35では>>84の例で出した1を出力しないのに停止しないマシンには対処できてない。
いましがた、詳細は省くが、任意のn状態数チューリングマシンに対して、
少なくとも21n状態数チューリングマシンなら1ステップごとに1の数が少なくとも1つは
増えていく、つまりステップ数を数えながら動くマシンを作れることが分かった。
これより、最大ステップ数関数S(n)
= "n状態数チューリングマシンが停止するまでにかかるステップ数の最大値+1"
とすれば、 BB(n) ≦ S(n) ≦ BB(21n) となる。
あとは>>26を改造して n ≧ S(M)が導けたときに n ステップまで動かせば停止性問題解消、
とすれば、あるMが存在し 0 < BB(21M), 1 < BB(21M), ...を加えても無矛盾と言える
ので、∀n (BB(n) < BB(n+1))から、結局は※と同じことを導出できるな。