HOUSE_OVERSIGHT_015911.jpg

The Machine

Turing probably learned of the Entscheidungsproblem in a lecture given at Cambridge University by Max Newman. Newman described a new proof by Gödel showing mathematics was incomplete. The proof solved the completeness and consistency problems by turning mathematical statements into numbers and showing you could generate a logical paradox if you tried to argue for completeness and consistency at the same time. Thus, of the three original Hilbert problems, completeness, consistency and decidability, only decidability remained unanswered.

Turing spent all of 1935 and much of 1936 thinking about this question: Is mathematics intuitive, or could a machine decide mathematical questions automatically? Eventually, cycling through the Cambridge countryside one day, he stopped to rest in a field near Grantchester and in a flash of inspiration envisioned his mathematical machine. The machine was entirely imaginary but made as if from mechanical parts common in the 1930s.

The idea was to reduce the process of computing with pen and paper to its most basic level. Turing hit upon the idea of using a long ribbon of paper tape similar to the ones used in telegraph machines. A paper tape is simpler than rectangular paper as it can be handled mathematically as a single sequence of numbers – we don’t have to worry about turning the page or working in two dimensions. If you are worried that a tape is less powerful than a sheet of paper remember Cantor’s theorem: an infinite plane is the same as an infinite line. The use of a tape massively simplified the mathematics, and subsequently many early computers used tapes, as they were easy to handle in practice as well as in theory.

HOUSE_OVERSIGHT_015911