S(n, m) と Σ(n, m) の値と下限について
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/28 03:01 UTC 版)
「ビジービーバー」の記事における「S(n, m) と Σ(n, m) の値と下限について」の解説
以下の表で示すのは、一般ビジービーバー問題におけるS(n, m) と Σ(n, m) に関する既知の値または下限である。既知の正確な値は単なる数字で表し、既知の下限には大なりイコール(≧)を付けている。註："???"と書かれた場所の値は、その升の左方向と上方向に存在する中で最大の値（または下限）が下限となる。これらのマシンは未調査か、または一旦得られた下限がより小さいマシンに抜かれたために取り消されたかのいずれかである。 これらの値を達成したチューリングマシンの実例はHeiner MarxenのサイトかPascal Michelのサイトで見ることができる。これらのウェブサイトでは、他にもチューリングマシンに関する研究や正確な値についての証明などが紹介されている。 S(n,m) の値: 2-状態3-状態4-状態5-状態6-状態2-記号6 21 107 ≧ 47,176,870 ≧ 7.4 × 1036534 3-記号38 ≧ 119,112,334,170,342,540 ≧ 1.0 × 1014072 ??? ??? 4-記号≧ 3,932,964 ≧ 5.2 × 1013036 ??? ??? ??? 5-記号≧ 1.9 × 10704 ??? ??? ??? ??? 6-記号≧ 2.4 × 109866 ??? ??? ??? ??? Σ(n,m) の値: 2-状態3-状態4-状態5-状態6-状態2-記号4 6 13 ≧ 4,098 ≧ 3.5 × 1018267 3-記号9 ≧ 374,676,383 ≧ 1.3 × 107036 ??? ??? 4-記号≧ 2,050 ≧ 3.7 × 106518 ??? ??? ??? 5-記号≧ 1.7 × 10352 ??? ??? ??? ??? 6-記号≧ 1.9 × 104933 ??? ??? ??? ???
※この「S(n, m) と Σ(n, m) の値と下限について」の解説は、「ビジービーバー」の解説の一部です。
「S(n, m) と Σ(n, m) の値と下限について」を含む「ビジービーバー」の記事については、「ビジービーバー」の概要を参照ください。
- S と Σ の値と下限についてのページへのリンク
