VSTTE 2012 Software Verification Competition - ひとり勉強会

VSTTEという国際会議の開催した「ソフトウェア検証大会」 https://sites.google.com/site/vstte2012/compet 問題文PDF に挑戦していました。48時間で5問の仕様と実装が提示されて、その正しさ、つまり停止性や、配列の範囲外アクセスをしないこと、仕様を満たしていることなどを、なんでも自由なツールを使っていいから検証してみよう！というコンテストです。 というわけで、Coq でやってみて、力尽きました。難しいですね！コードだけ貼り付けておきます（提出はしてない）。 Problem 1 とある bool のソートアルゴリズム。 Coq で書けたので停止性は示されているはず 配列は範囲内であることが証明されている整数でしかアクセスできない依存型なのでアクセスも安全なはず 返値が sorted であることも証明付きの依存型なので大丈夫なはず 元のpermu