1 of 1

Write now Article Tools

Page 2 of 4

it could be decided whether any given mathematical assertion was provable?" [AH-ATB2]. What Hilbert was getting at wasn't a method for finding a particular proof but a method for deciding if any proof existed at all.

The dream of finding such a method was partly shattered by Kurt Gdel who demonstrated that there existed mathematical assertions of the type found in Principia Mathematica which were not provable by the methods of Principia Mathematica and systems like it. What Gdel effectively demonstrated was that mathematicians couldn't find a method of proving every statement of mathematics, even if it was known to be true or false. Fortunately for us, the sorts of things that can't be decided by such systems aren't found in the everyday application of mathematics. However, Hilbert's proposition was not destroyed: Gdel had only shown that any method, if it existed, would be incomplete; he hadn't demonstrated that the method did not exist.

This was the situation in 1935 when a young, mildly eccentric, mathematics don at King's College, Cambridge attended a lecture on topology and heard about Hilbert's decidability problem. His name was Alan Turing and he was just 23 years old.

What Turing did was to show how the method could be constructed. More importantly he demonstrated that a method could always be constructed. That the method couldn't decide everything (as Gdel has shown) was immaterial. When Turing's paper, On Computable Numbers, with an application to the Entscheidungsproblem ("Entscheidungsproblem" is Hilbert's name for the decidability problem), was published in 1936, it introduced the world to the Universal Turing Machine. This was a purely theoretical machine which could be instructed to decide any mathematical problem (if such a proof existed). It didn't propose a solution to the Entscheidungsproblem, it showed how the method of deciding if a proof existed could be constructed.

The Universal Turing Machine can be imagined as a small box which moves over a paper tape reading and writing symbols on the tape. In order to decide a mathematical assertion, the problem is written onto the tape in some manner. The machine is then "let loose" on the tape. When the machine stops moving, the tape will contain the proof (or otherwise) of the assertion. If it never stops moving the assertion is unprovable (undecidable). Gdel had shown that there were some assertions for which the machine would never stop moving, but that's not the point here - for many, many assertions,

• << previous page
• 1
• 2
• 3
• 4
• next page >>

Add your voice

Know something about The legacy of Alan Turing?
We want to hear your view. Write now!