1 - Algorithms, Equations, and Logic

Summary

From the beginning of recorded history, people have worked with numbers using algorithms. Algorithms are processes that can be carried out by following a set of instructions in a completely mechanical manner without any need for creative thought. Until the 1930s no need was felt for a precise mathematical definition or characterization of what it means for something to be algorithmic. The need then did arise, in those years, in connection with attempts to prove that for some problems no algorithmic solution is possible. In 1935 Alan Turing considered this matter in isolation at Cambridge University. Meanwhile, in Princeton, the combined efforts of Kurt G ödel and Alonzo Church with his students Stephen Kleene and J. Barkley Rosser were brought to bear on the same topic. E.L. Post had also been thinking about these things, like Turing also in isolation, since the 1920s. Although the various formulations that were developed seemed superficially to be quite different from one another, they all turned out to be equivalent. This consensus about algorithmic processes has come to be called the Church–Turing Thesis.

Turing's conception differed from all the others in that it was formulated in terms of an abstract machine. What was striking about his characterization is his analysis that showed why even very limited fundamental operations would suffice for all algorithms if supplemented by unlimited data storage capability. Moreover, he demonstrated that a single such machine, Turing's so-called ‘Universal Machine’, could be made to carry out any algorithmic process whatever. These insights have played a key role in the development of modern all-purpose computers. But, as will become clear later, the notion of universality spills over into mathematical domains far removed from computation.

Turing began his investigation with a problem from mathematical logic, a problem, whose importance was emphasized by David Hilbert, that can be described as follows:

Find an algorithm that will determine whether a specified conclusion follows from given premises using the formal rules of logical reasoning.

By 1935 there were good reasons to believe that no such algorithm exists, and this is what Turing set out to prove. Turing succeeded by first finding an unsolvable problem in terms of his machines, specifically the problem of determining for a given such machine whether it would ever output the digit 0.