The Limits of Logic: Why AI Can't Be Fully Secured

A century of mathematics, from Gödel in 1931 to a 2026 NIST proof, explains why federal cybersecurity has to be continuous. Here's the full story and the practical takeaway for IT, security, and DevSecOps leaders.

Key takeaways

• In 1931, Kurt Gödel proved that any rule system powerful enough for basic arithmetic has true statements it cannot prove from within. That single insight still shapes computer science, cybersecurity, and AI.
• Turing, Church, and Rice extended it. No algorithm can decide, in general, what an arbitrary program will do, including whether it is malicious, buggy, or safe.
• In May 2026, NIST scientist Apostol Vassilev applied that same logic to AI and proved that no finite set of guardrails can block every adversarial prompt.
• For federal teams, the result is concrete. Security cannot be a one-time achievement. Continuous monitoring, ongoing red-teaming, and resilient design are the only defensible posture, and they map cleanly onto RMF, ConMon, and continuous ATO.

Key figures at a glance

Hilbert's dream: the idea that everything could be proved

Picture a mathematician in 1900. Physics is on the edge of Einstein. Cities are being rewired by engineering. And mathematics looks ready for its own final triumph, not the answer to one problem but the answer beneath all of them: what is mathematical truth, and can we reach all of it?

David Hilbert, the most influential mathematician of his era, believed the answer was yes. He set out a program, later called Formalism, with an elegant goal. Start from a finite set of self-evident axioms and a set of logical rules. From that foundation, mechanically derive every true statement. The system would be complete (able to settle any statement), consistent (never proving something and its opposite), and decidable (there would be an algorithm to determine, for any statement, whether it is provable).

In 1928 Hilbert and Wilhelm Ackermann named that last requirement the Entscheidungsproblem, German for the decision problem. Could a mechanical procedure take any proposition and, in finite steps, tell you whether it follows from the axioms? If so, mathematics would be a finished cathedral with every stone in place.

Hold that image, because a surprising amount of security thinking still quietly assumes you can build one. The airtight system. The complete control set. The tool that certifies the code is clean. Hilbert's dream lasted about a year longer.

Gödel's rupture: true, but unprovable

In September 1930, at a conference in Königsberg, a precise twenty-four-year-old named Kurt Gödel mentioned almost in passing that he had a result. Most of the room missed it. John von Neumann did not and cornered him after the session. By the time Gödel published in 1931, the foundations of mathematics had a crack running straight through them.

The First Incompleteness Theorem

Gödel proved that for any formal system rich enough to handle ordinary arithmetic, there will always be true statements it can never prove. Not statements that are merely hard. Statements that are permanently, structurally out of reach.

The trick was self-reference. Think of the old Liar's Paradox, "this sentence is false." If it is true it is false, and if it is false it is true. Gödel engineered a mathematical version using a method called Gödel numbering, where every symbol, formula, and proof is encoded as a unique number. That let mathematics talk about itself. He then built a statement that, decoded, says "this statement is not provable in this system." If the system is consistent, that statement cannot be proved, which means it is true. A true statement the system cannot reach. Completeness was gone.

The Second Incompleteness Theorem

The second result is more unsettling. No sufficiently powerful system can prove its own consistency from within. To show a system is free of contradiction you have to step outside it into a stronger framework, and that framework faces the same problem. The regress never ends. Hilbert had asked mathematics to prove its own reliability. Gödel showed that is exactly what it can never do.

Keep the second theorem in mind when a vendor tells you their AI can validate its own reasoning. A system that cannot fully certify itself from the inside is not a marketing gap. It is a mathematical fact.

The Halting Problem: Gödel's echo in the machine

Five years later, a twenty-three-year-old Englishman named Alan Turing reached the same wall from a different direction. His 1936 paper gave the world two things at once: a definition of what a computer fundamentally is, and a proof that even an idealized computer has hard limits.

Turing imagined a simple universal device, an infinite tape, a read and write head, and a finite set of rules. This Turing machine is a thought experiment, not a physical object, and he proved that anything computable by any reasonable process can be computed by such a machine.

Then he asked a practical-sounding question. Could you write a master program, a perfect universal debugger, which looks at any program and any input and tells you for certain whether it will finish or run forever? That is the Halting Problem. Suppose such a detector, call it H, exists. Now build a program P that runs H on itself and then does the opposite of whatever H predicts. If P halts, H said it would not, so it does not. If P does not halt, H said it would, so it does. Every branch is a contradiction. H cannot exist. Not because computers are slow. Because it is provably impossible.

The parallel to Gödel is not a coincidence. Both use self-reference to force a contradiction. Both show that certain questions asked from inside a system cannot be answered by that system.

Rice's Theorem: the result that matters most for cybersecurity

If the Halting Problem were one quirky corner of computing, its impact might stay small. In 1953, Henry Gordon Rice proved something far broader. No general algorithm can decide any non-trivial behavioral property of an arbitrary program. Not just "does it halt." Almost anything you actually want to know:

• Does this program contain a bug? Undecidable in general.
• Does it ever produce a particular output? Undecidable in general.
• Does it match its specification? Undecidable in general.
• Will it ever access forbidden memory? Undecidable in general.
• Is it free of malware? Undecidable in general.

The phrase "in general" carries the weight. Bounded, constrained versions of these questions often can be answered. Type checkers catch classes of errors. Static analyzers flag suspicious patterns. Formal verification proves properties of specific, carefully built systems. Those tools are real and valuable precisely because they are specialized.

What Rice ruled out is the universal version. No single algorithm can scan any arbitrary program and reliably report whether it has some non-trivial behavior. The perfect automated auditor, the tool that certifies the safety and correctness of any code, is not a hard engineering problem. It is a mathematical impossibility. Every federal security practitioner who has ever distrusted a green scan result already knew this in their gut. Rice proved it.

Church, lambda calculus, and why AI cannot escape

Turing was not alone in 1936. At Princeton, Alonzo Church attacked the same decision problem from a different angle, building an abstract algebra of functions called the lambda calculus. Different notation, identical conclusion. The Entscheidungsproblem has no solution.

When the two results were compared, something remarkable emerged. Church's system and Turing's machine could simulate each other perfectly. That convergence became the Church-Turing Thesis: any effective computation can be carried out by a Turing machine. It is not a theorem, because "effective procedure" is an informal idea, but the evidence is overwhelming. Every model of computation ever proposed, from quantum computers to neural networks to biological systems, has turned out to be equivalent in power to the Turing machine.

For AI, that carries a sobering implication. If all computation is Turing-equivalent, and Turing machines have provable limits, then those limits apply to any computational system, including the most advanced AI. No architecture, however powerful, escapes the map of undecidability that Gödel and Turing drew.

Why this matters for federal IT and cybersecurity today

These are not historical curiosities. They are load-bearing walls in everything we build with code.

Software verification and security

Every year, agencies and vendors spend enormous sums finding and fixing vulnerabilities, and every year new ones appear. Rice's Theorem says that it will never end, and not because the industry is incompetent. The perfect general verifier cannot exist. Fuzzing, static analysis, and formal verification earn their keep because they are bounded and specialized. Anyone who promises a complete, general solution, a tool that certifies any system as clean, is promising the impossible.

The same logic explains why perfect antivirus has never shipped. A program that could reliably flag every malicious program for every input would have to solve the Halting Problem. Real tools use signatures, heuristics, and behavioral sandboxing, all approximations wrapped around an undecidable core. That is the honest ceiling, and it is worth naming when someone pitches a silver bullet.

AI and the limits of self-certification

Large language models produce fluent, often accurate output. But can an AI guarantee its own outputs are correct, or verify that its own reasoning is sound? Gödel's Second Incompleteness Theorem points to the answer. No sufficiently powerful reasoning system can fully validate its own consistency from within. The dream of AI that self-certifies without external oversight is not blocked by weak engineering. It is blocked by principle.

In May 2026 this stopped being a philosophical extrapolation. NIST senior scientist Apostol Vassilev published a peer-reviewed proof in IEEE Security & Privacy, titled "Robust AI Security and Alignment: A Sisyphean Endeavor?", that extends Gödel's logic directly onto AI guardrails. The result: any finite set of safety rules governing an AI's behavior cannot be made universally robust against adversarial inputs. There will always be some prompt, not yet discovered, that defeats a fixed guardrail architecture. It is a close cousin of Rice's Theorem, arriving at the same practical place from a different direction, and it comes stamped by the federal government's own standards body.

Vassilev's prescription lines up almost exactly with where federal security is already heading:

• Constant red-teaming to find new adversarial prompts before adversaries do.
• Continuous hardening as each new failure mode surfaces.
• Operational resilience built on the assumption that some exploit eventually lands.

The goal, in his framing, is not an unbreakable system, which the math says does not exist. It is a system expensive enough to break that attackers run out of incentive before defenders run out of options.

What is and isn't affected

The mindset shift federal leaders should make

Notice what changes once you accept the proof. The old question was "how close to complete defense can we get?" That question is now retired. The better one is "how do we build systems that fail gracefully and recover fast, given that complete defense is off the table?"

That is fault-tolerant engineering more than security-as-assurance, and it reframes the attacker and defender relationship in an important way. The asymmetry between them is not just a temporary practical annoyance. It has a permanent mathematical component. Defenders can never hold a provably complete system. Attackers only need to find the gaps. Design for that reality and you stop chasing an impossible finish line and start building the thing that actually survives contact.

For teams standing up agentic AI, the stakes rise. Autonomous planning and acting surface the control, security, and alignment problems that compound as systems get more general. The same limits apply: no general algorithm can decide whether an AI is safe, aligned, or non-malicious across all inputs. That is precisely why layered defenses, alignment work, governance, and resilience engineering all have to run together. Fault tolerance is not a fallback. It is a permanent part of the solution.

Embracing the incompleteness

It is tempting to read all of this as defeat, a story where human ambition hits a wall and got turned back. That reading has it backwards.

In a single decade, a handful of mathematicians working with pencil and paper mapped the outer boundary of what systematic, algorithmic reason can reach. They did not fail to cross that boundary. They proved it was there and showed exactly where it sits. Cartographers used to write "here be dragons" at the edges of their maps. Gödel, Turing, Church, and Rice replaced the dragons with theorems.

For federal security, the lesson is steadying rather than grim. No machine, however capable, will ever automate away the need for judgment, red teams, and human oversight. That is not a shortcoming in the tooling waiting for the next release. It is the shape of the terrain. The agencies that internalize it stop buying silver bullets and start building programs that monitor continuously, test relentlessly, and recover quickly. Which, not by accident, is what the Risk Management Framework has been pointing at all along.

Frequently asked questions

Does this mean AI is too risky for federal use? No. It means AI security cannot be a checkbox. Paired with continuous monitoring, layered defenses, and resilient design, AI is deployable in serious environments. The proof argues for discipline, not avoidance.

Isn't continuous monitoring already required under RMF? Yes. ConMon is core to the Risk Management Framework. What is new is that the same logic now provably extends to AI guardrails, which closes the door on treating an AI authorization as a one-time event.

What is the first practical move? Stop treating guardrails as static documentation. Version them, monitor them, and test them continuously. Put adversarial testing inside CI/CD so it runs on every model update, prompt change, and agent reconfiguration, not once a year.

Does this apply to agentic AI and AGI too? Yes. Because all computation is Turing-equivalent, the same limits reach autonomous and general systems. The more capable and independent the system, the more these control and alignment problems compound, which raises the value of resilience engineering rather than lowering it.

What is the difference between Rice's Theorem and Vassilev's proof? Rice says no general algorithm can decide an arbitrary behavioral property of a program. Vassilev says no finite rulebook can achieve complete, contradiction-free coverage of an AI system's possible behaviors. Both descend from Gödel's 1931 insight and reach the same operational conclusion.

Who is Apostol Vassilev, and where can I read the proof? Vassilev is a senior scientist at NIST specializing in adversarial machine learning. NIST's announcement is on nist.gov, and the full paper appears in the May and June 2026 issue of IEEE Security & Privacy.

Sources and further reading

• NIST, "NIST Mathematical Proof Supports Transition to a Continuous-Monitor-and-Update Security Model for AI Systems" (June 2026)
• Apostol Vassilev, "Robust AI Security and Alignment: A Sisyphean Endeavor?", IEEE Security & Privacy (May and June 2026)
• Foundational work referenced throughout: Kurt Gödel (1931), Alan Turing (1936), Alonzo Church (1936), and Henry Gordon Rice (1953)

MFGS, Inc. is a U.S.-owned, FOCI-compliant provider of federal IT and cybersecurity solutions supporting the DoD, intelligence community, and civilian agencies.