Cover: Photograph of Kurt Gödel and Albert Einstein in Princeton, New Jersey, on December 5, 1947, by Oskar Morgenstern (Photo: Courtesy of the IAS Archive).

At the end of each semester, when teaching a theoretical course, I request that students prepare essays related to the subject as part of the evaluation. This practice aims to encourage broad reflection, going beyond the conventional topics of the syllabus, allowing the expression of ideas in writing, with the option to use Artificial Intelligence, such as ChatGPT, for editing enhancement. This semester, in “Mathematical Methods of Theoretical Physics 1” (Linear Algebra), I observed some remarkable essays in terms of content and writing. This motivated me to invite the responsible students to collaborate in adapting these essays into articles for our AI-focused website, ai-talks.org. In particular, I would like to highlight the work of students Letícia and Aishã, as well as the video produced by Arthur, accessible through the link provided at the end of this article (portuguese), delving deeply into Gödel’s incompleteness theorem(s). I appreciate all the students, as it is through them that I continue to learn and improve my knowledge.

Maurício Pinheiro
December 14, 2023

---

Gödel, Turing, the Theory of Everything, and Intelligent Machines

Letícia Silveira Martins, Aishã Yasmim Rodrigues
(Students, Physics Department/UFMG)
Prof. Dr. Maurício Veloso Brant Pinheiro
(Physics Department/UFMG)

Keywords: Diagonalization Argument, Bertrand Russell, Cantor, Equation of God, Formalists, Hilbert, AI, Infinity, Artificial Intelligence, Intuitionists, Logic, Intelligent Machines, Decision Problem, Hilbert’s Problems, Penrose, Halting Problem, Stephen Hawking, Gödel’s Incompleteness Theorems, Theory of Everything, Turing, Gödel.

---

Wir müssen wissen, wir werden wissen! — David Hilbert

Kurt Gödel’s achievement in modern logic is singular and monumental—indeed, it is more than a monument; it is a landmark that will remain visible for a long space and time. … The subject of logic has certainly completely changed its nature and possibilities with Gödel’s accomplishment. — John von Neumann

It is almost unbelievable that current educational systems have not completely extinguished the noble flame of intellectual curiosity — Albert Einstein

---

1 – Introduction

From David Hilbert’s visionary ideal of impeccably complete mathematics to Kurt Gödel’s meticulous investigation into the incompleteness of mathematical systems and Alan Turing’s insightful view on the impossibility of determining the outcome of all computer programs, we will embark on a fascinating journey here. We will begin our exploration by delving into the historical context preceding Gödel’s theorems, highlighting Cantor’s work in his attempt to grasp the concept of infinity. This effort sparked the clash between Intuitionists and Formalists, culminating in Gödel’s incompleteness theorems.

We will examine three crucial questions for mathematics and computing among the 23 problems posed by Hilbert: 1) “Is mathematics complete, and therefore, is there a way to prove every true statement?”; 2) “Is mathematics consistent, and therefore, completely free of contradictions?”; and 3) “Is there an algorithm capable of determining whether a statement directly follows from the axioms?”.

Next, we will address Gödel’s theorems themselves and how they answer the first two questions. The third part will take us beyond numbers and mathematics, exploring Turing’s Halting Problem as an insurmountable barrier in the quest for a universal algorithm that determines the termination of all programs. Here, we will delve into the realm of computing, confronting the fundamental limitations that Turing imposed on the ability of formal systems to decide crucial questions, thus answering the third question.

Moving forward, we will turn our gaze to the horizon of the future of science and human knowledge, questioning whether we will ever achieve mastery over all truths of the universe. This quest will be grounded in the most fundamental natural science of all scientific knowledge areas, Physics, and its master tool, Mathematics. We will establish connections between Gödel’s theorems and the realization of a Theory of Everything, inspired by the perspectives of Stephen Hawking.

Finally, in the conclusion, we will reflect on the influence of these fundamental theorems on the development of artificial intelligence and the pursuit of machine self-awareness. In this context, unconventional ideas resonate, such as those of Roger Penrose, physicist, philosopher, and Nobel Prize winner, who suggests that truly intelligent machines will be limited by these theorems, unable to attain consciousness and other notably human characteristics, such as intuition.

In a world where science intertwines with philosophy, this article seeks to unravel the mysteries underlying numbers, algorithms, and the eternal quest for knowledge, challenging us to reflect on the true scope of our understanding and persistence in the face of the uncertainties that the universe presents to us. Brace yourself for a journey that transcends the bounds of the comprehensible.

2 – Historical Context

2.1 -Cantor, Set Theory, and How Large Infinity Can Be

The odyssey that preceded the consequential revelations of Gödel’s work involved various paradoxes and conflicts between different schools of thought. To explore these origins, we need to go back to 1874. In that year, the mathematician Georg Cantor published a paper that initiated a new area of mathematics, now known as Set Theory.

We are aware of the existence of various sets such as the natural numbers (ℕ), formed by all non-negative integers, as well as the irrationals (ℝ-ℚ), composed of non-repeating decimals and non-exact roots, and the real (ℝ) and complex (ℂ) numbers, which encompass all these sets and more.

During the formulation of this theory, Cantor demonstrated that some infinities are larger than others, for example, the set of real numbers (ℝ) being larger than the set of natural numbers (ℕ). This thesis was proven through the Diagonalization Argument (see Appendix 1). In this method, Cantor proves that there are infinite sets that cannot be put into a one-to-one correspondence with the infinite set of natural numbers.

The truth is that this was just a drop in the bucket of a vast ocean of mathematical discoveries that were compelling researchers in the field to perhaps reconsider the once-thought solid foundations of the area. For 2000 years, Euclidean geometry had been considered the only one until in the 19th century, Gauss and Lobachevsky discovered non-Euclidean geometries, forcing them to reexamine such well-established concepts. Now, after the development of Calculus and a better acceptance of the conception of infinity (or infinities), perhaps mathematicians were just realizing that they knew nothing about this abstract concept that was at the heart of one of their most important areas.

2.2 – Intuitionists versus Formalists

Cantor obviously divided the mathematical community, placing on one side the Intuitionists, who believed that his works made no sense and could be considered practically a mathematical heresy, arguing that mathematics was a purely human invention, and that infinities like Georg’s were not only absurd but also not real. On the other side were the Formalists, who argued that mathematics could be completely grounded in logical foundations based on Georg Cantor’s Set Theory. Among the members of the first group, we could find Henri Poincaré, who claimed that ‘future generations would remember Set Theory as a disease from which mathematicians had fortunately recovered.’ On the other side was David Hilbert, with whom we began this text by referring to.

Hilbert indirectly led the formalists and was an avid supporter of Cantor‘s ideas. However, in 1901, Bertrand Russell realized that Cantor’s ideas, no matter how well-founded, could lead to a contradiction. This result became known as Russell’s Paradox and is a logical (Dialectical) paradox exemplified by Russell through the famous Barber Paradox (see Appendix 2).

To understand Russell’s Paradox, consider initially the Absolute set. To simplify notation, let’s refer to the Absolute as A. We will define it as the set of all sets that do not contain themselves as elements. If all sets form the set A, then it cannot be a set, and hence the paradox arises: there is no set of all sets, nor a class of all classes. When it is said that the class is within all others, it implies that it is greater than itself, which is obviously absurd. Formally stating this, we have: E is an element of A if, and only if, E is not an element of E.

A = {E | E ∉ E} 

In Cantor’s set theory, A is a well-defined set. Does A contain itself? If yes, it is not a member of A according to the definition. On the other hand, assuming that A does not contain itself, it must be a member of A according to the definition of A. Thus, the statements “A is a member of A” and “A is not a member of A” both lead to contradictions.

Despite this paradox revealing a significant flaw in Cantor’s Set Theory, Zermelo and other mathematicians associated with Hilbert resolved the issue by limiting the concept of sets and ensuring that sets like A are no longer considered sets.

With this, Hilbert aimed to ensure that mathematics was built on such a solid foundation that problems like this would not recur. Essentially, he sought to develop a proof system that referred to methods dating back to ancient Greece, starting with axioms—basic statements taken as true—from which other statements would be derived to maintain these truths as theorems.

However, this new system would be based on a symbolic language with a strict list of symbol manipulations. This system was developed and published in the book “Principia Mathematica,” a three-volume work on the foundations of mathematics written by Alfred North Whitehead and his student Bertrand Russell, published in 1910, 1912, and 1913. Although extensive, confusing, and densely notated, its authors gave up publishing a fourth volume, claiming exhaustion after the elaboration of the first three. Nevertheless, despite taking about 700 pages to simply prove that 2+2=4, the developed system proved extremely effective in avoiding errors and strange paradoxes arising from logical contradictions, demonstrating remarkable accuracy, and, above all, allowing objections to be refuted concerning the logical system itself.

Additionally, there were three questions that Hilbert wished to be answered about mathematics. These three questions were part of the famous list titled “Hilbert’s Problems,” which contains 23 mathematical problems proposed at the International Congress of Mathematicians in Paris in 1900. None of the problems had been solved until then, and several of them became highly influential in 20th-century mathematics. The three problems of fundamental interest to this work can be described as follows:

• Mathematics is complete, and therefore, is there any way to prove every statement considered true?

• The mathematics is consistent, and therefore, completely free of contradictions?

• Is there any algorithm capable of determining whether a statement follows directly from any of the axioms?

For Hilbert, the answer to all these questions was yes: “Contrary to the folly of Ignorabimus, our slogan must be we must know, we will know!” These were the words uttered by him at the annual meeting in 1930 of the German Society of Scientists and Physicians, one day after Kurt Gödel, in a roundtable during the Second Conference on the Epistemology of the Exact Sciences held in Königsberg, announced the first expression of his Incompleteness Theorem.

3 – Not everything that is true can be proven: Gödel’s Incompleteness Theorems

But for the Austrian philosopher, mathematician, and logician Kurt Friedrich Gödel, the answer to two of these three questions would be no.

Gödel used logic and mathematics to prove statements about logic and mathematics. He essentially formulated a kind of card game (a mathematical metalanguage), where he assigned a Gödel number to each mathematical symbol. The number zero, for example, would have the Gödel number 6, and to represent the number 1, you would concatenate 0 with the number corresponding to the Gödel number of the immediately succeeding symbol. This process was repeated for all other numbers.

Therefore, the equation 1 = 1 (symbolically S0=S0) would have Gödel numbers 7, 6, 5, 7, and 6. It would also be possible to create a unique number for each equation by taking the prime numbers and raising them to each of the Gödel numbers representing that equation. We would then have the number:

1=1 => 2⁷· 3⁶· 5⁵· 7⁷· 11⁶ = 4,25432 · 10²⁰ 

4,25432 · 10²⁰  is the Gödel number of the equation 1 = 1.

The beauty of this system developed by Gödel is that each assertion will have a unique number, and each number can be factored to discover its primary symbols, thus retrieving the set of fundamental cards and numbers. In this infinite deck, there are statements that are true and statements that are false. To prove them, one must resort to the axioms, which also have their own Gödel numbers. However, as these statements become more complex, their numbers become extremely large, and letters are introduced to represent them and simplify notation.

The most important Gödel number is that of the statement that says there is no proof for the statement with Gödel Number g. However, the Gödel number of this statement is g.

Hence, this card has no proof, and there is no card in our deck with infinite Gödel numbers that contains a proof for it. But if it is false and has a proof, what we prove is that it is true and has no proof. In the end, we will end up in a loop, a paradox, a contradiction. This would imply that the system created by Gödel is inconsistent.

If it were true and there really is no proof, it would show that the system is incomplete, and that is exactly what Gödel’s First Incompleteness Theorem tells us.

Theorem 1: Any recursively enumerable axiomatic theory capable of expressing some basic truths of arithmetic cannot be both complete and consistent at the same time. In other words, in a consistent theory, there are always propositions that cannot be proven to be either true or false.

This first theorem would show that the answer to Hilbert’s first question (“Is mathematics complete, and therefore, is there any way to prove every statement considered true?”) is NO. Some people might have hoped that the answer to the second question would have some room to be answered with a YES, but not long after, Gödel’s Second Incompleteness Theorem would come to crush Hilbert’s and many other mathematicians’ dreams of perfection.

Theorem 2: A theory, recursively enumerable and capable of expressing basic truths of arithmetic and some statements of proof theory, can prove its own consistency if and only if it is inconsistent.

Truth and provability are not equivalent. Hilbert was wrong, and there will always be truths in mathematics that cannot be proven. Not only that, but any consistent formal system of mathematics cannot prove its own consistency. Thus, the best mathematicians can hope for is a consistent yet incomplete system, and such a system cannot prove its own consistency. Therefore, some contradiction may always appear in the near future and undermine the entire system. Thus, the answer to Hilbert’s second question (“Is mathematics consistent and therefore completely free of contradictions?”) is also NO.

4 – Turing, Undecidability and the Halting Problem

The last question (“Is there any algorithm capable of determining whether a statement follows directly from any of the axioms?”) was answered in 1936 by Alan Turing, and to answer it, the creation of the computer was necessary. Thus, we will set mathematics aside for a moment and start thinking in terms of computation.

Just like Gödel’s Incompleteness Theorems, the Halting Problem, introduced by Alan Turing, explores the limitations of formal systems, particularly concerning the issue of undecidability. In essence, the Halting Problem demonstrates that there is no algorithm that could decide, for all Turing Machines and all possible inputs, whether the program would halt or not.

Similar to Gödel’s Theorem, the Problem also arises from the question of formalization (in this case, the formalization of the notion of computation) and the exploration of ideas put forth by David Hilbert. One of the challenges posed by the mathematician became known as Entscheidungsproblem (the Decision Problem), where he questioned whether there exists a general algorithm capable of deciding whether mathematical propositions are true or false.

In a paper published in 1936, Turing sought to define a precise mathematical model for computation, and to do so, he introduced the concept of Turing Machines: a theoretical machine capable of executing algorithms based on a finite set of rules.

In this context, the mathematician’s task facing Hilbert’s challenge was to formulate the Halting Problem, which, although simple, contains admirable depth. The Halting Problem revolves around the following question:

Given an arbitrary description of a Turing Machine and its initial input, is it possible to determine if this machine, when started with the provided input, will eventually stop or continue running indefinitely?

Using the diagonalization argument (the same used by Cantor and Gödel), Turing demonstrated that such algorithmic process is impossible, thereby establishing a fundamental limit on what can be decided through algorithms and marking the birth of the field of Computer Science. A demonstration of the Halting Problem is found in Appendix 3. An example of a simple halting problem, that of calculating Palindrome numbers, implemented in Python, is in Appendix 4.

The similarities between the argumentative resources used by Gödel and Turing in the study of undecidability are notable, allowing for a more detailed exploration of the parallels between the works of these two mathematicians.

In conclusion, we say that the Halting Problem is Undecidable for Turing Machines, and thus, bringing this result to mathematics, it is undecidable.

In the realm of Quantum Physics, one of the most relevant properties of multi-body systems lies in Spectral Gaps (or Forbidden energy Gaps), i.e., the energy difference between the ground state and the first excited state. That said, there are systems that exhibit this discontinuity between these states, presenting a gap ΔE known as Gap systems (such as semiconductors and insulators); while others are classified as Gapless for having a continuity in energy levels up to the ground state (metals).

In this context, at low temperatures, systems with a gap require a certain amount of energy to overcome this energy gap and, therefore, cannot undergo energy transitions that gapless systems can. Despite being a notable difference between the two systems, it has recently been proven that, in general, it is impossible to know whether, given a Hamiltonian, a many-body quantum system has a gap or not. This question carries with it undecidability for the vast majority of situations. A passage from the article that encapsulates this idea well (Cubitt, Toby S., et al. “Undecidability of the Spectral Gap.” Nature, vol. 528, no. 7581, Dec. 2015.) and the relationship with the themes addressed in this work is:

“Even a perfect and complete description of the microscopic interactions between the particles of a material is not always sufficient to deduce its macroscopic properties.”

The demonstration consists of formulating a Hamiltonian for the ground state that encodes the evolution of a quantum phase estimation algorithm and is followed by a Universal Turing Machine. Thus, the spectral gap depends on the result of the corresponding Halting Problem, implying the non-existence of such an algorithm and, consequently, also resulting in the fact that there are models to represent this issue of the presence or absence of the spectral gap that are independent of mathematical axioms.

We can consider that the real legacy of Hilbert’s beautiful but unreal dream in today’s world is all our computational systems. As for mathematics, Hilbert’s dream prompted Gödel to bring us a hard-to-swallow truth but capable of giving us a glimmer of hope.

5 – Will we ever know all the truths of the Universe? The Theory of Everything and the Equation of God

Since the dawn of its existence, the human race has tried to unravel mysteries that permeate the core of life and its purpose. We are naturally curious, and questions have guided us throughout history. Without delving too deeply into inquiries, we might not be where we are today. Without daring and dreams that could either materialize or not, we might never have advanced as a species.

With each passing day, we master nature more and more. We are confident that our knowledge is so excellent that the dream that has intrigued and motivated physicists the most in recent decades is the possibility of soon obtaining a Theory of Everything. Albert Einstein spent 30 years of his life searching for an equation that would unify the four fundamental forces of the universe: gravity, electromagnetism, and the two nuclear forces. The goal was to find a single theory that encompassed them, an Equation of God.

A vast array of scientists has dedicated their lives to this pursuit. Stephen Hawking, for many years one of the leading figures striving for this achievement, became convinced after a long time that perhaps this dream was unattainable.

“The real reason why we seek a complete theory is that we want to understand the universe and feel that we are not just victims of dark and mysterious forces. If we understand the universe, then we control it, in a sense. The standard model is clearly unsatisfactory in this regard. First of all, it is ugly and ad hoc. Particles are grouped seemingly arbitrarily, and the standard model depends on 24 numbers whose values cannot be deduced from first principles but must be chosen to fit observations. What understanding is there in that? Could it be the last word of Nature? […] Gödel’s Theorem is proven using statements that refer to themselves. Such statements can lead to paradoxes. What is the connection between Gödel’s theorem and whether we can formulate the theory of the universe in terms of a finite number of principles? A connection is obvious. According to the positivist philosophy of science, a physical theory is a mathematical model. Therefore, if there are mathematical results that cannot be proven, there are physical problems that cannot be predicted. […] Although this is a kind of incompleteness, it is not the type of unpredictability I refer to. Given a specific number of blocks, it can be determined with a finite number of attempts whether they can be divided into two prime numbers. But I think quantum theory and gravity together introduce a new element into the discussion that was not present in classical Newtonian theory. In the standard positivist approach to the philosophy of science, physical theories live freely in a Platonic paradise of ideal mathematical models. That is, a model can be arbitrarily detailed and contain an arbitrary amount of information without affecting the universes it describes. But we are not angels who see the universe from outside. Instead, we and our models are part of the universe we are describing. Thus, a physical theory is self-referential, as in Gödel’s theorem. We could, therefore, expect it to be inconsistent or incomplete. The theories we have so far are indeed inconsistent and incomplete.” — Stephen Hawking

As highlighted by Hawking, we are inhabitants of this Universe trying to unravel it through tools full of self-references. The chances that we will continue working for years and years without ever reaching a satisfactory conclusion are much greater than 0. There are limitations stemming from our level of technological advancement that may take centuries, millennia to overcome. There are others, intrinsic to our nature, laws that prevent us from seeing further and having a greater understanding of everything around us. However, only in the last century have we discovered that mathematics can never be complete and prove itself completely consistent, and two major physical theories had to be reformulated, forcing physicists to look at reality with different eyes. Every day, science expands, and we are forced to transform ourselves completely if we want to keep advancing. There may be some obstacles along the way, but we always need to be stubborn and determined not to give up on our dreams. Our mind can never close, even though sometimes it may unconsciously try to do so, as no human being is perfect enough to be free from external influences. Not even machines, intelligences that we insistently try to replicate and force to be like ours, may escape this influence. After all, we created them, and possibly, we cannot avoid imparting our traits to them unconsciously.

Fortunately, we are beings that always evolve. We undergo numerous metamorphoses and never remain the same. And that was the good news that Gödel brought us, and Hawking managed to see.

Hilbert said that we need to know, we will know. The harsh truth that Gödel brought us is that we do not know, and perhaps we never will. Some people may be disappointed with this, with the absence of a beautiful and unified theory capable of describing the birth of the universe and its end. But the good news is that our knowledge will never end. The true beauty of being a scientist is not only constituted by the conclusions and objectives we achieve but by the entire path and discoveries that fill it, expanding our minds ad infinitum. Knowing that this tool we call science is part of Cantor’s countless sets may be the best thing a scientist has discovered.

Our quest for knowledge will never end, and this is due to the fact that we always have the challenge of new discoveries. Without this, we would be stagnant. In the words of Stephen Hawking, Gödel’s theorem ensured that there would always be employment for mathematicians. This, being the language of the Universe, under which all Physics is based, perhaps shows that we may be in a similar position.

6 – Conclusion: AI and Intelligent Machines

Gödel’s theorems and Turing’s Undecidability Theorem represent crucial milestones in mathematics and computer science, with significant implications for artificial intelligence (AI). Published in 1931, Gödel’s incompleteness theorem, as we have seen, reveals intrinsic limitations in axiomatic systems by stating that no consistent and sufficiently rich system can prove all true propositions within itself. This implies that there will always be arithmetic truths that elude formal proof, challenging the notion of a perfect axiomatic system. In 1936, Turing’s Undecidability Theorem extended these limitations by demonstrating that there is no universal algorithm capable of deciding whether a computer program will terminate or not. This establishes that there is no comprehensive algorithm capable of solving all decision problems. These conclusions revolutionized understanding the boundaries of computation and formal logic.

When applied to AI, these theorems suggest that it is impossible to create an intelligent machine that can encompass all arithmetic truths or solve all decision problems. However, this impossibility does not negate the viability of artificial intelligence. Intelligent machines can, and indeed already do, perform complex and challenging tasks, even if they lack the ability to address all facets of human intelligence.

Let’s take chess as an example. Although there is no perfect algorithm that always wins, machines like Deep Blue have demonstrated a remarkable ability to defeat human champions. Automatic translation is another example, where algorithms like Google Translate perform complex tasks effectively, even though there is no perfect solution for translating all texts.

Despite these successes, Gödel’s and Turing’s theorems indicate that artificial intelligence cannot completely replicate the breadth of human intelligence. Nobel Prize-winning physicist and philosopher Roger Penrose argues that human intuition, based on a profound understanding of reality, escapes the capacity of intelligent machines, at least those with classical – not quantum – computing. He emphasizes that, while machines can excel at specific tasks, a holistic and intuitive understanding of reality remains beyond their reach, being, according to him, associated with quantum processes in our brain.

This discussion about the possibility of machines achieving human intelligence continues to be complex and controversial. While Gödel’s and Turing’s theorems provide a solid mathematical foundation for this reflection, they do not offer a definitive answer. AI remains an ever-evolving field, challenging established theoretical limits, while the quest to understand the true nature of intelligence persists.

---

7. References 

Videos

Articles and Books

Cubitt, Toby S., David Perez-Garcia, and Michael M. Wolf. “Undecidability of the spectral gap.” Nature 528.7581 (2015): 207-211.

Ferreirós, José. “The crisis in the foundations of mathematics.” The Princeton companion to mathematics (2008): 142-156.

de Morais, Lauro Iane. “UMA BREVE INTRODUÇÃO AO PARADOXO DE RUSSELL: o que ele é, como ele afetou o sistema fregeano e sua possível solução.” O Manguezal—Revista de Filosofia 1.2 (2018). (Portuguese)

Aaronson, Scott. Quantum computing since Democritus. Cambridge University Press, 2013.

Ben-Ya’acov, Uri. “Gödel’s incompleteness theorem and Universal physical theories.” Journal of Physics: Conference Series. Vol. 1391. No. 1. IOP Publishing, 2019.

Beklemishev, Lev D. “Gödel incompleteness theorems and the limits of their applicability. I.” Russian Mathematical Surveys 65.5 (2010): 857.

Peregrin, Jaroslav. “Gödel, truth & proof.” Journal of Physics: Conference Series. Vol. 82. No. 1. IOP Publishing, 2007.

Yan, Yutong. “Gödel’s Incompleteness Theorem and Problems Outside Quantum Mechanics.” Journal of Physics: Conference Series. Vol. 2012. No. 1. IOP Publishing, 2021.

Penrose, Roger. The Emperor’s New Mind: Concerning Computers, Minds and The Laws of Physics. 1989. 

Links:

What Is Russell’s Paradox?

Kurt Gödel: O Filósofo Paranoico Que Provou a Incompletude Da Matemática. (Portuguese)

O Logicismo, O Formalismo E O Intuicionismo E Seus Diferentes Modos de Pensar a Matemática. (Portuguese)

Formal Computational Models and Computability.

How Gödel’s Proof Works. Quantamagazine

Godel and the End of Physics 

Cantor’s diagonal proof

O programa do palíndromo (Portuguese)

---

8 – Appendices:

1. The Diagonalization Argument

To understand the Diagonalization Argument, Cantor proposed the following exercise:

Take a sheet of paper and write down on one side all natural numbers. Draw a line, and on the other side, write any real number between 0 and 1. Suppose you have completed this list, and it is both complete and infinite. Now, let’s write a new real number between 0 and 1. Take the first digit of the first number and add 1, then move to the second digit of the second number, add 1, and continue repeating this process until you reach the last digit of the last natural number. You can change the conception of this number by choosing to add 2 instead of 1, or even your favorite number; the important thing is to change all the digits. At the end of this process, you will have a new real number that has not appeared anywhere on this list because it differs from the nth real by its nth digit. This argument is known as Cantor’s Diagonalization Argument and basically implies that there must be more real numbers between 0 and 1 than non-negative integers, and therefore, there are infinities that are larger than others. 

---

2. The Barber Paradox

The Barber Paradox is based on the idea that there is a barber in a town who shaves all men that do not shave themselves. If the barber does not shave himself, then he must shave the men who do not shave themselves, but he must not shave the men who do not shave themselves. The paradox can be expressed as follows:

Hypothesis: There is a barber in a town who shaves all men that do not shave themselves.

Conclusion: The barber must shave himself.

If the barber shaves himself, then he falls under the definition of a man who does not shave himself. Therefore, he must be shaved by the barber himself. However, if the barber does not shave himself, then he falls under the definition of a man who shaves himself. Therefore, he must be shaved by the barber himself.

The conclusion of the paradox is that the hypothesis is false, meaning there is no barber who shaves all men that do not shave themselves.

Other examples of dialectical paradoxes include:

Liar Paradox: A man claims that he is a liar. If he is telling the truth, then he is lying. If he is lying, then he is telling the truth. The Liar Paradox is a self-referential paradox, based on the idea that a statement can be false if it refers to itself. In the case of the Liar Paradox, the statement is “I am lying.” If the statement is true, then it is false. If the statement is false, then it is true.

Epimenides’ Paradox: Epimenides, a Cretan, claims that all Cretans are liars. If he is telling the truth, then he is a liar. If he is lying, then he is telling the truth. Epimenides’ Paradox is similar to the Liar Paradox, also based on the idea that a statement can be false if it refers to itself. In the case of Epimenides’ Paradox, the statement is “All Cretans are liars.” If Epimenides is a Cretan, then the statement is true if he is lying and false if he is telling the truth.

Ship of Theseus Paradox: A ship is being restored, and each original piece is replaced by a new piece. When the ship is completely restored, is it still the same original ship? The Ship of Theseus Paradox is an identity paradox, based on the idea that the identity of an object is not determined solely by its parts. In the case of the Ship of Theseus Paradox, the ship is identified as a set of pieces connected in a certain way. If all the pieces of the ship are replaced by new pieces, is the ship still the same original ship? There is no easy answer to this paradox. Some people believe that the ship will still be the same original ship, while others believe it will be a new ship.

These paradoxes are important in logic as they demonstrate that not all seemingly true propositions are truly true. They also force us to question our assumptions about the nature of truth and reality.

---

3. Proof of the Halting Problem

Let’s imagine that we have a procedure called Halts(P, D), which takes as input a program P and data D, and answers ‘yes’ if P halts with D. However, we cannot simply simulate program P on input D because we don’t know whether P will halt or enter an infinite loop. One solution would be to consider that input D can also be a program. From this perspective, we can create a new, more limited program called NewHalts(P), which tests whether program P halts when the input is a copy of P (assuming D is equal to P).

Furthermore, we can build another program called Opposite(P) that does the opposite of NewHalts(P).

Now, let’s see what happens when we apply the concept of self-reference, that is, the possibilities for Opposite(Opposite(P)):

1. If the program Opposite(P) halts when the input is itself, then Opposite(Opposite(P)) continues running indefinitely.

2. If the program Opposite(P) does not halt when the input is itself, then Opposite(Opposite(P)) halts.

These are mutually exclusive situations—Opposite(Opposite(P)) can only either halt or run forever. This leads us to a contradiction! Examining the procedures used by Opposite(P), we realize that it relies on the program NewHalts(P), which, in turn, depends on the program Halts(P,D). Considering that our only assumption was the existence of the program Halts(P,D), we conclude that, in reality, this algorithmic procedure cannot exist! Q.E.D.

---

4. Practical Example of a Halting Problem: Palindrome Numbers

To illustrate with a practical example the Turing Halting Problem solution of this problem, let’s consider the Python code below that generates palindrome numbers, i.e., numbers that read the same backward as forward (e.g., 123321):

In this example, the input is a number n. If n is a palindrome (stdin = 121), it is returned (stdout = 121). If it is not (e.g., stdin = 13), from the number n = 13, a number m = 31 is produced, which is n read backward, and then the two are summed to produce c = 13 + 31 = 44, which is used recursively as a new n until a palindrome is produced, and the program stops. To clarify what the program is doing, it prints on the output all the numbers it generates.

The Lychrel function terminates when the input is the number 196. This is another open mathematical problem. The Lychrel conjecture states that this always happens. A Lychrel number is a natural number that cannot form a palindrome through the repetitive iterative process of reversing its digits and summing the resulting numbers. It is believed that this conjecture is false and that 196 would be the first counterexample to it and therefore the first Lychrel number. As this is an open mathematical problem, no one knows the answer, and after billions of iterations that produce numbers with billions of digits, a palindrome insists on not forming. However, it is not known if eventually one would form with a trillion, a quadrillion, a zillion, perhaps a googolplex of iterations, or maybe, if one would indeed never form (a googolplex is ten to the power of a googol, which is itself ten to the power of one hundred).

If the program terminates, a program capable of inspecting the code of another program to determine whether it enters an infinite loop or not when given any input, giving Yes or No as output in a finite time, were to examine the lychrel program to determine if it terminates with input 196, it would need to be able to either determine when it would end or find a reason why it would never end, and thereby solve the Halting Problem. To do this, such program terminates would not be something simple, and according to Turing, it does not exist.

---

Copyright 2024 AI-Talks.org