What AI cannot do, no matter how capable it gets

In a 2026 evaluation on C programs from an international software verification competition, frontier language models were asked to decide whether programs terminate. They ranked just behind the top specialist verification tools.

Turing proved in 1936 that no algorithm can decide this. The halting problem is undecidable, and that proof has not been weakened by anything since.

Both statements are correct, and the apparent contradiction between them is where almost every popular claim about the limits of AI goes wrong, in both directions.

Undecidable does not mean "cannot be determined." It means no single procedure works for every input. Most programs anyone actually writes are easy to decide. The impossibility is about universality, and confusing it with difficulty produces both the claim that AI has broken a mathematical law and the claim that AI can never do useful verification. Neither follows.

Three different failures, routinely conflated

The phrase "AI can't do that" covers three situations with completely different structures. Sorting them is most of the work.

Undecidable. No algorithm exists, for any amount of compute, ever. The halting problem is the canonical case, and Rice's theorem generalises it brutally: almost any non-trivial property of a program's behaviour is undecidable. Not hard, not expensive, not currently out of reach. There is no procedure.

Intractable. An algorithm exists and its cost grows exponentially with problem size. Many optimisation and scheduling problems sit here. Exponential growth in available compute does not beat super-exponential algorithms, so this is a wall too, and it is a different wall: something exists, and running it is impossible at scale.

Currently difficult. No fundamental barrier, just a capability we do not have yet. Most things people list as AI limits are here, and this category moves.

The errors follow mechanically from confusing them. Treating a currently-difficult problem as undecidable produces false pessimism. Treating an intractable problem as merely difficult produces the belief that a better model will solve it. And treating an undecidable problem as intractable produces the idea that enough compute would settle it, which it never will.

Why models do well on halting anyway

The resolution of the opening contradiction, and it is worth understanding rather than filing away.

Undecidability is a statement about the worst case over all possible inputs. It says no procedure decides correctly for every program. It says nothing about any particular program, and it certainly does not say programs are generally hard to analyse.

Real code is not adversarial. Loops have obvious bounds, recursion has visible base cases, the pathological constructions that make the proof work are constructions rather than things anyone writes. A tool that answers correctly on the overwhelming majority of real programs and gives up on the rest is useful, and it has not solved anything undecidable, because giving up on the rest is exactly the escape.

Every practical verification tool works this way. It returns yes, no, or I cannot tell. That third option is what keeps it consistent with Turing's proof, and any system claiming to always answer yes or no is either wrong or lying.

So a language model performing near specialist tools is a statement about the distribution of real programs, not about computability. The correct read is that the easy cases are more common than people assume, which was already true of the specialist tools.

The bound that applies to transformers specifically

A separate limit, narrower than undecidability and more immediately relevant.

A transformer performs a fixed amount of computation per token generated. Attention over a sequence of length N with dimension d costs roughly N² times d, and that budget does not expand because the problem is hard. A model given a difficult question and an easy question spends the same compute per token on both.

Work in early 2026 formalised the consequence: problems whose required computation exceeds that per-token budget cannot be solved correctly by a single forward pass, regardless of prompting or architecture. The model will produce output anyway, because producing output is what it does, and that output is a confident guess.

This reframes a class of hallucination. Not all confabulation is a training artifact. Some is a system being asked for an answer that its computational budget cannot contain, and responding with the only thing it can produce.

The consequence for reasoning models is that extended chains of thought truly help here, because they convert one forward pass into many and therefore buy more total computation. That is a real mechanism rather than a metaphor. It is also bounded: more steps is a linear increase against problems that grow exponentially.

Why one model cannot check another on hard problems

The sharpest practical consequence, and it connects directly to how evaluation is being built.

Verification is not automatically cheaper than solution. For some problems, checking an answer is far easier than finding one, which is the entire basis of the class NP and the reason a completed Sudoku takes seconds to check and twenty minutes to fill. For others, verification requires the same or more computation than solving.

Where verification is as hard as the problem, using a model to check a model's work provides no assurance. The checker faces the same computational wall as the solver, and if both are transformers with the same per-token budget, they face it identically.

This is a stronger objection than the usual one about judges sharing training data and correlating in their errors. That is an empirical concern about bias. This is structural: even a perfectly unbiased model of the same architecture cannot verify what it cannot compute.

The routing rule that falls out: verification must come from a system with different computational properties, not merely a different model. A solver, a type checker, a test suite, a simulation. Anything that can spend unbounded time on a bounded question.

A test you can apply to any "AI will never" claim

The three categories are only useful if you can sort a claim into one, so here is the procedure, which takes about a minute.

Ask what would happen with unlimited compute and a perfect model.

If the answer is still no, it is undecidable, and the claim is permanent. "AI will never be able to determine whether an arbitrary program terminates" survives this test. So does "AI will never be able to prove all true statements of arithmetic."

If the answer is yes but the compute required grows exponentially with problem size, it is intractable. "AI will never optimally schedule a thousand-machine factory" is here. Permanent in the worst case, and routinely worked around in practice, which is why the claim is technically true and practically misleading.

If the answer is yes and the compute is reasonable, it is currently difficult, and the claim is a prediction rather than a theorem. Almost everything in circulation is here. "AI will never write a good novel" and "AI will never do original mathematics" are predictions about capability, and predictions of that shape have a poor record.

The tell that a claim is in the third category and pretending to be in the first: it appeals to something about the nature of intelligence, understanding or consciousness rather than to a counting argument or a diagonalisation. Impossibility results are proved by construction. If there is no construction, there is no impossibility, however confident the phrasing.

The reverse tell is worth having too. When someone claims a system has overcome a limit in the first category, check whether they have changed the problem. Answering "I cannot tell" on hard cases, restricting the input language, or reporting a probability rather than a decision are all legitimate and all mean the original question is being declined rather than solved.

What actually extends the boundary

Three things move it, and none of them is a bigger model.

External computation. Handing the problem to a system that can iterate is the whole answer to the per-token bound. A SAT solver may run for hours on a question a transformer must answer in one pass. The model's job becomes recognising and formulating, which it is good at, rather than computing, which it is bounded at.

Accepting an incomplete answer. Verification tools return "I cannot tell" and remain useful. Systems designed to always answer are the ones that fail, and abstention is a feature that most deployed models are trained out of.

Restricting the input. Undecidability applies to arbitrary programs. Restrict the language enough and termination becomes decidable, which is why total functional languages exist. Narrowing the domain to buy a guarantee is a legitimate trade and it is the same one made when choosing a symbolic component over a learned one.

Notice that all three change the problem or the machinery rather than improving the model. The limits discussed here are not addressed by capability, and the recurring commercial mistake is trying to buy past them.

The part that keeps it honest

These bounds are not about artificial intelligence. They are about computation.

Humans cannot solve the halting problem either. No mathematician can look at an arbitrary program and always determine whether it terminates, and no amount of intelligence changes that, because the proof does not mention intelligence. It concerns any procedure whatsoever.

So the correct conclusion is narrower than it usually gets stated. Undecidability does not establish that machine intelligence is impossible, or that some human faculty exceeds computation. It establishes that certain questions have no procedural answer, and every reasoner, biological or otherwise, is subject to that.

The useful form of the observation is about system design rather than philosophy: build systems that can say they do not know, because for some questions that is the only correct output available to anything.

What is unresolved

Whether P equals NP. If they were equal, a large class of problems currently intractable would become tractable, and the practical landscape would change substantially. Nearly everyone expects they are not equal and nobody has proved it. Whether machine assistance changes the odds of a proof is being argued about, and the sceptical position notes that a proof must rule out infinitely many possible algorithms, which is not the kind of thing more search finds.

How tight the transformer bound is in practice. The per-token argument is clean in theory. How much extended reasoning, tool use and multi-agent decomposition actually buy against it is an empirical question with early and contested answers.

Whether heuristics have a ceiling. Much of AI is heuristics that beat worst-case bounds on realistic inputs. There are argued to be fundamental limits on how good heuristics can get, and where that ceiling sits for any particular problem class is not established.

And whether real problem distributions stay friendly. The halting result above depends on real programs being easy. If systems begin generating code at scale, the distribution of programs being analysed is no longer the distribution humans write, and nobody knows what that does to the easy-case assumption.

The counter-argument

This can be used to dismiss things unfairly. Pointing at undecidability to argue a system cannot do useful verification is exactly the error the article opens with. Impossibility results constrain guarantees, not usefulness, and a tool that handles 95% of real cases is valuable regardless of what the remaining 5% proves.

The transformer bound may matter less than it sounds. It concerns a single forward pass. Real systems loop, call tools, decompose and retry, and the practical ceiling of that combination has not been characterised. Treating a per-pass result as a system-level limit overstates it.

Complexity theory is about worst cases. Most instances of NP-hard problems encountered in practice are solved routinely by commercial optimisers. Reasoning from worst-case classification to practical impossibility is a standard error, and this article risks encouraging it.

And humans work around these limits constantly. We do not solve the halting problem; we write code in ways that make termination obvious, add timeouts, and restrict what we build. The bounds are real and they have never stopped anything, which is worth remembering before treating them as ceilings on ambition.

The short version

Frontier models rank just behind specialist tools at deciding whether real programs terminate, and Turing proved in 1936 that no algorithm can decide this in general. Both are true, because undecidable means no single procedure works for every input, not that any particular input is hard. Real programs are not adversarial, and every practical verification tool preserves consistency with the proof by being allowed to answer "I cannot tell."

Three distinct failures get conflated. Undecidable, where no algorithm exists at any budget, generalised by Rice's theorem to almost any non-trivial property of program behaviour. Intractable, where an algorithm exists and costs grow exponentially, so no amount of hardware progress reaches it. And currently difficult, which is where most claimed AI limits actually sit and which moves over time.

A narrower bound applies to transformers specifically. A model spends a fixed amount of computation per token, so problems requiring more than that budget cannot be answered correctly in a single pass, and the model produces confident output anyway because that is what it does. Extended reasoning truly helps by converting one pass into many, and it is a linear gain against exponential problems.

The practical consequence is sharper than the usual concern about judges sharing biases: where verification is as hard as solving, a model cannot check another model's work, because the checker faces the same computational wall. Verification has to come from a system with different computational properties, not just a different model.

And none of this is about artificial intelligence. Humans cannot solve the halting problem either, and the proof does not mention intelligence. The useful conclusion is about design rather than philosophy: build systems that can say they do not know, because for some questions that is the only correct output available to anything.

Common questions

What can AI never do? Solve undecidable problems, which are questions no algorithm can answer for all inputs regardless of compute. The halting problem is the canonical example, and Rice's theorem extends it to almost any non-trivial property of a program's behaviour. This is a property of computation rather than of AI, so humans cannot solve them either. Separately, intractable problems have algorithms whose cost grows exponentially, which is a different wall reached by scale rather than by principle.

Can AI solve the halting problem? No, and it can perform well on real instances, which is not the same thing. Undecidability means no procedure decides correctly for every possible program, not that any given program is hard. Frontier models evaluated on a 2026 verification competition ranked just behind specialist tools, because real code is not adversarial and the pathological cases in the proof are constructions rather than things people write. Practical tools stay consistent with the proof by being allowed to answer that they cannot tell.

What is the difference between undecidable and intractable? Undecidable means no algorithm exists at all, for any amount of time or hardware. Intractable means an algorithm exists but its cost grows exponentially with problem size, so it becomes impossible to run at realistic scale. They are frequently conflated, and the confusion matters: more compute never touches an undecidable problem, while an intractable one is truly affected by better hardware and better heuristics, just not enough.

Can AI solve NP-hard problems? It can solve many instances of them, which is what commercial optimisers have done for decades, and it cannot solve them in general in polynomial time unless P equals NP. Most people expect P does not equal NP and nobody has proved it. The important practical point is that complexity classes describe worst cases, and real instances are frequently far easier, so reasoning from NP-hardness to practical impossibility is a common error.

Why do language models hallucinate on hard problems? Partly because a transformer performs a fixed amount of computation per token generated, so a question whose required computation exceeds that budget cannot be answered correctly in a single pass. The model produces output regardless, because producing output is what it does, and that output is a confident guess. This reframes some hallucination as a computational limit rather than a training artifact, and it is why extended reasoning helps: more steps means more total computation.

Can one AI model verify another's work? Not reliably on computationally hard problems. Verification is only cheap for some problems, which is what the class NP describes, and for others it costs as much as solving. Where that holds, a checking model faces the same computational wall as the solving model, so it provides no assurance. This is a structural objection distinct from the empirical concern that judges share training data and correlate in their errors. Verification needs a system with different computational properties, such as a solver, a type checker or a test suite.

Does the halting problem mean AGI is impossible? No. The proof concerns any procedure, so it constrains humans equally, and nobody concludes from it that human intelligence is impossible. What it establishes is that certain questions have no procedural answer, and any reasoner is subject to that. The useful conclusion is about design: systems should be able to report that they do not know, because for some questions that is the only correct output available.

What actually extends what AI can do? Three things, none of which is a larger model. External computation, where the problem goes to a system that can iterate for as long as it needs, such as a solver running for hours on a question a model must answer in one pass. Accepting incomplete answers, since tools that report uncertainty stay useful while systems built to always answer fail. And restricting the input domain, since undecidability applies to arbitrary programs and narrower languages can be made decidable by construction.