なぜすべてカーネルにあるのか?
Why is it all in the kernel? (lawrencecpaulson.github.io)
要約
最近、Collatz予想の反証が発表されましたが、それはLeanカーネルのバグに起因するものでした。この記事では、証明支援システムにおけるカーネルの役割と、証明オブジェクト(proof objects)の必要性について論じています。証明オブジェクトは独立した検証を可能にしますが、そのメモリ負荷は大きく、カーネルのバグを検出できない場合もあると指摘しています。また、数学の構築における「盗み」(postulating)と「誠実な労働」(honest toil)の対比を挙げ、カーネル外で数学的構造を定義することの重要性を強調しています。
全文翻訳
なぜすべてがカーネル内にあるのか?
2026年7月30日
general Lean Isabelle HOL system philosophy memories
センセーショナルなニュースです!Collatz予想が否定されました。Ramana Kumarがその否定を証明しました。この証明はLeanでチェックされ、独立したNanoda型チェッカーでも再確認されました。残念ながら、その証明は間違っていました。Leanカーネルのバグが悪用されたのです。Nanodaもエラーを検出できませんでした。今、私がこれを自慢するために書いているわけではありません。健全性バグはIsabelleでも発見されていますし、他の多くの証明支援系でも同様です。明日、新たな、そして恐ろしいバグが発見されるかもしれません。それにもかかわらず、ここにはいくつかの教訓があります。さあ、始めましょう!
Collatz予想
この有名な予想は、ほぼ1世紀にわたり、真面目な数学者と奇妙な主張をする人々の両方の注意を引いてきました。それは次の手順に関係しています。数Nから始めます。次にこのステップを繰り返します:Nが偶数なら2で割ります。奇数ならNを3N+1とします。Collatzは、この手順がどんなNから始めても必ず1に到達すると予想しました。広範なテストでも、単一の反例は見つかっていません。最近の研究では、言語モデルが予想に対する反例を見つけるのに非常に優れていることが示されています。Collatz予想はどうでしょうか?これを解決すれば、まさにセンセーションを巻き起こすでしょう。
証明オブジェクトの死荷重
半世紀前から知られているように、証明オブジェクトは不要です。Robin Milnerは、証明支援系をサポートする特定の目的のためにML言語を設計しました。抽象型という概念を通じて、証明カーネルはプログラムの他の部分から安全に保つことができました。推論規則は抽象型内に限定され、定理を作成するためのAPIとなります。
それにもかかわらず、私たちのコミュニティの多くは証明オブジェクトの格納に固執しています。特に、証明オブジェクトは独立にチェックできる証明書であると指摘しました。しかし、証明支援系のカーネルを通過した健全性エラーを独立した証明チェッカーが検出した例は、私の知る限り一つもありません。Collatzの場合、見たように、Nanodaも騙されました。証明オブジェクトが表すメモリの負担を考えると、これは故障に備えてスペアカーをトレーラーに牽引してどこへでも運転するようなものです。そして車は故障しますが、驚くべきことに、スペアカーも機能しません。そして、車が故障した正確な理由は、スペアカーを牽引する負担でした。なぜなら、証明オブジェクトを持つ証明計算だけが、すべてをカーネルに入れる必要があるように見えるからです。
盗みか、誠実な労働か
20世紀のほとんどの間、論理学者は可能な限り少ない公理を仮定し、そこから数学の残りを導き出しました。おそらく彼らはRussellのパラドックスやその他のパラドックスを心配していたのでしょう。おそらく彼らは単に倹約家だったのでしょう。この見解は、Russell自身によって最もよく述べられているかもしれません。
私たちが欲しいものを「仮定する」方法は多くの利点があります。それは盗みが正直な労働よりも優れているのと同じ利点です。他の人々に任せて、私たちの正直な労働を進めましょう。(Russell, 1919)
したがって、噂によれば、Leanのバグはカーネル内のネストした帰納型によって引き起こされたことは注目に値します。Rocqの健全性バグの多くは、カーネル内の再帰関数を含むパターンマッチングによって引き起こされました。従属型理論が、より基本的な計算から再帰のようなものを表現するのに十分な表現力を持たない理由が、私は正確にはわかりません。理由は技術的なものでしょう。しかし、はっきりさせましょう:集合論と単純型理論では、非常に少ないことを仮定する必要があります。集合論は、集合を導入するためのいくつかの原則を提供します:和集合、分離、対、置換。単純型理論は、論理とλ計算の少しを提供し、それは型付き集合論を与えます。ここで、集合はブール値関数です。そして、誠実な労働によって、帰納的定義、レコード、再帰的データ構造、および帰納的関数を、パターンマッチングや部分関数を含む非常に一般的な設定で取得できます。記号的な二項演算を使用して数値計算を実行できます。これらすべてが原始公理に基づいて定義されており、仮定されているのではなく、カーネルの外にあり、矛盾につながることはありません。
1980年代、私がMartin-Löf型理論を扱っていた頃、再帰関数の表現に関する問題が生じました。理論は原始帰納の形式しか認識しませんでした。しかし、理論は高階型も認めており、より強力な形式の帰納の可能性を与えていました。誠実な労働の伝統で数学を学んだ私は、Martin-Löf型理論内で、広大な終端帰納関数の空間を表現できるコンビネータのシステムを定義するために(本当に骨の折れる作業でした)取り組みました。しかし、このゲームのやり方を理解していませんでした。質問に対する正しい答えは、一般的な帰納の概念でMLTTを拡張することでした。そして、それはシンプルかつエレガントに行うことができたと認めなければなりません。私のやったことを理解した人がいたかどうかはわかりません。数年後、私はその論文が「PaulsonはMLTTを帰納で拡張した」というコメントとともに引用されているのを見ました。彼らは、誰かが誠実な労働によって帰納を獲得するとは想像できませんでした。
誠実な労働とはどのようなものか?
証明支援系の実装者が「盗み」の選択肢を選ぶ理由はわかります。なぜなら、誠実な労働は本当に岩を砕くようなものだからです。多くの目標の中で最も簡単なのは再帰的データ構造です。帰納的定義は、集合上の単調作用素に変換できます。最小不動点が帰納的定義を与え、共帰納的定義を好む場合は、最大不動点を使用します。Isabelleでは、これらの構成を型にリンクすることはめったにありませんが、再帰的データ型は重要な特殊ケースであり、現在は有界自然数ファンクターを通じて一般的かつ洗練された方法で処理されています。
第一原理から再帰関数を構築することは特に面倒です。まずwell-founded relationから始め、well-founded inductionによって目的の再帰関数の存在を証明します。MLTTでの私の帰納に関する作業は、ある程度役立ったので、完全に無駄だったわけではありません。Isabelle/HOLは、パターンマッチングや終了チェックを含む、非常に一般的な再帰関数定義をサポートするようになりました。そして、これらのすべてはカーネルの外に安全に配置されています。
証明オブジェクトが、より大きな健全性保証につながると宣伝されることがあるという皮肉があります。逆が明らかに真実です。健全性があなたの主な関心事であるなら、HOL LightまたはHOL41を選ぶべきです。Isabelleはそれらよりも多くのバグがありましたが、数は少なく、確かに他のいくつかのシステムよりもはるかに少ないです。