AI can’t universally verify behaviour, and that limits safety

At a glance

What this is: This is a theory-led analysis of why universal prediction and verification of arbitrary program behaviour is impossible, and why that matters for AI safety and software governance.

Why it matters: It matters to IAM, NHI, and AI governance teams because the same limits that block universal program verification also constrain claims about autonomous systems, tool use, and policy compliance.

👉 Read Pentera’s analysis of AI verification limits and undecidability

Context

Universal verification breaks down when the question is not about a specific system under specific assumptions, but about every possible program and every possible outcome. That is the core governance gap in this chapter: once the problem is framed universally, computation stops being a complete answer. For identity and AI programmes, this matters because control models often assume that behaviour can be fully predicted, certified, or contained.

The article sits at the boundary between AI governance and security assurance. Its relevance to identity is indirect but real: as AI systems begin to act like agents, the question becomes who or what can be trusted to execute actions, call tools, or preserve policy boundaries. That is not a vendor problem. It is a design limit that affects NHI governance, privileged automation, and operational assurance alike.

Key questions

Q: How should security teams govern AI systems that can act without human approval?

A: Security teams should govern autonomous AI the same way they govern other high-risk identities, but with runtime enforcement instead of periodic review. That means tightly scoping tools, data, and actions; logging every material step; and making revocation and containment available while the session is still active. Static policy alone does not control machine-paced execution.

Q: Why do universal safety claims fail for arbitrary AI or software behaviour?

A: Because safety properties that apply to all possible programs quickly become undecidable. If a claim depends on what the system does rather than how it is written, and some systems satisfy it while others do not, there is no general algorithm that can decide it for every case. Assurance must therefore be scoped, evidence-based, and continuously reviewed.

Q: What breaks when teams assume AI behaviour can be fully verified?

A: What breaks is the assumption that a single proof can cover all future inputs, tool calls, and self-directed actions. In practice, that leads to overconfidence, weak exceptions handling, and controls that only work in the lab. Teams need operational monitoring, bounded test cases, and explicit limits on what the verification result covers.

Q: How do organisations decide between verification and runtime controls for AI systems?

A: They should use both, but for different purposes. Verification is best for narrow properties inside a clearly defined boundary. Runtime controls are essential when the system can change state, call tools, or operate under incomplete information. The right choice is not either or. It is layered assurance with human ownership of the final risk decision.

Technical breakdown

Why the halting problem blocks universal prediction

The halting problem proves that no general algorithm can decide, for every program and input, whether execution will stop. The proof works by self-reference: a hypothetical predictor is fed a program built to do the opposite of whatever the predictor says. This is not a weakness in current tooling, but a structural limit of computation itself. More compute, a better language, or probabilistic reasoning does not remove the contradiction. For AI governance, the implication is sharp: universal runtime certainty is not a solvable engineering problem.

Practical implication: scope verification to bounded systems and defined assumptions rather than promising universal behavioural certainty.

Why Rice’s theorem makes most safety questions undecidable

Rice’s theorem generalises the halting result to non-trivial semantic properties of programs. If a question depends on what a program does rather than how it is written, and some programs have the property while others do not, then there is no universal decider. That includes questions such as whether a system is always truthful, harmful, compliant, or safe across all inputs. For AI security, this means containment and policy compliance cannot be certified in the abstract for arbitrary systems. Assurance has to be evidence-based and context-specific.

Practical implication: treat behavioural safety as a scoped assurance task, not as a universal property you can permanently prove.

Busy Beaver shows behaviour outruns any computable predictor

Busy Beaver defines the maximum runtime for a halting Turing machine of a given size, and the function grows faster than every computable function. That means even tiny programs can exceed the reach of any algorithmic predictor. The point is not only that prediction is hard, but that some behaviour spaces are non-computable in principle. In AI terms, a model may be useful for spotting patterns, but it cannot exhaustively map the space of arbitrary program outcomes. This is a limit on certainty, not on utility.

Practical implication: use AI for triage, anomaly detection, and test generation, while keeping final assurance tied to bounded verification and human judgment.

NHI Mgmt Group analysis

Universal AI verification is a governance fantasy, not a product requirement. The chapter makes a formal point that security teams should recognise immediately: once the question becomes universal, no computational system can answer it for all cases. That means any assurance model promising complete prediction or containment of arbitrary software behaviour is overstating what computation can do. For IAM and AI governance teams, the correct frame is scoped control, not universal certification.

AI agent governance inherits the same limits as program verification. Once an AI can select actions, call tools, or chain decisions, the security problem stops being static configuration and becomes dynamic behaviour. That is where identity and agent governance intersect: credentials, permissions, and policy boundaries must be designed for bounded trust, not assumed to be exhaustively verifiable after the fact. The practitioner conclusion is to govern delegated capability as a constrained runtime problem.

Bounded assurance is the only workable security model for intelligent systems. The article is strongest when it shifts from impossibility to design: if universal verification is unavailable, then the answer is to restrict the architecture, define the operating envelope, and measure behaviour continuously. This aligns with established security thinking in zero trust and least privilege, but it also extends it into AI governance. The conclusion is simple: verify the slice you can defend, not the universe you cannot.

Human-chosen constraints become the real control plane for AI safety. The chapter argues that once you restrict the system to a finite library of provably safe primitives, the burden shifts to choosing those primitives well. That is a governance task, not a mathematical one. For security leaders, this reinforces a familiar identity lesson: controls fail when they assume the system will self-govern. The practitioner conclusion is to treat architecture, policy, and review as the decisive safety layers.

What this signals

AI safety programmes need to move from universal promises to defensible boundaries. For security leaders, the practical signal is that assurance language must become more precise. A claim that a system is safe in every case will not survive contact with real autonomy, so policy, testing, and access control need to be written around specific tasks, systems, and limits.

Identity controls become more important as AI systems gain runtime agency. If a model can call tools or trigger workflows, then the question is no longer only what it knows. It is what it can do, with whose credentials, and under what expiry conditions. That pushes AI governance closer to PAM, NHI lifecycle discipline, and continuous authorisation.

Bounded architectures will separate serious AI governance from aspirational language. Teams that can define the allowed action set, the maximum trust window, and the review path will have stronger control than teams relying on abstract safety claims. The near-term programme impact is to tighten scope, reduce ambient privilege, and align AI usage with least-privilege operating models.

For practitioners

• Define bounded assurance cases Limit any claim about AI or software behaviour to a named asset, a specific property, and a fixed operating window. Make the assumption set explicit so reviewers know exactly what was proved and what was not.
• Separate model utility from safety certainty Allow AI to assist with anomaly detection, test generation, and evidence gathering, but do not treat those outputs as proof of safe behaviour. Put final sign-off on scoped verification and accountable human review.
• Constrain agent runtime authority For AI systems that act like agents, assign only task-scoped permissions, short-lived access, and clear termination conditions. Behavioural control belongs in the permission envelope, not in post hoc analysis alone.
• Document the non-universal assumption Record where your assurance process stops, especially for self-modifying systems, tool-using agents, and workflow automation. If the control depends on universal prediction, it is not a control.

Key takeaways

• Universal verification of arbitrary program behaviour is mathematically impossible, so AI governance must be scoped rather than absolute.
• The most relevant control failure is the assumption that safety, truthfulness, or containment can be proven for all systems and all inputs.
• Security teams should pair bounded verification with runtime controls, short-lived permissions, and accountable human review.

Key terms

• Halting Problem: A foundational result in computability theory showing that no general algorithm can determine for every program and input whether execution will stop. It matters because it proves there are hard limits on prediction, even when the code and input are fully known.
• Rice's Theorem: A theorem stating that any non-trivial semantic property of programs is undecidable in the universal case. In plain terms, if the question is about what a program does rather than how it is written, no single algorithm can answer it for every possible program.
• Busy Beaver Function: A mathematical function that describes the maximum runtime of a halting machine of a given size. Its growth outruns every computable function, which makes it a clean demonstration that some behaviour spaces cannot be exhausted by computation, no matter how much compute is available.
• Bounded Assurance: A governance approach that limits claims about security or safety to a specific system, property, and operating window. It replaces universal certainty with scoped evidence, making it possible to verify what matters without pretending that every possible behaviour can be proven in advance.

What's in the full article

Pentera's full article covers the mathematical detail this post intentionally leaves at the principle level:

• Step-by-step proof logic for the halting problem, Rice’s theorem, and Busy Beaver.
• The role of self-reference and diagonalisation in undecidability arguments.
• How restricted architectures change the verification problem without removing the underlying limits.
• The broader learning series that connects these limits to AI learning and inductive bias.

👉 Pentera’s full chapter expands the proof logic, theory links, and the limits of universal prediction.

Deepen your knowledge

NHI Foundation Level course, the industry's only accredited NHI security programme, covers NHI governance, machine identity security, IAM, and secrets management. It is suited to practitioners who need to connect identity controls with broader security and assurance programmes.