No finite rulebook can certify every safe program: an impossibility theorem for gatekeeping AI agents
Authors: Tomas Perez-Acle
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
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.
Figures & tables
Figure 1: (a) The setting. An assistant submits a plan p (a program); the gatekeeper consults two rulebooks, one permissive and one prohibitive, each of which accepts only finite, mechanically checkable evidence: a receipt (a certificate). The gatekeeper admits p when a permission receipt is found, rejects it when a prohibition receipt is found, and otherwise can only keep searching. (b) Why the permissive rulebook cannot be complete. The plan “solve this puzzle, then open the safe” ( pe,w , which simulates a machine Me on input w and opens the safe only if the simulation halts) is safe exactly when the puzzle has no solution. A permission receipt for it would be a receipt that the kettle never boils, that is, that Me(w) never halts, and no rulebook can issue such receipts for every non-halting computation (Lemma 2.3 ). (c) A concrete instance. The plan that searches even numbers for one that is not a sum of two primes and opens the safe only if it finds one is safe exactly when Goldbach’s conjecture is true. Bounded tests of 10 to 106 steps all permit it (Section 6 ); no gatekeeper on Earth can currently certify it.
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 T
Judged on the first T steps only
Yes
Yes
Yes, at cost ≈T
Table 1: The main results at a glance. Confirmable : some procedure eventually confirms every member of the category and never a non-member (Section 2 ). The last row changes the question: with a computation budget every category is decidable, but no always-correct checker is fast (Theorem 3 ).
Notion
Plain meaning
In the gatekeeper’s terms
Plan ( p∈X )
A program submitted for execution.
A written plan handed to the gatekeeper.
P and F
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.
Table 2: Key notions in the gatekeeper’s terms. The pictures are aids to intuition, not definitions; each notion is defined formally where it is first used. Only three images are used throughout the paper: the receipt, the smoke alarm, and the kettle.
Figure 2: What one page of the logbook can settle (Theorem 2 ). Plans are arranged by how much visible behaviour they show; arrows point from a plan to one that visibly does everything it does and possibly more. (a) Once a finite record contains the forbidden operation, every plan above it is unsafe: the unsafe plans form an upward-closed region entered through finite records, so they can be confirmed. (b) The silent plan is safe but a plan above it opens the safe; a member sits below a non-member, so condition (i) fails and safe plans cannot be confirmed. (c) A plan that answers every customer has no finite record below it inside the category, because a page covers finitely many customers; condition (ii) fails.
Figure 3: One plan defeats three guarantees. (a) Unbounded: the plan q that searches for a receipt certifying itself and opens the safe if it finds one; a sound rulebook of n bits can never certify q , so q is safe and omitted, and ∣q∣=n+O(1) (Proposition 3.10 ). (b) Bounded: the plan dT that asks the gatekeeper about itself with budget T and then does the opposite; an always-correct gatekeeper must spend about the whole budget on it (Theorem 3 ). (c) Executable (Simulation 1, Section 6 ): the work each gatekeeper does on its own adversary, against the budget T ; only the gatekeeper that spends the whole budget is right at every T , and every faster one is wrong at every T .
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 ≈T (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.
Table 3: Deployed gatekeeping mechanisms and the condition of the theorems that each relaxes. None contradicts the results; each shows a restriction or a change of model under which a guarantee is possible.
Figure 4: Simulation 2 on 2.2 million random register-machine programs ( 200,000 per length; unresolved programs excluded). (a) Share of unsafe programs that the bounded safety test wrongly permits, by program length L and horizon H ; grey means none. (b) Share of compliant programs that the bounded confidentiality test wrongly forbids, by horizon, one line per length: the error plateaus and never declines, because every such program publishes the same endless sequence at different speeds in its two runs (Simulation 4). (c) The first-violation step among unsafe programs, by length: median, 99th and 99.9th percentiles, with the maximum shown faintly.
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]
–
∘
–
–
∘
–
–
–
Table 4: What each result covers. A filled circle marks a statement proved in the cited work for its own setting; a half circle a closely related statement; a dash none. The row for this paper is the only one with every column filled.
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 K
Yes
No
No
Total classifiers with K′
Yes
Yes
Yes
Appendix
Table B.1: Exact closure under declared expressive capabilities. The final row changes the computational model; it does not classify arbitrary universal programs.
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