No finite rulebook can certify every safe program: an impossibility theorem for gatekeeping AI agents

Tomas Perez-AclearXiv 2026 · arXiv

This paper, recently published by Tomás Pérez-Acle, provides a rigorous mathematical reality check for the field of AI safety and automated gatekeeping. It proves that no matter how clever our verification algorithms become, a perfect, finite, and checkable "rulebook" for certifying the safety of arbitrary AI-generated code is a theoretical impossibility.

TL;DR

The paper proves an impossibility theorem: no finite, mechanically checkable rulebook can perfectly classify every safe program while rejecting every unsafe one. While we can catch every safety violation by watching a program run, we can never definitively "clear" every safe program for properties like safety, confidentiality, or responsiveness without running into the fundamental limits of computation.

What Problem Does This Paper Address?

As AI agents increasingly move from generating text to generating and executing code (e.g., tool-using LLMs), we need "gatekeepers"—automated systems that inspect code and decide if it’s safe to run. We want these gatekeepers to follow a set of rules:

  1. Safety: Never perform a forbidden action (e.g., "don't open the safe").
  2. Confidentiality: Never leak secrets (e.g., "don't let the output depend on a secret memo").
  3. Responsiveness: Always provide an answer eventually.

The authors ask a fundamental question: Can we create a complete, finite rulebook where every "yes" or "no" is backed by evidence (a "receipt") that a machine can verify in finite time?

Methods

The paper approaches this through the lens of computability theory, building on classical foundations like Turing’s Halting Problem and Rice’s Theorem.

  • Theoretical Proofs: The authors use "reductions" to show that if a perfect gatekeeper existed, it could solve the Halting Problem (which we know is impossible).
  • Adversarial Construction: They employ a "self-referential device"—a program that essentially asks the gatekeeper, "What do you think of me?" and then does the exact opposite of the gatekeeper's verdict.
  • Simulations: To see how these theoretical limits manifest in practice, they ran empirical tests on a massive scale using a deterministic register-machine environment.
The gatekeeping setting: an AI assistant submits a plan, and a gatekeeper consults permissive and prohibitive rulebooks.

Datasets

The authors didn't just stick to theory; they tested their ideas against:

  • 2.2 million random programs: Generated with lengths ranging from 4 to 24 instructions to measure how often "typical" code triggers these theoretical obstructions.
  • Exhaustive Population: Every valid program of 1 to 4 instructions (483,641 programs total) was run to completion or until a state repeated.
  • Adversarial Benchmarks: Specifically designed programs (like the Goldbach conjecture plan) that are simple to write but impossible to certify with current mathematical knowledge.

Key Insights and Ideas

  • The "Smoke Alarm" Asymmetry: Prohibitions (Safety) are like smoke alarms. A "receipt" of a violation is easy to verify—you just show the step where the program "opened the safe." However, there is no finite receipt that proves a program will never open the safe. Silence is not proof of safety.
  • Liveness is Harder: While safety violations can at least be caught by watching, properties like confidentiality and responsiveness are even worse. For these, neither a "pass" nor a "fail" can be confirmed by any finite record of behavior.
  • The Budget Trap: You might think a time limit (a "gas budget") solves this. While a budget makes the problem decidable, it doesn't make it feasible. The authors show that an adversary can always force a gatekeeper to spend its entire budget before revealing its true behavior.
A plan that asks the gatekeeper about itself and then does the opposite, forcing the gatekeeper to spend its entire budget.

Key Results

  • Theorem 1 (Asymmetry): For safety, a prohibitive rulebook can be exact (catching all bad actors), but no permissive rulebook can be. For confidentiality and response, neither side can be exact.
  • Theorem 2 (Characterization): The authors characterize exactly which rules can be confirmed: only those settled by a finite, listable record of observed events.
  • Rulebook-sized Omissions: Any sound rulebook of $n$ bits will necessarily omit a compliant program of approximately $n$ bits.
  • Empirical Rarity: Simulations showed that while the obstruction is theoretically certain, it is rare in random code. For safety, 98.2% of random programs could be correctly certified by simple methods. However, for confidentiality, the "liveness" error created a persistent plateau of uncertifiable programs that didn't go away even with longer testing horizons.

Limitations and Future Work

  • Idealized Model: The paper assumes a universal programming environment with potentially unbounded time and memory. While Corollary 4.1 bridges this to finite machines, the primary results are asymptotic.
  • Binary Safety: The model treats safety as a binary "BAD" event. Real-world harm is often more nuanced and probabilistic.
  • Future Directions: The authors suggest moving from "perfect classification" to finding "separators"—checkable lists that contain everything a gatekeeper must allow and nothing it must refuse. They suggest future work should focus on justifying specific observation models and obligations for real-world AI deployment.

Summary based on "No finite rulebook can certify every safe program: an impossibility theorem for gatekeeping AI agents" by Tomás Pérez-Acle.

Summary updated

Abstract

An AI assistant writes small programs, and a gatekeeper must decide, from the code alone, whether each one may run. Suppose the rules are fixed: never perform a forbidden action, never let the output depend on a secret, always answer eventually. Can two rulebooks, one listing what is allowed and one listing what is not, both be complete, if every rule must be backed by evidence that a machine can check in finite time? We prove that they cannot. Checkable evidence can only establish what a finite record settles, and ``never'' and ``eventually'' are never settled by a finite record. For prohibitions the failure is one-sided: every violation can be caught by watching, but no safe program can be cleared for good. For confidentiality and responsiveness, neither side can be. We characterise exactly which rules about visible behaviour evidence can confirm, and we show that any sound rulebook of $n$ bits omits a compliant program of about $n$ bits. A time limit makes everything checkable, but only by running the program for essentially the whole limit, so a finite machine is not a feasible one. Finally, we show what a gatekeeper can still guarantee: not a verdict on every program, but a checkable list that contains everything it must allow and nothing it must refuse. Simulations on 2.2 million random programs and on self-referential adversaries show that the obstruction is adversarial rather than typical, and that the one error a longer test never removes is the liveness part of confidentiality.
BibTeX
@misc{perezacle2026no,
  author = {Tomas Perez-Acle},
  title = {{No finite rulebook can certify every safe program: an impossibility theorem for gatekeeping AI agents}},
  year = {2026},
  eprint = {2611.13367},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13367},
}
Figure