“All Cretans are liars,” said the Cretan Epimenides. So that statement must also be a lie, in which case he would mean that Cretans are not liars, and therefore the statement must be true. So is the statement by Epimenides true or false? This represents a problem that many clever minds have addressed in the history of the algorithm. Because statements which make a statement about themselves inevitably create insoluble contradictions.
The foundations of theoretical information science
This was also recognised by Leibniz’s pupil Gottlob Frege, who wanted to establish a firm foundation for mathematics with the help of set theory. He overturned the scholastic rigidity of logic in his day, modernised it completely and, in 1879, with his work “Concept notation. A formulaic language of pure thought, modelled on that of arithmetic”, he also laid the foundations for modern theoretical information science. “Without many of his findings, the construction of today’s programming languages would not have been possible,” writes Dr Manuel Bachmann, a researcher at the University of Basel and lecturer at the University of Lucerne, in his book “The triumph of the algorithm – how the idea of software was invented”.
That is because the principle of logical programming has its origins in the automated proving of mathematical statements. “Frege built an accessible temple for the universal algorithm, whereas Leibniz had not been able to progress beyond the construction of a mighty monument of thought,” says Bachmann. Frege thereby succeeded in expressing his teacher’s idea with an unprecedented degree of precision, yet at the same time he opened the door to a new ambiguity. In 1902, 23 years after the publication of Frege’s doctoral thesis, he received a letter from his young mathematician colleague Bertrand Russell, pointing out an insoluble contradiction in his theory. Gottlob Frege was grief-stricken and in the end gave up his work on set theory.
The dream of freedom from contradictions
In the 1920s, people wanted to eliminate such irritations from the world once and for all. David Hilbert, at that time probably the most influential mathematician in the world, declared that he had created the “Hilbert program”: he claimed that all of mathematics could be reduced to a clear and simple small number of axioms – clear-cut, immediately understandable basic principles. He also intended to prove that it is possible to decide unambiguously whether any statement is true or false by using mathematical methods.
However, this dream of a complete and consistent mathematical system was destroyed in 1931 by the Austrian mathematician and logician Kurt Gödel. He was able to demonstrate that, in any mathematical system, statements can be constructed which, although true, cannot be proven by the axioms. Gödel’s key insight was that these statements about numbers can themselves be encoded as a number. You simply have to assign appropriate numbers to the various symbols used in logic.
Digital encoding of any content
From today’s perspective, that is nothing special – in the digital age, we are used to it being possible to encode any content as a number: our holiday photos are saved as a sequence of numbers on our hard disk, as is our favourite music on our iPhone. In the same way, a number can be assigned to any mathematical statement – the so-called “Gödel number”, which the Austrian invented a decade before the first computers.
