No finite rulebook can certify every safe program: an impossibility theorem for gatekeeping AI agents
Organizations: Bioinspired Artificial Intelligence Lab, Facultad de Ingeniería, Universidad San Sebastián, Avda. del Valle Norte 725, Huechuraba, Santiago, Chile · Centro BASAL Ciencia & Vida, Universidad San Sebastián, Avda. del Valle Norte 725, Huechuraba, Santiago, Chile
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 bits omits a compliant program of about 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.
Figures & tables
| Requirement | In plain words | Violations confirmable? | Compliance confirmable? | Both rulebooks exact? |
|---|---|---|---|---|
| Safety | Never open the safe | Yes | No | No |
| Confidentiality | The published report reads the same for both secret memos | No | No | No |
| Response | Every customer eventually gets an answer | No | No | No |
| Any norm judging only visible behaviour | Permits some plans and forbids others | The side containing the silent plan: No (Corollary 3.7 ) | No | |
| Any requirement with a budget | Judged on the first steps only | Yes | Yes | Yes, at cost |
| Notion | Plain meaning | In the gatekeeper’s terms |
|---|---|---|
| Plan ( ) | A program submitted for execution. | A written plan handed to the gatekeeper. |
| and | The permitted and forbidden plans: the two groups into which a fixed norm divides all plans. | What the gatekeeper may allow and what it must refuse. |
| Rulebook | A finite rule with a fixed meaning: the set of plans it describes. Two rulebooks: permissive and prohibitive. | The gatekeeper’s two lists. |
| Certificate | Finite evidence that a plan fits a rule, checked by a procedure that always stops (Definition 2.1 ). | A receipt : quick to check, possibly endless to find. |
| Confirmable set | Every member is eventually confirmed and no non-member ever is; the procedure may run forever on a non-member. Also: computably enumerable, recognizable. | A smoke alarm : its alarm is conclusive, its silence is not. |
| Decidable set | A procedure always answers “in” or “out” correctly in finite time. | A gatekeeper who always reaches a verdict. |
| Mechanism | What it does | Which condition it relaxes |
|---|---|---|
| Kernel extension verifier (eBPF) Gershuni et al. [2019] | Admits only extension programs it can prove safe; rejects the rest. | Admits a decidable separator that omits some safe programs (Theorem 4 , Corollary 3.9 ). |
| Gas budget (Ethereum) Wood [2025] | Bounds the computation of every transaction. | Changes the norm to a bounded one; exact but at cost (Theorem 3 ). |
| Runtime monitor Schneider [2000] , Ligatti et al. [2009] | Intercepts the forbidden operation when it occurs. | Changes the execution rather than classifying the unmodified plan; the sandbox of Corollary 4.2 . |
| Proof-carrying code Necula [1997] | Each program arrives with a checkable proof. | Admits exactly the plans that come with receipts: a confirmable separator, omitting infinitely many safe plans (Proposition 3.10 ). |
| AI-control protocols Greenblatt et al. [2024] | A trusted model audits or rewrites code from an untrusted one. | Rewriting leaves the admission interface; guarantees are empirical, not universal. |
| Learned classifiers | A trained model predicts whether code is safe. | A fast checker; by Theorem 3 and Proposition 3.10 it must err or abstain on some plan of its own size. |
| Two-sided formulation | Safety asymmetry | Confidentiality | Response (liveness) | Confirmability characterised | Budget lower bound | Obligations / separators | Size of omitted plans | |
|---|---|---|---|---|---|---|---|---|
| Rice Rice [1953] | – | – | – | – | – | – | – | – |
| Rice–Shapiro Rogers, Jr. [1967] , Soare [2016] | – | – | – | – | – | |||
| Alfonseca et al. Alfonseca et al. [2021] | – | – | – | – | – | – | – | |
| Hamlen et al. Hamlen et al. [2006] | – | – | – | – | – | – | ||
| Melo et al. Melo et al. [2025] | – | – | – | – | – | – | – | |
| Ray Ray [2026] | – | – | – | – | – | – |
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
| Class | Safety | Confidentiality | Response |
|---|---|---|---|
| Effective finite certificates | No | No | No |
| Total computable classifiers | No | No | No |
| Finite Boolean combinations of confirmable sets | Yes | No | No |
| Classical arithmetic truth for the displayed formulas | Yes | Yes | Yes |
| Total classifiers with | Yes | No | No |
| Total classifiers with | Yes | Yes | Yes |
| Strategy | Why it does not restore checkable closure | Status |
|---|---|---|
| Classical negation of rules | “No certificate exists” is not confirmed by any finite search | Leaves the class |
| Exact abstraction | Must never merge a permitted with a forbidden plan; a computable abstraction cannot decide an undecidable boundary (Proposition D.1 ) | Subject to the barrier |
| Compression, macros, infinitely many listed rules | Aggregate denotation is still confirmable | Stays in the class |
| Assume termination | Pointwise termination does not decide norms over infinitely many inputs (below) | Subject to the barrier |
| Finite domains, nonuniform tables | Exact tables exist for each code-length bound but no algorithm produces them all | Changes the model |
| Restriction or enforcement | Classifies a restricted set or changes the execution | Changes the question (Section 5 ) |
AI Agent Safety
AI agent safety studies how to prevent and detect harmful actions by autonomous systems that use tools, memory, and multi-step plans.
See all 349 papers