Chris Bernhardt - Turing’s Vision: The Birth of Computer Science

Several biographies of his life have been published. He has been portrayed on stage by Derek Jacobi and in film by Benedict Cumberbatch. Alan Turing, if not famous, is certainly well known. Many people now know that his code breaking work during World War II played a pivotal role in the defeat of Germany. They know of his tragic death by cyanide, and perhaps of the test he devised for determining whether computers can think. Slightly less well known is the fact that the highest award in computer science is the ACM A.M. Turing Award. This award, often called the Nobel Prize in computing, along with a million dollars, is given annually by the Association for Computing Machinery for outstanding contributions to computer science. The ACM named the award after Turing because he is considered as one of the founders of computer science. But why? What did he do to help found computer science? The answer is that he wrote a remarkable paper in 1936, when he was just twenty four years old. This paper is Turings most important intellectual contribution. However, this paper and its groundbreaking ideas are not widely known. This book is about that paper.

The paper has the rather uninviting title, On Computable Numbers, with an Application to the Entscheidungsproblem. But dont be discouraged by the title, because it contains a wealth of elegant and powerful results. It also contains some remarkably beautiful proofs. Turing wants to show that a leading mathematicians view of mathematics is wrong. To do this he needs to study computation: What exactly is computation? How can we define it? Are there problems that cannot be solved by computation? He answers these questions with dazzling skill and creativity.

Turing thinks carefully about how humans perform computations. He realizes that any computation can be broken down to a sequence of simple steps. Then he constructs theoretical machines capable of performing each of these steps. These machines, which we now call Turing machines, are capable of doing any computation.the development of modern computers. Finally, he proves that there are certain problems that are beyond any computers power to solve.

Turing machines are theoretical models of our modern computers. Everything that can be computed on a computer can be computed by a Turing machine, so his paper is not just of historical interest; it tells us about what can and cannot be computed by any computer. It tells us that there are limitations to computation, and that there are simple questions that at first glance look straightforward, but are beyond the power of any computer to answer correctly.

The ideas contained in the paper are now taught at the undergraduate level, typically in a course called Theory of Computation. However, most university students dont take the course and so dont come across Turings work. In general, a very small proportion of the population knows what Turing did in this paper. This is a pity considering that the work both contains some extraordinary ideas and is relevant to our modern life.

General relativity and quantum mechanics were also both developed during the first half of the twentieth century. Most people have an idea, if rather hazy, of what these theories say. Part of the difficulty in really understanding these two theories is that they are based on sophisticated mathematics. This is not the case with Turings work. As Marvin Minsky writes, The sheer simplicity of the theorys foundation and extraordinarily short path from this foundation to its logical and surprising conclusions give the theory a mathematical beauty that alone guarantees it a permanent place in computer theory.

The aim of this book is to do exactly what Minsky describes. We begin with the foundations and build to Turings surprising conclusions, but we also try to place Turings work in context. To do this, some of the history that lead up to Turings paper and some of the history that followed afterwards is given.

There have been many people with many views of computation, and there is no right or wrong view. Different views can reveal remarkably different vistas. We will pause along the way to look at some of these. In particular, one completely different way of looking at computation was developed by the Princeton logician Alonzo Church. Both Church and Turing were working to give an answer to a challenge posed by David Hilbert. Both came to the same conclusion, that the implicit assumption that Hilbert was making was wrong, but Church published the result first. Turing was still working on his paper when he discovered and read Churchs paper he must have been bitterly disappointed to know that someone else had reached the same conclusion and beaten him to publication. However, they had tackled the problem in different ways, and their proofs were substantially different. Turings argument was remarkably simple and elegant. His paper was not published for the result, but for the proof of the result.

Mathematicians often describe proofs in terms of beauty. When doing mathematics there is an aesthetic that guides. At times you have a proof, but feel that it is clumsy and that there must be a better one that needs to be found. This is what the Hungarian mathematician Paul Erds was referring to when he talked about The Book. According to Erds, there is a book in which God had written down all the shortest, most beautiful proofs. Erds famously said You dont have to believe in God, but you should believe in The Book. Turings proofs, along with those of Gdel and Georg Cantor on which they are based, are definitely in The Book.

This book is for the reader who wants to understand these ideas. We start from the beginning and build carefully. The reader doesnt have to know much mathematics high school provides enough but it does require some mathematical aptitude and also a little work. It needs to be read carefully, and some sections may need to be re-read. This is to be expected since Turing is not saying trivial things about computation, but saying deep and nonintuitive things. That said, many people find these ideas quite fascinating and the work rewarding.