64ビットで表現できる最大値です。

日本語訳：

記事は、2023年11月のブログ投稿を再検討し、64ビットプログラムがグレアム数を遥かに超える天文学的に大きな数値を符号化できることを示しています。最小限のCプログラム（「main(){}」）はわずか8文字のASCII文字しか使用しませんが、組み込みプリミティブを持たない言語（例：bc、λ-計算）では、このようなプログラムで (9^{999,999}) やタワー (9^{(9^{(9^{99})})}) のような値を計算できます。

すべてのゼロから始まるn状態チューリングマシンの最長計算時間を与えるバスビーア（BB(n)）と、そのλ-計算類似体 BBλ(n)（サイズ n の閉項の最大 β-正規形サイズ）は、形式的な限界を提供します。既知の正確値は n=36 まで存在し、それ以上の場合は w218 のような最適化された λ-項から得られる下限が用いられます。

記事で言及される主なマイルストーンは、49ビット「最短停止プログラム」Melo（グレアム数を超えるチョーシュ数を出力）と、Discord ユーザー 50_ft_lock と Sam によって作られた61ビット λ-項 w218 であり、その出力はおよそ (2\uparrow\uparrow18) 回の補助関数 A の反復です。これは Melo の数とグレアム数をはるかに上回ります。

記事は、BB(7) > グレアム数が10年以内に証明されないという 1,000 ドルの賭けを引用し、BB(7) がすでにそれを超えていると信じられていることを示しています。

高速成長階層（Fast Growing Hierarchy）を用いて量を比較すると、w218 はおよそ ([ω_2\uparrow\uparrow18 – 1]2) に相当し、一方でグレアム数と Melo の数はそれぞれ ([ω+1]{64}) と (ω+1) に近い位置にあります。

最後に、現在知られている 64 ビット表現可能な最大値は w218 です。また、BBλ(61)（≥ 5 × (2\uparrow\uparrow18)）とその自己区切りバリアント BBλ₂(63) の両方に対して下限を提供します。記事は、さらなる λ-項の最適化がこれらの境界をさらに高め、極小プログラムにおける計算力の理論的理解を深める可能性があると結論付けています。

この投稿は、2023年11月に書いたブログ記事の改訂版で、多くの新しい洞察と更新が加えられています。

64ビットで表現可能な最大数

ほとんどの人は
(2^{64}-1 = 18446744073709551615)（あるいは (0xFFFFFFFFFFFFFFFF\））を、64ビットで表せる最大値だと考えています。英語では次のように言います。

eighteen quintillion four hundred forty‑six quadrillion seven hundred forty‑four trillion seventy‑three billion seven hundred nine million five hundred fifty‑one thousand six hundred fifteen.

これは確かに、64ビット符号無し整数（C の

uint64_t

や Rust の

u64

）の最大値です。
浮動小数点型は基数 2 の指数を持つため、より大きな数を表すことができます。
IEEE‑754 双精度（double）の 64‑ビット実装では、最大有限値は

[ 2^{1024}\bigl(1-2^{-53}\bigr)\approx 1.8\times10^{308}. ]

単なるデータ型を超えて

「プログラム」を表現として許可すると、最も一般的な形は 64 ビットに保存できる何らかの言語で書かれたプログラムです。

最小の有効 C プログラムは

main(){}

― ASCII 8文字。
ASCII は 7‑ビットコードですが、現代の機械では 8‑ビットバイト（あるいは UTF‑8）として保存されるため、これを唯一の 64‑ビット C プログラムとみなします。

他の言語はこのような枠組みを必要としません：

bc（任意精度計算機）は
```
9^999999
```
（954 242 桁）を 8 バイトで計算できます。
より大きな数、例えば
```
9^9^9^99 = 9^(9^(9^99))
```
（(10^{10^{953}})桁以上）は同様に計算可能ですが、bc はそれらで苦労します。
言語が階乗演算子 (
```
!
```
) やアッカーマン関数を組み込みで持っていれば、
```
9!!!!!!!
```
のような式は天文学的に大きな数を表すことになります。
こうしたプリミティブを許可するのは「チート」に感じるため、私たちは一から定義された言語を好みます。

バッキー・ビーバー手法

バッキー・ビーバー関数 (BB(n))（Radó, 1962）は、二進テープアルファベットの n‑状態チューリングマシン（TM）がすべてゼロで始まるテープ上で停止するまでに取る最大ステップ数として定義されます。

TM のサイズは状態数で測られ、プログラムのサイズはビット数で測られるため、n‑状態 TM をビット列として符号化します：

各状態 (s\in{1,\dots,n}) とスキャンされたシンボル（0 または 1）ごとに、遷移は次を指定します：
- 書き込む新しいシンボル（1 ビット）
- ヘッドの移動方向（1 ビット）
- 次の状態（または停止）― (\lceil\log_2(n+1)\rceil) ビット。

したがって、6‑状態 TM は (60) ビット、7‑状態 TM は (70) ビットを必要とします。

64 ビットでプログラム可能な最大数はゆえに (BB(6)) です。

(BB(6)) の大きさは？

(BB(n)) は (n\le5) まで既知です。
(n=6) の値は不明ですが、次のような下限があることが知られています：

[ BB(6) > 2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow10 . ]

この Knuth の上矢印記法で表した指数塔は天文学的に大きいですが、(Ackermann(9,9)=2^{712}-3 = 2\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow12-3) よりはずっと小さいです。

さらに、

[ BB(7) > 2^{112}{}^{113} > Ackermann(9,9). ]

多くの研究者は (BB(7)) がグレアム数を超えると考えています。私は「10 年以内に (BB(7)>G) の証明が見つからない」という 1,000 ドルの賭けを提案し、賭けは受け入れられました。

64 ビットでグレアム数を超える

λ-計算

Alonzo Church は約1928年に計算の形式的体系として λ‑計算（lambda calculus）を導入しました。
最近のコードゴルフチャレンジでは、49 ビットのプログラム Melo が発見され、その出力はグレアム数より大きいと報告されています。

バイナリ符号化は次の通りです：

01 00 01 10 10 00 01 10 01 10 00 00 01 01 10 110 00 00 01 110 01 110 10

これは λ‑項

[ (\lambda 1,1); (\lambda 1, (1,(\lambda \lambda 1,2,(\lambda \lambda 2, (2,1))))) ]

（デ・ブランヌ記法）をエンコードしています。
従来の表記に直すと：

[ (\lambda J.,J,J);(\lambda y.,y,(y;(\lambda g.,\lambda m.,m,g;(\lambda f.,\lambda x.,f;(f,x)))) ]

最後の 16 ビットは Church 数 ( \lambda f.,\lambda x.,f(f,x)) をエンコードしています。
一般に、Church 数 (n) は

0000(01110)n10

と符号化され、そのサイズは (5n+6) ビットです。

グレアム数を超える証明

Lemma 1. (J J = 2\uparrow\uparrow6,HH,2)、ここで (HH = H H)。

Lemma 2. (k,n \ge 2) のとき、( k,H,2,n > 3\uparrow k (1+n))。

Lemma 3. (n \ge 2) のとき、( HH(HH,n) > 3\uparrow n,3)。

Theorem. (J J > G(64))、ここで (G(n)=n(\lambda n.,3\uparrow n,3)^4)。

したがって Melo の数 はグレアム数を十分に超えています。

さらに大きな項 – w218

残りの 15 ビットを使えば、さらに値を高めることができます。
61 ビットのプログラム w218 は次の通りです：

01 00 01 01 10 10 10 00 01 10 01 10 00 00 00 01 01 01 10 1110 110 00 00 01 110 01 110 10

これは

[ (\lambda T.,T,T,T);(\lambda y.,y,(y,(\lambda a.,\lambda b.,\lambda c.,c,a,b;(\lambda f.,\lambda x.,f(f,x)))) ]

（デ・ブランヌ記法）または

[ (\lambda T.,T,T,T);(\lambda y.,y(y(\lambda a.,\lambda b.,\lambda c.,c,a,b;(2)))) . ]

Lemma 4. (T T T = 2\uparrow\uparrow18,A,2^{10})、ここで (A) は三引数関数。

これにより、グレアム数や Melo の数をはるかに上回る数が得られます。これは高速成長階層（FGH）に関連しており、特に w218 は ([,\omega^{2\uparrow\uparrow18-1},],2) に近似し、一方グレアム数は約 ([\omega+1],64) です。

関数型バッキー・ビーバー

λ‑計算に対するバッキー・ビーバーの類似概念は次のようになります：

[ BB_\lambda(n) = \text{サイズ } n の任意閉 λ 項の最大サイズ} . ]

最初の 36 個は既知で、(BB(n)) は (n=5) までしか知られていません。

Melo は (BB_\lambda(49) \ge 5(\text{Melo’s Number})+6) を示します。
w218 は (BB_\lambda(61) \ge 5(2\uparrow\uparrow18,A^2)+6) を与えます。

λ‑項はビット列として直接符号化できるため、(BB_\lambda(n)) は状態ベースのバッキー・ビーバーとビット単位で比較できます。

普遍性と最適性

(BB_\lambda) は (BB) よりも簡潔ですが、普遍性 が欠けています。
自己区切り（self‑delimiting）バリエーション

[ BB_{\lambda 2}(n) = \text{サイズ } n の自己区切り BLC プログラムが出力できる最大サイズ} ]

は、λ‑項を任意の二進データに対して動作させることを許可することで普遍性を実現します。
すべての (n) に対し、

[ BB_{\lambda 2}(n+2)\ge BB_\lambda(n) ]

が成り立ちます。

結論

現在知られている、正確に 64 ビットで表せる最大数は w218（61 ビット）です。
これは (BB_\lambda(61)) と (BB_{\lambda 2}(63)) の下限を提供し、グレアム数や Melo の数など以前の記録を大きく上回ります。