Gödel and Artificial Intelligence

Author: Chen Long
Abstract: Gödel’s Incompleteness Theorem states that no mechanical system can prove all true mathematical propositions. This theorem not only serves as a definitive logical result but also has profound implications for the nature of mathematical truth and the relationship between human minds and machines. This article discusses the relationship between Gödel and artificial intelligence from two perspectives: the first part examines the famous Lucas-Penrose argument and Gödel’s disjunctive argument from the anti-mechanism perspective; the second part focuses on Gödel’s seemingly contradictory comments on Turing’s analysis of mechanical programs. Ultimately, we will comment on the latest research by Koellner on Gödelian anti-mechanism and contemporary advancements in AI regarding mathematical theorem discovery and proof.

Keywords: Gödel; Artificial Intelligence; Anti-mechanism; Artificial Intuition

Introduction

When discussing artificial intelligence, one might first think of the famous Dartmouth Conference of 1956 and the remarkable achievements in theorem proving, chess, and language processing in recent years. Beyond its close ties to traditional mind-body philosophical issues, another major reason for the interest in AI is the opportunity for reflection it provides on the nature of human intelligence: What is it, and does it necessarily surpass artificial intelligence?

In fact, as early as 1950, Alan Turing, known as the father of computer science and artificial intelligence, proposed the idea of using machines to achieve intelligence in his paper “Computing Machinery and Intelligence”. He designed what later became known as the “Turing Test” to verify whether a machine possesses intelligence. Although there has been much debate over whether this behaviorist standard accurately characterizes human intelligence, Turing’s work laid the foundation for machine intelligence by providing a precise model in the form of the Turing machine. This model allowed discussions about the scope and limits of artificial intelligence to be grounded in a stable and solid foundation.

However, our understanding of the essence of human intelligence remains unclear. Traditional models centered on problem-solving have not adequately considered factors such as environmental interaction and learning through trial and error. We also face challenges regarding the existing models’ considerations of randomness and complexity, as well as the diversity of potential future models. From a more abstract, logical, and mathematical perspective, we can reduce the somewhat vague question of whether machines can possess intelligence to a clearer question: Do machines have the same mathematical proof capabilities as humans? This focus highlights the important role of Gödel’s Incompleteness Theorem (GT), which permanently delineates the limits of proof capabilities within formal systems in mathematics.

Gödel’s Incompleteness Theorem was a groundbreaking mathematical result aimed at addressing one of the 23 mathematical problems proposed by Hilbert in 1900. A century later, American mathematician Steve Smale also envisioned 18 mathematical problems for the 21st century, with the 18th problem being: “What are the limits of human intelligence and artificial intelligence?” He pointed out that this question is closely related to Gödel’s Incompleteness Theorem. The theorem can be stated as follows:

1. Mathematics is inexhaustible.
2. Every consistent formal mathematical theory must contain undecidable propositions.
3. No theorem proves that machines (or programs) can only prove all true mathematical propositions.
4. No consistent and complete formal mathematical theory exists.
5. Mathematics is mechanically (or algorithmically) inexhaustible (or incomplete).

In simple terms, Gödel’s theorem reveals the algorithmic inexhaustibility (or incompleteness) of mathematics (even arithmetic). According to Gödel, this fact of algorithmic inexhaustibility indicates that either the human mind surpasses computers, or mathematics is not created by the human mind, or both are true. Thus, this theorem has a clear relationship with the mathematical proof capabilities of the mind and machines.

Lucas-Penrose Argument and Gödel’s Disjunctive Argument

The debate regarding the relationship between mind and machine may have its earliest roots in Emil Post’s conjecture that the human mind is superior to machines. In 1921, Post suggested a theory of incompleteness and inferred that mathematicians are far more adept than machines, capable of achieving things that machines will eventually be able to do.

However, after careful consideration, Post soon revised this seemingly hasty conclusion, stating that the conclusion “humans are not machines” cannot hold. What we can say is that humans cannot create a machine that can perform all human thoughts. To illustrate this, we can imagine creating a “human-machine” composite capable of proving laws similar to its own mental operations.

In 1961, Oxford philosopher John Lucas proposed an argument similar to Post’s first idea, using GT as a basis to argue for the anti-mechanism claim that the human mind surpasses machines. Lucas’s argument is highly controversial, provoking various debates and objections, yet it has also garnered supporters, the most notable being British mathematician and physicist Roger Penrose. In his 1989 book “The Emperor’s New Mind”, Penrose not only expanded on Lucas’s argument but also attempted to directly argue from GT for the conclusion that “the human mind exceeds computers” from new perspectives such as consciousness and quantum mechanics. Given the similarities in their arguments, we will refer to the similar defense of the human mind over machines based on GT as the “Lucas-Penrose Argument”.

The core of the Lucas-Penrose anti-mechanism argument can be expressed as follows: No matter how complex a machine we create, as long as it is a machine, it corresponds to a formal system. Thus, following Gödel’s method of constructing undecidable propositions, we can find a formula within that system that cannot be proven. The machine cannot derive this formula as a theorem, but the human mind can see that it is true. Therefore, this machine is not a sufficient model of the mind. People always seek to create a mechanical model of the mind, which is essentially a “dead” model, whereas the mind is “alive” and can always perform better than any formal, rigid system. Thanks to Gödel’s theorem, the mind always has the final say.

If we understand “machines” as Turing machines that generate theorems, then due to the precision of the formal system’s definition and the constructiveness of undecidable propositions, Lucas’s argument seems technically irrefutable. However, the main objection from critics is regarding his application of GT: whether it is the case that “the human mind can see that the ‘undecidable statement’ is true” or that “if the human mind is consistent, then it can see that it is true”. For Lucas’s argument to succeed, it requires additional idealized assumptions, namely that the “ideal” human mind is indeed consistent and that we can recognize (or prove) this, which requires philosophical defense.

A typical objection from this perspective is that according to David Lewis, Lucas’s argument can be seen as defending the following ultra-weak reasoning rule:

R: If S is a set of statements and C is the consistency statement corresponding to this set, then C can be derived from S.

Compared to any formal system F that serves as a theorem-proving machine, if the human mind were a machine, it would be more powerful in terms of proof capabilities because it could also utilize rule R. R is evidently a reliable rule: if all statements in the premise S are true, then S must also be consistent, and thus C must also be true; hence R is a sound reasoning rule. Since no formal system or machine can derive its own consistency statement (otherwise it would contradict GT), but a human mind capable of using rule R can, it follows that the mind surpasses any machine. However, Lewis argues that Lucas’s argument is not decisive because to achieve his goal, he needs to further argue that we have sufficient ability to verify all theorems that the human mind can output. Unlike general formal systems, due to the use of rule R, we may face proofs with infinitely many premises, making it impossible to guarantee that this verification will succeed.

In fact, Gödel himself has carefully considered and reflected on what philosophical conclusions can be drawn from his Incompleteness Theorem, and his conclusions appear more cautious. From the earliest published texts, Gödel believed that his theorem does not directly lead to the desired conclusion:

On the other hand, based on existing proofs, there may still be (or even can be discovered) machines that are equivalent to mathematical intuition (i.e., the mathematical capabilities of the mind) that cannot be proven; we cannot even prove that such a machine will necessarily produce correct results when proving a finite number of arithmetic theorems.

In other words, Gödel’s theorem does not rule out the possibility of creating a machine M that is equivalent to mathematical minds. However, if such a machine exists, Gödel infers two results:

A. It is impossible to prove that M truly has this ability; B. It is also impossible to prove that it only produces correct theorems.

Assuming we can prove that M only produces correct theorems, then we would have proven the consistency of M. According to the assumption about M (that its capabilities are equivalent to mathematical minds), M should be able to prove its own consistency, which directly contradicts Gödel’s theorem; thus, B must hold. Similarly, if we assume that the “mind’s abilities” are correct and infallible, and “proof” refers to a stronger mathematical proof rather than a high probability empirical induction, we can also prove that A holds.

In Gödel’s own words, this result indicates a more general phenomenon:

Human minds cannot formalize or mechanize all their mathematical intuitions; that is, if they can formalize certain intuitions, this fact itself will generate new intuitive knowledge, such as the consistency of this formalization process. This can be referred to as the “incompleteness of mathematics”.

The indispensability of mathematical intuition and the incompleteness of mathematical truth are two core points in Gödel’s philosophy of mathematics, and they are also the most certain and reliable philosophical conclusions that can be directly derived from GT. In his 1951 lecture “Some Basic Theorems in the Foundations of Mathematics and Their Implications”, Gödel attempted to provide a more refined argument than the aforementioned conclusions, which is known as the famous disjunctive argument:

Either mathematics is incomplete in the sense that its evident axioms can never be contained within a finite set of rules, meaning that human minds (even within the pure mathematical domain) infinitely exceed the capabilities of any finite machine (or algorithm), or there exist absolutely undecidable mathematical problems.

Later scholars referred to this argument as Gödel’s Disjunctive Argument (GDA). The first disjunctive clause asserts that the abstract capabilities of human minds exceed any finite machine, even within the realm of mathematical knowledge; the second disjunctive clause asserts the existence of mathematical truths or propositions that are eternally undecidable and cannot be known by humans. Most discussions about the nature of the mind and mathematical knowledge based on the Incompleteness Theorem are built upon this argument, which can be roughly divided into three viewpoints: 1) Support for GDA, but remaining agnostic about which of the two disjunctive clauses is true, or even considering it unknowable; 2) Supporting the first disjunctive clause as true (i.e., the human mind surpasses machines); 3) Supporting the second disjunctive clause as true (i.e., there exist absolutely undecidable mathematical truths or propositions). Much evidence suggests that Gödel himself, from his rational optimism, tended to believe the first disjunctive clause is true, but he also believed that the Incompleteness Theorem itself is not sufficient to draw this conclusion.

The most cutting-edge and technically sophisticated discussions surrounding the Lucas-Penrose and Gödel disjunctive arguments can be found in Peter Koellner’s series of articles. In Koellner’s view, even from the perspective of comparing the mathematical outputs of an ideal mind and an ideal machine, it remains challenging to derive the anti-mechanism claim that “the mind cannot be fully mechanized” from GT. On one hand, from a philosophical perspective, the core concepts of “ideal mind” and “ideal machine” inherently contain too many idealized assumptions, making their precise meanings questionable, and reaching any fruitful discussion results seems difficult. On the other hand, if we set aside these philosophical doubts and provide more precise technical definitions for the aforementioned concepts, the technical results obtained are also trivial philosophical conclusions, which are hard to have the significance that Lucas, Penrose, or Gödel hoped for. Specifically, if we adopt a type-free axiomatic formal system DT regarding the truth concept T, and then add a type-free axiomatic system regarding absolute provability (equivalent to ideal human knowability) K, along with some basic bridging principles between K and T, we can express the weak mechanistic thesis (WMT) in the DTK system as ∃eK(K=Fe). Strangely, the statement of the non-mechanistic thesis (¬WMT) can be proven to be undecidable in the DTK system, meaning ¬WMT can neither be proven nor refuted (WMT also cannot be proven). Therefore, even if the disjunctive statement expressing Gödel’s disjunctive argument has a definite truth value, under sufficiently robust assumptions, we cannot determine its truth or falsity. To derive any non-trivial philosophical conclusions from GT requires further philosophical or technical arguments. Koellner believes that his conclusion has sufficient generality, meaning that even if we strengthen the axioms regarding T or K, ¬WMT is still likely to be undecidable. However, he does not completely rule out other possibilities; he believes that the greatest challenge left for scholars is to seek a more refined formal theory that includes absolute provability and truth predicates to determine WMT if we wish to derive any exact philosophical conclusions from GT.

Gödel’s View on Turing’s “Philosophical Error”

Another interesting angle to examine Gödel’s views on artificial intelligence is his seemingly contradictory dual attitude towards Turing’s definition of mechanical programs. This not only helps us better understand the role of Turing machines and other more complex models in artificial intelligence, but also highlights the efforts of both Gödel and Turing to overcome pure mechanistic and formalistic approaches.

As one of the most important concepts in the model of machine intelligence, “mechanical programs” can also be equated with “algorithms” or “computable programs”. Before 1936, it was merely an intuitive, non-formalized concept, broadly understood as a mechanical step or computable program that arrives at a precise calculation result within a finite time, according to clearly defined operational rules. In over two thousand years of mathematical practice, this intuitive concept has often been sufficiently clear and precise; for example, Euclid’s method for finding the greatest common divisor of two numbers is one of the most familiar classic algorithms. However, for certain restrictive problems, such as decidability in first-order logic, we often require a more precise mathematical definition. Miraculously, several definitions emerged simultaneously in 1936, all proven to be extensionally equivalent. All functions that are computable or mechanical are exactly those that are general recursive functions or Turing computable functions. This assertion is now widely accepted without doubt; it is known as the famous Church-Turing Thesis. In fact, Gödel initially proposed a concept of general recursion equivalent to the above definitions, but he was not confident that his concept encompassed all recursive forms and mechanical programs. Only after reading Turing’s analysis of mechanical programs did he become fully convinced, especially since he believed Turing’s analysis allowed the Incompleteness Theorem to be expressed in the most universal form.

In a very famous addendum written in 1965 regarding his 1934 Princeton lecture, Gödel stated:

In light of later developments, especially Turing’s work, we can now provide a universal definition of the concept of formal systems, which is precise and undoubtedly sufficient. For all consistent formal systems containing several finite arithmetic statements, there exist undecidable arithmetic propositions, and the consistency of this system cannot be proven within the system itself.

Turing’s contribution lies in his analysis of the concept of “mechanical programs” (or “algorithms”, “computational procedures”, or “finite combinatory procedures”) and proving its equivalence to the “Turing machine”. A formal system can simply be viewed as generating certain mechanical procedures known as provable formulas. For any formal system, there exists a corresponding finite procedure that generates the same formulas, as long as we understand it as a “finite mechanical procedure”. Of course, this is the essence of the concept of formal systems, as its nature lies in the fact that all operations on formulas are mechanical. (It is worth noting that the question of whether there exists a finite non-mechanical procedure that is not equivalent to any algorithm is entirely unrelated to Turing’s definitions of “formal systems” and “mechanical programs”. The Incompleteness Theorem and some related results do not set any limits on human rationality or mathematical ability; they merely establish a logical boundary for the potential of pure formalism in mathematics.)

Gödel’s clarification regarding GT, human rationality, and the limits of pure formalism can be seen as a response to Post. Church believed that there was no correct or incorrect issue regarding his (or Turing’s) definition of mechanical programs, as the generally accepted notion of computable processes does not have a precise definition. Thus, this working hypothesis does not have a precise meaning. However, Post disagreed; he also reached a conclusion about mechanical processes through his analysis of “finite combinatory processes”, stating that this analysis’s purpose was “not only to present a logically valid system but also to maintain psychological fidelity”. Although Post also anticipated the equivalence of his analysis with Church’s analysis, he was only willing to regard this analysis as a “working hypothesis”. Even if a stronger analysis that better aligns with psychological fidelity is proven to be equivalent to the current analysis, it would merely elevate the status of this working hypothesis to a natural law, rather than a definition or axiom. In a footnote, Post criticized Church’s view that equating computable processes with general recursive functions is regarded as a definition:

In fact, Church’s and others’ work has elevated this issue far beyond the status of a working hypothesis. However, treating this issue as a definition would obscure its true nature, which is a fundamental discovery about the limits of human mathematical ability (the mathematicizing power of Homo Sapiens), thus leading us to overlook the necessity of continuing to verify it.

Regarding the analysis and definition of mechanical programs, Gödel agreed with Post rather than Church. He did not believe that the question of whether this definition exists only from a practical perspective of utility, but rather it involves the correctness and sufficiency of conceptual analysis. However, unlike Post, Gödel believed that the precise definition of mechanical programs and the broadest meaning of the Incompleteness Theorem do not set limits on human rationality or mathematical ability. It is precisely against this backdrop that Gödel pointed out Turing’s “philosophical error” in arguing that “human mental activity cannot surpass any mechanical program”. Gödel believed that Turing assumed a finite number of distinguishable human mental states in his argument about mechanical programs, neglecting that the number of human mental states can converge to infinity through activities like understanding abstract concepts, thus rendering Turing’s argument insufficient and its conclusion avoidable. On one hand, whether Turing’s assumption of the finite nature of distinguishable states during his analysis of mechanical programs can also be seen as an argument for “human mental activity cannot surpass any mechanical program” remains to be clarified. On the other hand, whether Gödel’s comment can be viewed as a form of inconsistency—accepting Turing’s analysis results while simultaneously asserting that Turing’s argument contains a “philosophical error”—is also far from uncontroversial. From Gödel’s comments, it is clear that he realized once we can provide a precise definition of mechanical programs, the Incompleteness Theorem would logically delineate a boundary for any pure formalism. Whether it simultaneously constitutes a limitation on human minds or rationality requires further argumentation. Gödel believed we possess the ability to derive mathematical intuition through understanding abstract objects and concepts, which would be the area where the mind exceeds mechanical programs. While Turing assumed the finite nature of mental states in his analysis of the sufficiency of mechanical programs, this was merely an assumption in his analysis of this specific concept and not a universal stipulation regarding human mental capabilities. In fact, as early as his doctoral thesis, he proposed that “ordinal logic” would attempt to overcome the restrictive results brought about by GT. In his later reflections on machines and intelligence, he also transcended the purely mechanical model of the Turing machine, considering machines that could modify their own programs or improve through trial and error and learning. In other words, if Gödel argues for the mind’s superiority over pure mechanistic approaches from a more philosophical perspective of mathematical intuition, Turing, as a computer scientist, seeks to transcend the initial level of mechanical programs from a more practical perspective of intelligent machines. The two can actually be seen as complementary rather than opposing.

From the perspective of mathematical theorem proving and discovery, the latest results can be viewed as mutual confirmations of both: mathematical intuition is indispensable, but it can also be aided by machines. Traditional machines assist in theorem proving by employing brute-force methods through massive data calculations or helping to verify details in proofs to discover errors, but they struggle to generate interesting conjectures or prove problems in a manner understandable to humans. However, by introducing methods that combine reasoning and learning into traditional machines, they can produce some insights that seem only achievable through the wisdom of mathematicians. Through their powerful data processing and pattern recognition abilities, the latest artificial intelligence can help mathematicians see connections that were previously unnoticed or nearly incomprehensible, achieving results in knot theory and symmetry theory through collaboration between machines and mathematicians. As these authors emphasize, their motivation is not to directly generate conjectures or theorems using machines but rather to “focus on helping professional mathematicians gain reliable intuition, which can lead to interesting and profound outcomes”. Thus, rather than opposing intuition and mechanical methods, they can actually promote each other’s development in a mutually beneficial manner, potentially leading to the development of an artificial style of intuition.

Conclusion

Unlike Turing, Gödel did not directly participate in the actual development of electronic computers or artificial intelligence. However, as the discoverer of the most famous limiting result regarding mechanical programs—the Incompleteness Theorem—his reflections on the relationship between mechanical programs and the human mind are highly enlightening. The Lucas-Penrose argument and Gödel’s disjunctive argument, sparked by GT, remain among the most significant challenges in the philosophy of mind. The latest developments in artificial intelligence reveal the interaction and reciprocity between mathematical intuition and mechanical methods, highlighting the richness of Gödel’s and Turing’s explorations beyond pure formalism and mechanistic approaches. Further in-depth research on related issues will ultimately promote the progress and development of mathematical logic, cognitive philosophy, and artificial intelligence. Finally, to conclude this article, I would like to borrow a quote from Turing: “We can only see a short distance ahead, but we can see plenty there that needs to be done.”