証明とプログラムは同じものだった――数学とコンピューターを結ぶ驚異の対応(Proofs and Programs Are the Same Thing),理論,695
動画「証明とプログラムは同じものだった――数学とコンピューターを結ぶ驚異の対応(Proofs and Programs Are the Same Thing)」の内容について、裏話や雑学を交えながらわかりやすく解説します!
1. この動画のテーマ:「カリー=ハワード対応」とは?
動画で扱われているメインテーマは、論理学・数学とプログラミング(計算機科学)の間に存在する美しい一対一の対応関係「カリー=ハワード対応(Curry-Howard Correspondence)」です [00:40]。
一言で言うと、「数学の命題=プログラミングの型(Type)」であり、「命題の証明=その型を持つプログラム(項・値)」であるという発見です [00:29]。
動画で紹介されている対応関係のまとめ:
-
命題 $A \to B$(AならばB) = A型の値を受け取ってB型の値を返す関数 [06:58]
-
命題 $A \land B$(AかつB) = A型とB型を合わせたペア(タプル / 構造体) [07:46]
-
命題 $A \lor B$(AまたはB) = A型かB型かのどちらかを持つUnion型(直和型) [08:02]
-
証明の簡略化(整理) = プログラムの実行・計算(ベータ還元) [09:01]
2. 業界話・裏話&雑学で味わう歴史と背景
💡 雑学1:実は「狙って作られた」わけではなく「偶然一致した」!
動画でも触れられている通り、1930年代の論理学者(ダフィット・ヒルベルトやアロンゾ・チャーチ)と、計算機科学の先駆者(アラン・チューリングら)は、全く別々の目的で研究をしていました [01:25, 04:13]。
-
論理学者は「数学の証明って本当に完璧に形式化できるの?」を追求。
-
計算機科学者は「機械的な計算ってどこまでできるの?」を追求。
それぞれが極限まで構造を削ぎ落とした結果、ハスケル・カリーやウィリアム・ハワードによって「え、やってること全く同じじゃん!」と後から気づいたのです [04:35, 05:01]。この奇跡的な一致が学問の面白さと言えます。
💡 業界話:プログラミング言語「Haskell」の由来
カリー=ハワード対応の名の由来にもなっている数学者ハスケル・カリー(Haskell Curry) [04:35]。
実は、関数型プログラミング言語として非常に有名な「Haskell(ハスケル)」は、彼のファーストネームから名付けられています。また、複数の引数を取る関数を1つの引数を取る関数の連鎖に変換するプログラミング手法「カリー化(Currying)」も彼の名前に由来しています。
💡 雑学2:「証明」ができるプログラミング言語たち
動画内に登場する Lean(リーン), Coq(コック), Agda(アグダ) は、業界では「証明支援系(Proof Assistant)」や「インタラクティブ定理証明器」と呼ばれます [13:11]。
-
Lean: 現在、数学界で爆発的に普及が進んでいます。元々はMicrosoft Researchが開発を開始し、数学者フィールズ賞受賞者のテレンス・タオ氏などもLeanを用いた現代数学の形式化プロジェクトに熱中しています。動画にある数学ライブラリ「mathlib」には、世界中の数学者が協力して数学の定理を登録し続けています [15:36]。
-
Coq: フランスのINRIAで開発された老舗の証明支援系です。動画で紹介されている「CompCert」というC言語コンパイラは、Coqを用いて「コンパイル結果に絶対バグ(バグを生むバグ)がないこと」を数学的に証明したことで、航空宇宙や原子力などの超高信頼性が求められる業界で有名になりました [15:10]。
3. 動画の全体的な流れと要点
-
歴史的背景 [01:00]
数学を記号のルール(形式化)として扱おうとしたヒルベルトの計画や、チャーチのラムダ計算・チューリングの計算模型が結びついていった経緯。
-
命題と型の対応構造 [06:16]
論理の記号(かつ、または、ならば)が、プログラミング言語におけるデータ構造や関数とどう対応しているかの解説。
-
証明の実行と直感主義論理 [08:53]
「証明を整理する作業」が「プログラムの実行」と同一であること。また、「存在することを証明するには、実際に作ってみせなければならない」という直感主義論理(構成的数学)との相性の良さ [10:20]。
-
コンピューターによる証明検証(型チェック) [11:13]
コンピューターは数学の「意味」を理解しているのではなく、プログラムの「型チェック(型検査)」を行うことで、証明に一切の不備がないかを厳密に確かめている点 [12:16]。
-
現代への応用と限界 [16:24]
依存型(Dependent Types)を利用して「バグが存在しないプログラム」を最初から作る手法や、証明からプログラムを自動抽出する技術 [17:14, 18:55]。ただし、通信や状態変更といった現実のプログラムの複雑さとの兼ね合いなど理論的な限界もある点 [19:46]。
動画の該当URL: 証明とプログラムは同じものだった――数学とコンピューターを結ぶ驚異の対応
動画の内容をベースに、さらに深掘りした追加事項を雑学・業界話を交えて解説します。
1. 発見の「偶然性」と、Howardの原稿が「コピーで回った」話
動画でも触れられている「狙って作ったわけではなく、後から気づいた」という点は、実はもっと劇的です。
William Howardが1969年に書いた原稿は、正式にジャーナルに投稿されることなく、コピーが手渡しで回るという形で広まりました。彼自身が後に語ったところによると、当時は「こんな対応関係があるよ」という程度のメモで、大きな発見だとは思っていなかったそうです。それが1980年にH.B. Curryの80歳記念論文集に載るまで、正式な出版を待った形になります。
興味深いのは、同じ頃に独立して似たような気づきを持っていた人が複数いたこと。Joachim Lambek(圏論からの視点)、Jean-Yves Girard(System F)、de Bruijn(Automath)などです。結果として「Curry-Howard」という名前が定着したのは、歴史的な偶然と、Philip Wadlerなどの後世の研究者たちが整理して広めた影響が大きいです。
2. 「Haskell」と「Currying」の名前の由来、もう少し詳しく
動画でも触れられていましたが、関数型言語HaskellはHaskell Curryのファーストネームから取られています。さらに面白いのは、**Currying(カリー化)**という手法自体も彼の名前由来だということ。
Curryは「組み合わせ論理(Combinatory Logic)」の大家で、複数の引数を取る関数を「1引数の関数の連鎖」に変換する考え方を徹底的に推し進めました。現代の関数型言語で当たり前に使われる「部分適用」や「高階関数」の基礎が、ここにあります。
ちなみに、Curryは「パラドックスから逃げない」というスタンスで知られていました。1930年代に自分の体系に矛盾が見つかったとき、ChurchやKleeneが体系を縮小して一貫性を保とうとしたのに対し、Curryは「パラドックスを直視して研究を続ける」と宣言したそうです。この姿勢が、後の型理論や証明支援系の「厳密にやる」精神にもつながっています。
3. 証明支援系の「業界内エピソード」
LeanとTerence Taoの「ハマり方」
動画で触れられているmathlibとTao氏の関係は、近年かなり加速しています。Taoは最初「もう二度とやらないかも」と言っていたのに、数週間後には別のプロジェクトでLeanを使い始め、「中毒性がある」とまで語るようになりました。
特に面白いのが、Liquid Tensor Experiment(Peter Scholzeの結果を形式化したプロジェクト)がきっかけで、数学者コミュニティが一気にLeanに注目したこと。Scholze自身が「この証明は正しいか自分でも自信が持てない部分がある」と漏らしたのを、Leanで厳密に検証して解決したんです。これが「数学者が本気で使うツール」という認識を一気に変えました。
現在のmathlibは、数十万人規模の定理・定義が集まり、AIとの連携(AlphaProofなど)も進んでいます。「手書きの数学が劇的に変わる」とLeanの開発者Leonardo de Moura自身が語るほどです。
CoqとCompCertの「本当のところ」
動画で紹介されているCompCertは、確かに「バグのないコンパイラ」として航空宇宙や原子力分野で使われてきました(Airbusやドイツの原子力関連など)。ただし、最近の業界話として「完全にエンド・ツー・エンドで検証されているわけではない」という指摘も出ています。
具体的には、最適化やコード生成部分はほぼ検証されていますが、フロントエンドの一部やアセンブラ・リンカ周りは未検証のままです。形式検証の「定理で保証されている範囲」と「ユーザーが期待する範囲」にズレが生じやすい、という典型的な話です。それでも、普通のコンパイラ(GCCやLLVM)に比べてバグが極端に少ないのは事実で、fuzzing(Csmithなど)でもほとんど壊れないという実績があります。
4. 直感主義論理との相性が「なぜ」良いのか、もう少し深く
動画で触れられている「存在を証明するには実際に作ってみせなければならない」という直感主義(構成的数学)の立場は、Curry-Howardの核心です。
古典論理では「排中律(Aか¬Aのどちらかが必ず真)」を認めますが、これをプログラムに対応させると「どちらかが必ず存在するが、どちらなのかはわからない」という状況になります。これは計算としては不自然です。一方、直感主義では「実際に構成できるものだけが存在する」とするため、証明=プログラムの対応が綺麗に成り立ちます。
この考え方が、依存型(Dependent Types)につながります。「この配列はソート済みである」という性質を型として直接書けるようになり、「バグが存在しないプログラム」を型レベルで保証できるようになるわけです。
5. 現代の広がりと「限界」の話
動画の最後で触れられている限界(通信や状態変更など)は、実は活発に研究されている分野です。線形論理やセッション型、モナドなどを使って、副作用や並行性を型システムに取り込む試みが続いています。
また、最近では「コードのリファクタリング」と「数学の理論の再定式化」がCurry-Howard的に対応する、という視点も出てきています。プログラムを整理する作業が、数学の概念をより良い形で捉え直す作業と本質的に同じだというわけです。
まとめると、動画で紹介された対応関係は「偶然の一致」から始まり、今や数学と計算機科学の両方を根本から変えつつある「共通言語」になっています。特にLeanの急速な普及とAIとの融合は、ここ数年で最も面白い動きの一つです。
もちろんです😊
数学の**「証明」とラムダ計算(Lambda Calculus)**は、一見すると別々の話に思えますが、実は現代コンピュータ科学では「ほぼ同じものを違う言葉で見ている」と言われるくらい深く結び付いています。
① 証明は「プログラム」である
数学では、
「この命題は正しい」
ことを、論理的な手順で示します。
例えば
- AならB
- Aは真
- よってB
という流れですね。
プログラムでも
入力 A
↓
処理
↓
出力 B
という構造になっています。
実は
証明 = 入力から結論を作るアルゴリズム
と考えられます。
この考え方を
Curry–Howard対応(カリー=ハワード対応)
と呼びます。
これは
「証明はプログラムである」
という、理論計算機科学最大級の発見です。
② ラムダ計算とは?
ラムダ計算は1930年代、
アロンゾ・チャーチ
によって考案されました。
驚くことに、
ラムダ計算には
- if文
- while文
- for文
- クラス
などは一切ありません。
あるのは
λx.x
だけです(笑)
つまり
「関数を作る」 「関数を呼ぶ」
これしかありません。
例えば
λx.x+1
は
「1を足す関数」
です。
これに
5
を渡すと
(λx.x+1) 5
↓
6
になります。
Pythonなら
lambda x: x + 1
とほぼ同じですね。
③ なぜラムダ計算はすごい?
衝撃的なのは
これだけでコンピュータ全部が作れる
ことです。
実際、
理論上は
- 足し算
- 掛け算
- リスト
- 木構造
- 再帰
- AIアルゴリズム
全部書けます。
④ 「数字」すら関数
もっと驚く話があります。
ラムダ計算では
数字もありません。
例えば
0
は
λf.λx.x
です。
1は
λf.λx.f x
2は
λf.λx.f(f x)
3は
λf.λx.f(f(f x))
つまり
数字とは
「何回関数を適用するか」
だったのです。
これをチャーチ数と呼びます。
⑤ 業界ではどう使われている?
ラムダ計算は大学の遊びではありません。
実際に
- Microsoft
- Meta
では、
コンパイラや型理論、プログラム検証などの基礎として使われています。
関数型言語
- Haskell
- OCaml
- F#
はラムダ計算が土台です。
最近では
RustやSwiftにも
ラムダ(クロージャ)が普通にあります。
⑥ 証明支援システム
最近は
「証明を書くソフト」
があります。
例えば
- Lean
- Coq
では
数学の証明を書くと、
コンピュータが
「そこ飛躍してます」
「この定理使えます」
と教えてくれます。
面白いことに、
ここでも内部では
ラムダ計算が動いています。
⑦ AIとの関係
ChatGPTのようなAIはニューラルネットワークが中心ですが、
AIを**「絶対に間違えないようにする」**研究では、
証明支援系の技術が重要になっています。
例えば
- このプログラムは必ず終了する
- この暗号は安全
- この飛行機制御ソフトは暴走しない
といったことを数学的に証明するために、ラムダ計算や型理論が活躍しています。
⑧ 業界の雑学
理論系プログラマーには、こんなジョークがあります。
「ラムダ計算では全部関数。」
「オブジェクト指向では全部オブジェクト。」
「C言語では全部ポインタ。」
どの世界でも、「すべてを一つの考え方で表そう」とする美学があるのです。
また、研究者の間では
「Haskellを理解すると世界の見え方が変わる」
という冗談めいた言い回しもあります。実際、関数を組み合わせて考える発想が強く身につくため、プログラムだけでなく数学の見方も変わると言う人は少なくありません。
まとめ
数学の証明とラムダ計算は、
- 証明:命題が正しいことを論理的に示す手順
- ラムダ計算:関数だけで計算を表す最小限の計算モデル
- カリー=ハワード対応:**「証明はプログラム、命題は型」**という深い対応関係
という形で結び付いています。
そのため、現代のプログラミング言語、コンパイラ、定理証明、形式検証、さらには安全性が重要なソフトウェア開発まで、これらの理論はコンピュータ科学の土台として幅広く活用されています。
大人のストレッチ