What Can No Machine Ever Compute?

Somewhere in an idealized workshop, a machine reads symbols off an infinite paper tape, one square at a time, following a fixed table of rules. It is the most stripped-down device imaginable — no silicon, no clock speed, no memory hierarchy, just a read-write head and a rulebook. And yet this austere contraption, invented in 1936 by a 24-year-old mathematician trying to settle a question about the foundations of logic, turned out to be either the most powerful computational object that can possibly exist, or merely the most powerful one we've thought of so far. Nobody knows which. That uncertainty, patient and almost embarrassingly simple to state, is one of the strangest open wounds in all of science.

The machine is the Turing machine, and the question it raises has outlived every technology built in its shadow: transistors, lasers, superconducting qubits, strands of DNA. Ask a physicist what energy is, and she can point to a conserved quantity in Noether's theorem. Ask a computer scientist what is computable, and he will eventually have to shrug and say: computable by what, exactly — and how do you know you've imagined the most powerful "what" there could be?

This isn't a question about engineering better computers. It's a question about whether "computation" itself, as a concept, has a fixed, discoverable boundary set by the laws of physics — the way the speed of light sets a boundary on velocity — or whether it is an open-ended frontier that could, in principle, be pushed outward forever by stranger and stranger physics. We have a very good guess about where that boundary lies. We do not have proof.

svg[The landscape of computability, and where the open question lives]

:::The outer boundary — "Turing-computable" — is where the Church-Turing thesis says all physical computation must live. Inside it, P versus NP asks how much of that territory is reachable efficiently. Whether the outer boundary itself could be pushed outward by exotic physics is the frontier this essay is about.

The diagram above deliberately places two different open questions side by side, because they are often confused and they are not the same question. Inside the blue ellipse of Turing-computability sits the much narrower question of efficient computability — the P versus NP problem, which asks whether every problem whose solution can be quickly verified can also be quickly found. That is a question about resources — time and space — within the world of what's computable at all. It presupposes the Church-Turing boundary and asks how the territory inside it is structured. The question this essay is about is different and, in a sense, more primitive: it asks whether the boundary itself, the blue ellipse, is really the outer wall of physical possibility, or whether some part of the gray region outside it — the undecidable — might secretly be reachable by a machine built from the right exotic physics.

A third, related frontier is quantum computation and the limits of BQP, which explores whether quantum mechanics lets us compute some things exponentially faster than classical devices (as with Shor's factoring algorithm), while — importantly — quantum computers are still Turing-computable in the classical sense. A quantum computer cannot solve the halting problem. It can be simulated by a classical Turing machine, just perhaps with an astronomical time penalty. So quantum computing, radical as it looks, has not (so far) touched the outer wall at all; it has only rearranged the furniture inside the efficiently-computable room. That fact is itself informative: even the strangest confirmed physics of the twentieth century left the Church-Turing boundary completely intact. This is part of why the thesis commands such confidence.

If the classical Church-Turing thesis is so well-supported, why call it an open question at all? Because "well-supported" is not "proven," and there are specific, serious places where the ground gets uncertain — not because anyone has found a working counterexample, but because our theories of physics keep producing hypothetical scenarios that would be counterexamples if they turned out to be physically realizable. Three of these deserve a close look, because each teaches something different about where the real uncertainty lives.

The trouble with infinite tasks. Imagine a machine that performs its first step in half a second, its second step in a quarter second, its third in an eighth, and so on — a geometric series that sums to exactly one second. After one second has elapsed, has it performed infinitely many steps? This is the idea behind so-called "Zeno machines" or accelerated Turing machines, and it isn't merely a thought experiment confined to logic seminars: general relativity actually contains solutions, called Malament-Hogarth spacetimes, in which an observer could in principle watch an infinite computation unfold along another worldline that only takes a finite proper time from the observer's own perspective, because of the extreme time dilation near certain kinds of spacetime singularities or event horizons. If you could send a Turing machine into such a spacetime region and station yourself at the right vantage point, you could — at least according to the mathematics of general relativity taken at face value — receive a signal in finite time telling you whether that Turing machine ever halts, even if it runs literally forever from its own point of view. That would decide the halting problem. Physicists including Itamar Pitowsky and later Gábor Etesi and István Németi have taken this seriously enough to publish analyses of exactly what kind of spacetime and what kind of physical signal would be required.

Nobody thinks we will ever build one of these. The engineering requirements are absurd — you'd need to actually construct or locate a very particular kind of rotating black hole, survive the trip, and solve serious problems about noise, quantum effects near the horizon, and the actual global structure of the spacetime in question, which quantum gravity might forbid entirely. But the honest point is this: the objection to Malament-Hogarth computers is not a proof that they're impossible. It's a well-founded suspicion, resting on unresolved questions in quantum gravity, that the classical general-relativistic solutions permitting them are not the final physical story. Nobody has shown that quantum gravity rules them out. Nobody has shown it doesn't.

The trouble with continuous physics. Classical physics, at the level of Newtonian mechanics and general relativity, traffics in real numbers — continuous quantities with, formally, infinite precision. A real number can encode infinite information; almost all real numbers, in fact, are not even individually specifiable by any finite description, let alone computable by an algorithm (this is a consequence of a counting argument nearly identical to the one Turing used against the halting problem — there are only countably many Turing machines but uncountably many reals). If nature's fundamental quantities really are continuous, unbounded-precision reals, and if some physical process could be built that reads out such a quantity to unlimited precision, you could in principle encode uncomputable information directly into the geometry of the universe and read it back out. This is the seed of proposals for "analog" hypercomputers — devices exploiting continuous-valued fields, like certain idealized fluid systems or wave-based analog computers, that some researchers (going back to Claude Shannon's differential analyzer studies, and more recently pursued by figures like Hava Siegelmann with her work on analog recurrent neural networks) have argued could in principle compute non-Turing-computable functions, if the underlying continuous parameters could be realized and manipulated with true, unbounded precision.

The catch, and it is a serious one, is that physical measurement is always noisy, and quantum mechanics itself seems to forbid the kind of infinite-precision readout these schemes require. The uncertainty principle, thermal noise, and the discreteness suggested by quantum mechanics (photons come in discrete quanta; angular momentum is quantized) all conspire to make it look, at least under our current theories, as though nature never actually lets you access an infinite-precision continuous parameter — even if the underlying mathematics describing space and time is written in the language of real numbers. Whether spacetime itself is fundamentally continuous or secretly discrete at the Planck scale is itself one of the deepest open questions in physics, closely tied to the search for quantum gravity. So this route to hypercomputation runs straight into an unresolved question about the ultimate texture of physical reality.

The trouble with quantum measurement and "oracle" proposals. Some more exotic proposals imagine using quantum mechanics not for speedup (the BQP story) but for something structurally different: encoding an infinite computation into a quantum superposition and then somehow "reading off" the answer to an undecidable question via a clever measurement. These schemes have repeatedly turned out, on close analysis, to secretly assume some form of infinite precision or an infinite number of steps performed in finite time — smuggling in a Malament-Hogarth-style or infinite-precision assumption under a different name. This pattern — an initially exciting hypercomputation proposal that, upon rigorous inspection, always turns out to hide an unphysical idealization — has repeated often enough that many computer scientists treat it as near-empirical evidence for the physical Church-Turing thesis. But "every attempt has failed so far" is inductive evidence, not deductive proof, and the history of physics is not short on examples where the "obviously impossible" waited a century for its refutation.

There is a second, quieter kind of breakdown worth naming, which is not about hypercomputation but about the thesis's own logical status. Gödel's incompleteness theorems show that any sufficiently powerful, consistent formal system of arithmetic contains true statements it cannot prove. Gödel himself, in private correspondence and later remarks, wondered whether the human mind might not be bound by the same limitations as a fixed formal system — whether human mathematical insight could somehow "see" the truth of Gödel sentences that no fixed mechanical procedure could certify. This is the seed of arguments later made explicitly (and controversially) by the philosopher J.R. Lucas and, more famously, the physicist Roger Penrose, who has argued across several books that human mathematical understanding cannot be the product of any algorithmic process, and that this points toward some as-yet-unknown non-computable physics operating in the brain, possibly connected to quantum gravitational effects in microtubules within neurons. This argument is almost universally rejected by computer scientists and most philosophers of mind, on grounds that are themselves interesting: the argument seems to require that humans can somehow know, with certainty, their own total consistency — a kind of self-knowledge that Gödel's own theorem suggests is exactly what a truly rigorous formal reasoner cannot have. But it is worth stating plainly that this is a real, serious disagreement among serious people, not a resolved matter, and it links the computability question directly to the frontier of Gödel incompleteness and mathematical truth: is the human mind itself a Turing machine, a hypercomputer, or something for which the question doesn't even cleanly apply?

There isn't a tidy two-sided debate here so much as a spectrum of positions, each with real defenders and real weaknesses.

Position one: the thesis is a law of nature, effectively as solid as conservation of energy. This is the majority position among computer scientists and most physicists. Its appeal is enormous: every physical process ever experimentally probed — chemical reactions, planetary orbits, particle collisions, even the strange nonlocal correlations of quantum entanglement — has been successfully simulated, in principle, by a classical Turing machine (perhaps an impractically slow one, but that's a resource question, not a computability one). No physical experiment has ever produced an output that required uncomputable information to explain. Proponents such as the computer scientist Scott Aaronson have argued forcefully that the physical Church-Turing thesis deserves to be treated with the same provisional-but-firm confidence as the second law of thermodynamics: not derivable from pure logic, but so thoroughly and repeatedly confirmed, and so deeply woven into every successful physical theory we have, that betting against it looks a lot like betting against entropy increasing. The trouble with this position is precisely that it is inductive. Every physical theory we have used to test the thesis — Newtonian mechanics, electromagnetism, special and general relativity, quantum mechanics, the Standard Model — is known to be incomplete. We do not have a theory of quantum gravity. It is at least logically possible that the completed theory of physics contains processes not describable by any Turing machine, and every past physical revolution (Newton to relativity, classical to quantum) changed our picture of what exists so drastically that confidence extrapolated from old theories has sometimes been badly wrong.

Position two: hypercomputation is physically possible in principle, even if wildly impractical. This position doesn't require believing anyone will build such a device soon, or ever. It only requires believing that nothing in known physics rules it out, and that the Malament-Hogarth spacetime constructions, or some future exploitation of quantum gravity, or some property of continuous fields, could genuinely transcend the Turing barrier. Proponents like Németi and Etesi have done careful general-relativistic analysis showing these spacetimes are legitimate solutions of Einstein's field equations, not merely sloppy thought experiments — the mathematics is real general relativity. Their honest caveat is that general relativity is known to break down at singularities and event horizons, exactly where their constructions need to operate, so the real verdict depends on physics nobody yet possesses. This position's strength is intellectual honesty about the limits of current theory; its weakness is that it currently amounts to "physics we don't yet have might allow this," which, while true, is true of almost anything.

Position three: computability is not really a question about physics at all, but about mathematics, and the physical Church-Turing thesis is a category error. On this view — associated loosely with more mathematically purist traditions in logic — "computable" is best understood as a mathematical idealization, like a perfect circle or a frictionless plane, and asking whether physics can "exceed" it is like asking whether a real wheel can be rounder than the mathematical concept of roundness. What's actually interesting, on this view, is the mathematical structure of the computable/uncomputable boundary itself (which is settled and beautiful), not speculative claims about physical devices. This deflationary position has the virtue of sidestepping unresolvable physics questions, but its critics point out that it dodges the genuinely empirical and interesting question: whatever we call it, is there or is there not a physical process in this universe whose input-output behavior cannot be reproduced by any Turing machine? That's a real question about the actual universe we live in, and calling it a category error doesn't make it disappear.

Position four: the question will dissolve once we have quantum gravity, because spacetime itself may be discrete. Several approaches to quantum gravity — loop quantum gravity, causal set theory, and some readings of the holographic principle and the Bekenstein bound (which limits the amount of information that can be stored in a finite region of space given its energy) — suggest that at the Planck scale, spacetime and information alike come in discrete, finite units rather than continuous infinities. If that is correct, many of the hypercomputation proposals collapse for a clean reason: there is no way to access truly infinite-precision continuous data, because the world simply doesn't contain it at the bottom. This would be a satisfying resolution in one direction — vindicating the classical Church-Turing thesis from deep physical principle rather than mere induction. But it remains a conjecture nested inside another set of open conjectures, since no complete, experimentally confirmed theory of quantum gravity exists yet.

None of these four positions has been refuted. The honest state of the field is a genuine, live disagreement resting on unresolved physics — not a settled consensus with a few holdouts.

Because this is a question straddling mathematics and empirical physics, its resolution — if it ever comes — will look different depending on which way it breaks.

If someone actually built a working hypercomputer, the resolution would be immediate and dramatic, though the engineering bar is almost unimaginably high. It would need to either exploit a genuine Malament-Hogarth-type spacetime region (requiring us to locate or construct an appropriate extreme rotating black hole and survive sending and receiving signals across an event horizon in exactly the right configuration — currently not just impractical but plausibly forbidden by physics we don't yet understand), or demonstrate a physical process that reliably outputs the correct answer to instances of the halting problem, or Hilbert's tenth problem, or another proven-undecidable question, with a track record good enough to rule out coincidence, noise, or hidden approximation. Given the difficulty, most researchers regard this as unlikely within any foreseeable timeframe — plausibly never, if the discrete-spacetime intuitions from quantum gravity are correct.

More realistically, the resolution is likely to come indirectly, through progress in fundamental physics that either closes off or opens up the loopholes. A complete, experimentally validated theory of quantum gravity would be the single most important development here. If such a theory firmly establishes that spacetime, information, and physical quantities are all fundamentally discrete and finite at the smallest scales — as suggested by the Bekenstein bound, by holographic entropy arguments, and by several quantum gravity research programs — that would amount to strong theoretical support (not a strict logical proof, but close to physical proof) for the classical Church-Turing thesis as an inviolable feature of any possible physics in our universe. Conversely, if some future theory turned out to permit genuine continuum-valued, infinite-precision physical quantities that are in principle (if not practically) accessible, or if it validated exotic causal structures resembling Malament-Hogarth spacetimes as physically realizable rather than pathological artifacts of classical general relativity, that would crack the door back open.

There's also a purely theoretical route: someone might find a rigorous argument, grounded in accepted physical principles (say, quantum field theory plus general relativity, or their eventual union), proving that no physically realizable process can exceed Turing computability — a genuine derivation rather than an inductive generalization. This would be an extraordinary achievement, roughly analogous in status to deriving the second law of thermodynamics from statistical mechanics: taking something that looks like an empirical regularity and showing it follows necessarily from deeper theory. A handful of theoretical computer scientists and physicists have sketched partial arguments along these lines using information-theoretic bounds (finite-speed information propagation from relativity, the holographic bound on information density, and the finite-precision limits from quantum mechanics, taken together), but nothing rising to the level of a complete proof exists, and any such proof would be hostage to the completeness of the physical theories it assumes.

Timeline honestly: quantum gravity has been "twenty years away" for the better part of a century, and there's no serious reason to expect the situation to change quickly. This question may remain genuinely open — not dead, not forgotten, but unresolved — for a very long time, possibly permanently, if it turns out that we can never fully verify claims about the ultimate, Planck-scale structure of spacetime through any conceivable experiment. That itself would be a strange and fitting outcome: a question about the limits of computation whose answer might be forever beyond our ability to confirm, in an echo of the very undecidability it's asking about.

It would be easy to file this under "beautiful but useless" — a question for people who enjoy vertigo. That would be a mistake, for at least three reasons.

First, practically: every claim of "quantum supremacy" or "quantum advantage," every debate about whether some future exotic computing substrate — DNA computers, neuromorphic chips, whatever comes after — offers something genuinely new rather than just a speedup, is implicitly a question about where that device sits relative to the Turing boundary. Understanding this frontier sharply is how researchers avoid both undue hype (claiming a device transcends computability when it merely runs fast) and undue dismissal (missing a genuine advance because it doesn't look like a conventional computer). The distinction between what is computable and how efficiently — the line this essay has been careful to draw, and the line connecting to P versus NP and to the power of quantum computation (BQP) — is one of the most consequential organizing ideas in all of computer science, discriminating between problems worth attacking with cleverness and problems that no amount of cleverness, quantum or otherwise, can crack.

Second, foundationally: this question sits at the exact intersection of logic, physics, and the philosophy of mind, and progress in any direction ripples into the others. If the physical Church-Turing thesis turns out to be a genuine law of nature, it says something remarkable about the universe: that the same finite, mechanical notion of "step-by-step procedure" invented by mathematicians thinking about pure logic in the 1930s, with no thought of physics at all, happens to be exactly as powerful as physical reality itself permits. That would be a strange and beautiful coincidence, or perhaps not a coincidence at all, but a deep clue about why mathematics describes the physical world so effectively in the first place — a mystery as old as Eugene Wigner's remark about the "unreasonable effectiveness of mathematics." If instead it turns out that physics can exceed Turing computability, that would be one of the most important discoveries in the history of science, on par with the discovery of any new fundamental force, because it would mean that entire classes of mathematical questions we've long assumed permanently unanswerable — the halting problem, Hilbert's tenth problem's undecidable cousins, potentially deep questions in number theory — could become empirically answerable by building the right machine.

Third, and most unsettlingly: it touches the question of what we are. If Penrose and Lucas are even partly right that human mathematical insight outruns any algorithm, that would mean minds are not Turing machines — a claim with enormous consequences for artificial intelligence, for the philosophy of consciousness, and for how we understand the relationship between brains and computation. If they're wrong, as most experts believe, then minds — including the very act of reasoning about undecidability itself — are, in principle, computational processes bound by exactly the same Turing wall as every laptop and phone. Either answer reframes what it means to think.

history

• 1931 — Gödel proves the incompleteness theorems, introducing the technical machinery of computable arithmetized proof.
• 1936 — Church and Turing independently formalize "effective computability"; Turing proves the halting problem undecidable.
• 1970 — Matiyasevich, completing work of Davis, Putnam, and Robinson, proves Hilbert's tenth problem undecidable.
• 1992 — Hogarth formalizes Malament-Hogarth spacetimes and their implications for computing the halting problem via general relativity.

There is something almost moving about a question this old and this simple still standing open. Turing wrote down his machine before the transistor existed, before anyone had built a working general-purpose computer, and the question he left behind — is this the outer wall, or just the wall of our current imagination? — has survived a hundred years of the very revolution his idea triggered. Every laptop, phone, and data center built since 1936 has, in a sense, been a running experiment testing his thesis, and the thesis has passed every single time. That is either because it's true in the deepest possible sense, or because we simply haven't yet built, or discovered, or stumbled into the physical situation that would break it.

What makes this different from many "open questions" in science is that we may not get the usual kind of resolution. Most open scientific questions get settled by an experiment, a telescope, a collider, a proof. This one might get settled that way — a completed theory of quantum gravity could, in principle, close the case definitively. But it's equally possible that this question is one of those rare scientific mysteries that resists resolution not because we lack ingenuity, but because verifying the answer would require knowledge of physics at scales and precisions we may never be able to probe, leaving us to reason, forever, from theory and inductive confidence rather than direct confirmation — a strange, self-referential echo of the very undecidability the question is about.

• Does the completed theory of quantum gravity establish that spacetime, energy, and information are all fundamentally discrete — closing off the continuum-based hypercomputation proposals for good?
• Are Malament-Hogarth spacetimes genuine physical possibilities, or artifacts of applying general relativity beyond where it remains valid?
• Is there a rigorous derivation of the physical Church-Turing thesis from first principles, rather than mere accumulated inductive confidence?
• Is the human mind — the very thing doing this reasoning — a Turing machine, something strictly weaker, or something that transcends the whole framework?
• If a genuine hypercomputer were ever built, which of today's "impossible" mathematical questions would fall first?

Ask the tutor: If a Malament-Hogarth spacetime really could answer the halting problem for a program dropped into it, what would that mean for a program designed to compute its own answer and then act on it before the outside universe receives the result?