コルモゴロフ複雑性によるAI安全性検証の不完全性
arXiv cs.AI / 2026/4/7
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、AIの安全性や政策順守の検証が困難である理由は、計算上の制約やモデルの表現力だけでなく、本質的な情報理論的障壁にもあると主張する。
- 政策順守を、符号化されたシステム挙動に対する検証問題として形式化し、コルモゴロフ複雑性を用いて限界を分析する。
- 著者らは、不完全性定理を証明する。すなわち、どの固定された健全な計算可能な可算（c.e.）検証器に対しても、複雑性がある閾値を超えると、真に政策順守する事例を認証できないことがある。
- これは、資源制約を無視したとしても、任意に高い複雑性をもつすべての政策順守事例について、有限の形式的検証器が認証を保証することは不可能であることを意味する。
- 本研究は、有限で固定された検証器のみに依存するのではなく、事例レベルの正しさ保証を提供できる「証明運搬（proof-carrying）」アプローチの動機づけとなる。
