How Gödel and Turing outlined the limits of AI | heise online
heise+ entdecken
SuchenAbo
Suchen
Alle Magazine im Browser lesen<br>Newsletter<br>heise-Bot<br>Push-Nachrichten
${lead}
${lead}
${content}
${content}
${content}
${content}
Advertisement
Advertisement
During their studies, students encounter names like Kurt Gödel and Alan Turing, usually with the same mix of respect and mild resignation. One reads what they have proven, accepts it as impressive, and then files the knowledge away in that mental archive located somewhere between “interesting” and “I'll never need this again.” A few years ago, I wouldn't have believed anyone who said that the incompleteness of arithmetic or the undecidability of the halting problem could one day coincide with the question of why a chatbot is currently hallucinating a book title at me.
Continue after ad
Yet, that is precisely what has happened. Several scientific papers from the last three years show that the hallucinations of language models are not an implementation error that could be trained out with more data or a better architecture. They stem from the same theoretical limits that once shattered the most ambitious project of modern mathematics. Once you see this connection, you read the current debate about the future of AI with a much more sober perspective.
Golo Roden is the founder and CTO of the native web GmbH. He works on the design and development of web and cloud applications and APIs, with a focus on event-driven and service-based distributed architectures. His guiding principle is that software development is not an end in itself, but must always follow an underlying technical expertise.
The Promise of 1928
To understand why the research landscape of AI is the way it is today, it's worth taking a detour through the International Congress of Mathematicians in Bologna in 1928. There, David Hilbert, one of the most influential mathematicians of his time, together with Wilhelm Ackermann, formulated a research program that was intended to place all of mathematics on a completely new foundation. Three properties were to underpin this foundation:
Consistency, i.e., the certainty that no contradictory statements can be derived from the axioms.<br>Completeness, i.e., the guarantee that every true statement within the system can also be proven.<br>And decidability, i.e., the existence of a procedure by which it can be decided in a finite number of steps whether any given statement follows from the axioms.
The third requirement has gone down in history as the Entscheidungsproblem (decision problem). Behind it lay a concrete vision. Mathematics was to become mechanisable. A machine that applies a finite number of rules to a finite number of symbols should, in principle, be able to answer any mathematical question. Those who recognize the shadow of what we now call computers in this vision are not mistaken. Hilbert conceived of the computer long before it existed.
His optimism remained unbroken. In September 1930, he gave a famous radio address in Königsberg, which he concluded with the sentence, “We must know, we will know.” It was the last great proclamation of a mathematics that still felt capable of anything. A few days earlier, at the same location, during a parallel epistemology conference, a young man named Kurt Gödel, in a casual remark, first sketched out the results that were to shake Hilbert's program to its foundations. The fact that the two events occurred so close together is a historical coincidence that one should not overemphasize symbolically. But it is certainly interesting.
Continue after ad
Gödel Without Formulas
What Gödel presented in 1930 and published in detail in 1931 can be explained surprisingly well without mathematical notation. His trick relies on a procedure that anyone who has seen a self-calling function will understand: self-reference. Imagine a sufficiently powerful formal system in which arithmetic statements can be formulated. Gödel showed how, within such a system, a statement can be constructed that essentially says, “This statement is not provable within the present system.”
At this point, one should pause briefly because the consequence is unavoidable. If the statement is true, then there exists a true arithmetic statement that the system cannot prove. Thus, the system is incomplete. If the statement is false, then the system proves a statement that claims to be unprovable, even though it apparently is. Thus, the system is inconsistent. There is no third way.
Anyone familiar with the liar paradox from ancient philosophy who accuses himself of lying will recognize the pattern. However, what Gödel achieved was not a philosophical game but a strictly formal proof within arithmetic itself. He showed that self-reference is not limited to common-language statements but appears in any sufficiently expressive formal system.
Gödel did not show that mathematics is broken. He showed that there are fundamental limits at...