計算機援用証明

計算機援用証明とは、コンピュータによって少なくとも一部が生成された数学的証明である大石進一 et. al. (2018), 精度保証付き数値計算の基礎, コロナ社.。
今日における計算機援用証明のほとんどは数学的定理に対するの実装である。具体的には、膨大で複雑な計算をコンピュータによって実行し、計算結果が与えられた定理の主張を裏付けることを示す試みである。1976年に示された四色定理が計算機援用証明によって示された最初の定理である。
計算機援用証明は人工知能の分野でも使われ、簡明かつ陽的で新しい（数学の）定理の証明を作り出すことが目指された。このような自動定理証明機はいくつかの新しい結果を生み出し、既存の定理に対しても新しい証明を発見した。

手法
数学的証明の中でコンピュータを用いる方法の一つとして精度保証付き数値計算が挙げられる。これは数学的厳密さを保持したうえで数値計算を行うことを意味する。数値的プログラムの出力が与えられた数学的問題の解を含むことを示すために集合値演算などを使用する。これは区間演算などによって丸め誤差と打切り誤差を包含、伝播させることでなされる。より具体的には、数値計算を四則演算に簡略化する。計算機では四則演算の結果は計算精度に応じて丸められる。だが、四則演算の結果に関する上界と下界を与える区間を作ることができる。そして数を区間に置き換え、四則演算を計算機で表現可能な数で構成した区間で行う。

計算機援用証明で示された定理
四色定理Appel, K., Haken, W.(1976) Every planar map is four colorable, Bulletin of the American Mathematical Society Volume 82, Number 5.
ケプラー予想Hales, T. C. (2005). A proof of the Kepler conjecture. Annals of mathematics, 1065-1185.Hales, T. et. al. (2017). A formal proof of the Kepler conjecture. In Forum of Mathematics, Cambridge University Press.
Double bubble 予想Hass, J., Hutchings, M., & Schlafly, R. (1995). The double bubble conjecture. Electronic Research Announcements of the American Mathematical Society, 1(3), 98-102.
Wright 予想van den Berg, J. B., & Jaquette, J. (2018). A proof of Wright's conjecture. Journal of Differential Equations, 264(12), 7412-7462.
14番目のスメイルの問題、ウォリック・タッカーによって区間演算を使って解決されたTucker, W. (1999). The Lorenz attractor exists. Comptes Rendus de l'Académie des Sciences-Series I-Mathematics, 328(12), 1197-1202.。

Lamb, E. (2016). Two-hundred-terabyte maths proof is largest ever. Nature. 534: 17–18.

出典

参考文献

 Meyer, K. R., & Schmidt, D. S. (Eds.). (2012). Computer aided proofs in analysis. :en:Springer Science & Business Media.
 Lanford, O. E. (1992). Computer assisted proofs. In Computational Methods in Field Theory (pp. 43-58). Springer, Berlin, Heidelberg.

関連項目
 精度保証付き数値計算
 区間演算
 INTLAB
 証明
 自動定理証明
 モデル検査

外部リンク

Category:アーギュメント・テクノロジー
Category:数値解析
Category:計算機科学
Category:応用数学
Category:アルゴリズム
Category:数学に関する記事