Rule 30: 一つの黒いセル

Rule 30: 一つの黒いセル

単純なプログラム、40年の問い

一つの黒い正方形から始めます。一つの小さなルールを、行を重ねて適用します。成長するものは、一部は秩序正しく、一部はワイルドであり、その中央をまっすぐに走る列が繰り返されるかどうかは、まだ誰も証明できません。

Rule 30が一つの黒いセルから成長する様子。中央の緑色の列は、Stephen Wolframの賞が問うものです。各行が現れると、その中央のセルは右側のストリップに読み取られます。これまでのところ、公正なコインの投げ方と全く同じように見えます。

1 · ルール

ペンで実行できるルール

黒または白の正方形の行を想像してください。次の行を作成するために、各正方形は上の3つの正方形を見ます：真上にあるもの、およびその左と右の隣接するもの。それら3つの色は8つの組み合わせで現れる可能性があり、ルールは単純に、各組み合わせに対して新しい正方形の色が何であるかを述べています。

8つの答えをバイナリ数で書くと、00011110、つまり30になります。それがRule 30のすべてです。以下では、ルールが一度に一つの正方形に適用されます。3つの囲まれた正方形が新しいものを決定し、ルールの対応するエントリが点灯します。

言葉で言うと：新しい正方形は、左上の正方形が「上の正方形または右上の正方形が黒い」と異なる場合に黒くなります。一つの論理行が、どこでも同じように、永遠に適用されます。

2 · なぜ重要なのか

何もないところからのランダム性

1980年代初頭、Stephen Wolframはこのような最も単純なプログラムを体系的に調べることを始めました。それらは256種類しかありません。ほとんどはつまらないことをします：消滅する、繰り返す、またはきれいなネストされたパターンを作る。Rule 30はそうしません。その左側は規則的な縞模様に落ち着きますが、右側は決して落ち着かず、その中央の列はランダム性の標準テストをパスします。

非常に単純なルールがランダムに見える振る舞いを生成できるというその観察は、Wolframの『A New Kind of Science』（2002年）の礎となりました。長年、Rule 30はMathematicaの乱数を生成しました。そのパターンはケンブリッジ・ノース鉄道駅の壁を飾っています。そしてそれは挑戦の対象となりました。

Rule 30を見てからほぼ40年になりますが、今でも私を驚かせます。Stephen Wolfram、Rule 30賞の発表、2019年10月1日

その日、Wolframは中央の列に関する3つの質問それぞれに10,000ドル、合計30,000ドルの賞金を提供しました。7年経った今も、3つすべてが開いたままです。列をコインとして読み、黒をヘッド、白をテールとして：

問題1中央の列は常に非周期のままか？コインは永遠に繰り返されるパターンに陥るか？開く

問題2各色は平均して同じ頻度で現れるか？長期的にはコインは公正か？開く

問題3そのn番目のセルを計算するには少なくともnステップの労力がかかるか？n番目の投げ方にショートカットはあるか？開く

コインはランダムではありません：各投げはルールによって固定されています。したがって、各答えは単にイエスかノーであり、証明だけがそれを解決できます。Wolframのチームは、列の10億個のセルを計算しました。それらは完全にランダムに見えますが、それは何も証明しません。

3 · 端の秩序

秩序がある場所、そしてそれが終わる場所

ピラミッドをもう一度見てください。その左側は縞模様で、右側はワイルドですが、どちらも見た目通りではありません。両方の端は正確な形状の秩序を運び、そして両方の形状は2026年10月9日に注意深く見た結果見つかりました。

左側の縞模様はギザギザの線に沿って並ぶ

ピラミッドを左端に平行な線、つまり対角線で読み取ります。最初のいくつかの対角線は短い繰り返しパターンに落ち着き、それらが繰り返されると、それらは永遠に繰り返されます。なぜなら、それらの対角線は互いにのみ依存するからです。したがって、各行で、永遠の縞模様に到達した対角線の正確な数が存在します。以下では、それらは色付けされており、マゼンタ線は色付けされた帯のエッジです。秩序が終わる正確な場所です。

それはピラミッドの側面をまっすぐ下りません。それは一番上の中心近くから始まり、ピラミッド自身の端の約4分の1の速度、平均して1行あたり0.244セルで傾斜します。これは、右側の変化がランダムな行を介して左に広がる速度、約0.246に近いです。グラフは行524,288までエッジを追跡します。その直線状では、ランダムウォークのようにさまよいます。

左前面を独自のページで開く →

ライブ：Rule 30が一つの黒いセルから行512まで成長する様子。秩序のある帯は色付けされ、その正確なエッジはマゼンタ色で示されています。点線は光速の4分の1です。サウンド（押されるまでオフ）は、グラフのカーブを滑らかな一つの音に変えます。ピッチはそのカーブの高さで、2つの点線のガイドの間になります。エッジの定義は正確であり、秩序のある帯は決して縮小しません。その平均速度とランダムウォークのさまよいは測定値であり、証明ではありません。グラフの時間軸は各ティックで倍増するため、最後のストレッチにはすべての行の半分が含まれます。遅い上昇は、ウォークの通常の揺れであり、突然の変化ではありません。

ワイルドな側でさえ定規がある

Garethがこれを目で見て気づきました。ワイルドな右端に沿って、それに触れる白い三角形は完全に均等な間隔で現れ、そのサイズだけが異なります。それは完全に正確です。各2行目に、白い三角形がエッジから1セル内側に始まり、その幅は行番号を2で割った回数にのみ依存します。定規の目盛りと同じです。行2、6、10、14など（奇数の2倍）は最小の三角形、行4、12、20は次のサイズ、行8、24、40はさらに次のサイズ、といった具合です。

理由は、右端に平行な各対角線が2の累乗の周期で繰り返されることです。対角線の周期の倍数である行では、対角線は開始時と同じように白くなります。三角形は、その周期が行を割り切らない最初の対角線で終わります。これはすべて時間に対して証明されています。

エッジルーラーを独自のページで開く →

ライブ：ピラミッドが行ごとに成長します。各偶数行のエッジ三角形は、生まれると色付けされ、その幅はエッジの右側のティール色のティックとして繰り返されるため、ティックはルーラーを描きます。マゼンタ色のトレーサーは、新しい三角形の角をそのティックに接続し、跡を残します。エッジの内側では、跡は右側の前面、つまり目に見える秩序が終わる場所であり、各2の累乗で最も深くなります。サウンド（押されるまでオフ）は、各三角形を音として再生します。倍増ごとに1オクターブ低くなり、独自の時間を保ちます。画像が終わるまでルーラーを下って再生し、一時停止するまで続きます。

どちらの種類の秩序も賞の列には達しません。行tでは、中央の列はどちらのエッジからもt番目の対角線上にあり、ますます深くなります。そこでは周期が長すぎて見えなくなります。右端から54番目の対角線は4,194,304行後にのみ繰り返されます。端の秩序は、中央についてはまだ何も語っていません。だからこそ、問題は難しいのです。

4 · 全体像

三角形、正方形、そして円

さて、賞の列そのものについてです。問題1は、それが繰り返される可能性があるかどうかを尋ねます。したがって、最も単純な方法で繰り返されると仮定します：白、黒、白、黒、永遠に。中央を壁のようにそのビートに合わせ、右側からRule 30をランダムな開始で実行します。壁のすぐ右隣の列は驚くべきことをします。それは56ステップの固定ループ、つまりホイールに陥り、右側から何かがそれをノックするまでそこに留まります。その後、新しい位置でホイールに戻ります。

下のプレートは、レオナルド・ダ・ヴィンチの『ウィトルウィウス的人体図』に倣って、ピースを組み合わせています。上部には、Rule 30が一つのセルから描く三角形があり、その中央を賞の列が走り、オフセンター領域にカオスが存在します。それは、角の上に立つ正方形の上半分です。下にはホイールがあり、実際には同時に2つの時計（8と7の位置）です。その隣には、それを駆動する壁の実験が実行されています。点線は、ホイールの現在の位置を両方の時計とそれが表すセルに追跡します。

プレートを独自のページで開く →

ライブ：三角形、その正方形、賞の列、オフセンターコア、および8点と7点の時計を持つ56点のホイール。各キック（列1がホイール上の新しい場所にノックされたとき）は、読み出しでカウントされます。

5 · 反対を仮定する

繰り返される中心が要求すること

Rule 30には便利な特性があります。中心列とその隣の列を知っていれば、左側のすべてのセルが一つずつ強制されます。したがって、繰り返される中心は左側全体を強制します。賞は一つの黒いセルについて尋ねますが、私たちは有限の開始、つまり有限個の黒いセルを持つパターン（それを含む）についても同じことを尋ねます。それらのいずれについても、強制された左側は、ある深さ以降は永遠に白くなる必要があります。問題1の反例はまさにそれです：決して壊れない白いエッジ。

中心に何を言わせても、有限の開始が終わるのを見る

同じ特性は逆にも機能します。中心に何を言わせるか（素数、フィボナッチ数、πのバイナリ数字、あなた自身の名前など）を選び、左側に1セルずつ開始を構築します。中心からtセル左のセルは、それ以前のステップを乱すことなく、tステップで中心を直接決定します。したがって、すべてのシーケンスを作成できます。ただし、開始は決して終わりません。各ステップにはさらに多くのセルが必要です。それを有限の開始にカットすると、シーケンスは壊れます。ちょうど、それが欠けている最初のセルが中心に到達したときのように。18セルの開始の最良のものさえ、素数については18ステップ、πについては19ステップしか続きません。有限の開始は、シーケンスがRule 30自体で生成されるものでない限り、それが言わされていることに関係なく、約1ステップ/セルを購入します。問題1は、繰り返されるパターンがそれらのうちの1つであるかどうかを尋ねます。

中心に何を言わせるか独自のページで開く →

インタラクティブ：中心に何を言わせるか、開始に使用できるセルの数を選択するか、「開始を成長させる」を押します。画像の横にある2つのストリップは、要求されたものと中心が行うものを比較します。赤い点線は、最初に見つからないセルが中心に向かうのを追跡し、空のコーナーのチャートはステップとセルの数をプロットします。18セルまでの最良の有限開始はオーク色で示されています。すべてのシーケンスが無限の開始から構築できることは正確です。1ステップ/セルは小さな開始での測定値であり、定理ではありません。

ビットを1つ反転させ、変化が広がるのを見る

開始単語もアニメーション化できます。そのビットを1つ反転させると、下の画像が変化しますが、反転したセルから開く円錐の内側だけで、変化はステップごとに1つずつ到着するため、ページを下に掃引します。その右端は直線であり、ステップごとに正確に1セルです。これは、開始がセルごとに構築できたのと同じ理由です。左端は、色がそれを通過させる場合にのみ移動します。ランダムに見える内部では、ステップあたり約4分の1セル、白い外部に到達すると1セルになります。中心の左側を反転させると、中心列には、それがセルから離れているステップ数と同じステップ数で到達します。Grayコード順にビットを反転させると、フレームはすべての可能な開始を通過します。各フレームは前のフレームから1つのビットが異なります。

ビットを1つ反転させる独自のページで開く →

ライブ：各フレームは24セルの開始の1ビットを反転させ、新しい画像を上から下に掃引します。変更されたセルは色付けされ、円錐の端は赤で描かれ、中心が最初に変化したステップがマークされます。「変更のみ」は変更されたセルのみを表示します。右端の正確な速度は証明されており、4分の1はランダムな行での記録の測定値であり、読み出しは発生した各フリップを測定します。

中心列の隣の列も繰り返される場合、左側は結晶化する

試してみてください。以下では、中心はビート（ティール色）に固定され、隣の列（アンバー色）には繰り返されるパターンが与えられます。メニューから選択するか、ランダムなものを要求してください。Rule 30は次に左側の列を一つずつ固定するため、画像は中心から左に成長します。どのようなパターンであっても、短いストレッチ（点線）の後、左側は結晶化します：単一のレンガで構築された壁で、横方向および下方向に繰り返されます。レンガは決して空白ではなく、したがって左側は決して白くなることはありません。これは1990年のJenの定理です。20までのすべての偶数長のパターン（1,398,100個）のうち、20種類の異なるレンガしか現れません。

結晶を独自のページで開く →

ライブ：時間は下へ、中心の左側の深さは左へ進みます。アンバー色の輪郭は1つのレンガとそのコピー（薄い色）です。3つの点線トレーサーは、3つの値をリング上で追跡します。実行中は斜めに、フレームがそれに合わせて回転するとまっすぐ下に表示されます。ページはロード時にリングをその84ビット証明書に対して再計算します。

白いエッジが要求するもの

そのようなエッジが何をもたらすかを見ました。それは摂動を伴って引きずり、ビートを維持しなければならないセルを引っ張ります：奇数、奇数、偶数、奇数、奇数、偶数、フィボナッチ数のパターン1、1、2、3、5、8、13。内部の何かが永遠にそのビートに応答する必要があります。短い4つのアニメーションは、ビート、それに支払うことができる唯一のパターン、そしてRule 30がそれを禁止する理由、支払いが常にますます古いイベントを必要とする理由、そして実際のRule 30がそれにもかかわらず試み続ける理由を示しています。

4つの行為を独自のページで開く →

ライブ：行為0から開始します。このフレームが横向きにしたおなじみのピラミッドであることを示します。時間は横に、左側の深さは下に走ります。ボタンの下の線は、文全体で議論を示し、あなたが現在いる行為をマークします。行為1と2では、赤い点は摂動です。ターゲットの三角形に着地した各点は番号が付けられ、ターゲットにトレースされます。ターゲットのラベルはカウント（奇数または偶数）を示し、行の横のバーは支払われるべきビートを示します。

6 · 私たちが見つけたこと

問題1の現状

私たちは3つの問題のいずれも解決していません。以下は、その過程で判明したことを平易な言葉でまとめたものです。以下の各証明は、プロジェクト内で第二読者によってチェックされました。まだ外部でのレビューは受けていません。計算は、実行前に期待される結果とともに発表され、少数の探索的なものは記録でそのようにマークされています。

私たちが攻撃したケース

• 有限の開始パターン（黒いセルが1つ以上あるもの）において、中心列が最終的に永遠に単色で留まることは不可能である。これは2026年9月にCondreyによって証明されました。彼は、白、黒、白、黒という次のケースを未解決のケースとして命名しました。そして、この作業はこのケースについてです。
• 中心列の近くには、そのような反例は存在しません。その白いエッジは、中心から248セル以上左から始まる必要があります。108セルまでの左側と組み合わせて機能する32セルまでの右側はありません。これは43億ケースすべてがチェックされました。
• Rule 30の近縁であるRule 210についても同様の質問が解決されました。有限の開始パターンは、その中心を白、黒、白、黒と刻むことはありません。

反例が存在する場合、それは以下のようになります

• 中心列の隣の列は決して繰り返しのパターンに落ち着かず、したがって上記のホイールは永遠に滑り続けます。
• その滑りは、固定比率よりも速く稀になることはありません。
• 1ステップおきに読み取ると（左側がそれを見るすべて）、その列は、右側に何があっても、1リードあたり8分の1ビット未満の情報しか運びません。
• それは有名なフィボナッチ単語やその種のシーケンスではなく、ほとんどすべての回転速度で、ウィンドウを通しての回転円の読み取りでもありません。Thue–Morseシーケンスは、少なくとも15,868セルまでの左エッジについては除外されています。

最初の点（1990年のJenの定理）を除き、これらは10月4日時点の記録にはなく、限定的な検索でも印刷物で見つけることはできませんでした。これらを合わせると、反例はありそうもないように思えますが、証明ではありません。すべては、誰も方法を持っていない一つの声明に帰着します。中心をそのビートに合わせるには、実際の情報が必要です。ビートを維持する開始パターンの数は、時間とともに指数関数的に減少するはずです。私たちはその減少を測定でき、それはステップあたり約1ビットに近いです。開始の左側によって支払われるコストの部分は証明されています。右側によって支払われる部分は未解決の問題です。

中心列自体

• 最初の4,194,304セルにおいて、線形テストに対してはコインのように予測不可能であり、その半分の長さ以下の線形再帰では生成されません。これは、公正なコインが与えるものと全く同じです。
• その色は公正なコインのようにバランスが取れており、16セルまでのどの単語も、サンプルの中央で有利なままである単語を探した場合でも、チャンス以上に繰り返し現れることはありません。
• コードとして読み取ると、列はどこから来たのかを言うことができません。無限に多くの他の有限開始パターン（11、101、1011、10101など）が全く同じ中心列を生成します。右側に最大20セル、左側に最大108セル、または右側に最大28セル、左側に最大200セルのすべての開始パターンの検索では、他のものは見つかりませんでした。

永遠に時計を刻むリング

一つの構築が、可能性の端がいかに近いかを示しています。84個のセルからなる行が、端から端まで永遠に繰り返されると、6ステップごとに元に戻ります。その中心は永遠に白、黒、白、黒と刻み、その隣の列は短いループを繰り返し再生します。これは反例ではありません。なぜなら、無限に多くの黒いセルがあるからです。しかし、これは反例がしなければならないことを正確に行っている実際のRule 30パターンです。

[画像: ネックレスのパターン]

リングが回転し、その履歴はレンガの壁になる

実行中に見ると、リングは見た目よりも単純です。Rule 30の各ステップは、リング全体を84個のセルのうち14個（6分の1回転）回転させます。これが6ステップごとに元に戻る理由です。「リングと一緒に回転」を押すと、紙も一緒に回転するように再描画されます。各列は永遠に単一の色になります。その無限の履歴は、幅14セル、高さ6行、黒いセル43個の1つのレンガで、レンガを壁に敷き詰めたようになります。各レンガの列は、前の列よりも1行下になります。これは上記の20個の結晶のうちの1つです。

その背後には、私たちが証明した一般的な事実があります。Rule 30は8つのジグソーパズルのピースにカットでき、それぞれがルールの各ケースに対応します。そして、その履歴はそれらを組み合わせる方法に正確に対応します。行が変化よりも遠くまで移動して元に戻る行（このリングのように）は、横方向にも繰り返さなければなりません。したがって、その履歴は1つのレンガの壁になります。同じピースがこのような壁を作成します。したがって、問題1はピースに関する質問ではありません。それは、単一の黒いピースから成長した1つの画像が中央で繰り返される可能性があるかどうかを尋ねています。

回転するリングを独自のページで開く →

ライブ：リングの48ステップ、1行あたり1ステップ。アンバー色の輪郭は1つのレンガとそのコピー（薄い色）です。3つの点線トレーサーは、3つの値をリング上で追跡します。実行中は斜めに、フレームがそれに合わせて回転するとまっすぐ下に表示されます。ページはロード時にリングをルールに対してチェックします。

7 · 数学における双子：Collatz

任意の整数を取ります。偶数なら半分にし、奇数なら3倍して1を足してから半分にします。これを繰り返します。Lothar Collatzは1937年に、すべての開始値が最終的に1に到達するかどうかを尋ねました。コンピュータは271未満のすべての開始値をチェックしました（約2.4 × 10^21）。誰もそれを証明できません。そして、証明または反例に対して1億2000万円（Bakuage、2021年）の賞金が待っています。

それは別の世界のように見えますが、バイナリではRule 30と同じマシンです。バイナリで書かれた数値は黒と白のセルの行であり、それを3/2倍すること（Collatzの奇数ステップの中心、つまり3n/2 + 1/2）は、その行に対してRule 30が行うことと似たような操作を行います。どちらも、単一の単純なステップであるGrayコードから始まり、補正を加えます。

Grayコードは、各数値が前の数値と単一の桁で異なるバイナリの数え方です：000、001、011、010、110、111、101、100。これはBell LabsのFrank Grayにちなんで名付けられ、ロータリーエンコーダーのように読み取りがジャンプしてはならない場所で使用されます。そのレシピは一つの比較です。数値をバイナリで書き、各桁を左隣の桁と比較し、異なるところを黒にします。このステップを単一の黒いセルから行ごとに繰り返すと、第5章のSierpinski三角形が現れます。Grayコードで数えると、ステップ1、2、3、4、...で桁番号が0、1、0、2、0、1、0、3、...と変化します。その桁は、ステップを2で割った回数であり、これは第3章のエッジルーラーと同じです。したがって、ルーラーのリズムとその音はGrayコードの数え方です。以下では、一つの数値が3つのルールを並べて通過します。

Rule 30はGrayコードに、セルが白で右隣が黒の場合に補正を加えたものです。そのため、補正は単一のセルであり、隣接することはありません。3/2倍することは、数値とその半分の合計であり、これはGrayコードにその加算の繰り上がりを加えたものです。繰り上がりは0に遭遇するまで続きます。同じステップ、それを補正する2つの方法です。

したがって、2つの問題は、同じ単純なルールをわずかに間違って適用する2つの方法であり、どちらもSierpinski三角形の重なりとして展開されます。ここでは両方とも単一の黒いセルから始まります。Rule 30、および3の累乗（単一の1に3/2を繰り返し乗算した結果、偶数での除算は行をシフトするだけです）。

右側の図のt行目は3tをバイナリで表したもので、最後の桁（常に1）が右端にあり、Rule 30のように行ごとに1マスずつ移動します。補正は、次の行がSierpinskiステップから外れる各セルをマークします。Rule 30では単一のセルですが、乗算では繰り上がりであり、文字列として実行されます。エッジルーラーは、各偶数行の黒いエッジのすぐ内側にある白いランをマークします。

類似性はエッジにも及びます。3の累乗の各2行目には、黒いエッジのすぐ内側に白いセルのランがあり、その長さは行番号を2で割った回数のみに依存します。これは、GarethがRule 30のエッジで発見したものと同じ種類のルーラーです。3の累乗の場合、これは「指数を上げる」補題という古典的な定理であり、ルーラーは完全に規則的で、2倍になるごとに1マス長くなります。Rule 30のものは、2倍になるごとに約2.5マスずつ不規則に増加します。そのレートは測定されたものであり、証明されたものではありません。両方の図で、右端に平行な各対角線は2の累乗の周期で繰り返され、両方で中央は証明できない場所です。

質問の形状も同じです。どちらの場合も、有限の開始（数値の有限の桁数または行の有限の黒いセル数）が、逆方向に実行できるルールに与えられ、問題は、開始が制御する部分を超えて出てくるものがコイン投げのように振る舞うかどうかです。一つの正確なステートメントは、両方で単語ごとに成り立ちます。出力の一部が繰り返されるのは、それが現在の状態の大きさ（桁数またはセル数でカウント）を超えない場合に限られます（Collatz側ではこれはすでに知られていました）。そして、簡単なケースを解決する方法は、両方で同じ場所で停止し、さらに3つの有名な問題、1968年のMahlerの3/2問題でも同様です。これは、制約された部分が有限の方法でしか振る舞えない場合には反例が存在しないことを示し、無限の方法で振る舞えるようになると何も言わなくなります。これはまさにRule 30の白黒ケースとMahlerの質問が位置する場所です。

したがって、各側はもう一方にないツールを持っています。Collatzは算術（3の累乗による剰余、対数の線形形式、これは3の累乗が2の累乗にどれだけ近づけるかを制限します）を持っています。Rule 30は局所性を持っています。その補正は単一のセルであり、これがエッジイベントに関する正確なルールを可能にしたものです。どちらかの側での証明は、もう一方の側での証明が置き換えるべきものを示すでしょう。どちらの側にもまだ証明はありません。詳細は、各主張の出典とともに、記録のCollatz部分にあります。

8 · 作業方法

5日間、3人の共同作業者、すべてオープンに

この作業は2026年10月4日から9日にかけて、GarethがAI共同作業者であるAnthropicのClaude（2つの役割）とOpenAIのGPTと協力して行われました。各証明は一方の当事者によって提案され、もう一方の当事者によってチェックされた後、証明済みとして提出されました。予測は実験の前に書き留められ、失敗したすべての予測は保持されました。証明、反論、計算を含む完全な記録は公開されています。