最大シフト数関数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/28 03:01 UTC 版)
シェン・リンは Σ(3) = 6 であることを証明した（ラドーとの共著論文 Computer Studies of Turing Machine Problems [1965年]）。 この証明に際し、彼は停止する n-状態チューリングマシンに関連するもう一つの極限関数である最大シフト数関数(maximum shifts function) を導入した。以下を定義する： s(M) = En に含まれる全ての M について、停止するまでに M がシフトする回数 S ( n ) = max { s ( M ) | M ∈ E n } {\displaystyle S(n)=\max\{s(M)|M\in E_{n}\}} （あらゆる n-状態 2-記号チューリングマシンの中で最大のシフト回数） これらのチューリングマシンは遷移関数を起動するごと（言い換えれば「ステップ」ごと）にシフトしなければならないので（「停止」状態に遷移する場合も含む）、最大シフト数関数は同時に最大ステップ数関数でもある。 さて、もし S(n) の値がわかるなら、全ての n-状態チューリングマシンを S(n) ステップだけ順次走らせて、テープ上に最多の 1 を印字して止まったマシンを見いだすことができる。それがビジービーバーであり、そのマシンが書いた 1 の数こそが Σ(n) ということになる（なぜなら、停止するすべての n-状態チューリングマシンは S(n) ステップ以内で停止するはずであるため）。 このように、最大シフト数関数の研究は、ビジービーバー関数の研究と密接に関連している。
※この「最大シフト数関数」の解説は、「ビジービーバー」の解説の一部です。
「最大シフト数関数」を含む「ビジービーバー」の記事については、「ビジービーバー」の概要を参照ください。
- 最大シフト数関数のページへのリンク
