Gödel’s Incompleteness Theorem, Turing’s Halting Problem, and the Theoretical Limits of Artificial Intelligence: On The Non Computationality Of Consciousness.
Present What You Take To Be The Best Argument Against The Possibility Of Artificial Intelligence? Does It Succeed?
This essay explores the feasibility of artificial intelligence by distinguishing between weak AI, which mimics human cognitive processes in specific tasks, and strong AI, which envisions machines attaining genuine consciousness and understanding - a contentious idea (Mureithi. 2024; Flowers, 2019). This essay argues that Gödel’s Theorem demonstrates the existence of truths within formal systems that cannot be proven using the system's own rules (Feferman, 1995). Since machines operate based on formal rules, they are bound by these same limitations (Lucas, 1996). In contrast, the human mind can comprehend the truth of these Gödelian statements, highlighting that the mind transcends computation by grasping truths beyond the constraints of formal systems (Penrose, 1995). This challenges the possibility of strong AI, suggesting the mind surpasses what algorithms can achieve (Penrose, 1995). Strong AI assumes cognitive processes like reasoning and learning are computational and can be fully replicated in machines (Feferman, 1995). Proponents, rooted in computational functionalism, argue that cognition depends on algorithms rather than physical structure, aligning with the Church-Turing thesis (Feferman, 1995). If the brain operates on computational principles, replicating its functions in machines might seem feasible (Edelman, 2008). However, Gödel’s insights suggest otherwise, highlighting the unique, non-computational nature of human cognition (Penrose, 1995).
Kurt Gödel’s incompleteness theorem, published in 1931, is a landmark discovery in mathematical logic with profound implications for mathematics, the philosophy of mind, and artificial intelligence (Sabinasz, 2017). Gödel demonstrated that any formal system capable of basic arithmetic contains true statements - known as Gödel sentences - that cannot be proven within the system itself (Goldstein, 2006). This means no formal system can be both complete (able to prove all truths) and consistent (free of contradictions) (Goldstein, 2006; Sabinasz, 2017). Gödel achieved this by constructing a self-referential statement that essentially asserts, “This statement is not provable within this system.” If the system could prove the statement, it would create a contradiction, rendering the system inconsistent (Penrose, 1994). Conversely, if the system cannot prove the statement, the statement is true but unprovable within the system (Penrose, 1994; Sabinasz, 2017). Thus, Gödel’s theorem reveals that sufficiently complex formal systems always contain true but unprovable statements and cannot prove their own consistency (Goldstein, 2006). This discovery highlights the inherent limitations of formal systems, challenging the notion that they can fully capture all truths or provide absolute reliability in fields like mathematics and computation (Goldstein, 2006; Penrose, 1994; Sabinasz, 2017).
Gödel’s Incompleteness Theorem consists of two interconnected results. First, any consistent formal system F capable of performing basic arithmetic is incomplete, meaning there are true statements in its language (for example, mathematics) that cannot be proven or disproven within the system (Penrose, 1994; Sabinasz, 2017). These findings demonstrate that absolute consistency proofs are impossible for axiomatic systems capable of arithmetic. Such systems will always contain statements that cannot be resolved through their formal rules but are nevertheless true (Goldstein, 2006). Thus, Gödel’s Theorem reveals that any sufficiently strong formal system has inherent limitations, with truths that lie beyond its scope of provability.
Gödel’s theorem can be challenging to grasp, but it becomes clearer by examining its implications. Consider the analogous statement, “This formula is unprovable in the system.” If it were false, it would mean the statement is provable, leading to a contradiction: a provable statement that claims to be unprovable (Lucas, 1996). In a consistent system, anything provable must be true, so the statement must be true but unprovable to avoid inconsistency (Lucas, 1996). This self-referential logic demonstrates that in any consistent system capable of basic arithmetic, there will always be true statements that cannot be proven within the system itself (Penrose, 1994; Lucas, 1996; Sabinasz, 2017). Gödel’s rigorous proof establishes this without flaw, showing that these unprovable truths exist, and from outside the system, we can recognise them as true (Lucas, 1996; Penrose, 1994).
The Halting Problem is a valuable parallel to articulate this point clearly. The Halting Problem shows that no machine can universally determine whether a given computer program will eventually stop running (halt) or run forever, highlighting a fundamental constraint of computation (Penrose, 1994). Consider a hypothetical machine H designed to solve the Halting Problem. H takes two inputs: a description of a program P and its input data D. H outputs “halts” if P stops running on D and “does not halt” if P runs indefinitely (Burkholder, 1987). While this seems plausible, Turing proved it is impossible (Lucas, 1996). The proof involves creating a program P′ that uses H as an input and behaves as follows: If H predicts P′ will halt, P′ enters an infinite loop. If H predicts P′ will not halt, P′ halts immediately. This setup creates a contradiction: if H says “halts,” P′ loops forever, making H’s prediction incorrect. If H says, “does not halt,” P′ halts, again contradicting H (Penrose, 1994). This paradox demonstrates that H cannot solve the Halting Problem for all possible programs, revealing an inherent limitation of machines: they cannot resolve problems involving their own predictions (Prokopenko et al., 2019; Lucas, 2021; Penrose, 1994).
Humans, unlike machines, can recognise why the Halting Problem is unsolvable (Penrose, 1994). The contradiction arises because program P′ is designed to act contrary to H’s prediction, and humans can understand this self-referential issue without needing to compute an answer within H’s framework (Penrose, 1994; Lucas, 1996). This ability to "step out" of the formal system and analyse its structure is uniquely human, allowing us to identify why the contradiction occurs and understand the system’s limitations (Lucas, 1996; Penrose, 1994). Machines, constrained by their formal rules, cannot reflect on their own limitations in the same way (Lucas, 1996). This distinction mirrors Gödel’s incompleteness theorem, where a Gödel sentence - a true statement a formal system cannot prove - reveals similar limitations of machines governed by formal rules (Sabinasz, 2017; Goldstein, 2006). While machines are bound by their programming and unable to recognize such truths, humans can reason about the system as a whole and understand why the Gödel sentence must be true without leading to contradiction (Lucas, 1996; Sabinasz, 2017). Thus, the Halting Problem illustrates that machines are fundamentally limited by the rules of their formal systems. They cannot solve certain problems or recognise specific truths (Lucas, 1996; Penrose, 1994). Humans, however, engage in meta-reasoning, using intuition and conceptual understanding to transcend these limitations (Penrose, 1994). This capacity to “step out” of formal systems supports the argument that human reasoning is non-computational and fundamentally distinct from machines (Lucas, 1996).
In summary, Gödel’s incompleteness theorem and Turing’s Halting Problem highlight the inherent limitations of formal systems and computational logic (Prokopenko et al., 2019; Penrose, 1994). Gödel’s theorem demonstrates that any formal system capable of arithmetic will contain true statements that cannot be proven within its rules, while the Halting Problem shows that no algorithm can universally determine whether a program will halt or run indefinitely (Penrose, 1994; Sabinasz, 2017).
Vitally, Gödel’s Incompleteness Theorem offers a compelling argument for the fundamentally non-computational nature of the human mind (Lucas, 1996; Penrose, 1994; Goldstein, 2006). By proving that any formal system capable of arithmetic is inherently incomplete - containing true statements it cannot prove - the theorem exposes the limitations of computational systems, which are bound by formal rules (Goldstein, 2006). Machines, as formal systems, are necessarily subject to these same constraints (Goldstein, 2006). In contrast, human reasoning appears capable of transcending these boundaries, suggesting that the mind operates beyond mere computation (Penrose, 1994).
In The Emperor’s New Mind, Penrose contends that human consciousness involves processes beyond algorithmic computation, as our ability to grasp truths outside formal systems demonstrates reasoning that no machine can replicate (Penrose, 1994; Sabinasz, 2017). Gödel’s theorem shows that formal systems capable of arithmetic contain true statements - Gödel sentences - that cannot be proven within their own rules (Sabinasz, 2017). Machines, bound by formal systems, cannot prove such statements algorithmically (Sabinasz, 2017). In contrast, the human mind can step outside these constraints and recognise the truth of Gödel sentences, even when they cannot be proven within a formal system (Lucas, 1996). This ability to perceive truths beyond algorithmic proof indicates that human reasoning transcends computation (Penrose, 1994). The reasoning is as follows: if the mind were purely algorithmic, it would share the same limitations as machines and formal systems (Penrose, 1994). The fact that the mind can overcome these constraints suggests that consciousness and reasoning are not reducible to algorithms. Instead, they involve processes fundamentally distinct from the rigid, rule-bound operations of computational systems (Bringsjord and Xiao, 2000; Lucas, 1996). This conclusion, grounded in Gödel’s theorem, reinforces the view that the human mind is far more than a machine and thus must be more than mere computation (non-computationalism) (Penrose, 1994).
John Lucas presents a similar argument in his paper Minds, Machines, and Gödel, asserting that machines, including computers, operate as formal systems (Penrose, 1994). Machines rely on predefined rules and assumptions, akin to how mathematical systems derive conclusions from axioms and inference rules (Sabinasz, 2017; Lucas, 1996). Since machines are constrained by a finite set of operations and assumptions, their processes can be represented as logical proofs within a formal system (Lucas, 1996). However, Gödel’s incompleteness theorem demonstrates that any formal system capable of arithmetic contains true statements, such as Gödel’s formula G(F) that cannot be proven within the system itself (Lucas, 1996; Penrose, 1994). Lucas argues that, while a machine cannot prove such statements, the human mind can recognise their truth (Lucas, 1996). This ability indicates that the human mind operates beyond the limitations of formal systems, reinforcing the conclusion that the mind is fundamentally non-computational and distinct from machines (Bringsjord and Xiao, 2000; Lucas, 1996). Moreover, since the human mind can perform arithmetic, any formal system F that attempts to model the mind must also be capable of arithmetic. Therefore, there are true statements, like G(F) that the machine cannot produce but the human mind can recognise as true (Lucas, 1996). By following Gödel’s proof, the mind can ascertain that G(F) is true, even though it cannot be proven within the formal system F (Lucas, 1996). Thus, Lucas concludes that machines cannot adequately model the mind, as there exist truths the mind can know that machines cannot (Sabinasz, 2017; Lucas, 1996).
Before addressing counterarguments, it is crucial to clarify Lucas’s position. He asserts that machines, as formal systems, operate under predefined rules and assumptions, constrained by logical proofs within their frameworks (Sabinasz, 2017). Gödel’s incompleteness theorem shows that such systems contain true statements, like G(F), that cannot be proven within the system (Lucas, 1996; Penrose, 1994). Unlike machines, Lucas argues, the human mind can recognise these truths, transcending formal constraints. Thus, he concludes that the mind is fundamentally distinct from machines, operating beyond mechanistic computation (Sabinasz, 2017; Lucas, 1996). To evaluate this claim, it is necessary to consider whether this distinction holds and whether iterative advancements might enable machines to replicate the cognitive abilities Lucas attributes exclusively to humans.
One central counterargument, known as the Extended Machine Objection, challenges Lucas’s claims by asserting that machines could be iteratively improved to address their limitations (Rogers, 1987). This objection posits that if a formal system F cannot generate or recognise the truth of its Gödel sentence G(F) a new machine could be designed as a formal system F′ with additional rules or axioms specifically tailored to handle G(F) (Rogers, 1987). Proponents argue that this iterative process could continue indefinitely, with each subsequent system (F′′,F′′′, and so on) addressing the Gödel sentence of the preceding system (Sabinasz, 2017; Rogers, 1987). By systematically upgrading machines with more advanced formal systems, they contend that machines could eventually approximate or even match the reasoning capabilities of the human mind (Sabinasz, 2017). If true, this iterative upgrading of machines to handle G(F)) and similar limitations would undermine Lucas’s assertion that the human mind is fundamentally distinct from machines (Sabinasz, 2017). It would suggest that, through continuous improvements, machines could overcome the constraints imposed by Gödel’s incompleteness theorem and replicate the human mind’s ability to recognise truths beyond formal systems (Rogers, 1987). This challenges the core of Lucas’s argument by proposing that the limitations of formal systems are not insurmountable for machines but instead represent opportunities for iterative enhancement (Sabinasz, 2017).
However, this counterargument ultimately fails to disprove Lucas’s claim because each new formal system created to handle its predecessor’s Gödel sentence would itself have a new Gödel sentence that it cannot resolve (Sabinasz, 2017; Lucas, 1996). For example, if system F is upgraded to F′ to handle G(F), the new system F ′would generate its own Gödel sentence G(F′) which it cannot prove (Lucas, 1996; Sabinasz, 2017). This iterative process would repeat indefinitely, with each upgraded system (F′′,F′′′ and so on) encountering a new Gödel sentence G(F′′)G(F''), etc., that lies beyond its capacity to prove (Sabinasz, 2017). This endless cycle stems from the intrinsic nature of Gödel’s incompleteness theorem, which shows that any sufficiently complex formal system capable of arithmetic will always contain true statements it cannot prove within its framework (Goldstein, 2006). When previously unprovable truths, like G(F), are added as axioms to create a new system F′, Gödel’s theorem guarantees that the new system F′ will have its own unprovable Gödel sentence G(F′) (Lucas, 1996; Sabinasz, 2017). The same applies to F′′, and all subsequent systems, resulting in an infinite regress of Gödel sentences (Sabinasz, 2017). In contrast, the human mind appears capable of recognising the truth of these Gödel sentences for any formal system, regardless of its limitations (Lucas, 1996). This unique ability supports Lucas’s argument that the mind operates beyond the confines of formal systems in ways that machines, even through iterative improvements, cannot replicate (Sabinasz, 2017). Gödel’s theorem thus reinforces the distinction Lucas draws between human cognition and computational systems, as the mind consistently transcends the limitations imposed by formal frameworks (Lucas, 1996).
This distinction is central to Lucas’s argument, as it emphasises the fundamental difference between machines and the human mind (Lucas, 1996; Sabinasz, 2017). Machines, regardless of their complexity, are constrained by the formal systems they embody. Their operations are limited to the axioms and rules encoded into them (Lucas, 1996). In contrast, Lucas argues, the human mind transcends these formal boundaries by recognising truths that are inaccessible within the system itself (Lucas, 1996). This unique capability, Lucas contends, makes the human mind fundamentally distinct from, and superior to, any machine or formal system (Lucas, 1996). The Extended Machine Objection attempts to counter Lucas by suggesting that machines could eventually replicate or surpass human cognition through iterative improvements (Sabinasz, 2017). However, Lucas’s response underscores that Gödel’s incompleteness theorem imposes an insurmountable barrier to such advancements (Sabinasz, 2017; Lucas, 1996). Each upgraded machine, as a new formal system, would still face Gödelian limitations, leaving it unable to fully replicate the human mind’s ability to recognise truths beyond formal systems (Lucas, 1996). This reinforces Lucas’s claim that machines remain fundamentally constrained, while the human mind operates in a non-computational manner (Sabinasz, 2017). These insights directly challenge the feasibility of Strong AI, which posits that human cognition can be fully replicated through computational processes (Bory et al, 2024). Gödel’s theorem and related arguments demonstrate that computation has inherent limits. If the human mind can grasp truths that no machine can recognise or prove, then it operates on principles beyond computation (Penrose, 1994). This undermines the core premise of Strong AI, which assumes that cognition is purely algorithmic and reducible to formal systems (Mureithi, 2024).
In conclusion, this essay has argued that Strong Artificial Intelligence, defined as AI replicating or surpassing human cognition, is fundamentally implausible. Drawing on Gödel’s incompleteness theorem and the Halting Problem, it highlighted the inherent limitations of computational systems and the unique capabilities of the human mind. Gödel’s theorem shows that all formal systems contain true statements they cannot prove, and the Halting Problem demonstrates that no machine can universally determine whether a program will halt. Machines, as computational systems, are bound by these constraints. In contrast, the human mind transcends such limitations, recognising truths that machines cannot through intuition and meta-reasoning. These insights undermine Strong AI’s premise that human cognition is fully replicable through computation. Machines cannot grasp truths beyond formal systems, whereas the human mind operates beyond algorithmic constraints – showing that the mind must be more than computation (non-computational). Thus, while machines excel in specific domains, they cannot replicate the full scope of human cognitive abilities, making Strong AI incompatible with the nature of the non-computational mind.
1) Burkholder, L., (1987). The halting problem. ACM SIGACT News, 18(3), pp.48-60.
2) Bringsjord, S. and Xiao, H., (2000). A refutation of Penrose’s Gödelian case against artificial intelligence. Journal of Experimental & Theoretical Artificial Intelligence, 12(3), pp.307-329.
3) Bory, P., Natale, S. and Katzenbach, C., (2024). Strong and weak AI narratives: an analytical framework. AI & SOCIETY, pp.1-11.
4) Edelman, S., (2008). Computing the mind: How the mind really works. Oxford University Press.
5) Flowers, J.C., (2019), March. Strong and Weak AI: Deweyan Considerations. In AAAI spring symposium: Towards conscious AI systems (Vol. 2287, No. 7).
6) Feferman, S., (1995). Penrose’s Gödelian argument. Psyche, 2(7), pp.21-32.
7) Goldstein, R., (2006). Incompleteness: The proof and paradox of Kurt Godel. WW Norton & Company.
8) Lucas, S., (2021). The origins of the halting problem. Journal of Logical and Algebraic Methods in Programming, 121, p.100687.
9) Lucas, J., (1996). Minds, machines and Gödel: A retrospect. Artificial intelligence: critical concepts, 3, pp.359-76.
10) Lucas, J.R., (1963). Minds, machines and Gödel. Philosophy, XXXVI: 112–127, 1961. Reprinted in The Modeling of Mind, KM Sayre and FJ Crosson, eds.
11) Mureithi, V., (2024). Functionalism, Algorithms and the Pursuit of a Theory of Mind for Artificial Intelligence. Critical Humanities, 3(1), p.2.
12) Penrose, R., (1994). Shadows of the Mind.
13) Prokopenko, M., Harré, M., Lizier, J., Boschetti, F., Peppas, P. and Kauffman, S., (2019). Self-referential basis of undecidable dynamics: From the Liar paradox and the halting problem to the edge of chaos. Physics of life reviews, 31, pp.134-156.
14) Rogers Jr, H., (1987). Theory of recursive functions and effective computability. MIT press.
15) Searle, J., (1980). Minds, Brains, and Programs.
16) Sabinasz, D., (2017). Gödel's Incompleteness Theorem and Its Implications for Artificial Intelligence. [online] Available at: https://www.sabinasz.net/godels-incompleteness-theorem-and-its-implications-for-artificial-intelligence/ [Accessed 18 January 2025].
