Think outside the box

Earlier this year, some curious commentary appeared in my LinkedIn feed. Amid all the discussion about AI, generative AI and whether we might ever achieve artificial general intelligence (AGI), some analysts started invoking the 20th century Austrian mathematician Kurt Gödel. They referred to his famous Incompleteness Theorems as part of their argument that generative AI, specifically, will never lead us to AGI. Now, I believe that Gödel’s theorems are among the most important works of modern mathematics and should not be taken lightly. So, when they are cited during social media debates about AI, I think it’s worthwhile to take a closer look at what Gödel really said (and didn’t say) and then determine how or whether his work is applicable to AI.

Gödel’s theorems are not for the faint of heart—they shook the very foundation of mathematics itself. But before diving into those mathematics and their implications for AI, let’s approach Gödel by way of an analogy: the familiar game of chess.

Chess is like mathematics
Game theorists would call chess a game of perfect information. This means that there is no element of chance, and nothing is hidden from either player—each move and countermove is played openly. But this doesn’t mean that chess isn’t extremely complicated. White has 20 legal opening moves available, to which Black can counter with 20 moves of their own. So, there are already 400 possible opening positions and, after only 10 moves by each player, this number goes up to over 69 trillion. Wikipedia suggests that there are at least 10^120 possible complete chess games—a rather large sum, considering that the number of atoms in the known universe is estimated to be only 10^80.

The same board positions, especially in the beginning and at the end of a game, are very likely to be repeated over multiple different games. So then I wondered, how many legal board positions could there be? Ignoring the question of which positions or moves make sense strategically, the same Wikipedia article told me that there are very likely at least 10^44 possible chess positions. This number was calculated by extrapolating how many legal moves and countermoves can be made over an estimation of an average game length of 60 moves—effectively, constructing all possible positions from the initial state of the chessboard.

My next question was, what would happen if you just randomly scattered pieces on the chessboard? Obviously, the vast majority of random configurations would be illegal—pawns lined up improperly, or all bishops on the same colour, for example. But if you repeated the scattering often enough, some random configurations would be legal positions, and most of those would correspond to the roughly 10^44 constructed positions. But, I asked myself, would it be possible, by random scattering, to come up with a correct chess position that could not be constructed from the initial position and the rules of the game? What would that mean, and how could you prove or disprove it?

He came in like a wrecking ball
These are exactly the questions that Kurt Gödel sought to answer in 1930—not about chess, but about mathematics itself.

Gödel’s contemporaries—the German David Hilbert, the Dutchman L. E. J. Brouwer, and the famous English duo of Bertrand Russell and Alfred North Whitehead—had all busied themselves for years with a constructivist approach to mathematics. They, along with pretty much all mathematicians up to then, believed that in principle, given a particular set of axioms and operations (just like the initial position and rules of chess), one could then construct all the truths of mathematics. Russell and Whitehead’s Principia Mathematica, first published in 1910, was the most ambitious attempt at codifying mathematics—and the authors eventually gave up, admitting to “intellectual exhaustion” at the magnitude of the task.

The argument really centred on two terms: completeness and consistency. A mathematical system is said to be complete if all true statements can be proven within the system, and consistent if it avoids contradictions, i.e., if it is impossible to prove both a statement and its opposite. Consistency, and especially completeness, as Russell and Whitehead discovered, are extremely difficult to prove—how do you know when you’re finished? Despite the lack of a solid proof, but at least based on a very plausible intuition, these were the orthodox view of mathematics at the time.

Enter Gödel, with an intriguing thought. If completeness and consistency were so difficult to prove, maybe there was a way to disprove them? And in 1930, he did exactly that—his first and second incompleteness theorems demonstrated that mathematics was not complete and could not prove its own consistency. In doing so, he aimed a wrecking ball squarely at the foundation of mathematical orthodoxy and knocked down the constructivist view forever.

How Gödel did it required, literally, out-of-the-box thinking combined with some clever mathematical legerdemain. Not only did he prove that unprovable statements exist; in doing so, he showed how to create them. Instead of thinking inside the rules of mathematics, he took a holistic approach to look at the structure of mathematical operations—addition, subtraction etc.—and manipulate them mathematically. The details of his work are as brilliant as they are complicated, and Wikipedia is as good a place as any to study them further if you’re interested. Suffice to say, he blurred the distinction between operators and operands. He assigned numeric values to each mathematical axiom and operator, then combined those “Gödel numbers” in such a way that he could create a statement that asserts its own unprovability.

“Aha!” say his critics, what if we just take that new statement and add it to the existing set of axioms about mathematics? “No problem,” replies Gödel. He would just create an additional Gödel number for the new axiom, and then create a new unprovable statement—ad infinitum. Next, Gödel’s second theorem built upon the first. Simply put, he created a formal statement that would assert the consistency of mathematics, but then used his numbering technique to demonstrate that such a statement would be unprovable.

The upshot of Gödel’s work is that there are forever going to be true statements that we cannot prove, and not only that, we can’t even be certain that any specific line of mathematical reasoning won’t lead to a contradiction. But in order to know these things, we have to be able to step outside the box of mathematical reasoning, and work in the realm of metamathematics—which Wikipedia succinctly defines as “the study of mathematics itself using mathematical methods.”

AI in the box
I used chess as an analogy to introduce Gödel’s theorems but I’m not certain that Gödel’s proofs apply to chess because the game, despite having a large number of permutations, is still finite and bound by a simple initial position and fixed set of rules—and therefore too simple. One of the most important conditions about Gödel’s theorems is that they only apply to logical systems of sufficient complexity, and it turns out that arithmetic[1] fits this condition. Second, and perhaps more importantly, Gödel requires an external actor who can think outside the box—a metamathematician, so to speak.

So what does this mean when we think about AI? First of all, Gödel never said anything about AI or consciousness, and he worked with a purely theoretical notion of computers. He was simply asserting, and proving, certain limitations on mathematical reasoning—and mathematics is no less a vibrant and useful discipline without constructivism or formalism.

Therefore, secondly, critics of generative AI who casually invoke Gödel would need to demonstrate exactly how his theorems apply to systems such as ChatGPT or Gemini. If the claim is that either incompleteness (by way of Gödel’s first theorem) or an inability to prove internal consistency (Gödel’s second theorem) are natural barriers to intelligence, then they must also show that LLMs are at least as complex as arithmetic and also show that some form of “Gödel-numbering” can be done with an LLM. Personally, I’m not convinced that LLMs exhibit the necessary complexity—but either way, I think this argument misses the point. It’s like saying that Gödel proved that mathematics itself is not intelligent. It makes no sense to even speak of intelligence as an attribute of the discipline of mathematics.

Now, let’s dive a little deeper into the specifics of computer systems and the relevance of Gödel’s theorems.

Computational limits
Interestingly, five years after the publication of Gödel’s theorems, Alan Turing picked up that work in the context of computer science. He described a universal mathematical model of computation now known as the Turing Machine. Turing and his doctoral advisor Alonzo Church had a lengthy correspondence and collaboration with Gödel through the 1930s and beyond. Their work centred on the problem of computability—determining what kinds of problems could be proven to have a solution using a Turing Machine. Most of their effort was spent trying to prove a proposition, now known as the Church-Turing Thesis, that any function on the set of Natural numbers is effectively calculable if and only if it can be computed on a Turing Machine.

Unfortunately, there is no precise definition of effectively calculable—just an intuitive notion that the concept covers problems that can be solved by a competent mathematician using pencil and paper[2] in a reasonable amount of time. Therefore, there is no formal proof of the Church-Turing Thesis, although it has been generally accepted as probably correct. But the thesis did get people also thinking about whether there might be problems that are not computable on a Turing Machine, and what would such non-computability mean? The most commonly known such problem is the Halting Problem, which seeks to determine whether a Turing Machine, given any particular algorithm, will be guaranteed to stop in a finite number of steps or whether it might spin off into an infinite loop.

I want to highlight two key points here. First, it appears that Church and Turing extended Gödel’s theorems, or at least the First Incompleteness Theorem, from mathematics to computer science. By coming up with a counterexample in the form of the Halting Problem, they proved that at least some problems are not computable. Second, and maybe more importantly, they followed Gödel in thinking outside the box. To even conceive of the Halting Problem, you have to think not just within the rules of the Turing Machine, but think about the machine itself.

Gödel’s Second Theorem is a bit more problematic. With most current programming languages, you can avoid contradictions, so, with enough limitations, computer systems can be considered consistent. There doesn’t seem to be a clear definition of where consistency might apply or be provable (or unprovable) but, as we’ll see, I’m not sure it matters.

Is it or isn’t it?
Does the fact that some problems are not computable shed any light on AI? Does the fact that generative AI systems occasionally hallucinate incorrect answers have anything to do with Gödel’s Second Theorem? I think the answer to both questions is no. As I’ve said, mathematics is perfectly fine after Gödel, and in a similar way, I don’t think it’s meaningful to apply his theorems directly to AI systems.

What’s important isn’t so much Gödel’s results as his methods—in other words, the metamathematics. The British mathematician Sir Roger Penrose has been considering AI and consciousness for decades, at least since the 1989 publication of The Emperor’s New Mind. Penrose is extremely skeptical about what we would now call AGI, and in a recent interview summed up his argument, referencing Gödel, very simply: “understanding transcends the use.” He further suggests that “people have lost the plot” when it comes to AI. I interpret Penrose as saying that truly understanding any system is exactly the out-of-the-box thinking that pertains to human consciousness, and AI systems are not self-reflective or self-conscious in the way that humans are—they only operate within their rules to produce answers to our questions, nothing more.

Having said that, I hasten to emphasize again that this in no way diminishes AI’s usefulness—as long as we understand its limitations. Penrose’s fellow mathematical genius, Fields Medalist Terence Tao, puts it this way in an online forum: AI is a “combination of a technology that can be very useful and impressive, while simultaneously being fundamentally unsatisfying and disappointing—somewhat akin to how one’s awe at an amazingly clever magic trick can dissipate (or transform to technical respect) once one learns how the trick was performed.”

And that’s the whole thing with AI—because we are human, we know how it works. And when we know how it works, we know its limitations. We stand outside the box that AI doesn’t even know it’s in.

[1] Actually, a simplified version called Peano Arithmetic, which works only on Natural numbers (0, 1, 2, 3, …) will suffice.

[2] Remember, computers themselves were still mostly theoretical in those days.