Why Perfect AI Code Review Is Impossible
Transcript
Made automatically from the audio, so it may contain mistakes. Click a line to play from there.
So in our last deep dive into the source material, we were exploring zero knowledge proofs.
Right, yeah.
And it really felt like I don't know, a total victory for mathematics. Like we had finally figured out how to mathematically guarantee that we could prove a secret without ever actually revealing it.
Yeah, it's a very it's an empowering concept. You feel like you've completely conquered the machine's logic.
Exactly. But today we're doing a complete 180. We are bridging right from those unbreakable cryptographic guarantees to basically the ultimate question of the AI era.
The big one.
Right. Which is if large language models and autonomous agents keep getting smarter and smarter. I mean, if they can write code and deploy infrastructure, why can't we just build an AI verifier that reads any pull request or any workflow and mathematically guarantees it will never hang, never crash, and never fall for a prompt injection.
Well, because I mean that's the holy grail, right? An omniscient bug checker.
Yeah, an infallible auditor. But the my betting answer to why we don't have that yet isn't because we're waiting on like GPT 6.
No, not at all.
It's because we fundamentally mathematically cannot build it. Because in 1936, before a single electronic computer even existed, Alan Turing, who was 23 at the time, proved that this exact program mathematically cannot exist in our universe.
It's a hard law of physics for computation, just an absolute boundary.
And that boundary sets the stakes for you, the listener, as I officially welcome you to the series finale. This is part twelve, the conclusion of our hard problems and computing journey.
We've covered a lot of ground.
We really have. Over the past episodes from S0800 to S0801, we've synthesized everything from distributed state to the depths of recursion, right up to Rust's static borrow checker. And today, we are pulling all of that together to understand how elite systems actually survive by intentionally giving up absolute power.
Yeah, and to really get why Turing's proof was such a shock, you kind of have to understand the mood in mathematics before in 1936.
Okay, set the scene for us.
So back in the early 20th century, the biggest name in math was David Hilbert. And Hilbert had this this beautiful utopian dream called the finetary formalist program.
Right, because math was dealing with some weird paradoxes around infinity, right?
Exactly. Hilbert hated the ambiguity. So he proposed what he called the Entscheidungs problem.
The decision problem.
Right. He wanted a mechanical method, a strict, infallible rule book to determine the truth of literally any mathematical statement.
So basically a crank. Like you just feed a complex formula into a machine, turn the crank, and it spits out true or false. No human guessing required.
Exactly that just pure mechanical certainty. But then in 1931 Kurt Girdle comes along and just shatters the whole thing with his incompleteness theorems.
Right, Girdle. So how did he actually break Hilbert's crank?
Well he used this brilliant trick with Diophantine equations.
Hold on Diophantine equations we are jumping straight into the deep math here. For anyone who you know hasn't taken advanced algebra lately, why does Girdle care about those?
Good point. So diophantine equations are just polynomial equations where we only care about the integer solutions.
Okay. Whole numbers.
Right. Girdle cared about integers because they are discrete. They are distinct, countable steps. He realized he could take any logical proposition, like say this statement proves that statement, and map it to a unique integer.
Oh wow.
Yeah, it's called girdle numbering. He basically turned logic into arithmetic. And by doing that, he could write mathematical equations that were secretly talking about themselves.
Wait, so he essentially invented code. Like he wrote a math equation that translates to this specific equation cannot be proven.
You nailed it. He proved that in any sufficiently complex system, there are effectively generated sets that simply are not decidable. There are true statements that the system's own rules can never prove.
So Hilbert's dream of mechanical certainty was just dead on arrival.
Completely dead. Math was incomplete. And then just five years later, Alan Turing comes in and breaks computation before it's even born.
Right, 1936. So Turing was trying to solve that same decision problem.
Yeah. And he did it by inventing a theoretical machine, what we now call the universal computing machine.
And we should clarify in 1936 the word computer was actually a job title, right? Like a human clerk doing math on paper.
Exactly. Turing was literally modeling a human working with an infinitely long paper tape.
Okay, so picture an infinite paper tape with little squares.
Right. And the machine reads one square at a time. It has a finite number of internal states or M configurations. And based on its current state and the symbol on the tape, it just follows a strict rule book. Move left, move right, erase a one, print a zero.
Just the absolute core of what a CPU does today. Read memory, execute, write memory.
Exactly. And Turing realized these theoretical machines fall into two categories circle free machines and circular machines.
Okay, circular sounds like it's broken.
Like it's going in the circles. Right. In Turing's term, circular is the bad one. A circle free machine computes infinitely without hanging. Like calculating the digits of pi forever.
It just keeps doing its job.
Yeah. But a circular machine gets stuck. It hits a state where it has no valid moves left or it falls into an infinite loop, just spinning over empty squares forever.
It freezes.
Right. So the ultimate question for Turing was can we build a master machine that reads the blueprint of any other machine and mathematically predicts if it will be circle free.
Can we predict a freeze before we even turn it on?
Exactly. And Turing used a method called the diagonalization argument to prove that you can't.
Okay. Let's unpack this. Because diagonalization sounds like heavy math, and I want to keep this super grounded. Let's use that famous poem, The Loop Snooper, by Jeffrey K. Pullham to explain the paradox.
Oh, the loop snooper is absolutely the best way to visualize this. It makes it so clear. So Pullum says, let's imagine we somehow build that perfect bug checker. Let's call it program P.
Right. Program P is our omniscient AI auditor, the holy grail.
Yeah. You feed it some source code, and if that code is going to run safely and halt, P prints out good. But if the code has a flaw and is going to infinite loop, P prints out bad.
It seems pretty straightforward. P just outputs good or bad. So where's the trap?
The trap is that I can use P's perfection against it. I can write a tiny wrapper program, let's call it Q.
Okay, what does Q do?
Q takes a piece of code, asks P to evaluate it, and intercepts P's answer. If P says the code is bad and will loop forever, Q is programmed to immediately halt safely.
Oh, I see. And if P says good, meaning the code is safe.
Then Q intentionally throws itself into an infinite loop.
So Q is just a malicious troll program. Whatever the perfect Oracle predicts, Q is hard coded to do the exact opposite.
Exactly. Now here is the fatal blow of Turing's proof. What happens when you feed the source code of Q into Q itself?
Oh wow. Okay, let me trace this. So Q starts up, and the first thing it does is ask the Oracle Pull Q do.
Right.
If the perfect Oracle P predicts that Q will get stuck in an infinite loop, it says bad. But Q intercepts that, and based on its own rules, it immediately halts. So P was completely wrong.
Yep. And what if P predicts that Q will halt safely and says good?
Then Q intercepts the good, executes its rule book, and intentionally loops forever. So P is wrong again. It's mathematically guaranteed to be wrong.
Exactly.
It's like it's like a spiteful psychic. You find someone who guarantees they can predict your future perfectly. You ask them, am I gonna raise my left hand or my right hand? And whatever they say, you just do the exact opposite out of spite. The psychic cannot possibly be right because the prediction itself alters the outcome.
That's a perfect analogy. Turing proved that because you can always construct a spiteful wrapper like Q, a universal bug checker like P cannot exist. It is logically impossible.
That is just wild. A 23 year old in 1936 proved that the ultimate dream of modern AI code review is a mathematical mirage.
Yeah, and it gets even deeper. Because an infinite loop is just one kind of bug, right?
Right.
This concept evolved over time into what we call Rice's theorem.
Okay, Rice's theorem.
Yeah.
1953, right?
Yeah, Henry Gordon Rice extended Turing's work. Rice's theorem is essentially the great impenetrable wall of static program analysis. It proves that predicting almost any non-trivial behavior of a program is mathematically equivalent to solving the halting problem.
Wait, any non-trivial behavior.
Any non-trivial property at all. Like, does this code eventually access this specific memory address? Or does it trigger an out of bounds array error? Because of the halting problem, predicting any of those things with 100% certainty for all programs is undecidable.
Let's make that really concrete. Let's use Matt Might's array bounds example, because that makes it painfully real for any developer.
Sure.
How does checking a simple array index turn into the halting problem?
Okay. Imagine you're building a tool to just check if the expression AI ever causes an out of bounds error.
Seems simple enough.
Right. But to prove it's undecidable, we play a trick. We take a totally different mysterious program and we want to know if it halts. First, we rewrite that mysterious program so that every normal exit point is changed into an infinite loop.
Okay, so the mysterious program can never naturally finish now. If it reaches the end, it just spins forever.
Exactly. Then we take our target array check, AI, and wrap it in a logic block. We say, if I is perfectly valid, greater than zero and less than the array length, then immediately exit the entire program.
Got it.
And we drop that block right into the middle of our mysterious looping program.
Oh, I see the trap. So the only way this new hybrid program can ever cleanly exit is if that specific array index is safe and valid.
Right. Because we replaced all the normal exits with loops.
So if you build a magical tool that perfectly proves whether the array error happens or not, you've accidentally built a tool that proves whether the original mysterious program halts.
Yes. You've inextricably linked the array check directly to the termination of the program. And since Turing proved we can't decide termination, guaranteeing array bounds for all programs is equally impossible.
And the exact same problem.
Just wearing different clothes, yeah. This is the wall that static analysis hits.
And this ties back so perfectly to SO8E10, where we talked about Rust. Rust has this famously strict static borrow checker, right?
Oh, yeah. Very strict.
Yeah, because of this undecidability wall, tools like the Rust compiler are forced to make a deeply uncomfortable choice. They have to choose conservative soundness over completeness.
Exactly. Because the compiler mathematically cannot prove that every complex path is safe. It has to reject some perfectly valid code.
It essentially says I can't prove this is safe, so I'm assuming it's a bomb and I'm throwing a compiler.
Right. It has to be pessimistic. It sacrifices the completeness of accepting all good code just to ensure the absolute soundness of blocking all bad code.
Wow. It's crazy that a theoretical paper from 1936 dictates the daily frustrations of a modern Rust developer.
It really is.
But let's look at the flip side. Systems like Rust and EBPF survive by limiting their own power. But what happens when we do the exact opposite? What happens when a system that's just supposed to be a dumb configuration file. Secretly mutates into a Turing machine?
This is where things get genuinely terrifying. There's this famous list by Andreas Zwinkau called Accidentally touring Complete.
I love this list.
It's hilarious and horrifying. It highlights this massive vulnerability where if you accidentally give a system enough features, usually just some form of memory and some conditional branching, it can spontaneously acquire enough power to simulate Turing's universal machine.
And the examples are just they're mind blowing. Like the TypeScript type system is on there?
Yes. Not the JavaScript runtime executing the code, but the static type definitions themselves.
Right. People have built prime number checkers that run entirely during the compilation phase, just using the type system.
C templates and Java generics fell into the exact same trap. They were supposed to just be simple ways to say, you know, this is a list of integers. But the evaluation logic became rich enough to perform arbitrary computation.
Wait, it gets weirder. HTML5 combined with CSS3 is on the list.
Oh, that one is fascinating.
You can literally build a working computer out of HTML and CSS. How does that even work? CSS just makes buttons blue.
Well, to build a computer, you fundamentally just need memory and logic gates, right?
Yeah.
In HTML, a hidden checkbox can be checked or unchecked. That's your binary memory state, your ones and zeros.
Okay, sure.
And CSS has something called an adjacent sibling selector. It lets you say, if the checkbox is checked, apply this style to the element next to it.
Oh my god. So the checkbox is the RAM and the adjacent sibling selector acts as the if-then logic gate.
Exactly. You chain enough of those together and you have a processor. You can run a rule 110 cellular automaton, which is mathematically proven to be Turing complete.
That is insane. And it's not just web stuff. Recursive SQL is on the list. Using common table expressions, people are out there rendering fractals like the Mandelbrot set using pure SQL queries.
Yeah, SQL is definitely Turing complete if you use CTEs.
My favorites of the games, though. Like Magic the Gathering.
Oh, right. The rulebook for magic is so ridiculously complex that researchers proved you can arrange a specific board state where optimal play actually forces the game to simulate a Turing machine.
But how does a card game simulate a paper tape?
The creature tokens on the board act as the infinite tape. And the triggers like when this creature enters the battlefield act as the read-write head, moving back and forth, making new tokens or destroying them. Determining who wins that specific game is mathematically equivalent to the halting problem.
That is brilliant. Or the Super Mario World Memory Glitches, where speedrunners use pixel coordinates to write arbitrary code directly into the Super Nintendo's memory, building Flappy Bird inside Mario.
It's a gorgeous display of hacking.
Okay, but while it's a great party trick to run Doom in PowerPoint or whatever, why does this actually matter? What is the real world consequence if say an email config file is accidentally Turing complete?
The consequence is the core of why this matters for infrastructure. If a system is Turing complete, it is subject to the halting problem, period.
So it can get stuck.
It means it can mathematically get stuck in an infinite loop and consume unbounded resources. If your network routing protocol, like BGP or your email config is Turing complete, a malicious actor or just a clumsy dev can hand you a config that freezes your servers forever.
And because of Alan Turing, you can't build a pre-checker to catch it before it loads. Exactly.
Wow. You just have to run it and pray.
Okay. Let's move from the theory into an absolute production nightmare. Let's talk about the Cloudflare outage of July 2nd, 2019.
Yeah, this is the classic painful case study in hitting the limits of computability on a global scale.
Just to set that stage, Cloudflare's massive. A huge percentage of the entire internet flows through their edge nodes. And on that Tuesday, an engineer deployed what they thought was just a minor routine update to the web application firewall, the WAF.
Right. They were trying to improve detection of cross-site scripting attacks, finding malicious JavaScript payloads. And it went through standard CI CD, the tests passed.
They were even cautious enough to deploy it in simulate mode first. It wasn't supposed to block traffic, just silently observe and measure false positives. But the second it hit the global edge network, the alarms went crazy.
Yeah, first a localized CPU alert, and then three minutes later, a global traffic drop alert. Customers worldwide just slammed into a wall of 502 bad gateway errors.
The CPU usage on the edge servers, as specifically the core serving HTTP and HTTPS traffic, spiked to nearly 100% globally. The servers just locked up. For 27 agonizing minutes, a huge chunk of the internet was just blacked out.
And the root cause was a single regular expression denial of service vulnerability, a reados.
Let's break down the mechanics of this because the regex snippet they shared in the post-mortem looks like gibberish. But Cloudflare simplified the core problem down to this tiny string.
That tiny string is a ticking time bomb. Because of how standard regex engines like PCRE process text, when you write dot plus, you're telling the engine to match zero or more of any character and to do it greedily.
Greedily meaning it tries to eat the whole string of text immediately.
Yes. So in dot star dot star equals plus, the first dot star tries to eat everything. Then the engine realizes, wait, I still need to match another dot and an equal sign, so it has to backtrack.
It spits out the last character, takes a step back and tries again.
Right. And if that fails, it spits out another character. It methodically explores every possible combination of matching characters against those two overlapping greedy blocks.
And because there are two dot star patterns back to back, the permutations just explode.
They scale exponentially. Big O of two to the power of N. Cloudflare shared this data point. If you feed the string X equals X into that engine, it takes 11 steps to match.
Not bad.
But what if a weird request sends X equals followed by 20 X's?
Okay, so 20 characters.
Because of the overlapping wildcards, the engine is forced to explore every single possible path of assigning those 20xs between the two blocks before it finally gives up. For just 20 characters, it took 5,353 computational steps to fail.
Over 5,000 steps for 20 characters.
And attackers know this. Yeah. They send slightly longer garbage strings to intentionally trigger worst case backtracking. A few dozen requests can pin a CP to 100%, starving all other traffic.
So a system allowing unbounded backtracking gets stuck in the mud. How do you fix that? How do we ever parse text safely at scale?
We go back to 1968 to Ken Thompson. He realized backtracking is a trap. He developed an algorithm to convert a regular expression into a non-deterministic finite automaton, an NFA.
A finite automaton.
We're right back to Turing state machines.
Exactly.
But the brilliant part is how it executes. Instead of trying one path, hitting a dead end and backtracking, the NFA engine processes the string while existing in multiple states simultaneously.
Wait, how can a computer be in multiple states at once?
Think of it like pouring water into a complex maze. The water doesn't go down one path, stop and magically flow backward. It flows down all open paths at the same time. If a path hits a dead end, the water there just stops. But the water in the open paths keeps moving forward.
Oh, that's a great analogy. So it reads each character exactly once, like a wave, and updates all the states in parallel.
Yes. Because it never backtracks, the processing time is strictly linear based on the string length, big O of N. Whether it's 20 characters or 20,000, it's one single pass. This is what's used in Google's RE2 or classic Unix tools like AUK and Grep.
So Cloudflare's fix was swapping their engine for RE2, which guarantees linear time. But to get that guarantee, they had to give up complex features like back references. They gave up power for absolute certainty.
Which is the synthesis of modern elite engineering. Turing completeness is a liability. Elite systems win by giving up power.
And we see that philosophy in the Linux kernel too with EVPF.
Absolutely.
If a regex can take down Cloudflare, how could we safely run untrusted code deep inside the operating system kernel? Because EBPF lets developers run sandboxed programs right in ring zero, hooking into network events or system calls.
Right, and if an eBPF program goes into an infinite loop, the whole OS freezes. Your server is dead.
And we just established you can't build a verifier to catch infinite loops. So how do they do it?
By explicitly making eBPF not Turing complete. Before eBPF code attaches to a kernel hook, it goes through a viciously strict static verifier. First it does a directed acyclic graph check, a DAG check.
Okay. Acyclic meaning no cycles, no loops, the code only flows forward.
Exactly. Historically, eBPF forbade all loops. Now they allow bounded loops, but the rules are draconian. The verifier has to mathematically prove by simulating every execution path that the loop has a strict, unchangeable exit condition that will be met within a finite complexity limit. If it can't guarantee that, it rejects the code.
It chooses soundness over completeness, just like Rust. Rejects code that might be fine just to guarantee it never accepts code that freezes the kernel.
Precisely. And it cracks every register state. It guarantees the program finishes in microseconds without crashing or accessing forbidden memory, all by sacrificing Turing completeness.
And we see this in authorization policies too, like Google CEL.
Right, the common expression language. If you're evaluating an API list filter or an OPA Rego policy for cloud access, it has to happen in nanoseconds.
Yeah, if my access policy hits a recursive loop, the whole cloud stops while it tries to figure out if I'm an admin.
So CEL is strictly non-Turing complete.
It's a total language like DAL. Every expression is guaranteed to terminate. And because of that restricted grammar, you can use formal verification.
This goes all the way back to Hilbert's dream. Yes. You can use Theorem Provers like the Z3 SMT solver or Lamport's TLA plus bounded model checking to mathematically prove that your policy maintains security and variance across the entire infinite input space. You get mathematical certainty, but only by limiting the language.
But you know the software industry right now is moving in the exact opposite direction. Everyone is rushing toward unconstrained AI agents.
And this is where the theoretical danger becomes an immediate threat. The vibecoder trap.
Right, a vibe coder being someone who just prompts an LLM to generate code without really understanding the mechanics.
The first trap is the AI illusion, treating the LLM as that omniscient auditor. You paste untrusted code into a prompt and ask, does this have infinite loops? Is it secure?
And the AI confidently says, yes, I've reviewed it, it's perfectly secure.
But an LLM is just a computable function. It's bound by the church Turing thesis.
It's just another Turing machine.
Exactly. And Turing proved no machine can perfectly analyze another machine. Because of the halting problem, no AI can mathematically guarantee a pull request is free of logic bombs. Relying on it as a perfect auditor is a fallacy.
And like the UK NCSC and Simon Willison point out, LLMs operate on token streams. They don't have a strict boundary between code and data. You can't guarantee it won't fall for prompt injection.
Right. And the second trap is worse. Letting the AI generate the code itself without constraints. Let's look at the OWASP top 10 for LLMs, specifically LLM10, unbounded consumption.
Let's role play this. Say I tell an AI agent, connect to the database and write a script to clean up user roles.
Highly realistic. The AI looks at the schema, sees a hierarchy, and writes a recursive SQL query, a CTE.
Which is accidentally Turing complete.
Yes. And remember, the AI generates the statistical average of public code, which is flawed. So it hallucinates a join condition that slightly misses, creating a circular reference. Bob reports to Alice, Alice reports to Charlie, and the AI makes Charlie report to Bob.
Oh no. And the agent deploys it.
It executes it. The database traverses the hierarchy. Bob, Alice, Charlie, Bob, Alice, Charlie. Because the AI didn't include a cycle cap, the query infinite loops. Your database CPU hits 100%, logins timeout, application goes down. The agent just launched an accidental denial of service attack because it flew blind into the halting problem.
Unbounded consumption. If you ask for a data filter, it uses a val, opening you do arbitrary code execution.
If you let an agent write a Turing complete loop without a physical step circuit breaker or a hard dollar limit, you're handing a loaded gun to a system that mathematically cannot prove it won't pull the trigger.
Okay, so what's the playbook for the listener? Give us concrete constraints we can implement right now.
Be explicit and dictatorial in your prompts. Demand invariance. Don't just ask for a regex. Dictate use linear time RE2 syntax, no nested quantifiers, no back references.
What about generating user data filters?
Demand total DSLs. Tell it to use CEL or strictly validate against a JSON schema. Explicitly forbid eval or Turing complete scripts for untrusted data.
And for databases or autonomous loops to prevent that CTE disaster.
Institute hard system invariants. Force manual termination. If it writes recursive SQL, mandate a strict cycle limit clause. Put hard max iterations counters in any while loop. Use aggressive wall clock timeouts for network requests and deterministic sandboxes. Put a literal dollar limit on compute.
But you know, we don't want to over-engineer everything. Yagni still applies.
Absolutely. You aren't gonna need it. Don't use TLA plus for a simple internal crud app. That's an overkill. Apply these guardrails at the boundaries, where untrusted input hits complex logic, or where agents generate production policy.
Okay. As we wrap up this episode and this entire series finale, let's tie this 13-part journey together. From S08E00 to S08E12. We looked at how distributed systems struggle with time and order, how primitives like strings and floating point math are deceptively broken. We conquered logic with zero knowledge proofs. And now we've hit the absolute limits of computation.
The builder's mandate for this new era is this. AI coding agents are incredibly fast, but they generate the statistical average of human code. And human code is full of undecidable traps, backtracking regexes, unbounded loops, accidental Turing machines.
So our job changes.
Entirely. Recognizing the halting problem in a code review, supplying the strict invariants, the DAG checks, the non-Turing completeness of CEL, the SQL cycle caps that an AI simply cannot deduce on its own.
We have to become the architects of the boundaries. Which brings us to a final thought for you to chew on. If we're rapidly building AI agents that write other AI agents, and all of them are inherently bound by Turing's undecidability, are we inevitably building a digital ecosystem where catastrophic, unpredictable freezes are just a lot of physics?
It's a highly probable thought.
And if so, perhaps the ultimate skill of the future isn't writing code at all. It's writing the exact boundaries where code must stop. Thank you for taking this 13-part journey with us. Keep building, keep questioning the boundaries, and we will catch you on the next deep dive.