1. くわラジ
  2. #29 証明は"探索ゲーム"だ——Le..
#29 証明は"探索ゲーム"だ——Lean・Isabelleで学ぶ形式手法の証明の仕組み
2026-11-20 56:36

#29 証明は"探索ゲーム"だ——Lean・Isabelleで学ぶ形式手法の証明の仕組み

おたよりを送る

形式手法とは、結局なにをしているのか?形式手法シリーズ3回目の今回は、Lean・Isabelle などの定理証明支援ツールを使い、契約による設計の考え方でプログラムを数学的に証明する方法を kuniwak に聞きました。「証明ってどういう仕組み?」という問いを、定理・公理・補題の構造からゆるく深掘りします。


前回のプロパティベースドテスティングから一歩進んで、今回はいよいよ本丸です。証明エディタで"グリーン"を広げていく試行錯誤、CIでの検証、型クラスと証明課題、数学的帰納法が入ると自動証明が急に難しくなる理由などを話しています。へんてこ は「それってライブラリの依存関係と同じでは?」「完全にゲームですね」と噛み砕いていきます。後半は、プログラミング言語意味論や Featherweight Java を手がかりに、ソフトウェア開発・設計へ形式手法をどう適用するかを考えます。形式検証が広まらない一番の理由にも踏み込みます。


▼チャプター

オープニング

定理証明支援ツール(Lean・Isabelle)の概要

CIでの検証とエディタでの試行錯誤

証明の仕組みと定理・公理の構造

数学的帰納法と自動証明の難しさ

ソフトウェア開発・設計への形式手法の適用

エンディング


▼この回で話していること

・定理証明支援ツールとは?Lean と Isabelle の違いと使い心地

・証明をCIでチェックする使い方とエディタでの試行錯誤

・定理・公理・補題の関係と「証明木」という考え方

・ゲーデルの不完全性定理はなにを示したのか

・数学的帰納法で自動証明が難しくなる理由と Isabelle の Sledgehammer

・契約による設計の事前条件・事後条件と定理の関係

・プログラミング言語意味論とは?Featherweight Java の狙い

・形式手法で結合バグを仕様段階で見つけられる?E2Eテストとの関係


▼こんな人におすすめ

・形式手法に興味はあるけど、難しい用語で挫折しそうな人

・Lean や Isabelle を触ってみたいソフトウェアエンジニア

・テストだけでなく「証明」で品質を担保する考え方を知りたい人


▼関連リンク

- くわラジ 公式サイト: https://kuwa-raji.henteko07.com/

- くわラジ Spotify: https://open.spotify.com/show/6uUjalUT94ugSgtLI5WF6a

- くわラジ Apple Podcasts: https://podcasts.apple.com/jp/podcast/id1894147982


くわラジ(もっと詳しく教えてくださいラジオ)は、スーパーエンジニアの kuniwak に一般エンジニアの へんてこ が「もっと詳しく教えてください」と質問しながら技術を深掘りする、ゆるくてディープな技術雑談番組です。感想は X でハッシュタグ #くわラジ をつけてつぶやいてください。


#くわラジ #形式手法 #定理証明 #Lean #Isabelle #数学的帰納法 #契約による設計


- くわラジ 公式サイト: https://kuwa-raji.henteko07.com/

- くわラジ Spotify: https://open.spotify.com/show/6uUjalUT94ugSgtLI5WF6a

- くわラジ Apple Podcasts: https://podcasts.apple.com/jp/podcast/id1894147982


─────────────

YouTube: https://youtu.be/m19Oz8S3kro

Web: https://kuwa-raji.henteko07.com/

X: https://x.com/kuwa_raji

感想

まだ感想はありません。最初の1件を書きましょう!

サマリー

今回は、LeanやIsabelleなどの定理証明支援系が、定理・公理・補題を積み重ねて証明木を作る仕組みを解説する。証明はエディター上で試行錯誤しながら「グリーン」の領域を広げる探索ゲームで、見つかった証明はCIで高速に検証できる一方、数学的帰納法が入ると探索範囲が増えて自動証明が難しくなる。ゲーデルの不完全性定理や、前提条件を強めて証明可能な性質を得る考え方にも触れ、契約による設計との関係を考える。後半では、プログラミング言語意味論を使ってプログラムの振る舞いを証明する方法や、Featherweight Javaが型安全性を示すために機能を絞っていることが話題になる。仕様段階でコンポーネント間の結合バグを見つけ、E2Eテストを減らせる可能性が示される一方、証明にかかる時間や成功可能性を見積もれないことが形式検証の大きな課題とされる。Leanのライブラリ蓄積、証明しやすい言語設計、セキュリティへの応用にも話が広がり、形式手法を学ぶには教科書を読むのが近道だと勧めて締めくくられる。

Lean・Isabelleと証明エディター
前回、プロパティベースド・テスティングで、形式手法について考え方に慣れる、みたいな形で入り口を教えてもらったんですけど、
今回は、本丸の形式手法をどうやっていくのか、どうやってやっていくのか、というところを聞きたいなと思っています。
今回は、形式手法の中でもいろいろあるんですけど、前回はプロパティベースド・テスティングだったので、
そこからの延長線上にある契約による設計という理論を使って、数学的に証明していくという方法を説明していきたいと思います。
ツールは、リーンでもイザベルでもロック、昔はコックって呼んでましたね。でも、何でも大丈夫です。
ありがとうございます。ちなみに、このツールからして馴染みがないんですけど、リーンとかイザベルとかロックですかね、これらって何が違うんですか?
基づいている理論がちょっとずつ違うんですけど、でもできることはほとんど同じです。
どれもいずれも数学的な証明を、数学的、そうですね、だから、前に話しましたけど、人間はいつか死ぬ。アリストテレスは人間である。であるなら、アリストテレスはいつか死ぬ。
このような論章を助ける定理証明支援系、定理証明というのは数学的な証明ですけど、これを助けるツールというので大雑把に括ることができるツールです。
その中でも、特にリーンはコマンドラインでいろいろなことができるというのが最近の有利かなと思っていて、結構プログラマーフレンドリーかなという印象がありますね。
ただ、個人的には証明は一番イザベルがやりやすいかなという印象も抱いているという感じです。
リーンの場合はインターフェースとしてCLIがサポートされているみたいな。
そうですね。イザベルにもCLIのやつあるんですけど、リーンの方が私にとっては触りやすい、とっつきやすいCLIの見た目をしているという感じですね。
エンジニアフレンドリーみたいな。
そうですね。CIとか組み込みやすい感じですね。
で、イザベルとかの方はGUIが付いている。
GUIがくっついているのと、もともとイザベルはサーバーがありますね。
イザベルサーバーというのがあって、そこと対話するみたいなこともできるので、フロントエンドは選べます。
クライアントは選べると。
昔はEMACSを接続できるプルーフジェネラルというのがあったんですけど、最近使えなくなっちゃって、代わりに最近はVSコードが接続できるようになりましたね。
例えば、組み込みのエディターはJeditベースのエディターになっていますね。
多分これ徐々にVSコードに置き換えていきたいんだろうなとは思っています。そんな雰囲気を感じています。
じゃあGUIというよりかは、テキストをイザベルのサーバーに対して送って、それを評価して帰ってきた何かを見るみたいなことなんですね。
イメージとしてはそんな感じですね。
それのフロントエンドがVSコードなのか、昔だったらEMACSなのかというような違いがクライアントもある。
その部分がリンの場合はCLIから呼び出せるということですか?
呼び出せる、そうですね。
ERRORというツールがあって、そこで結構いろいろな、Rubyで言うとRAKEみたいなコマンドがあるじゃないですか。
RAKEでいろいろなことができると思うんですけど、あれみたいな感じでいろいろなことができるという感じですね。
イザベルもイザベルコマンドというのがあるんですけど、あんまり私にとっては使いやすいとは感じなかったですね。
じゃあ、形式処方をやっている人からすると、CLIに普通に組み込んだりするものなんですか?
2つの目的があって、基本的には組み込めるが答えなんですけど、
まず数学的な証明というのは、機械にここの部分探しといてっていうふうに結構ぶん投げるタイプのコマンドと、
ここの部分をダイレクトに書き換えてねって言って、機械がここをやればいいんだってすぐわかるようなコマンドの大雑把に分けてこういう2つがあるんですね。
証明ってすごく探索とかには時間がかかるんですよ。
こことここの部分が繋がるらしいんだけど、地名なので省略みたいな状態になっちゃってると。
なのでそこを探索するんですね。こことここが繋がるかなみたいな証明のキーを探索するんですけど、
その探索をするっていうコマンドがあると、ちょっとだけ時間がかかったりとかタイムアウトしたりする時があるんですね。
なので、証明を探させるみたいなそういうことにはCLIは使えないんですけど、
もう既に探し済みであって、かつ探索コマンドが1msとか10msとかで終わるってことがわかっているんだったら、
CLIの中でこの証明は通るかみたいなことはチェックできる。
やることはあるけども、そこまで一般的ではないっていう。
私はイザベルのプロジェクトでやってました。
CLIでチェックするってことは。
でも基本的にはエディターと直結しているっていうところからわかる通り、試行錯誤ってことですよね。
そうです。
試行錯誤する前提ってことですよね。
人間が書いて、チェックして、書いて、チェックしてみたいないう試行錯誤が前提のものだから、
CLIで回すというより変わっているような。
そう。CLIはもう既に見つかった証明が正しいことだけを確認するみたいな感じで、
人間はそこの探索を担います。
ここの証明とここの証明をくっつけなきゃいけないんだけど、どうしたらいいかなみたいなとかっていうのを探すっていう、
そういうふうなゲームなんですよね。
一度その経路が見つかると、その見参はすごく高速に終わるんですよ。
さっき言ったように10msとか探索とか10msとかで終わるって。
なので、CI上で一応回せるっていうことになるんですね。
あともう1個、2つあるって言ったんですけど、
もう1個は特にイザベルとかは、
イザベルで書いたコードっていうのをPDFとかにプリントすることができるんですね。
なぜかというと、要するにすぐに論文にできるようになってるんですよ。
そういうものも組み込まれてるんですね。
テフみたいなことができます。
テフ、テック、いろんな読み方ありますけど。
ああいうことができるので、私はそれを印刷して証明を読んでました。
ちょっと紙に印刷して、改めて見てみたいな。
説明とかもつけて、他の人に理論として読めるようにして、
論章に間違いがないことが保証されてるプリントですよっていうふうにしてましたね。
なるほど、そういう使い方もあるよっていうようなところで、
やはり試行錯誤プラスアルファ、
そういう論文向けとか物理のアカデミックなところに出す用途が結構強そうですね。
一般的なソフトウェアエンジニアが使うような、ウェブのエンジニアが使うようなツールとは若干違いますね。
そうですね。特にエディターもかなり使い勝手が違っていて、
証明のエディターっていうのはすごくステートフルなんですよ。
普通のエディターもかなりステートフルですけど、
今どこまで証明が通っていて、ここまではOK、ここからダメっていうのに塗り分けることができるんですね。
なので、自分が今触っているところ、証明が通っているところまでが全部グリーンなイメージ。
それ以降、今描いてたりとか、動いてない部分がレッドな感じ。
だんだんそのグリーンな部分を進めていって、どんどんレッドを減らしていって描いていくっていう、
そんな感じのニュアンスのことをやっていきますね。
業ごとではないかもしれないんですけど、ある一定の括りごとにチェックしていって、
それが上から順番にチェックOK、チェックOK、チェックOK、みたいな感じのプレイブックみたいな感じですよね。
Pythonとかであるような。
そんなイメージですね。
ノートブックか。
Jupyter Notebookみたいな。
みたいな。
あんな感じになっていて、
定理・公理・補題と証明木
じゃあ一体そのプレイブックに書かれていることは何なんだって当然思うと思うんですよ。
ちょっと分かりやすい例を一つ考えてみるんですけど、
そんな分かりやすくないな、ごめんなさい。
これ例分かりやすいと、ハスケルやってる人にだとすごく分かりやすく伝わるんだけど、どうしたらいいかな。
まあまあ言ってみましょう。
言ってみましょう。
よくモノイドとかって言われてるものがあって、
邪魔の人たちで言うインターフェースみたいなものなんですけど、
ただしそのインターフェースはこのテストを通らなければならないっていう条件が課されているインターフェースなんです。
なるほど、外部に条件があるっていう。
そう、外部に条件がある。
このメソッドが生えてるだけじゃダメってことですね。
生えた上でこういう風な性質を満たさなきゃいけない。
例えばひっくり返しても大丈夫とか。
右と左をひっくり返しても同じになるとか。
そういう風な性質が課されているんですね。
っていうのがあったときに、例えばハスケルとかだとこういうのがあって、
メソッドみたいなものを持ってればOKになっちゃう。
つまり性質は確かめられてない。
お前がこれをモノイドだと言うんだったら確かにモノイドなんだろうっていう風なことをやってくれるんですよ。
でもこれ間違えてるとちょっとサンジ側見るんですけど。
メソッドの中身までは検証してないよね。
検証してない。
なんだけど、イザベルとかみたいなものによってくると全く同じような型クラスと言われているインターフェースみたいな機能があって、
それをやるときにその性質を満たしてないとインターフェースを実装したことにならないんです。
強制力がありますね。
強制力がある。
つまり私は今からこの配列クラスみたいなのを足しました。
こいつはモノイドだと思いますって言ったら、ほうほうわかった。
じゃあお前はこの性質が全部成り立つことを証明しなさいっていう証明課題が出るわけです。
新しく別軸で枝が入るっていう意味ですね。
こっちもやらないといけないよってお前がそう言うんだったらみたいな。
そうそう。
それが通らない限りそいつをモノイドとして使うことはできないっていうそんな感じ。
それがグリーンだとOKになってて、レッドが入っているとそいつはインターフェースとしては使えないっていう。
めちゃくちゃ面白いですね。
しかもそれは入れ子構造ですよね。
その先にもう一回インターフェースで、もう一回じゃあこの別のやつAってやつがモノイドだって言ったから
じゃあ次その中を検証してみたらじゃあ次Bってやつが出てきてそいつもモノイドだみたいな感じになって。
その通りです。
これは何が入れ子になっているのかってことが大事で、これは実は定理ってものが入れ子になっているってことなんですね。
これはまず定理っていうのを少し説明していきましょう。
定理ってよくその三変法の定理とかよく聞いてますよね。
定理一体何者なんでしょうって話ですね。
なんか誰か決めた人がいて決めた人というか発見した人がいてこういうルールあるわって。
でなんか全部試していったら証明できてよしじゃあこれをこういう定理と呼ぼうみたいな感じかなと思うんですけど。
定理ってのはまさにそうである前提が成り立つのであればあなたはこういうふうなことを結論しても良いっていうものが定理なんですね。
例えば二等辺三角形があった時に定角って言われているその二等辺三角形の線が同じものを上に向けて下にそこにあるものを定角って言いますよね。
これって等しいっていうのがちょっとこうイメージするとわかりますよね。
これはもし三角形が二等辺三角形ならば定角は等しいっていうなんとかならばなんとかっていう形になってるんですね。
これがいわゆる定理の形なんですけど。
この定理っていうのは他の定理とか公理って呼ばれてるこれはもうみんな無条件でない人たちと認めようって言ったルールがあって。
このいずれかのルールからくっつけて作っていくものなんですね。
段階的な許された論章だけをこうやって最初に公理っていうのから出発して公理からこれが言えるねこれが言えるねっていうのをやって小さな定理ができて。
その小さな定理を扱ってもっと大きな定理をどんどん証明していく。
そういうふうなゲームが数学の証明になっているんですね。
はいはいはい理解できました。
なので定理は入れ子構造なんです。
ある定理の証明に別の定理を使うことがよくあるんですよ。
でそれを入れ子構造で表現してでここまでないここの行はグリーンだけどその先からまだその定理を使ったもの依存している定理が依存した定理はもう ok だからその次じゃあその定理を使ったものをもう一回じゃあ証
明してみてみてどんどん続いていくってことですよね。
使える定理はグリーンのところにある定理だけなんですよ。
今まで証明済みって言われてるグリーンの領域にあるところしか使えないのでそこで定理を切り出してたりよくそういうふうな切り出してた定理のことを補大とか言い方をするんですね。
定理っていうのはこういうふうななんかそのあるその前提から季節こんなことが言えるっていうふうなもののうちなんとなく切れ目のいいところのことをよく定理って言うんですよね。
その切れ目のいいところ定理って言うんだけどその定理を証明するのに必要なちっちゃな定理みたいなところを補大とか言い方をしてその補大っていうのがまあ定理と何が違うんだって言われたらほぼ同じなんですけどその
補大とかをいっぱいグリーンの領域に溜めていってとうとう本丸の定理を証明する。
そしてその証明した定理がまた他の人の別の定理に使われるとそういうふうな構造を持っていますね。
流度の違いですよねさっき言ってくれたのはその大きさの違いなだけですべては定理によって成り立つ定理っていうことですよね。
リーンとかイザベルとかで証明するものに関してはすべて。
今の構造ってすべてソフトウェアエンジニアであれば絶対使ってるライブラリープラス依存関係と全く同じ構造だなと思ったんですが。
本当にそうですね。その通りです。
ただフレームワークみたいな概念がちょっとだけあるんですよ。
この 사고理っていうのがフレームワークみたいなものでどのフレームワークを使うかっていうのによって引き出せる期決と違うんですね。
よく故れとして知られているのがテレメルフランケルって言われている絶対不って言われてるやつなんですね。
ここに選択降りっていうのを追加すると絶対不 cって言ってよく数学で使われる。
あのやつになるんですけど えっとこの氷を c がいかにもいかがわしい結論が結構引き出せることができる
ので c を認めないって人たちの立場もいて zf と言われている立場だと思って そこらへんがフレームワークの違いになっていて
なかなか面白い それは流派の違いって言ってもいいぐらいですか
ただ選択氷ってこの c はすごく強力で これがないとなんかこんなことも言えないのみたいなことが言えなかったりするんですよ
そこが難しくて いかにもちょっと危ない変なことも出てきちゃうんだけどでもこれを仮定しないといろんな
ことが言えない なんか泣いたって思えることが証明できないみたいなことがあるんで
なかなか扱いに困っちゃうのが選択氷ですね だからあれですよね すごい単純化すると1たす1は2であるっていうことが言えない場合どうするのかってことですよね
なんかそのあるめちゃくちゃ前提となる何らかの定理が使えないっていう場合において 氷が足らないと使えない
これどうするのみたいな 氷をうまく選んであげる言いたいことに対してうまく選んであげなきゃいけないっていうのは
そういう意味は結構ありますね さっきの1たす1が2にならないってことはよくあるんですよ例えば
ブール大数と呼ばれているトゥルーとフォールスだけの世界 これ0と1だけでよく表すことがあるんですけどこれには2が存在しないわけです
1たす1は1なわけですよ 1or1なんで1になるっていう世界があって確かにそういう成り立たない世界が
いるこれ何が違ったかっていう定義が違ったんですね その定義その大数1っていう意味
たすっていう意味それぞれが違うセットを持ってきたから違う結論が出てきるよね なるほどたすという意味合いが違う
世界線なんですね そうですそうです
なのでこういうふうな定義とかっていうのをうまく使っていってだんだんと論章を進めていく
ですねさっきのモノイドとかっていうとこのブール大数っていうのは本当に形としては 同じでブール大数もこういうふうな
カタクラスみたいに作ることができるんですよ インターフェースが足し算っていうインターフェースがあって足し算はorですね
かけ算っていうインターフェースこれはandですねっていうのがあって あとは0と1っていう値だけがある
そんな感じのその世界を作ることができて そうすると各種のいろんな性質が成り立つんで
じゃあこいつはこういう数学的な構造として認めても良いみたいな証明を書いてあげると
イザベルの中ではそいつのインターフェースを持っているものとして扱うことができる そんな感じの世界観を持っていますね
なるほど でそうやっていって小っちゃい定理からどんどん積み立てていって自分がやりたい証明
っていうものを組み立てていく レゴみたいな感じで組み立てていくっていうのが
形式手法のやり方 ツールを使ったリーンとかそういうものを使ったやり方だよねっていうことなんですね
証明を今レゴに例えてもらいましたけど 結構よく例えられるのは木ですね 証明木って言い方をするんですけど木に例えることがよくあります
その木っていうのは根っこが氷なんですよ 氷って要するにみんながもうこれはねもう何かずっと言うことにするんだよっていうふうに決めたルールがあって
自明だよねっていうことですね そのルールから出発してずっとこういろんなことをたどっていって最初
あごめんなさい逆か言いたいことが根っこにあってこれをずっとこう論章をたどっていく 例えば1たす1が2っていうのは足し算の定義とかは遡っていったりするんですよ
あとは2の定義ってなんだっけって2の定義っていうのはサックサックゼロみたいなちょっといろいろそういうのがあって
そういうのとかをこうやってたどっていくと定義とかをたどって展開していくといつか定義とか氷にたどり着く
他の定義とか氷にたどり着くそうすると証明ができたことになる やっとやっとこのルート行けたわーみたいなことになる
不完全性定理と数学的帰納法
これから観察できる事実がいくつかあります 一つは失敗する証明ってあるじゃないですかって
行き詰まっちゃうってあるよね 証明できないって一体どういうことがこの木の中で起きてるのかっていうのとかが結構大事で
その行き詰まっちゃう木っていうのは行き詰まっちゃった証明つまりだいたい行き詰まっちゃう証明っていうのは定理にしようと思ってたことに反例があるんですよ
例えば二等辺三角形の定格は等しいっていう定理にちょっとこれこの三角形さ定格等しくないんだけどっていうのを出してくると
確かにみたいになったりする時があるかもしれない そうなった時にそれはえっと反例があるので証明ができない成功しないですね
その証明が成功しないことはどんな形で一緒に見えるかっていうといつまで経っても氷にたどり着けないんですよ
氷とか定義にたどり着けないどこにグルグル行っちゃってわかんないわかんない たどり着けないってでもむしろ逆ノット定理っていうのを証明しようとすると証明できちゃうんです
なるほどそれは反例があるから
反例があるっつってっていうのが見え方でどっちとも言えないってものもあるんですよ
それも面白くて証明できないどっちとも何とも言えないみたいなところもあってなかなか面白い世界になる
それはあのまだたどり着いてないだけなのかそれとも本当にわからないなのかで言うと
この解釈はちょっと私も苦しむ時があるんですけど
結構有名なその定理の中に不完全性定理って言われてるものがあってゲーデルの不完全性定理ってのがあって
ちょっとこの解釈私はあのちょっとそこまで自信があるわけじゃないんですけど
これは何か自然数とかその足し算とかっていうのは簡単なものを入れたような論理体系を考えてあげた時に
こういった事態が正しい論理だよつまり矛盾したりしないよってことをそいつ自体で証明できるかってことを考えた人がいるんですよ
これは前の前回に出したヒルベルトさんっていうのが数学自体に矛盾がないってことは数学を使って示せるだろうって思ってたっていうことの
延長線上にあるんですよもっと小さな数学ってもっと本当はもっと色々な微分積分とかありますけどそんなこととか言ったらなくて
自然数しかないだけの世界でもあってもそれが実は証明できないってことを示したのがゲーデルさんなんですね
それが証明できないってのは一体どういうことなのかっていうのが反例があるっていうようなことなのかそれとも
有限に証明を書いていってもたどり着けないような証明があるっていうことなのか
このどっちなのかってのはちょっと私は解釈がわからないんですけどともかく証明は成功しないつまり合理にくっつくことができないっていう証明が
どこにあるらしいってことをゲーデルさんは見つけたんですね
なるほどまあ一旦諦めろよっていうことだとは思うんですよね当然現実的には
そういうことですそういうことです
たどり着かないからまだ思考が足りてないのかどうかはわかんないけども
ある一定有限な現実時間においてはたどり着けなかったのでこれについては今のところ証明できないよねっていう
もう今のところというよりも証明できないですって言い切りだったんですよ
ゲーデルさんと関係でなのでヒルメイトさんの目論みは砕け散ったというわけですね
こんな簡単な体系であっても矛盾がないことを証明できないっていうことがわかってしまったので
マジかーってなったってやつですね
これは結構有名でよく誤解されがちな定義で数学が不完全になるっていうふうなことの詳細にされちゃったりして
そういう意味じゃないんだけどなみたいなことがあったりするんですけどそれはそういうことを言ってるんですね
なので基本的に証明っていうのはさっき言った通り木で木構造みたいな感じで
それがいつかその葉っぱが全部氷とか定義とかにたどり着いていればオッケーだ
そういうふうな木を見つけるゲームなんだってことなんですね
そう言ってもらえるとめちゃくちゃ取っ付けやすいというか
割と本当に今言ってもらった通りゲームなんだなって思えますよね
こういうことをじゃあ証明したいです
Aっていうことを証明したいですっていうのを立てて
問い通して自分で立ててそれをじゃあ氷にどうやってたどり着いていこうかなっていうような
ただの探索ゲームであると
そうなんですよ
って言ってくれたらめっちゃ取っ付きやすいなと思ったんですよ
そういうふうに証明がそういうふうな木構造であるってことを理解すると様々なことが理解できるようになります
例えばXたすYがひっくり返してYたすXになるってことを証明するときにどうやってやるかっていうと
じゃあまず0たす0はどうかなってやって
0たす0はひっくり返しても0たす0じゃないですか
だからこれは結構同じだよね
じゃあ0のときはOK
0と1のときはどうだろう
1たす0たす1と1たす0計算すると一致しますよね
1たす1イコー1になってOK
ってことは証明はこういうふうにこう0たす10試していく
0たす0試して0たす1試していく
こういうふうな試し方ができるわけですね
でもこんなことやってもいくらやっても終わらないってもう想像つけますよね
なのでここに私たちは飛び道具を持ってくるんですね
数学的機能法っていう飛び道具を持ってきます
数学的機能法っていうのは高校のときと大学のときで自然数の定義が違うので難しいんですけど
大学の定義を採用すると自然数は0から始まるので
まずは0のときに成り立つことを示しなさいと
XたすYがXかYのどっちかを0の計算をまず考えてあげて
そのときに成り立つことを示しなさい
そしたら次はもしNのとき成り立つとしたら
Nプラス1のときも成り立つということを示しなさい
この2つを示したら全部の自然数で成り立つということを認めてもよいですよ
っていうことを決めました
これは実は公理というか定義というかに近いようなものなんですね
これを入れてあげると自然数全部についての証明ができるようになる
これが数学のすごいところですね
この機能法を呼び込むことで無限大に対しての言明ができるようになる
というのが定義証明神経の一番すごいところなんですね
確かに数学的機能法がなければ有限な時間において
無限の数字に対して適用していかないといけないんだけど
もう偉い人が数学的機能法というのはOKです
定義として成り立ってますって言ってくれているからこそできることなんですね
そうですねこれは定義公理というのかな難しいですね
自然数を決めると勝手についてくるんですよ
勝手についてくる
そうなんですよ
なのでそれをみんなにだいたい認めることにしているんですね
こういうふうな論章と比較してみると
一個一個試していくっていうふうな機
いつまでもたどり着かない機というのと
数学的機能法というのでバーンって示した機というのがあって
これがうまくいくときとうまくいかないときの分かりやすい例ですね
つまり無限に広がっちゃった機と
コンパクトに全部公理と定義にくっついちゃった機
これが成功失敗の分かりやすい例の一つです
ただこの機能法厄介者なんですよ
厄介者なの何が厄介者なのかっていうと
ゼロの時に証明すれば簡単なんですよ
大抵いつだってゼロの時に何かを言いたいってことは簡単なんですけど
何か言いたいことでNが成り立ってるんだったら
Nプラス1が成り立ってるここがすごくクセモノで
前提にも規決にも両方とも言いたいことが出てくるんです
例えば言いたいことっていうのは例えばそうですね
全ての自然数はゼロより大きいってことを言いたかったとするじゃないですか
全ての自然数はゼロより大きい
ゼロの時はそうですね
ゼロ以上であるって言うとゼロ以上だから
ゼロはゼロ以上だから
ゼロ入ってるから
じゃあ次何か1の時とか試していくんじゃなくて
Nはゼロより大きいんだったら
Nプラス1もゼロより大きいよね
ゼロ以上だよねっていうようなことを証明せよっていうふうなこと言われるんですよ
なのでほうほうほうとなるわけですよね
でそうするともしその前提の部分で何とかだったならっていうふうなことを言って
ここの部分がすごく難しくて
ここで言いたいことが強すぎると証明できなくなるし
言いたいことが弱すぎるとそれもそれで前提が弱くなりすぎて証明できなくなるっていう
難しい緊張関係にあって
長範囲のところを探さなきゃいけないっていうのが
これちょっと感覚は実際やってみると分かるんですけど
この機能法っていうのが登場した瞬間に証明がすごく難しくなるんです
逆に難しくなっちゃう
逆にじゃなくてもう機能法が入らなければ
大抵の証明は機械的に解くことができる
なんだけど機能法が入ると数学はすごく嬉しい
無限を扱いになって嬉しいんだけど
証明が途端に難しくなるんですよ
なるほど
数学上では綺麗にいくんだけど
でも証明上では
リーンとかそういうツール上ではちょっと難しくなってしまう
そう自動探索が難しくなるって言い方をしますね
そうあり得るパターンが増えすぎちゃうんですよ
っていうのがあって
その機能法が登場するときはとっても難しくなります
それはすごく経験的にもよく分かるんですけど
イザベルとかリーンとかには
スレッジハンマーとかってちょっとかっこいい名前の
自動定理証明キーが入ってるんですよ
つまりこのキーをパーってめっちゃ探索してくれて
やっぱりこれ何か判例があるみたいなことを
調べてくれるようなツールがあって
判例があるまで調べてくれないな
証明が見つかるってことを教えてくれるツールがあって
スレッジハンマーは大抵機能法が入ってなければ
見つけてくれるんです証明を
これはこの手とこの手と組み合わせることができるんだよ
かかっていって出てきてバーンって出てきて
おぉ賢いみたいなこと思うんですけど
めっちゃ便利じゃないですか
めっちゃ便利
でもどっかで機能法が必要になると
帰ってこなくなります
それはずっと無限ループ落ちてるんで
無限ループしたら帰ってくる
で何かいつかタイムアウトするんですよ
何十分ぐらいでタイムアウトしたから
なるほど
ツール側が先に数学的機能法入ってたら
切りたいみたいな感じで返せばいいじゃんと思っちゃうんですけど
そういう話でもない
そういう話じゃないんですよね
なかなか見分けるのが難しい
なるほど
一旦探索してみないと分かんないぐらい
分かんないんですよねそうそうそう
っていうのがあってここはすごく難しいんですよね
ただちょっとズルをすることもあって
数学的機能法が必要なんだけど
すでに数学的機能法を使った定理っていうのが
どっかで証明されてると
そこをうまくカチッとはめてあげると
うまくいくみたいな時があるんで
そういう時はうまくいくんですよ
だからこれがちょっと面白い
数学的機能法を使っている定理がもうすでに
okなのグリーンなのであれば
それは数学的機能法の部分の計算は不要なので
スキップするっていうこと
似たようなこと言ってるんで
すでに似たようなこと言ってると
そいつを流用することができるっていうのがあって
なのでなかなか証明っていうのは
一筋縄ではいかない
なかなか先が読めないような展開のゲームになるんですよね
なんかめちゃくちゃやっぱゲームですね
ゲームです本当に
どこまで行ってもゲームなんだなっていう
ゲームであり探索であるってことは
すごくよく伝わるといいなと思ってるんですけど
今数学の人たちっていうのは予想とかを立てて
そこの予想に対して探索をしてるんですよ
何とか予想とかって結構よく言いますよね
今だと有名なのがABC予想っていうのは
今これが合ってるのかってのが問題になってますよね
あれとかっていうのは
今みんなが仮定してる氷から出発して
ずっと定理とかいっぱい言って
いつかたどり着けるんだったらオッケーとする
厳密に言うとそんなに厳密にやり始めたのって
前に言った通り最近なんですけど
そういうふうなことが言われてて
その探索がいつか繋がるんだったら
その予想は合ってるってことになるし
どうやっても繋がらなくていい
むしろ範例があるってなったら予想が成り立ってない
これは繋がる道を早く見つかるか
範例が早く見つかるかみたいな
そんな感じのゲームをやってる
契約による設計と探索ゲーム
じゃあ予想って言ってるのは予想であって
これが証明されたら
ABC予想の場合ABC定理みたいな感じで名前変わる
まさにその通りその通りです
ABC定理です
そういうことなんですね
ああいう何とか予想っていうのは
そうだからフェルマーの最終定理とかも
証明されるまではフェルマーの最終予想だったわけですね
多分成り立つ
ここに書くには証明が短すぎるけどみたいな
多分成り立つってなってて
今そこが判定ないからみたいな
で、範例が現れたらそれは予想ではなくて
定理ではない
定理ではない
そうそうそう
なのでその名前もなくなるってことですね
そうですね
で、そういうわけで面白いのは
じゃあその定理じゃないってことが分かったら
もうそれでおしまいなのかっていうと
そうじゃないってなって
これが結構面白いところなんですけど
前提を強めると定理を証明できる時があるんですよ
だから条件を狭めると
そう正解です
そう条件は前提条件を狭めると
要するにゴミが入っちゃってるってことなんですよね
定理を証明すると言いたくないゴミが
そのゴミを取り除くと言えることがあって
つまり現実でもそういうふうな
いくつかの条件を課してあげると
いい性質が出てくる時があるっていうのもあって
これは面白いところですね
つまり証明できなかった時に
どうしようやったら
これが証明できるような前提を
考えることができるだろうか
っていうふうな立場も結構あって
これも面白い立場です
だから判例見つかったら
ごめんその判例の条件抜けてましたわ
っていうことですよね
そうですそうです
そいつゴミなんですわって時に
前提を強めるってことですね
この判例も条件に事前条件入れるんで
もう一回お願いしますみたいな
そうですそうです
これ事前条件って
契約による設計って言ったのと
すごく似てませんか
前提条件で何を弾くかっていうことを
やってその事前条件をどんどん強めていくと
どんどんどんどん言いたいことが
簡単になってくるんですよ
なんだけどできるインプットが減ってくから
どんどん役に立たなくなってくるんですよ
だから使い物にならなくなってくる
そういうふうな見方をすることができます
このメソッド
すごい
一部の条件においてはめっちゃ便利なんだけど
それ以外使えないっすみたいな
そうそうそうそうそういう
でもそういうアルゴリズムって結構ありますよね
っていうのがあって
例えばバイナリーサーチとかあるじゃないですか
バイナリーサーチ二分探索
あれって相当されてないとできないですよね
そういうことです
なるほど相当されてるという事前条件があるからこそ
早く見つけられる
そういうことですね
なるほどねそういうちょっと関係性があるっていう
そうそうそうそう
だから定理も全く同じで
全然点でバラバラな配列の中から
うまく早く見つけるってことはできないんだけど
そいつが相当されてるって前提を足してあげるだけで
早く見つける方法があるわけですね
なんかそれって結構数学の関係によく似てて
前提条件を強めてあげると
いい性質が出てくる
っていうのがなかなかよく定理とかに似てるなぁ
って思うところですね
いや結構分かってきました
なんとなくそのツールを使う上での
まあやっぱりそのゲームであり探索であり
なんかローグライクゲームみたいな感じのことを
ずっと頑張ってやってるみたいな
いうところなんだなっていうのを
なんとなく理解っていうか雰囲気つかめたんですけど
そうですそうです本当にそうなんですよ
RPGみたいなものなんですよ
今使える前提がこれですって
要するに私の持ち物がこれだけありますっていう前提があって
そこに今示したいことからはこれですっていう
敵がモンスターがいて
そのモンスターに対する攻撃コマンドっていうのは
見えてるんですよ実は
例えば足し算があるんだったら
足し算の定義を展開するとか
足し算の例えばひっくり返すっていう定義とかが
入ってたりするのでひっくり返してみるとか
いろんな定義とかが使える
その定義とかで使えるものの一覧がバーンってあって
でそれをどれどれかな
じゃあ今回はこれってやると
そのモンスターの方が変化するか
持ち物が増えるかどっちかが分かるんですね
そういうことをこうRPGのようにポチポチポチポチって
繰り返していくと
いつか持ち物とそのモンスターっていうのが
一致するときがあるんですよ
一致したら証明ができたってことですね
まああのなんか渾身の一撃かませて
いい感じにクリアできたみたいな
いい感じにクリアできたそうそうそうそう
前提とその言いたいことが全く同じになりました
っていうのが証明できたってことですね
なのでこれは要するにたどり着いたってことなんですよ
前提要するに木があって
さっき言いたいことが根っこにあって
その氷とかがこう葉っぱにあるって言ったんですけど
前提を変えるときはこの葉っぱ側から攻めてきます
葉っぱ側から下に降りてきて
モンスターを攻撃してる時には根っこからたどってるわけです
これがいつかたどり着いてくっつくと同じになりますよね
言いたいことが
それが同じになったら証明できたっていうことなんですよ
うまいこと木を見つけたということ
そういうふうなゲームがその形式証明と言われてるゲームです
なるほど
いやなんかあのめちゃくちゃ形式手法の話って
なんかいろいろこう単語難しいじゃないですか
難しい難しい
いろんな単語あって
しかもそんな聞き慣れないし
普通にソフトウェアエンジニアやってたら合わない単語たちだし
すごいなんでしょう
心理的障壁がめちゃくちゃでかいんですよね
なんですけど今の説明聞くと
本当に単純なゲームだし
単純じゃないとは思うんですけどゲームだし
でもやってることとしたら
なんか本当に依存関係だったりとか
そういう考え方もだいたい近しいし
なんかそう説明してくれたらいいのになぁ
ていう気が本当にしちゃうんですけどね
なんか難しいこといっぱい言ってんなっていう
実際最近なんかリンの考え方とか
あるいは自然駅と呼ばれてる考え方の裏側にあるんですけど
自然駅まあこれも難しいことですね
自然駅って言葉とかを
あのゲーム的にこうゲームみたいな感じでやってくれる
その学習サイトみたいなのを作ってくれた人が
最近ツイッターで結構いってらっしゃる方がいて
でなんかこういう式があるときに
どの鍵を使ってこう開けていって
前提と期決を決めにしていきますかみたいなことをやる
ゲームを作ってくれた人がいるので
まさに同じことを考えてゲーム化してる人たちがいます
でもそれあのトルネコとか風雷の試練みたいな感じで
ゲーム化してくれたら
絶対なんかもっと流行るというかもっと分かりやすく
なんかみんな形式手法に入門しやすいし
それを使いやすく道具としてちゃんと使えるように
って思いますね完全に
実際そんなモンスターとかの見た目がなくても
照明がうまく通った時には脳汁が出ますよ
溶けた!俺はサシさんの反対にひっくり返すやつ溶けたんだ!
みたいなとこになってもうこれは感動しますね
いいですね大人のゲームってことだと思うんですけど
競技プログラミングみたいな感じでやったテスト通ったみたいな
そんな感じとほぼ一緒だと思うんですけど
私は思うに数学のルールっていうのは単純だと思ってるんですよ
すごく単純なんだけど探索範囲がすごく広い
がゆえに人類はまだ手の届くところしか見られていない
だと私は思っていて
なのでルールは本当に単純だから
皆さんは入門は簡単だと思っているんですよ
ただし何かやっぱり遠くに行きたい
すごくいいことを見つけたいとかっていう時には
ものすごーく苦労していろんなところを探して
ここら辺にはないなとかってことを割り切る
知識をつけて歩いていかなきゃいけない
そこが数学の難しいところだと思っています
難しくはあるがでも基本的な概念としては
単純であると
単純にいけるっていうようなところですね
いやすごい何でしょう
苦手意識かなり解消できたかなと思います
そうですよね
海外とかだと今言った自然影響っていうそのルール
その照明のルールっていうのを教えてくれるらしいんですけど
日本だと全然やってこないですよね
だから照明なんてなんかよくわかんないけど
イコールのところは同じ横にしてみたいな
そこじゃないんだよなみたいな
そういうのがはびこっているんで
そこはちょっと教育的に
もうちょっとなんとかなんないかなって思う部分ですね
なんかそれこそ中学ぐらいの数学から
ちょっとずつ入っていってもいい概念な気もするんですけどね
ただやっぱり論理のところで終わっちゃうんですよ
&とかはの部分で終わっちゃってるところがあるなと思ってて
私はちょっと普通の高校じゃなくて高専卒なので
ちょっと普通の高校出た人たちがどんな教育を受けてるのかは
詳しくは知らないんですけど
ただやっぱりその自然影響とかっていうような
その照明のルールっていうのは
もうちょっと教えてくれてもいいのになっていうのは
すごく思いますね
しかもそれをわかりやすくっていうか
取っつけやすく本当にゲームみたいな感じで
教えてくれればいいのにって思いますね
そんな感じで取っつけやすいっていうところがわかってきたんですけど
プログラミング言語意味論とFeatherweight Java
じゃあこれをソフトウェアに適用する
何らかのメソッドに対してこれを証明したいみたいないう時には
具体としてはどんな感じで理にとか使っていくんですか
そうですね さっきいろんな証明っていうのは
定理とか定義から出発するよって話があったと思うんですけど
要するにプログラムっていうのが書かれた時に
それがどんな振る舞いをするのか
これはどんな意味を持ってるのかって言い方をするんですけど
その意味っていうのをプログラミング言語意味論っていうので与えるんですね
プログラミング言語意味論
例えばある言語で1たす1って書いた時に
それが何を意味するのか
例えば2になるのかそれともあるいは
ブール台数だから1になるのかとかっていうようなことを
そういうことルールを決めるっていうのがプログラミング言語意味論
これは定義ですね
こういうプログラム言語なんだっていう定義を与えると
この定義1たす1っていうのはじゃあどうなるのかってことは
その意味論と他の定義とかを使っていくと
最終的にこれは絶対に2にしかならないとかってことが言える
たりするわけですね
これを使うとテストみたいなことができるんですよ
さっき言ったように0の時はどうなるとか
1の時はどうなるとかっていうのは
そのプログラミング言語意味論と
その0たす1とかって中に組み込まれてる
いろいろな数学の言葉とかっていうのを使ってあげると
うまく表現することができる時がある
そうすると
なんと定義としてこのメソッドは
例えば並んでない配列を与えたら
絶対並んでる配列になるという定義が証明できた
すごい
そんなことができるんですね
できる
そこまでいけるんですね
それがまさに私たちがやりたかった検証じゃないですかと
どんな入力に対しても
そう絶対相当されて出てくるんだよこれ
そいつを相当関数って言うんですけどみたいな
それがプログラミング言語意味論と
いろいろなモデルから引き出される規決して出てくる
それが証明によるその形式検証なんですね
じゃあ大前提リーンとかに組み込まれているプログラミング言語意味論というものを使うという
そうですね
自分で作ることもできますよ
イザベルとかリーンとかにもそれぞれプログラミング言語意味論が入ってはいるんですけど
リーンの意味論とかイザベルの意味論とかが入ってるんですよ
入ってるんだけど
自分でプログラミング言語を作りたいという時もあるじゃないですか
例えば国枠言語があって
国枠言語っていうのがこれこれこういう意味論だとする
それをイザベルにインポートすることができます
その時に私の言語だとこれは必ずこういう風になる
とかっていうようなことを定理とかを証明することができて
だから意味論を外側から持ち込むこともできるし
内側に元からあるものを使うこともできる
どちらでもできますね
なるほどじゃあ世界に例えば語言語であれば
語言語のプログラミング言語意味論の定理は存在しているってこと
えっとこれがすごくなかなか難しい質問で
語言語に関してはフィーザーウェイト語っていう形式的な定義のやつがあることが知られてます
フィーザーウェイト語っていうのはすごく羽のように軽い語言って言われてる
なんでフィーザーウェイト語かっていうと
語言語の全ての機能を入れちゃうと
とてもじゃないけどプログラミング言語意味論がでかすぎて
なんかもうただの言語実装ですよねそれは
そうもう何のことだってなっちゃうので
だからちょっともうだいぶ機能をいろいろ削っちゃって
これでもギリギリ語言って言えるかなみたいな感じのところまで削ってあげて
えっとそういうふうに意味論することができて
その範囲で説明できることは全部証明ができます
なるほどだからプログラミング言語ごとのそのライトセットというか
本当にコアな部分の言語の処理体系みたいなところがまとまっている
ゴルーチンしかないみたいなそうそうそうそうそういうイメージです
なるほど今の話で言うとゴルーチンが出てくると
なんかまた複雑になってきそうだなっていう気がしてくるんですけど
なるほど確かにフィーザーウェイト
元々フィーザーウェイトJavaっていうのでJavaがやられてて
何のためにそのフィーザーウェイトJavaが作られたかというと
確か型システムがちゃんと合ってるってことを示したかったんですよね
なるほどそう型エラーが起きないってこのやつだったらってことを言いたくて
でフィーザーウェイトJavaっていうのができて
それとJavaの型システムそのJavaが型あるじゃないですか
例えばオーバーライトできたりとかオーバーロードできたりとか
っていうのをやった時にこういうふうな条件下だったら
かつ型検査が通っていたら実行時に型エラーは起きないってことを定義として証明したかった
なるほどそういう言語の方がそういうプログラミング言語
そうやって証明されているプログラミング言語の方が確実になんか硬そうですよね言語仕様として
そうそうそう性質がいいわけですよ
ただ性質がいいものっていうのは大抵いろんなことの便利な機能が入ってないことが多いんで
そこはねちょっとトレードオフですね
だからメタプログラミングができないとかそういうちょっと自由度が落ちるみたいな話にもなる可能性はあるってことですか
そう自由度が落ちます例えばJavaとかだとダウンキャストができないんですよ
ダウンキャストを許したらそれは型エラー起きるようなことになるじゃないですか
一度アレイをオブジェクトにしてからこいつをイントーして解釈するみたいなことができなくはないみたいな
それはちょっと違くないかとなったりするじゃないですか
それは許されてないそういうのは便利だけど危ないから入れないとかっていうことで
featherweight Javaってできてるんですね
まあでもそれができないからこそ安全だよねっていうことも言えるわけですよね
そうそうそう性質が良くなる前提を狭めたから性質が良くなったんですね
ゴミが入ってくる
なるほどそういうのを使ってじゃあこのプログラム自分が書いたプログラムはどうやったらこの性質このリソットが達成したい性質を証明できるのかなっていうのを探索していくってことなんですね
そういうことですだからその形式的な検証証明による検証っていうのはこのさっき事前条件とか事後条件とか言いましたけど
この事前条件が成り立つんだったら必ず事後条件が成り立つっていう定理を証明することに相当するんですよ
なのでそういうふうなことをやっていくとうまいことできる
プログラミング言語意味論がはっきりした言語を使えばそういうことができるってことなんですね
めちゃくちゃ面白いですね
仕様検証の可能性と形式手法の課題
それがプログラミング言語だけじゃなくて設計書とかにも言えるってこと
そう設計書とかにも契約による設計っていうのは設計ってついてる通り設計のための理論でもあるので
その設計とかに対しても同じことを言うことができます
これ私エンドツーエンテストの会の時にちょろっと言ったかもしれないんですけど
エンドツーエンテストって設計のバグなんですよ
見つけるんですよ結合バグっていうのがあるって話をしましたよね単体テストでは見つからないんだけど単体テストが通ってる2つのものをくっつけるとバグが起きるっていう話をしたと思うんですけど
これは実は形式手法を使うと使用段階で見つけることができるんですね
この仕様とこの仕様をくっつけた時に何が起こるかってことは設計その形式手法を使うとこれはこういうことが起きますってことは予測できるんで
こういうエラーは起きませんとかこういうエラーは起きることがありますとかってことは定義として証明ができる
なのでそうするとエンドツーエンテストが要らない世界が来る
全部設計バグと
理解しました
さっきの設計の話で言うとこのコンポーネントとこのコンポーネントをくっつけるとこういうことをエラーが起きないというか問題がないということを証明したかったんだけど
それを探索していったら反例がありましたっていうのがわかるってことですよね
そう反例があるってことですねそういうことです
でそれがリンとかイザベルとかでわかるってこと
つまり反例がなければ定義になるのでつまりバグがなければ定義になるってことです
もう全人類やるべきなんじゃないですか
ちょっとだけ私はなぜ全人類がそれをできないかのキーワードをすでに話しているんですけど
見通しが高いんですよ証明って本当に
うまくいくかうまくいかないかがわかんないんです本当に
めっちゃ時間かかるかもしれないししかもわかんないかもしれないし
わかんないかもしれないどうやっても有限の証明値で飛びつけないかもしれないとかあったら最悪じゃないですか
そうなっちゃうとだから本当に見通しが高いっていうのが私は形式検証の最大の問題だと思っていて
見積もりできないってことですね
見積もりできないそうどれくらい証明時間にかかるかなっていうのはわかんないんですよ
ちょっと来週までに証明できるかできないかやってきますって言えないってことですよね
言えない言えないそんなこと言ったらABC予想は何十年後に解けるかなって言えちゃうみたいなことになってくるんでそんなこと言えんだろうっていう話だけで
なるほど見積もりができないと営利企業としてコストがどれくらいかかるかわかんないからこそちょっと踏み入れないっていうところも何となくわかる気がしますね確かに
それだけだったらもう読めないからやめちゃおうかなってなっちゃうかもしれないから希望も伝えておきたいんですけど定理は積み上げられるんですよ
定理は積み上げられるだからあるプログラミング言語意味論例えばみんな最近リーン使い始めたんでリーンはどんどんどんどんライブラリーが豊かになっていってるんですね
でリーンで証明されている定理がどんどんどんどん増えているから私たちはそれを私たち自分たちの定理として使うことができるようになっている
ライブラリーとしてね
そうだからどんどんどんどん難易度が下がってきています
だからエコシステムは成熟してきているしかつあれですかね
例えば設計っていう話で言うと違うかもしれないですけど
例えばRubyで書かれたプログラムを証明したいっていう話であればRubyのプログラミング言語意味論のやつを使ったりのやつがどんどん成熟していけばちょっとやりやすくなってくるみたいなことが起きる
そうですねただRubyについてはいろいろ難しいとはちょっと思っています
Rubyはね難しい私は特に印象的だったのがRubyにおいてストリング型って一体何なんだって自体が難しいとかっていう話を聞いてはぁーって思った
めっちゃ難しいことを言い始めますねストリングとは
ストリング型って何だみたいな
なるほど定理が証明できないというか一つに定まらないということを
そうそうそうそうそう
でもRubyでも実行したら毎回同じ結果をだいたい返すじゃないですか
自乱数生成器とか使わない限りはだから同じ結果を返すってことは
これを動かしたら何が起こるのかってことは予想できるはずなんですよ理論的には
だけどそれがあまりにそのルールが難しすぎてまだ見つかってない記述しきれてないそういうふうな感じの現状っていうふうに捉えるのがいいと思います
ってことはこれあの形式手法で証明しやすいプログラミング言語があるべきであって
でそれを使ってみんなリーンとかで証明してエンドとエンドテストなんてものは撲滅していくという未来が
そうしていきたいそうしていきたい
実際そのMLメタランゲージって言われてるその言語の子供たちはすごく証明しやすい
イザベルはMLの子孫ですしね
そういう思想を最初から言語仕様に入れないといけないんですよねプログラミング言語にした
どっちが先なんでしょうねMLはすごく理論が綺麗ですけどあれは理論が先だったのかプログラミング言語が先だったのかちょっとわからないですね
ちょっと私も調べてみないといけない
でもあれですかね最近AI使ってその言語処理系作るみたいなのがまあちょっと一部界隈かもしれないんですけど若干ブームになってきている
みたいなようなこういう形式手法で証明しやすいものみたいなのも若干入ってたりするんですかね
そう思いますね私もちょっと言語を手元でちょろっと作ろうとした時期があって
それはまずプログラミング言語意味論から先に作ろうと思ってもう何年経ったんだろう3年4年経ったらそうな感じです
いやでもそれのデファクトスタンダードが今後出てこないとは絶対限らないですね
限らないですまあでもすごく夢の内部といえば
リーンで書いてリーンで動かすのが一番証明は簡単だし速度は出ないかもしれないけど
なるほどまあでもそういうプログラミング言語出てくるかもしれないもっとやりやすくなってくるし今後っていう
そうそうそうです
あとは定理証明支援系って作ってる人たちも結構いて
定理証明支援系ってすごく実はパーツはちっちゃいんですよエンジンの部分がちっちゃくて
だから実は手書きすることができるんですね
なのでそことかも作ってみると結構面白いと思いますよプログラミング言語作るのも面白いし定理証明支援系作るのも面白いと思います
それはリーンの中で動いてる定理支援系ではなくてってことですね独自の
でもそういうものとか独自のものとか理論をいくつか取ってくれば作ることができるんですよ
そういうのとかいろんな理論があるんですけどその理論を使うと使ってやるんですけどその理論がすごくコンパクトで
だいたいこいつはもうさすがに間違ってないやろみたいなレベルでできてるからイザベルとかリーンとか信頼されてるんですよね
お前たちにもさすがにバグないだろって最近リーンがちょっと矛盾見つかってましたけど
そういうふうにして定理証明支援系は作られているっていう感じなんですね
定理証明支援系の定理証明支援系みたいなそういうことだと思うんですけど
どこが品質を定義するかみたいな話ですよねきっと
だから多分定理証明支援系の正しさを定理証明支援系で示すことはおそらくできない
なぜなら自然水でいただけて自分自身の正しさを証明できなくなっちゃうのにどうして定理証明支援系ができようかってことですね
それで考えるとやっぱプログラミング言語のコンパイラーとかってすごいなぁって
すごいですよちなみにそのコンパイラーで足元からそのコンパイラーの高級言語まで全部が証明されたSEAL4っていう化け物みたいなプロジェクトがあって
CPUとかの命令セットとかから全部意味論があるんです
それ使えば良くないですか?
そう使えば良いですね
まあそういう話でもないんだろうなという気がする
なのでそういう化け物みたいなプロジェクトとかも結構昔からあるんですよ
そのコンパイラーからその命令セットから全部が意味論があって証明できるみたいなものとかもあって
そういうものが昔から実はあったんですよ人で作ることができた
だからすごく品質信頼性が重要な時にはそういうものが使われていたんですね
なるほどまあでもだからといって人が使いやすいとは限らないぞと言ったんですけど
だから流行らないしっていうことだと思うんですけどね
でもなんか昨今ね
ちょっと次の回とかでもAI絡めた形式手法の話最後できればなとは思うんですけど
その中でもしかしたら話すかもしれないんですけど
昨今やっぱ品質とかそういうなんでしょう
今までちょっと緩ふわすぎたよねみたいないうところがもうちょっとガチガチにしてもいいんじゃないみたいな
勢力結構強くなってきてるなという気がなんとなくしてて個人的に
そういう流れの中でこういう形式手法でガチガチに固めていくっていうのはありな流れなのかもしれないですね
あのちょっと歴史的な流れとしては
特にセキュリティがすごく重要になってきましたからね
攻撃する余地を与えちゃいけない
つまり攻撃が成功しないっていう定理を証明できればいいわけですね
そういうことです
そういうことですよねだから攻撃者の手が届かないということを証明できればいいんですよね
単純に
ただそれはその基地の手法で証明するみたいな感じになっちゃうんで
知らん方法そんな方法があったんかみたいなとかはよくある
例えばサイドチャンネル攻撃とかって言われてる
CPUとかの温度の上昇とかからあったとか
ずるいぞそんな方法があったとかみたいなとかはまあそれはもうどうしようもないんで
あとはデータセンターに物理でこじ開けに行くとか
そういうのですね
それはずるいぞみたいなとこがあるんで
そういうのとかを抜きにすれば
攻撃が存在しないっていう定理とかは作ることができます
インターネット上で閉じられればみたいな
っていうところを事前条件としてそういうのを聞きつつってことですね
そういうことですね
形式手法を学ぶ方法
めちゃくちゃ今回面白い話になったんじゃないかなと思いますね
これ聞いてやっぱゲームでやってほしいっす
クワラジのツイート毎回してるんですけどそこにぶら下げますね
ぜひ見てください
ゲームで学べるししかももっとそれが一般的になってほしいですね
もっとその考えを宿したゲームがいっぱいできてもいいぐらいだし
それをそれでやっていくぞっていうスタートアップがいてもいいぐらい
モーカルかどうかわかんないですけど
でもそうやってぶち上げるスタートアップがあってもいいぐらいな感じがするんで
教育系な感じで
そうですね
なのでこういうのとか調べたかったら
自然演劇とか調べると結構その考え方わかると思うんで
ぜひ興味があったら調べてみてください
あとあれですね
形式手法をやりたかったら
これで聞いて
なんとなくわかったっていう感じじゃなくて
ちゃんと本とか読んで
自主体によって
みんなから形式手法ってどうやって始めたらいいんですかねって言われて
毎回紹介する方はちょっと困るっちゃ困るんですけど
でも確実に一つ言いたいことは
私とか勉強会のスライドとか読むより
教科書読む方が100万倍早いぞと思って
やっぱね教科書って教えるためにあるから
あれが最短なんですよやっぱり正しいし
結局ね
だから教科書読もうなって話ですね
はいまあこれでちょっと突きやすそうだなって
入り口半歩入りかけたら
じゃあよしじゃあちょっとやってみて
やっぱ分かんないってなって
教科書に立ち戻って
わかったって感じになったら一番いいですね
そうですね
ぜひ形式検証の証明の具合みたいなのを試してみたら
こんなことねってのが分かって
それはこういう風に書くのねってのが分かれば
もうすぐ伝わると思うんで
そんな難しくないですから
だからちょっとぜひやってみてください
はいありがとうございます
じゃあ今回かなり盛り上がったんですけど
今回ここまでにしたいなと思います
もっと詳しく教えてください
ラジオ略してクマラジでは
スーパーエンジニアであるクマ役さんに
一般エンジニアであるヘントコが
技術的な質問していく番組になってます
今後もいろんなこと聞いていけたらなと思ってますんで
お聞きのプラットフォームで高評価やチャンネル登録とか
フォローとかお願いします
またこんなこと聞いてほしいとかありましたら
コメントいただけると取り上げますんで
よろしくお願いします
感想もぜひXなどでお待ちしております
それでは今回もありがとうございました
ありがとうございました
56:36

コメント

スクロール