Right and wrong

In the play Breaking the Code, written by the British playwright Hugh Whitemore about the life of Alan Turing, there is a scene depicting the interview Dillwyn Knox gives him before recruiting him to the Bletchley Park team to break the Enigma codes.

In that scene Knox asks him to explain his theoretical work in mathematics in simple terms. Turing answers:

“It’s a technical paper in mathematical logic, but it’s also about the difficulty of telling right from wrong. People think — most people think — that in mathematics we always know what is right and what is wrong. Not so. Not any more. It’s a problem that’s occupied mathematicians for forty or fifty years. How can you tell right from wrong?”

(you can watch the full scene here)

Think about the Pinocchio paradox:

If Pinocchio says his nose will grow, and it doesn’t, he would be lying, but when Pinocchio lies his nose grows, and if his nose grows then he would be telling the truth. So what the hell is supposed to happen after Pinocchio says that sentence?

This is a restatement of the old Liar’s Paradox. The interesting thing is that this paradox plays a fundamental role in the solution of an important problem in mathematical logic, one that eventually led to the development of Turing’s ideas and his famous machine (and without it there would be no computers, no web, no blog, no Twitter, and we would not be telling this story this way).

At the beginning of the twentieth century mathematicians were trying to build the foundations of mathematics, to turn it into the most beautiful and purest of the sciences. On these foundations of solid rock the other, more complex areas of mathematics would rest, and expand. Eventually every proposition in mathematics could be declared, uniquely and crystal clear, either false or true, and whenever a mathematician proved a theorem little bells would ring in heaven and an angel would get its wings. How lovely!

One of the greatest works embodying this ideal was that of Whitehead and Russell, set down in their three-volume magnum opus Principia Mathematica.

The tremendous effort of these two thinkers, which took them years, reaches its peak when on page 379 of the first volume the proof that 1+1 = 2 is set up, and it is finally completed on page 86 of the second volume! (thank goodness)

Back then there was a great mathematician named Hilbert who posed a series of problems to his fellow mathematicians. It is suspected that after falling asleep reading the Principia he decided to have other enthusiasts summarize the three heavy volumes for him, and he posed what is known by the grandiose name of Hilbert’s second problem, which in plain terms can be translated as: “can somebody explain to me whether this s**** by Whitehead and Russell is consistent!?”*

That is, what Hilbert wanted was for some pimply thesis student to tell him whether those three bricks full of mathematical gibberish contained internal contradictions.

And good old Kurt Gödel solved the problem, and found that the answer was 42….. nooo, just kidding, the answer to Hilbert’s second problem is negative.

Gödel, considered the greatest logician of the twentieth century, whom we see in the photo out for a walk with one of his buddies, was quite a character.

The story goes that his scientist friends got him asylum in the United States to get him out of Austria and away from the Nazi regime. In time they convinced him to accept American citizenship. Rigorous as he was, he decided to carry out a logical analysis of the Constitution of the United States, and discovered that without stepping outside the constitution it was possible to establish a fascist-style dictatorship in that country (how odd, don’t you think?). Worried, he told his friends that he refused to swear allegiance to this country under those conditions, unless some changes were made to the constitution. It took some convincing, but they managed to restore his confidence and he agreed to swear loyalty to the American constitution, a prerequisite for being granted citizenship. Well, the official who was to administer the oath asked him where he was from, and on hearing his answer the clerk remarked how good it was to be in a nation where democracy protected them from the rise of a tyranny. Big mistake! On hearing this, poor Gödel jumped as if stung and started explaining that he was wrong, and that the constitution had a series of logical flaws, and at that point his friends had to step in, cover his mouth and calm him down so the ceremony could go on.

Well, before that anecdote took place, and while still a shy thesis student, Kurt Gödel proved his famous incompleteness theorems. And to do it he used a variant of the liar’s paradox. Basically what Gödel did was formulate a proposition that says “This proposition is unprovable”. If the proposition is unprovable, then it is true, and therefore the formulation of arithmetic is incomplete (because there is an unproven proposition); on the other hand, if the proposition can be proved, that is, it is false, then the formulation of the theory is inconsistent.

The interesting thing is that Gödel’s proof involves building a sort of logical machine, a rudimentary computer that writes logical statements following certain rules, which makes Gödel’s original proof long and intricate.

Today Gödel’s result covers much more than number theory and arithmetic, thanks to the precise notion of a computational algorithm introduced by Alan Turing. Nowadays Gödel’s theorem is considered applicable to every formal axiomatic system.

What matters to us, in summary, is that the work of Gödel, Turing and other logicians and mathematicians of the early twentieth century, who set out to solve these abstract fundamental problems of mathematics, led to the development of the concepts of algorithms and of automatic machines that resulted in the development of modern computing.

We will talk about Turing’s achievement, which followed Gödel’s feat, in the second-to-last article of this series.

Comments