“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 Leibnizs 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 teachers 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.

Articles on Innovation

  • From Ada to Zuse: the computer has many mothers and fathers15.03.2018.
    Articles on Innovation

    From Ada to Zuse: the computer has many mothers and fathers

    However, many more years went by before the first real mainframe computers saw the light of day, and the final breakthrough had many mothers and fathers.

  • The Polymath's Calculator15.03.2018.
    Articles on Innovation

    The polymath’s calculator

    This was what is called a pinwheel calculator for the four basic arithmetic operations, which could be used to enter up to 8-digit numbers and display up to 16-digit results.

  • Artificial intelligence15.03.2018.
    Articles on Innovation

    Screw up your eyes and examine any lack of clarity

    The only identifiable principle in the over 2000-year history of the development of computer programs is: “Screw up your eyes and examine any lack of clarity in existing ideas to see if there is any as yet unrecognised potential for making them more precise.”

  • Computer Pioneers in Switzerland15.03.2018.
    Articles on Innovation

    Computer pioneers in Switzerland

    Information science in Switzerland owes its birth and early growth primarily to the farsightedness and drive of the Professor of Mathematics, Eduard Stiefel.

  • The concept of the algorithm15.03.2018.
    Articles on Innovation

    The concept of the algorithm

    Although nowadays algorithms are primarily associated with software and computers, their origins lie much further in the past.

  • Wheel Innovation15.03.2018.
    Articles on Innovation

    Innovation doesn’t happen by chance

    Even though in the history of science there have been some spectacular discoveries made by chance from time to time – from penicillin to Teflon to Viagra – these tend to be the exception.

  • Book15.03.2018.
    Articles on Innovation

    How new things come about

    The source of innovation is “epistemic” recycling. This is a term from psychology and denotes the kind of curiosity that is directed at delivering more information to the organism and enabling it to acquire new knowledge.

  • How Software Was Born15.03.2018.
    Articles on Innovation

    How software was born

    In order to compete with the German encryption machine “Enigma”, just a few weeks after arriving at Bletchley Park Turing ordered a machine to be constructed – the hardware.