Godel's shadow: what mathematics says computation can never do

The Short Version

Three different limits on calculation come out of these conversations, and they are not the same limit. Gödel's theorem, as Roger Penrose and Edward Frenkel both explain it, says that any consistent set of rules rich enough for arithmetic leaves some true statements unprovable, and Turing's halting problem sets a similar limit on what a machine can decide [1][2]. Stephen Wolfram's computational irreducibility is a limit on prediction: even when you know the rules exactly, often the only way to learn what happens is to run every step [3]. Penrose draws the boldest conclusion, that human understanding is "not a computational procedure," while Wolfram thinks minds are computation and that the limits apply to us as well [1][3]. What the three share is that none of them treats the limit as bad news: each says it leaves room for something, whether understanding, discovery or surprise [1][2][3].

Table of contents

What They Said

Roger Penrose: understanding the rules lets you step past them

Penrose met the idea as a first-year graduate student in Cambridge [1]. He was meant to be doing algebraic geometry, but he sat in on three courses that had nothing to do with it: Hermann Bondi on general relativity, Paul Dirac on quantum mechanics, and a course on mathematical logic [1]. The logic course introduced him properly to two things he calls fundamental to his thinking, Turing machines with the whole idea of computability, and Gödel's theorem [1].

He arrived with a worry. He had heard of the theorem and, in his words, "I was a bit worried by the idea that it seemed to say there were things in mathematics that you could never prove" [1]. The course showed him it meant something else [1].

The argument, as he tells it, starts by pinning down what a proof is: "suppose what you mean by proof is something which you could check with a computer" [1]. Whether the steps have been followed correctly "can be checked by an algorithm, by a computer" [1]. The next question is why anyone would trust such a system. Penrose's answer is that you use those rules only "Because you have understood them to be rules which only give you truths" [1]. People sometimes say one set of rules is as good as any other, and he says that is not true: "So you have to understand what the rules mean" [1].

Gödel then shows how to build a statement that, given that trust, you can see is true, yet that the rules themselves cannot prove [1]. So the understanding of why the rules work reaches further than the rules do. Penrose says understanding why the rules give you truths "enables you to transcend the rules," and adds, "That's what blew my mind" [1].

His conclusion is that the quality of understanding, whatever it is, is not governed by rules: "It's not a computational procedure" [1]. He is deliberate about the word. He says "I've always concentrated on understanding" and avoids resting the argument on creativity, which is too slippery to argue about, whereas Gödel's theorem gives him something precise to say [1]. Asked what understanding is, he describes a kind of standing back, stepping outside the game you are playing and asking what you are doing, and he agrees when Lex Fridman calls it reflection [1].

Penrose supports the claim with an observation about the brain. The cerebellum, he is told, has far more neurons and more connections than the cerebrum, and "an incredible amount of computation going on," yet as far as we know "it's completely unconscious" [1]. If consciousness came from computation, he asks, why is the most computational part of the brain the unconscious part [1]? The idea that the brain is like a complicated computer "just seems to me to be completely missing the point" [1].

He does not belittle computation. He considered whether the difference between discrete computers and continuous physical laws mattered and concluded that computers can get close enough, pointing to the black-hole merger calculations confirmed by LIGO: "You can get very close" [1]. That is why he looks for the non-computational ingredient somewhere specific. Following the Schrödinger equation, he says, "that's still computable," so "you've got to go beyond that," to the place where quantum mechanics is incomplete [1]. His proposal with Stuart Hameroff is that the quantum state reduces in a non-computational way we do not yet understand [1].

He is candid about the status of all this. There is no theory yet, only experiments in development, and by his own grading of theories as superb, useful or tentative, a theory of consciousness probably has not reached "tentative" [1]. The Gödel argument is also disputed. Penrose reports that Douglas Hofstadter, whose book he calls fantastic, reaches the opposite conclusion, and that when Penrose tried to corner him with the absurd consequence that certain large integers must be conscious, "He took the view that certain numbers were conscious" [1]. Penrose's view of why many AI researchers assume consciousness will emerge from enough computation is that they cannot think of anything else [1].

Edward Frenkel: incompleteness is where the observer comes in

Frenkel tells the story as history. Every field of mathematics rests on axioms, statements taken without proof, and someone has to choose them, which is where he says the observer enters [2]. His example is Euclid's fifth postulate about parallel lines, which resisted proof for 2,000 years until mathematicians realized it could be replaced, giving consistent non-Euclidean geometries on spheres and hyperbolic planes [2].

By 1900, he says, many believed all of mathematics could be derived mechanically from the right axioms, a purely symbolic process a computer could run [2]. Gödel proved in 1931 that any consistent system rich enough to include arithmetic contains true statements it cannot prove [2]. Alan Turing proved a similar limit with the halting problem [2].

Frenkel's reaction is the opposite of dread. He finds the result life-affirming, since it leaves room for new discovery [2]. He attaches a caveat that Penrose does not: future notions of computation may change the picture [2].

The theorem fits a larger pattern in how Frenkel now thinks. He embraces paradox, quoting Niels Bohr's idea that "the opposite of a great truth is another great truth" [2]. He places Gödel beside quantum mechanics and relativity as 20th-century results that put the observer back into science, quoting Heisenberg that "what we observe is not reality itself but reality subjected to our method of questioning" [2]. He points to images such as the dress that some saw as blue and black and others as white and gold, the Rubin vase and Wittgenstein's duck-rabbit, which have no single correct answer, and wonders how neural networks should handle inputs that are truly ambiguous [2].

He is wary of the claim that everything is computation. Computer scientists, he says, may be tempted to see the world that way because it flatters their expertise, much as priests once explained everything theologically [2]. His comparison is the writer Georges Perec, who wrote a whole novel without the letter E; it would be absurd for Perec to then declare that E does not exist [2]. Against the idea that discovery is accumulation, he sets the story of complex numbers, where all prior knowledge said a negative number has no square root, and he wonders whether a large language model trained on everything known could have made that leap [2]. Insight, in his experience, does not arrive in a straight line: "the moment of discovery is the moment when thinking stops" [2].

Stephen Wolfram: knowing the rules is not knowing the outcome

Wolfram's limit starts from a discovery he dates to the early 1980s: extremely simple programs can produce enormously complicated behavior, and he believes that is how nature works [3]. Rule 30, a simple cellular automaton he printed in high resolution in 1984, is his standard example of simple rules that "produce apparently random behavior" [3].

From that comes computational irreducibility. Even if you know the rules, often the only way to find out what happens is to run every step [3]. Of rule 30 he says, "even though the rules are simple, you can't tell what's going to happen and you can't prove things about it" [3]. He has offered prizes for proofs about it [3]. The universe performs its own computation as fast as it can, so there is no shortcut from inside it [3]. A complete model of the universe would be impossible to run for the same reason: "The only thing that successfully runs that model is the actual running of the universe" [3].

The limit is not total. Science and invention, in his account, are the story of finding "pockets of reducibility" where we can jump ahead, and he says there are always infinitely many of them [3]. Ordinary life depends on such pockets, like the reliable fact that the air in a room will still be air in a few seconds [3].

He applies the idea widely. His version of the second law of thermodynamics is that things tend to get more random over time, and his explanation is that it is "a story of a computationally bounded observer trying to observe a computationally irreducible system" [3]. Molecules follow simple deterministic rules, but we cannot do enough computation to see that, so their behavior looks random [3]. He says no sandbox for software is ever perfect, because the fundamental problem of computer security is computational irreducibility [3]. And he applies it to AI. People assume that "we built the machines so we can understand what they do and we're going to be able to control what happens," and his reply is, "Well, that's not really right" [3].

Wolfram also touches the Gödel side of the picture, though in the passages available he does not name Gödel. Human mathematicians have published "about three or four million" theorems, he says, but "there are an infinite number of possible mathematical theorems," and a theorem picked at random from that space would leave people saying, "I don't know what this theorem means" [3]. He doubts there is an apex intelligence, much as there is always a longer-running Turing machine or another invention to make [3].

Where They Agree, and Where They Don't

All three agree that the limits are real and proven, not a matter of taste or of slow hardware. Penrose and Frenkel give matching accounts of Gödel's result, and both pair it with Turing [1][2]. Wolfram's irreducibility does not depend on the speed of the computer, since the system itself is already computing as fast as anything can [3].

All three also agree that the limits are liberating. Penrose's fear of unprovable truths turned into amazement at what understanding can do [1]. Frenkel calls incompleteness life-affirming [2]. Wolfram calls himself "intrinsically an optimist" and says, "I have faith in computational irreducibility," because it means "there's always unintended corners" and a single catastrophe rarely wipes out everything [3].

They are describing different limits, and it helps to keep them apart. Gödel's is about proof: what a fixed set of rules can establish [1][2]. Turing's, in Frenkel's telling, is about what a machine can decide [2]. Wolfram's is about prediction: how much work it takes to know what a rule will do [3].

The sharp disagreement is about minds. Penrose argues that understanding goes beyond any computation and that explaining it requires new physics beyond conventional quantum mechanics [1]. Wolfram holds close to the reverse. He argues that neural nets show the missing intermediate language of neuroscience does not require exotic quantum effects, he believes even an ordinary computer has some version of inner experience, and he describes consciousness as a particular, limited kind of computation, not the pinnacle of what can happen in the universe [3]. Each view follows from its starting point. Penrose starts from the mathematician's experience of seeing that a Gödel statement is true, which no rule system he trusts can deliver [1]. Wolfram starts from the finding that very simple rules already produce behavior as complicated as anything, so he sees no need for an extra ingredient [3].

They also differ on neural networks. Penrose says modern networks trained on huge numbers of examples show no understanding at all [1]. Wolfram says the discovery is that neural nets generalize the way humans do, and he expects the regularities of meaning that ChatGPT has picked up to be finite and eventually written out explicitly, like Newton's laws [3]. Wolfram still calls ChatGPT "wide and shallow" compared with deep computation, so he is not claiming it reasons as a mathematician does [3].

Frenkel stands between them. He shares Penrose's suspicion of the claim that everything is computation and appeals to a subjective certainty he cannot prove, quoting Pascal that "the heart has its reasons of which the reason knows nothing" [2]. But he does not claim Gödel proves the mind is non-computational, and he allows that future notions of computation may change the picture [2].

One more difference concerns who is bound by the limit. In Penrose's argument the human steps outside the rules [1]. In Wolfram's, humans are computationally bounded observers, and that boundedness is why the world looks the way it does to us [3].

Why It Works

The Gödel mechanism

Penrose's version has three moves. A proof system is something whose steps a computer can check [1]. You trust it only because you understand that its rules give nothing but truths [1]. Gödel constructs a statement that this very trust lets you see is true, while the rules cannot prove it [1]. Frenkel adds the conditions: the system must be consistent and rich enough to include arithmetic [2]. The sources give the outline of the argument and not the construction itself, so this article cannot take the reader through how the statement is built.

Why axioms cannot settle everything in advance

Frenkel's history of the fifth postulate shows the same thing from another side. An axiom that seemed forced turned out to be a choice, and different choices gave different consistent geometries [2]. The dream of 1900 was to make all such choices once and then let a mechanical process do the rest, and Gödel showed that this cannot be completed [2].

The irreducibility mechanism

Wolfram's argument rests on a comparison of computing power. To predict a system you must out-compute it, and a system that is already computing as fast as possible cannot be out-computed from inside the same universe [3]. Rule 30 is the evidence he offers that this happens even with the simplest rules [3]. He also put up a prize in 2007 for a small universal Turing machine, which Alex Smith won within about six months [3].

Why models always leave something out

Wolfram uses snowflakes. An older literature modeled snowflake growth rates well, but by those models snowflakes would be spherical [3]. Real ones grow from hexagons into arms because each bit of freezing ice warms its surroundings and inhibits growth nearby [3]. His general point is that a model reduces the world to what you care about, and no model except the system itself captures everything [3].

Why bounded observers see the laws they see

Wolfram's favorite recent result is that general relativity, quantum mechanics and statistical mechanics all emerge from the interplay between computational irreducibility and observers like us, who are computationally bounded and believe they persist through time [3]. This is his own research program, and the other two sources neither discuss nor confirm it [1][2][3].

Where It Applies, and Where It Doesn't

The limits do not make computation weak. Penrose says computers get very close to the physics of general relativity, as the black-hole calculations show [1]. Wolfram's working life is built on deep computation that produces things never computed before [3].

Incompleteness does not stop mathematics. Frenkel describes Fermat's Last Theorem, which resisted proof for about 350 years and was then proved by Andrew Wiles, with a gap closed with Richard Taylor and the result published in 1995 [2]. A statement can be hard for centuries and still be provable [2].

Irreducibility does not make everything unpredictable. There are always pockets of reducibility, and new tools open new ones; Wolfram's example is electronic amplifiers, which helped reveal quantum mechanics [3].

Gödel's theorem does not, on the evidence here, settle whether machines can think. That step is Penrose's argument, which he admits is tied to a physical theory that does not yet exist, and which Wolfram's account of minds contradicts [1][3]. Readers should treat it as one contested position.

Nor do the limits tell us how AI will turn out. Wolfram says of the future that "it's hard to be clear about what will happen," and he admits that giving ChatGPT the ability to run code on his own computer felt a little bit scary [3]. These conversations are also dated: Penrose's was recorded before the pandemic, and what neural networks can and cannot do has moved since, so check current work before leaning on any claim here about AI systems [1].

What To Do With It

1. Separate the three limits when you hear them invoked: unprovable truths (Gödel), undecidable questions (Turing) and unpredictable outcomes of known rules (Wolfram) are different claims [2][3].
2. Before trusting a rule system, ask Penrose's question: why do you believe its rules give only truths? The trust comes from understanding, not from the rules [1].
3. Treat axioms and starting assumptions as choices. Frenkel's example is a postulate that looked necessary for 2,000 years and turned out to be replaceable [2].
4. When a system is irreducible, stop looking for a formula and run it, since running every step may be the only way to find out what it does [3].
5. Look for pockets of reducibility. Wolfram's comparison is riding a horse: "We don't really understand how the horse works inside," but we can learn rules that get us from here to there [3].
6. Ask what a model was built to care about before arguing over whether it is correct, as the spherical-snowflake models show [3].
7. Do not assume that building a machine means understanding or controlling it, and do not assume any sandbox is perfect [3].
8. Practice standing back. Penrose's description of understanding is stepping outside the game and asking what you are doing in playing it [1].
9. Leave room for the leap. Frenkel's model of discovery is intense preparation followed by a moment that cannot be forced [2].
10. Hold open questions without panic. Frenkel says allowing mystery has been liberating after years of being unable to tolerate an unanswered question [2].

Sources

1. Roger Penrose on Why Consciousness Isn't Computation and the Infinite Cycles of the Universe · Lex Fridman Podcast
2. Edward Frenkel on Mathematics, Paradox, Imagination, Trauma and Love · Lex Fridman Podcast
3. Stephen Wolfram on ChatGPT, Computational Irreducibility, Truth and the Second Law · Lex Fridman Podcast