Algorithmic Unverifiability of Safety for Fixed and Recursively Self-Improving Systems

arXiv:2606.28639 · cs.LO, cs.AI, cs.CC, cs.CL · Submitted 2026-06-26 · Read on arXiv

cs.LO, cs.AI, cs.CC, cs.CL

Submitted: 2026-06-26

Updated: 2026-09-23

Terminology

• Verification — 51× in this paper · explained in 2 episodes
• Verifier — 40× in this paper · explained in 2 episodes
• Trace — 35× in this paper · explained in 2 episodes
• Alignment — 29× in this paper · explained in 1 episode
• Consistency — 3× in this paper · explained in 3 episodes
• First-Order Logic — 3× in this paper
• AI Alignment — 2× in this paper · explained in 2 episodes
• Alignment Verification — 2× in this paper · explained in 1 episode
• Failure Modes — 2× in this paper · explained in 3 episodes
• Grounding — 2× in this paper · explained in 3 episodes
• Agentic AI — 1× in this paper · explained in 1 episode
• Alignment Problem — 1× in this paper · explained in 1 episode
• Axioms — 1× in this paper · explained in 2 episodes
• Formal Verification — 1× in this paper · explained in 2 episodes
• Least Fixed-Point Logic — 1× in this paper
• Reinforcement Learning — 1× in this paper · explained in 4 episodes
• Second-Order Logic — 1× in this paper
• Unverifiability of Artificial General Intelligence — 1× in this paper

Sources

• No Certificate for Alignment: Two Independent Impossibilities and the Pareto Frontier of Achievable Safety Guarantees
• Concrete Problems in AI Safety
• Supervising strong learners by amplifying weak experts
• AI safety via debate
• Scalable agent alignment via reward modeling: a research direction

Related papers

• An Information-Flow Perspective on Explainability Requirements: Specification and Verification
• A programming language combining quantum and classical control
• Causal Past Logic for Runtime Verification of Distributed LLM Agent Workflows
• Encoder-Decoder Transformers: Logical Characterizations and Periodicity
• Ultraconstructive Model Theory via Bounded Adversarial Finite Structures