ビジービーバー関数 Σ(n)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/28 03:01 UTC 版)
「ビジービーバー」の記事における「ビジービーバー関数 Σ(n)」の解説
ラドーは n-状態ビジービーバー・ゲームには well-defined な「優勝」チューリングマシンが存在することを示した： n 個の状態と2つの記号を用いるチューリングマシンは有限個しかない（この場合は [4(n+1)]2n 個）。さらにこのうちの幾つかは停止することが自明である。すなわち、すべての n について、n-状態かつ 2-記号の停止するチューリングマシンが少なくとも一つ存在する。 ビジービーバー関数 Σ(n) は、「状態」 (Turing-instructions) の個数を表す数字 n と空テープが与えられた時に、ビジービーバー・ゲームの「優勝」チューリングマシンが印字する 1 の個数を導く関数として定義される。 前述の性質（二方向の無限長のテープ、5タプルで定義される遷移関数など）を持ち、n-状態かつ2-記号の停止するチューリングマシンの有限で空でない集合を E n {\displaystyle E_{n}} と書く。 チューリングマシン M {\displaystyle M} を空テープから走らせた後で、テープ上に残された 1 の個数を σ ( M ) {\displaystyle \sigma (M)} と書く。これは E n {\displaystyle E_{n}} に含まれる全ての M {\displaystyle M} について定義される。 このとき、あらゆる n-状態 2-記号チューリングマシンが書いた 1 の個数の中で最大の個数を表す関数 Σ ( n ) = max { σ ( M ) | M ∈ E n } {\displaystyle \Sigma (n)=\max\{\sigma (M)|M\in E_{n}\}} をビジービーバー関数とする。 （En に含まれる）全ての停止する M について、σ(M) は非負整数であり、かつ、En は空でない有限集合なので、 全ての n について Σ(n) は well-defined な負でない有限の数である。 また、σ(M) = Σ(n) を満たす（つまり最大値を与える）ような n-状態 2-記号マシン M を ビジービーバー と呼ぶ。なお、n-状態ビジービーバーは一つとは限らない。つまり σ(M1) = σ(M2) = Σ(n) というようなことは有り得る。
※この「ビジービーバー関数 Σ(n)」の解説は、「ビジービーバー」の解説の一部です。
「ビジービーバー関数 Σ(n)」を含む「ビジービーバー」の記事については、「ビジービーバー」の概要を参照ください。
- ビジービーバー関数 Σのページへのリンク
