チューリングマシンの状態数について

質問

この質問で言うチューリングマシンは、
「使用できる文字が0,1,Xだけのもの」とします。

自然数nに対し、
「空列を入力して動作を開始すると、有限ステップで停止して、停止したときにテープに書き残されている文字数がn以上」
であるようなチューリングマシンを全て集めた集合をKnとします。
そして、 g(n)= min{size(M) | M∈Kn }
とします。ただし、size(M)はチューリングマシンMの状態数であり、minは「最小値」を意味します。
各nに対してKnは非空集合なので、g(n)の値はどんなnに対しても一意に定義されます。
すなわち、gは自然数上の全域関数です。
ビジービーバー関数は「状態数」から「その状態数のチューリングマシンが書き残せる最大字数」を求めるものでありますが、
この関数gは「字数」から「それ以上の字数を書き残せるチューリングマシンの最小状態数」を求めるものです。

このgが計算可能であるか、計算不可能であるかを述べて、そのことを証明してください。
よろしくお願いいたします。

((関数が)計算可能の定義は、「それを計算するＣ言語プログラムが存在する」です。)

回答No.2

Tacosan · ベストアンサー

この g はある意味で「ビジービーバーの逆関数」とみることができます. つまり, (てきと～な例ですが)
g(5) = 3, g(6) = 3, g(7) = 4
だとしたら
・3状態で 6文字残す TM が存在する
・3状態で 7文字残す TM は存在しない
ことがわかります.

ということは, g が計算できればビジービーバーの方も計算できますね.

でもこれ, カテゴリは「数学」の方が適切だよなぁ....

お礼

ありがとうございました。
カテゴリー選びに迷ってC言語にしてしまったので、今後似たような質問をする場合は「数学」のほうで投稿しますね。

回答No.1

Tacosan

ちと調べると, ビジービーバーで「状態数を与えたときに字数がどれだけになるか」は計算不可能って書いてあるんだけど, それは使っていいの?

補足

回答ありがとうございます。
はい、使っていただいてかまいません。