新智元（AI New Era）報道
編集：Aeneas KingHZ
【新智元ダイジェスト】直前、Claude が単独でグラフ理論の未解決の予想を克服し、『コンピュータのプログラミング技法』を著したコンピュータサイエンスの巨匠、ドナルド・クヌース氏を完全に震撼させました！今回、AI は自動推論と創造的問題解決において、新たなマイルストーンに到達しました。
衝撃です！衝撃です！
まさに今、Claude はわずか 31 ステップで、未解決のグラフ理論の予想という難問を単独で攻略しました。
『コンピュータのプログラミング技法』を著し、アルゴリズムの祖とされるクヌース氏はこう叫びました。「生成 AI が数学研究において果たす役割を再評価せざるを得ない」。
スタンフォード大学の公式ウェブサイト上にて、彼自身による論文が公開されました。その冒頭の 2 語は「Shock！Shock！（衝撃だ！衝撃だ！）」でした。
論文アドレス：https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf
クヌース氏とは誰でしょうか？
『コンピュータのプログラミング技法（TAOCP）』を執筆し、TeX を発明したチューリング賞受賞者であり、アルゴリズム界の祖です。
『コンピュータのプログラミング技法』はクヌース氏の人生における最大の事業であり、彼がこの本を執筆した目的は、「自身が知るコンピュータ科学の方法論に関する知識を整理・要約し、確固たる数学的・歴史的基础を築くこと」です。
50 年間もアルゴリズムの本を書き続けてきた人物が、AI の数学的能力を真に重視し始めたということは、AI が人間の中核的な知性の領域に踏み込みつつあることを示しています。
アルゴリズムの祖を悩ませた問題
Opus 4.6 によって攻略される
論文の冒頭で、クヌース氏はこのように語っています。
「昨日、私が数週間も研究に費やしていた未解決の問題が、Anthropic 社が 3 週間前に発表したハイブリッド推論モデルである Claude Opus 4.6 によって解決されたと知った！」
彼は率直にこう述べています。
「どうやら私は遅かれ早かれ『GenAI』に対する見方を見直す必要がありそうだ。自分の予想に対する美しい解法が存在するだけでなく、自動推論と創造的問題解決におけるこの劇的な進歩を目撃できるなど、これほど喜ばしいことはない」
物語はこの通りです。『コンピュータのプログラミング技法』というシリーズは 1960 年代から執筆が始まり、現在までに 5 冊が刊行されています。
88 歳という高齢でありながら、このアルゴリズムの祖はまだこのシリーズの執筆を続けています。
彼はその著書の中で、有向ハミルトン閉路に関する問題を準備し、友人らとその特殊な解を証明しましたが、それを一般化しようとした際に解決できなくなってしまいました。
その結果、この問題は Claude Opus 4.6 によって解決されました。
より厳密に言えば、AI が見事な構成方法を発見し、その後にクヌース氏が厳密な数学的証明を与えたのです。
この論文もまた、1 つの象徴的な出来事となりました。生成 AI が初めて、数学研究の物語において真摯に記録されたのです。
アルゴリズムの祖を悩ませた問題とは何か
この問題は、一見単純そうに見えますが、実際には非常に複雑なグラフ理論の問題です。
まず、3 次元の格子空間、例えばm×m×m の立方体を想像してください。
その中の各点は (i, j, k) という 3 つの座標で表すことができ、各座標は 0 から m-1 の範囲にあります。したがって、空間全体にはm³个点が存在します。
次に、各点からは 3 つの方向に移動できると規定します。i を 1 増やす、j を 1 増やす、k を 1 増やす、の 3 つです。m-1 を超えた場合は 0 からやり直します。これにより、トーラス状の空間（環状空間）が形成されます。
クヌース氏の論文における正式な定義によれば、各頂点からは 3 つの有向辺が出ており、それぞれ 3 つの方向の「次の」頂点を指しています。
したがって、グラフ全体には m³個の頂点と、3m³本の有向辺が存在します。
ハミルトン閉路とは、すべての頂点を一度だけ通り、最後に出発点に戻る経路のことです。これは古典的なグラフ理論の問題です。
クヌース氏が出した問題はさらに困難なものでした。1 つの経路を見つけるだけでなく、3 つの経路を見つけ、それぞれがハミルトン閉路であり、長さがすべて m³で、かつ 3 つの閉路ですべての辺をちょうど 1 回ずつ覆うようにすることでした。
つまり、各辺は 3 つの閉路のいずれか 1 つにのみ属さなければならないのです。
本来、クヌース氏はこの問題を『コンピュータのプログラミング技法』の新しい章に記述する予定でした。
なぜこの問題がこれほどまでに困難なのでしょうか。その理由は、各頂点から 3 つの出辺があるためです。ハミルトン閉路を構成するには、そのうちの 1 つを選択する必要があります。つまり、各頂点で選択を迫られるのです。
したがって、問題の規模は 3^(m³) 通りにも達します！これは総当たり検索ではほぼ不可能なため、何らかの規則性のある構成方法を見つける必要があります。
これまで、クヌース氏は m=3 の場合を解決しており、友人のFilip Stappers氏もまた実験を通じて 4≤m≤16 の解を発見していました。
これは、解が存在する可能性が極めて高いことを示していました。
では、一般的な公式を見つけることはできるのでしょうか。
試行錯誤を繰り返す Claude、研究を行う
Filip 氏はこの問題を Claude Opus 4.6 に提示し、厳格なルールを設けました。それは、プログラムを実行するたびに探索の進展を記録しなければならないというものです。
興味深いことに、Claude は突然ひらめいたわけではなく、31 回もの探索を経ており、その過程はまるで大学院生が研究を行っているようでした。
最初のステップで、Claude は単純な関数を試し、各点の方向を決定する関数 g(i,j,k) を使おうとしました。しかしすぐに、単純な線形関数ではうまくいかないと気づきました。
2 ステップ目で、総当たり検索を開始し、深さ優先探索（DFS）を試みましたが、探索空間が大きすぎて非効率でした。
3 ステップ目は 2 次元分析でした。Claude は、2 次元の場合に限定すれば「蛇のような経路」が見つかることに気づきました。そこで、この 2 次元の考え方を 3 次元に一般化しようと試みました。
その後、グレーコードに似た 3 次元の蛇行経路を構成しましたが、最初の経路を削除すると、残りの構造を分解するのが困難でした。
その後の 10 数回の探索で、Claude はひたすら試行錯誤を繰り返しました。
決定的な突破口：ファイバー分解
15 回目の探索で、Claude は「ファイバー分解（fiber decomposition）」という重要なアイデアを提案しました。
s = (i + j + k) mod m と定義すると、すべての辺は頂点を s から s+1 へ移動させることに気づきました。これは、グラフ全体を s に基づいて層状の構造に分割できることを意味します。
これにより、各層は 2 次元格子のようになり、問題が大幅に単純化されました。
Claude はその後、ランダム探索、シミュレーテッド・アニーリング、バックトラック探索などを試みましたが、いくつかの解は見つかったものの、一般的な法則性は発見されませんでした。
そこで Claude は、純粋な数学的構造が必要であるという結論に達しました。
31 回目の探索で、Claude が規則を発見
31 回目の探索で、Claude はついに単純な規則のセットを提案しました。核となるのは依然として s = (i + j + k) mod m です。
そして、s、i、j の状況に基づき、i を増やすか、j を増やすか、k を増やすかを決定します。論文ではこれを「バンプ（bump）規則」と呼んでいます。
規則はおおよそ以下の通りです。s=0 の場合、j の値に基づいて移動方向を決定します。0 < s < m-1 の場合、i の値に基づいて決定します。s=m-1 の場合は、別の規則を用います。
これにより、完全な 1 本の経路が生成されます。
Claude はプログラムで検証しました。m=3, 5, 7, 9, 11 の場合、経路はすべて成立しました。しかも、3 つの経路はすべてハミルトン閉路であり、すべての辺が使用されました。
もちろん、Claude が提案したのは構成方法のみであり、数学的には厳密な証明が必要です。
その後、クヌース氏は、この経路が実際に同じ i の値を持つすべての m²個の頂点を訪問し、続いてすべての i を順にカバーし、最終的に長さ m³の完全な閉路を形成することを証明しました。
同様の証明が他の 2 つの閉路にも適用され、こうして問題全体が解決されました。
さらに、クヌース氏による追加の研究で、Claude が見つけたのが唯一の解ではないことも判明しました。
実際には、760 通りもの同様の分解方法が存在し、これらの解はすべて同じ構造を満たしています。Claude はそのうちの 1 つを見つけただけなのです。
また、Claude が解決したのは m が奇数の場合のみです。
m が偶数の場合、一般的な解はまだ見つかっておらず、m=2 に至っては不可能であることが証明されているため、この研究はまだ完全には終了していません。
最大の意義は、問題を解いたことそのものではない
この出来事が真に意味を持つとすれば、それは問題を解いたこと自体ではなく、AI が問題を解く方法にあります。
この過程において、Claude は答えを推測したのではなく、問題の再定式化、プログラムの作成、法則の発見を行いました。このプロセスは人間の研究活動に非常に近いものです！
何十年もの間、数学的証明は AI が最も参入しにくい分野だと一般に考えられてきました。
しかし、この論文は、AI がすでに本格的な数学的探求に参加し始めていることを示しています。
将来的には、人間が問題を提起し、AI が構造を探求し、人間が証明を完成させるという、新しい研究の形が現れるかもしれません。
そして、この「Claude's Cycles（クロードのサイクル）」は、その出発点と見なされるかもしれません。
クヌース氏が『コンピュータのプログラミング技法』を執筆し始めてから半世紀以上が経ちました。このシリーズは人間のアルゴリズム思考の発展を記録してきました。
そして今、AI がアルゴリズムの大家の論文に記されることになりました。これは、まだ始まりに過ぎないのかもしれません。
クヌース氏とは誰か？コンピュータ科学の父だけではない
ドナルド・アーヴィン・クヌース（Donald Ervin Knuth）、通称クヌース氏は、1938 年 1 月 10 日、アメリカ合衆国ウィスコンシン州ミルウォーキーに生まれました。
ドナルド・クヌース、アメリカの計算機科学者、スタンフォード大学名誉教授
クヌース氏は、アルゴリズム解析の「祖」として広く認知されており、現代コンピュータ科学の先駆者として、理論計算機科学のいくつかの分野において礎となるような貢献をしました。
アルゴリズム解析とプログラミング言語設計への多大な貢献により、1974 年にチューリング賞（計算機科学界のノーベル賞）を受賞しました。
当時、彼はわずか 36 歳であり、この最年少記録はいまだに破られていません。
授賞式では特に、彼の著書シリーズ『コンピュータのプログラミング技法（The Art of Computer Programming, TAOCP）』がコンピュータ・プログラミングの芸術に対して行った傑出した貢献が強調されました。
1999 年末、この本は『アメリカン・サイエンティスト（American Scientist）』誌によって 20 世紀の学術専門書ベスト 12 の 1 つに選出され、アインシュタインの「相対性理論」や、ラッセルとホワイトヘッドの『数学原理』など、科学史上の重要な著作と並ぶ必読の古典とされました。
1968 年に第 1 巻の初版が出版され、1976 年までには 100 万部以上を売り上げました。
ビル・ゲイツはこのシリーズについてこう評価しています。
「もし自分が本物の優れたプログラマーだと思うなら、『コンピュータのプログラミング技法』を読むべきだ。もしこの本を読み終えたら、必ず私に履歴書を送ってください」
1977 年、彼はこの本の印刷をより美しくするために、組版システムの開発を決意しました。そして 8 年後、TeX を携えて復帰しました。
TeX は、特に複雑な数式を扱う際、世界中の学術組版において最も信頼される選択肢となっています。
2025 年現在、既刊巻は第 1、2、3、4A、4B 巻であり、今後もさらに多くの巻が出版される見込みです。
第 1 巻から第 5 巻は、順次処理マシン向けのコンピュータ・プログラミングの中核的内容を説明することを目的としており、第 6 巻と第 7 巻のテーマはより専門的ですが、それでも重要な意味を持っています。
ちなみに、彼の中国名「高德纳（ガオ・ドゥーナ）」は、1977 年の中国訪問前に、友人である清華大学「姚班（ヤオ・クラス）」の父こと姚期智（アンドリュー・ヤオ）氏の夫人、儲楓（フランシス・ヤオ）氏によって名付けられたものです。
クヌース氏は風変わりな人物でもあります。例えば、彼の著作から誤りを 1 つ見つけた人全員に 2.56 ドルを報酬として贈っています。これは「256 ペニーが 16 進数の 1 ドル（256 pennies is one hexadecimal dollar）」であるためです。
中国の掲示板サイト「水木（Shuimu）」には、クヌース氏に関する 18 のエピソードがまとめられています。
出典：https://mp.weixin.qq.com/s/jmEhfkw_3w2sDuACQCwTOQ
「Vibe Coding」の先駆け
クヌース氏にとって、プログラミングとは技術であると同時に科学であり、芸術でもあります。
日常生活もプログラミングに似ています。あることを愛していれば、その中に美しさを取り入れることができるのです。
組版システム TeX は彼に「リテラル・プログラミング（文学的プログラミング）」という概念を思い浮かばせました。
リテラル・プログラミング・パラダイムは、コンピュータに強制される従来の方法や順序でプログラムを記述するのではなく、プログラマー自身の思考の内在的な論理と流れが求める順序でプログラムを開発することを可能にします。
彼にとって、「リテラル・プログラミングは、TeX プロジェクトから派生した最も重要なもの」でした。
後に、クヌース氏はこう回想しています。
「それは私がかつてないほど迅速に、信頼性の高いプログラムを書き、保守することを可能にしただけでなく、1980 年代以降の私にとって最大の喜びの源となりました。時には、それは実際に不可欠なものでした」
「MMIX メタシミュレータのような他のいくつかの大規模プログラムは、私が見た他のいかなる方法論を使っても書くことはできなかったでしょう。その複雑さは私の限られた知能を挫折させるほどでした」
「リテラル・プログラミングがなければ、私のキャリアプラン全体が崩壊していただろう。……リテラル・プログラミングは、あなたが次の段階へ進むために必要なツールなのです」
完全にそう言えるでしょう。「Vibe Coding（ヴァイブ・コーディング）」はリテラル・プログラミングと一脉通じるものです。ご老人自身が本物の Vibe Coding を体験したかどうかは定かではありませんが。
神童から計算機科学の全才へ
クヌース氏は幼い頃から「並外れて賢明」でした。
彼が 8 歳の時、あるキャンディーメーカーが小学生向けの知的クイズ大会を開催しました。それは「Ziegler's Giant Bar（キャンディーメーカー名および商品名）」という文字列に含まれる文字を使って、できるだけ多くの英単語を作るというものでした。
少年クヌース氏は胃の痛みを装って 2 週間自宅にこもり、分厚い辞書を使って 4500 個の単語をリストアップしました。審査員が把握していたのは 2000 語だけでした！
これにより、彼のクラスは優勝（賞品はテレビと全員へのジャイアント・バー 1 本）し、彼個人もソリを 1 つ獲得しました。
ケース工科大学（現ケース・ウェスタン・リザーブ大学）での数学の研究成績は極めて優秀で、学部を修了する頃には、大学から数学の修士号を授与されました。
1963 年、カリフォルニア工科大学で数学の博士号を取得しました。
1963 年から 1968 年にかけて、カリフォルニア工科大学で助教授、准教授を歴任しました。
1968 年から 1992 年まで、スタンフォード大学で准教授、名誉教授などの一連の教授職を務めました。
1993 年より、スタンフォード大学「コンピュータのプログラミング技法」名誉教授（Emeritus）。
統計によると、クヌース氏は生涯に 100 以上の大小の栄誉を受賞しており、その一部は以下の通りです。
参考資料
https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf
https://valeman.substack.com/p/donald-knuths-30-year-problem-solved
https://mp.weixin.qq.com/s/jmEhfkw_3w2sDuACQCwTOQ
https://mp.weixin.qq.com/s/PkrJnuvtrL0OCJXzRPCxxA
https://mp.weixin.qq.com/s/XIcafYS9PbNgE2cMYHfQ5w