An accidental blog

"If God is sovereign, then his lordship must extend over all of life, and it cannot be restricted to the walls of the church or within the Christian orbit." Abraham Kuyper Common Grace 1.1.

Friday, 17 August 2007

Turing on maths

This piece is taken from the play/ film 'Breaking the Code'. The screenplay was by Hugh Whitemore based on Alan hodges biography. Dilly Knox asks Alan Turing to explain in 'general terms' his research. This is Turing's response. It is a great summary of twentieth-century mathematics from Russell to Turing.

A few words of explanation general terms?

Well, erm, it’s about right and wrong in ... general terms...It’s a technical paper in mathematical logic. but it’s also about the difficulty of telling wrong from wrong. You see people think, that well, most most people think that in mathematics we always know what is right and wrong, not so, not anymore. It’s a problem that has occupied mathematicians for forty or fifty years.
How do you tell wright from wrong?

Bertrand Russell has written a book on it his Principia Mathematica – his idea was to break down all mathematical concepts and arguments into little pieces and then show they can be derived from pure logic. Well it didn’t quite work out that way and after many years of intensive work all he was able to show was that it was terribly difficult to do anything of the kind; but it was an important book. Important and influential it influenced both David Hilbert and and Kurt Godel. It’s rather like what physicsts call splitting the atom. As analysing the physical atom has led to a new kind of physics so the attempt to analyse these mathematical atoms has led to a new kind of mathematics.

David Hilbert took the whole thing a stage further. I don’t suppose his name means much if anything to you? Wel there you are you see, it’s the way of the world people never really seem to hear about the really great mathematicians. But Hilbert looked at the problem from a completely different angle He said that if we are to have any fundamental system for mathematics, like the one Russell was trying to work out

It must satisfy three basic requiremts: consistency, compelteness and decidability.

Now consistency means you won’t ever get a contradiction in your own system, in other words you will never be able to follow the rules of your and end up with showing 2 + 2 = 5.

Completeness means that if any statement is true there must be some way of proving it by using the rules of your system

and decidability means, well decidability means that there must exist some method, some definite procedure or test which can be applied to any given mathematical assertion and which will decide whether or not that assertion is provable.
Now Hilbert thought this was a perfectly reasonable set of requiremtns to impose.

But within a few years Kurt Godel showed that no system for mathematics could be both consistent and compete and he did this by constructing a mathematical assertion, which said in effect: This assertion cannot be proved.
Classic paradox! This assertion cannot be proved. Well, either it can or can’t
If it can be proved we have a contradiction and the system is inconsistent
If it cannot be proved then the assertion is true. But it can’t be proved, which means the system is incomplete.
Thus mathematics is either inconstent or incomplete. It’s a beautiful theorm. It’s quite beautiful. I think Godel’s theorem is the most beautiful thing I know.

The question of decidabilty was still unsettled. Hilbert thought there should be one single clearly defined method of proving whether mathematical assertions were provable. The decision problem he called it the entscheidungsproblem. In my book on computable numbers I wanted to show that no one method can work for all questions, solving mathematical problems requires an infinite supply of new ideas. It is one thing to make this claim it is a monumental task to prove it. I needed to examine the provability of mathematical assertions past present and future. How on earth was it it be done?

Eventually one word gave me a clue – people had been talking a bout a mechanical process and process that could be applied mechanically to mathematical problems, a process without requiring any human invention or ingenuity – machine; that was the crucial word. I conceived the idea of a machine. A Turing machine which would be able to scan mathematical symbols, it read them if you like it would read a mathematical assertion and then arrive at a verdict whether that assertion was provable. I was able to show that Hilbert was wrong. My idea worked.

No comments: