ビジービーバー関数Σ(n)、最大シフト数関数S(n)、最大停止時間関数T(n)

ビジービーバー関数Σ(n)はすべての計算可能関数より速く増大する関数の一つで、定義としては

「停止する｛0,1｝記号・n状態チューリングマシン」が
停止までに印字する1の個数の最大値

となる。

同じく計算不可能関数である、最大シフト数関数S(n)の定義は

「停止する｛0,1｝記号・n状態チューリングマシン」が
停止までにシフトする回数の最大値

となる。

このn状態というのは各チューリングマシンが持つ有限の数値の一種で、
別の数値を使って計算不可能関数を定義することもできる。

例えば最大停止時間関数T(n)を

「n文字以内で書かれた、有限時間で停止するプログラム」のうち
停止までにかかる時間の最大値

と定義するとこれも計算不可能関数になる。（※）

この定義ならチューリングマシン知らなくてもプログラム知っていたら理解できると思う。

計算不可能性の証明。背理法を用いる。
(停止性問題を解くアルゴリズムが存在しないという事実は既知とする)

■■■■■■証明■■■■■■

T(n)が計算可能関数だったと仮定する。
すると以下の方法でプログラムの停止を判定するアルゴリズムが作れる。

1.与えられたプログラムPの文字数を数え、その数をnとする。

2.T(n)を計算する。（ここでT(n)が計算可能であるという仮定を使っている）

3.プログラムPを走らせる。

4.時間がT(n)経った時に
A:停止していたら、Pは当然停止するプログラムである。
B:停止していなかったら、Pは停止しないプログラムである。
なぜなら、T(n)はn文字以下のプログラムの停止時間の最大なので、
n文字からなるプログラムPがこれ以降に停止することはない。

これでPの停止が判定できる。
しかしプログラムの停止を判ずるアルゴリズムは作れないので矛盾である。
よってT(n)が計算可能であるという仮定は偽である。

■■■■■■証明終了■■■■■■

※n文字以内で書かれたプログラムは有限個なので、停止時間の最大値は必ず存在する。
（有限個の実数なら最大値は存在する）
つまり、T(n)は関数として存在する。
もしも
「「有限時間で停止するプログラム」のうち停止までにかかる時間の最大値」
だったら、最大値は存在しない。