At the end of the 19th century, human knowledge experienced a moment of turmoil. The industrial revolution had completely changed life in Western countries and science and engineering had become indispensable tools for the development of these societies. Mathematics was the language on which all these advances were sustained; it was becoming more and more precise and sophisticated, and its potential seemed to be endless. However, in the last decades of the century, serious doubts began to emerge within this field, many of them related to an elusive concept that scientists had been shunning for centuries: infinity.
In 1874, the German mathematician Georg Cantor awoke the beast and certain paradoxes appeared that turned out to be a big problem. The hitherto unshakeable science of mathematics began to falter. Thus, at the beginning of the 20th century, the so-called “crisis of fundamentals” broke out, which would lead to a terrible conclusion: mathematics was not infallible. Two young mathematicians, Kurt Gödel and Alan Turing, were responsible for demonstrating, among others, those limitations.
A few years earlier, the foundational crisis had divided the scientific community into several factions. One of them, the so-called formalists, was convinced that everything was achievable through mathematics by dedicating enough time. David Hilbert, a mathematician of tremendous reputation who championed the movement, summed it up with a phrase: “We must know. We will know.” They aspired to re-establish the bases (or axioms) of mathematics to avoid the paradoxes that arose, derived, surely, from an error or a lack of precision in the approaches.
Consistent, finite and complete
This mission, which was called the Hilbert Program, proposed a mathematical view from a higher level to prove that well-defined axiomatic systems had three properties that would make them infallible. In the first place, they were consistent, that is, they did not produce contradictions (they did not permit proving at the same time that an affirmation was true and false). They were also finite, so that the proofs could be carried out following a sequence of logical steps, algorithmically, and ending at some point. And finally, they were complete, or what is the same, for each statement of the system it could be shown either that it was true or that it was false.
In 1930, after years of intellectual disputes, a mathematical congress was organized in the city of Könisberg, the hometown of Hilbert. The goal was to make peace between the two sides and thus work together towards the conclusion of the program. In the closing discussions, a young Austrian mathematician gathered his courage and raised his hand to speak. Under the watchful eye of those great sages, Kurt Gödel (April 28, 1906 – January 14, 1978) made a devastating statement: he was about to complete a proof that ended the discussion, as he formally proved that no system could be both consistent, recursive and complete, that is, the Hilbert program was impossible to complete.
Just one year later, he published the article On Formally Undecidable Propositions of Principia Mathematica and Related Systems. In that work Gödel proved, in a complex and tremendously thorough manner, his First Incompleteness Theorem, which put an end to the Hilbert program. He corroborated that, whatever the definite system, if it is constructed in such a way that contradictions do not exist, there will be statements in it that can never be proven either false or true. Gödel’s proof marked a turning point in the history of mathematics.
The universal machine
One of those responsible for continuing with the legacy of Gödel was the English mathematician Alan Turing (June 23, 1912 – June 7, 1954). Although nowadays he is recognised mainly for his collaborations in the Second World War deciphering the Nazi messages encoded with the “Enigma” machine, years before he had published the article that would really change profoundly not only mathematics, but the whole society. Using reasoning with certain similarities to Gödel’s, Turing solved the so-called Entscheidungsproblem, or “decision problem.” It states that, in any system, it is not always possible to determine (with a finite number of steps) whether a problem chosen at random has or doesn’t have a solution.
In other words, we know that there are problems that cannot be solved (thanks to Gödel), and we cannot know in advance what they are (added Turing). To develop the proof of his theorem, Turing imagined a revolutionary concept: the universal machine, on which he bases all his proof. This was a simple device consisting of an infinite paper tape divided into squares, a head that can read and overwrite symbols in the boxes—and also move the tape to the right or left—and a series of instructions and starting states that configured the “program” of the machine. In addition, Turing showed that this simple mechanism, or a set of them, could solve any presented algorithmic task. It could add, subtract, multiply… and do any other task based on a repetition of steps, however complex it may be.
This abstract idea may seem a little trivial, but it is the essence of the functioning of the device on which you are reading this article right now. Indeed, any computer (and smartphone) is nothing more than a complex system that serves to apply in the real world a group of Turing machines put to work. Thus, the apparent barrier that Gödel had discovered, not only failed to limit the potential of mathematics, but it helped to conceptualise the machine that has led to humanity surpassing more limits than any other.
Comments on this publication