Leanで証明を書くとはどういうことか、DFAの形式証明で見せる
Anatomy of a Lean proof for software engineers
Sipserの教科書の問題を題材に、LeanとMathlibで言語の正規性を形式証明した記録。最下位ビットから読む加算器DFAを構成し、反転の閉包性を使って元の言語の正規性を導く。型付き言語と帰納的証明に慣れたエンジニアなら追える構成で、システムの性質を機械的に証明する実際の流れが見えてくる。
もしDFAを構成してB^Rを認識できるなら、B^Rは正規言語だと結論できる。B^Rを反転したものがBなので、正規言語の反転の閉包性を使ってBも正規だと結論でき、これで解法が完成する。
HNでの議論
67- thom
だからこれは全部素晴らしいんだけど、チェックは通るものの、重大な意味論的エラーが簡単に隠れている可能性がある50万行以上のLean証明を受け入れろと言われている身としては、どういう計画なんだ?実行環境が約束する優れた堅牢性にもかかわらず、これらは独特に壊れやすいソフトウェア成果物のように思える。
- WalterGR
投稿者さん:あなたの記事では、目次が表示されるはずの場所に「[Contents]」と表示されていますよ。
- fooker
Leanや証明支援系を理解しようとする前に、まず関わる論理の基本的な理解を得てください。この記事はそれをある程度飛ばしていますが、かなり込み入っているので妥当です。
たとえ大量の数学の証明を書いたことがあっても、通常は証明自体の言語や論理を学んではいません。また、たとえ優れた計算機科学者であっても、論理は単なるAND、OR、NOTではありません。
以下は必要な読み物です。より良い情報源を自由に見つけてください。Wikipediaでも十分です。
* 証明木 - https://en.wikipedia.org/wiki/Method_of_analytic_tableaux
* 構成的/直観主義論理 - https://en.wikipedia.org/wiki/Intuitionistic_logic
* 証明と型 - https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
* (不)完全性 - https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
* コンパクト性 - https://en.wikipedia.org/wiki/Compactness_theorem
- whattheheckheck
仕様と証明のインターフェースはそれほど明確ではない。仕様を理解するために証明を見なければならないことがよくあるからだ。そして、証明の中に奇妙なものを見つけたら、それは何かがおかしいという良い兆候だ。
そう、これは私が何かを緑だと言ったとき、私の緑があなたの緑だとどうやってわかるのか、というようなものだ。数学的にモデル化されたシステムの証明は、それが同じプログラムであるか、トレース・リファインメントを行っているのでない限り、それを実装する記号に何らかの形で結びついているわけではない。そして、ビジネス機能を果たす上でプログラムが正しいことを証明する方法は、実際に動かしてみる以外にない。かなり計算的に既約、状態機械を構築する状態機械だ。
- woggy
人々がLeanを主にソフトウェア仕様言語として使い、必ずしもすべてを証明しようとしないことはできるのだろうか、と興味がある。
モジュールの意味と法則を指定するために使い、設計を正確で検証可能にし、実装においてそれらの法則に対するプロパティベーステストを実装できるようにする。Leanは設計についてより正確に考えるためのツールになる。