Canadian mathematician Simon Kochen recalled in his tribute to Kurt Gödel how during his PhD exam, he was asked to name five of Gödel’s theorems. The essence of the question was that each of the theorems either gave birth to a new branch of, or revolutionized, modern mathematical logic. “Proof theory, model theory, recursion theory, set theory, intuitionistic logic - all had been transformed by, or, in certain cases, had gotten their inception from, Gödel’s work” (Goldstein, 2005). But among the brilliant achievements of Kurt Gödel one stands out exceptionally.

One need not to be a practicing mathematician in order to grasp the basic idea and message of the Incompleteness Theorem. And maybe that is why this result gained so much audacity in the popular scientific debate. But, of course, this ingenious simplicity is only one of many aspects of the 1931 work that distinguish it from other outstanding works of the Austrian intellectual giant.

It seems to me that what strikes us from the beginning when we come across the Incompleteness Theorem for the first time is the observation that it is not merely one of many mathematical results. That is, it does not aim at establishing whether some abstract object X has the property φ. Rather, it pertains to the totality of utterable mathematical statements in a certain (quite infinite and quite fundamental) domain. It says something about everything, one might be inclined to say.

Of course such contention is a bit premature, since the original paper only dealt with the set of sentences expressible in the formalism of Principia Mathematica, but since the incompleteness arises as soon as the system contains basic arithmetic, we aptly conclude that there is something very deep and very far-reaching in this result. Yet, Gödel himself, careful as he was, did not believe that the incompleteness features all formal systems with some finitistic arithmetic (e.g. Robinson’s arithmetic) up until 1935, when he saw Turing’s analysis of computability. It was Turing’s work that made undecidability a general, philosophically captivating notion. In his lecture at the Princeton bicentennial conference on problems in mathematics Gödel remarked:

Tarski has stressed in his lecture [that preceded Gödel’s](and I think justly) the great importance of the concept of general recursiveness (or Turing’s computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e., one not depending on the formalism chosen.

As long as Gödel refers to a formal system in which certain true statement is unprovable, Turing showed that one can think of a “computing machine” that cannot compute the value of a certain function. And thanks to his analysis of the notion of computability, Turing’s case was unbound by the choice of a formal system, and in this way absolute. He explained:

Gödel has shown that (in the formalism of Principia Mathematica) there are propositions U such that neither U nor ~U is provable. As a consequence of this, it is shown that no proof of consistency of Principia Mathematica (or of K [an arbitrary formal system with basic arithmetic]) can be given within that formalism. […] I shall show that there is no general method which tells whether a given formula is provable in K. (Turing, 1936)

Indeed, it was a giant step in the reflection on the concept of mathematical truth, probably the most significant in history. It showed us, in a uniquely simple way, that true does not immediately mean provable. In this sense, such meta-mathematical result is of greater importance to philosophers than to mathematicians. And so, philosophers, Gödel and Turing included, began to reflect upon the philosophical consequences from the startling theorem.

Now, generally speaking, since Turing’s work laid foundations for computer science and ultimately led to the construction of first computers, one can ask about the mathematical capacities of computers: what are the limitations to their “abilities” in proving mathematical theorems?

Some thinkers, such as John Lucas and celebrated physicist Roger Penrose (yes, the 2020 Nobel Prize winner) believed Gödel’s and Turing’s work to show with mathematical precision that the human mind “infinitely surpasses the machine”. Although Lucas’s and Penrose’s arguments differ, the gist of their reasoning is this: (1) consider a formal system S with recursive axiomatics and enough expressive power to state arithmetical truths — it has a counterpart in a finite Turing machine M. (2) You can find a Gödel sentence for this system (a sentence undecidable from the perspective of the system), whose truthfulness is intuitively apparent for humans. (3) Since M cannot produce the proof for this Gödel sentence, its mathematical capabilities fall short of those of the mind. Therefore human mind possesses some ability that lets it make mathematics, which machines lack.

Gödel also believed that the mind is cognitively more able than machines. He was of the opinion that the process of analyzing basic mathematical notions, leading to establishing new, more perfect axioms of infinity (in ZFC), is the evidence for our progress and superiority upon the machines. He claimed:

In the systematic establishment of the axioms of mathematics, new axioms, which do not follow by formal logic from those previously established, again and again become evident. It is not at all excluded by the negative results mentioned earlier [the incompleteness results] that nevertheless every clearly posed mathematical yes-or-no question is solvable in this way. For it is just this becoming evident of more and more new axioms on the basis of the meaning of the primitive notions that a machine cannot imitate. (Gödel, 1995, p. 385)

This conviction — that every mathematical yes-or-no question can be answered — Gödel called ‘rationalistic optimism’. And though he openly subscribed to it, he was careful enough to spot that his Incompleteness Theorem (along with Turing’s work) do not necessarily imply that humans are and always will stand over and above the machines.

For who can say that we ourselves are not machines, only more capable than (the very limited) Turing machines? Maybe there is a Gödel sentence for us? Who can prove the consistency of the human mind? And even if the mind surpasses the machine, maybe there is still something unknowable to it? Gödel expressed the scope of possibilities in what is today known as ‘Gödel’s Disjunction’:

Either the human mind surpasses all machines (to be more precise: it can decide more number theoretical questions than any machine) or else there exist number theoretical questions undecidable for the human mind.

Each possibility is captivating: if human’s mental capabilities go beyond those of the machine, than there must be something unconstructible by the IT engineers in our brains. In other words, the mind cannot be mapped into a computer. Consequently, our AI dreams get shot to the curb. This option inspires to ask about the nature of consciousness. Maybe the reason why it is impossible to structure it into the machine is because it is immaterial, one might wonder.

The second option seems to be even more unrealistic. If there are certain mathematical questions that have an answer, which is not accessible for the human mind, this implies that we can talk about some Platonic “Mathematics” — objects (theorems) independent of our thinking, yet objective and unchanging. This seems to push us towards some philosophical view against our will!

There is also a third option: although the Disjunction is stated in the “either-or” form, both possibilities do not seem to exclude each other. Both could be the case. One can think of some kind of hierarchy of epistemic capabilities that begins with a Turing machine, then goes to the human mind, and then reaches the realm inaccessible to the latter. This option introduces a lot of ontological differences and hence is quite uneconomic. Still we cannot exclude it.

But the issue is even more problematic. It must be highlighted that the second disjunct does not immediately mean that the answers that are inaccessible for the mind even exist. That is, it still could be the case that there is no “Mathematics”, and that maths is purely a fruit of free activity of human mind (As Brouwer would put it): if there are no answers for humans, then there are no answers period. This path leads us towards an even deeper question: can we somehow study whether mathematical problems have answers in abstraction from “practical” task of solving them one by one? Maybe the concepts used in mathematics have some inherent form which causes the “well-stated-ness” or unsensicality of a given question? Maybe there is some deep mathematical grammar, which could show us not only that “there is no general procedure of deciding an arbitrary problem”, but why that is so?

If we wanted, we could problematize the initial case even further. Since it is not disproved that the mind is in fact a machine (only not a finite Turing machine), one might hypothesize that there could exist some “super-machine” that was able to see our incompleteness. This would turn the initial philosophical conclusion from the Theorem upside down.

Turing believed that his and Gödel’s results entail that the abstracted human mind will always be mathematically more capable than one human-built computer. But the question whether it would surpass the totality of all computing machines when they “join forces”, is not so obvious. And Turing also saw that option, when he said in his 1951 BBC radio broadcast that it is still not excluded that machines cannot be intelligent and that we could not learn anything about our own minds from the study of machines.

Gödel, on the other hand, believed (but did not know) that the mind infinitely surpasses the machine. He (mistakenly) took Turing’s reasoning in his seminal 1936 paper to argue that the mind could be equated with the machine. He called this claim a “philosophical fallacy”. Later in conversation with Hao Wang, he said that

“Mind, in its use, is not static, but constantly developing”

And machines cannot develop in this way. This process of development is something non-algorithmic, non-mechanical, untraceable for machine.

And so, the new discourse between the Mechanism and Anti-mechanism began with the statements of two fathers of the results that laid theoretical foundations for computer science.

Of course, there is a lot to clarify in the discussion. The notion of the “human mind”, the “abstracted mind” and also of the “machine” still need some explanations (although serious developments in the automata theory and theoretical linguistics seem to give some first results). Not to mention Turing’s concepts of “ingenuity” and “intuition”, and Gödel’s “mathematical intuition” that play a vital role in the debate, but are still very vague.

We go deeper and deeper into the forrest of questions. Some time ago the Incompleteness Theorem seemed to me as a decisive argument that closed a number of discussions. But lately I tend to see the opposite: how many questions it inspires and how philosophically fertile this artwork is.

Reading List

Gödel, K. (1995) “The modern development in the foundations of mathematics in the light of philosophy” in: Collected Works, Vol. III: Unpublished Essays and Lectures, Oxford Univ. Press.

Goldstein, R. (2005) Incompleteness. The Proof and Paradox of Kurt Gödel, W. W. Norton & Company, Inc.

Turing, A. (1936) “On computable numbers, with an application to the Enscheidungsproblem” in: Proceedings of the London Mathematical Society. 42 (1), pp. 230– 265.