[2604.04876] Incompleteness of AI Safety Verification via Kolmogorov Complexity

Computer Science > Artificial Intelligence arXiv:2604.04876 (cs) [Submitted on 6 Apr 2026] Title:Incompleteness of AI Safety Verification via Kolmogorov Complexity Authors:Munawar Hasan View a PDF of the paper titled Incompleteness of AI Safety Verification via Kolmogorov Complexity, by Munawar Hasan View PDF HTML (experimental) Abstract:Ensuring that artificial intelligence (AI) systems satisfy formal safety and policy constraints is a central challenge in safety-critical domains. While limitations of verification are often attributed to combinatorial complexity and model expressiveness, we show that they arise from intrinsic information-theoretic limits. We formalize policy compliance as a verification problem over encoded system behaviors and analyze it using Kolmogorov complexity. We prove an incompleteness result: for any fixed sound computably enumerable verifier, there exists a threshold beyond which true policy-compliant instances cannot be certified once their complexity exceeds that threshold. Consequently, no finite formal verifier can certify all policy-compliant instances of arbitrarily high complexity. This reveals a fundamental limitation of AI safety verification independent of computational resources, and motivates proof-carrying approaches that provide instance-level correctness guarantees. Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2604.04876 [cs.AI]   (or arXiv:2604.04876v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2604.04...