0_tutorial_AI/6b.book(保存済みの内容) … 編集へ / ファイル一覧へ

ページ 1 / 3 … 1 2 3 … 次のページ →

実践:投げ先・失敗・戦略
admin
import 6.book

1 早見表

この Book は、prf を実際に書くときの判断(どの投げ先に投げるか・FAIL したら何をするか・難しい定理をどう進めるか)をまとめた実践編です。定義や記号は 6.book のもの(ヘッダで import 6・thmel /common/zf)。基本の書き方は 3.book、slash の規則は 4.book、クラスと -|・--| は 5.book にあります。
まず表にまとめます。理由と実測は後の節にあります。
段の式に含まれるもの書く段理由・実測
クラス変数も述語変数も無い(一階の式)-| … p;掲載した例では最速。まず試す候補(3.1)
クラス変数(X_ など)min.thmel:◀ … v;(Wc. は入らない)/default・zf.thmel:--| … v;(本が紹介した Wc. の定義も前提に入る=5.book)-| は「|0 翻訳不可」。◀ … p; も通るが、相対化で式が大きくなるので項が増えると遅くなりやすい(3.2。遅くなる実例は 3.1 のクラスを含まない式)。◀ … v; と --| … v; はどちらも通る例が多い(--| は内包を cls-elim し Wc. を足す=5.book)
内包 \{ cls x | … \} を含む多ソートの段v;掲載した例では vampire+ が速かった(3.3)
述語への代入が要る(schema を使う段)実例 SOURCE[P:=θ] を sos に書いて v; など証明器に述語を探させない。prop の高階変数にはどの backend でも代入しない(3.4)
goal の断片が自明で数が多いp[whole];起動の回数が減る(4.book)
1段で通らない補題に切って段ごとに投げ先を選び、最後を h; で結ぶp; で timeout する段も v; なら一瞬で通ることがある(3.book・第4〜5章)

証明器は、時間内に証明が見つからないと timeout を返します。探索を早く打ち切って not_proved を返すこともあります(Prover9 の not_proved は「証明が見つからなかった」で、無いことが確定したわけではありません)。Vampire の CounterSatisfiable は「渡した問題には反例がある」という答えです。どちらも FAIL で、主張が偽という判定ではありません。
FAIL したときの次の一手(原因は候補で、どれかを確かめながら試します):
症状(FAIL の文言)意味次の一手
「|0 翻訳不可: … ∈_ が残っています」クラス変数を含む段を -| で投げた◀ … v;(default・zf なら --| … v;)にする
すぐ not_proved(Vampire なら CounterSatisfiable)この前提とこの展開では証明が見つからなかった(CounterSatisfiable なら、渡した問題には反例がある)。定義が開ききっていない・前提(橋渡しの定義や補題)が足りない・主張が偽のどれかreview_cli.php … --inputs で投げた入力を読み、開いていない記号が残っていれば / を足し、足りない定義は前提に置く(第4章)
timeout考えられる原因:定義を開きすぎ(/ W. の本数が多い・=. の外延性など)か、1段に詰め込みすぎ。必要な前提を消した場合もあるW.!〇. で開く定義を減らす・補題に切る・投げ先を替える
h; の段で落ちる各段は示せたが、組み合わせても thm の主張にならない最後の段(h;)の goal・sos が thm の行と同じか、途中で使った定義が W. に入っているか、h; の段の関係がつなぐ段と合っているか(/ で展開した段をつなぐなら -| h;・3.book「h; の段の関係」)を確かめる

表の各行の詳しい見分け方と、実際に直した例は「失敗の種類を見分ける」の節にあります。

1.1 backend

prfの各段は、末尾の投げ先の文字で backend を選びます(仕組みは3.book)。どれに投げるかで、通るか・どれだけ速いかが大きく変わります。
・prover+(p;)… Prover9 を使います。一階言語のThmを受け取ります。-| の段は Thm を |cvt+|0(min.thmel では |0)で翻訳して、◀ の段は{s,c}ソートを一項述語で相対化して投げます。goal を断片に割って投げ、すべて証明できたら OK です(割らない p[whole]; は4.book)。
・vampire+(v;)… Vampire を使います。{s,c}ソート言語のThmを、ソートを保ったまま(多ソートの TFF 形式で)受け取ります。
・satallax+(s;)… Satallax を使います。高階言語のThmを受け取ります。Thm に自由に現れる命題変数・述語変数は、Thm 全体で1つの記号として渡します(|v-elim をした p; v; と同じ意味・HOL.book)。 ただし .thmel に satallax+ predicate:all と書いた本で、--| … s; の段の sos に素の名前で書いた ∀ ?R^ ( … ) の prop だけは、その式の中で ?R^ を ∀ で閉じた高階の公理として渡します(下の「述語変数の代入」)。
・hyperion(h;)… 証明器ではありません。prf の前の段で示したThmを組み合わせて、thm の主張を導けるかを確かめます(例外:関係をまたいで Thm を確かめ直すときだけ Vampire を呼ぶ・3.book「h; の段の関係」)。
.thmel ごとに書ける関係と投げ先が違います(1.book の .thmel の節に表があります)。target に無い投げ先の文字を書くと、コンパイルの段階で「この本は -| … s; を書けません(… target は p;v;h です)」のように拒否されます。

ページ 1 / 3 … 次のページ →