[First published in GOTOXO as Python-XO: Alan Turing’s Definition of a Computing Machine on December 20, 2007.]

In a previous post in this series about the Python programming language and the XO laptop, XO-Python: On Von Neumann’s First Program, I made mention of the work of John von Neumann in 1945 in which he wrote one of the first known programs in a form close to that used in today’s programming languages.

In this post we look at the work of another of the greatest mathematicians of the twentieth century, Alan M. Turing. One of the fundamental papers in the history of mathematics and computing is Turing’s ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM, published in 1936.

Turing asked himself the question, “What does it mean to compute something,” especially in a mathematical sense. Towards that end he defined the notion of a “computing machine” as follows (with my emphasis added in bold):

We have said that the computable numbers are those whose decimals are calculable by finite means. This requires rather more explicit definition. No real attempt will be made to justify the definitions given until we reach §9. For the present I shall only say that the justification lies in the fact that the human memory is necessarily limited.

We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions q1, q2, …, qR which will be called “m-configurations”. The machine is supplied with a “tape”, (the analogue of paper) running through it, and divided into sections (called “squares”) each capable of bearing a “symbol”. At any moment there is just one square, say the r-th, bearing the symbol S(r) which is “in the machine”. We may call this square the

“scanned square”. The symbol on the scanned square may be called the“scanned symbol”. The “scanned symbol” is the only one of which the machine is, so to speak, “directly aware”. However, by altering its m-configuration the machine can effectively remember some of the symbols which it has “seen” (scanned) previously. The possible behaviour of the machine at any moment is determined by the m-configuration qn and the scanned symbol S(r). This pair qn, S(r) will be called the “configuration”: thus the configuration determines the possible behaviour of the machine. In some of the configurations in whichthe scanned squareis blank (i.e. bears no symbol) the machinewrites down a new symbol on the scanned square: in other configurations it erases the scanned symbol. The machine may also change the square which is being scanned, but only by shifting it one place to right or left. In addition to any of these operations the m-configuration may be changed. Some of the symbols written down {232} will form the sequence of figures which is the decimal of the real number which is being computed. The others are just rough notes to “assist the memory”. It will only bethese rough notes which will be liable to erasure.It is my contention that these operations include all those which are used in the computation of a number. The defence of this contention will be easier when the theory of the machines is familiar to the reader. In the next section I therefore proceed with the development of the theory and assume that it is understood what is meant by “machine”, “tape”, “scanned”, etc.

Turing went on to prove some of the major results in mathematics in the last century. By defining in abstract form a “computing machine” he was able to characterize the kinds of things that could be computed by this machine. He then proved there were some things that could not be computed by this kind of machine, and in doing so he demonstrated there were fundamental limits to what could be computed. While these computers were universal in power, they were not universal in reach. There were, and are, some questions that cannot be answered by any computer, no matter how powerful.

Moreover, while his machine was abstract, all the computers we use today — the creation of scientists and engineers — are but practical instances of this abstract computing machine. Our real computers can compute everything that can be computed by what is known as “Turing’s machine,” and they can compute nothing that cannot be computed by Turing’s machine. For example, the XO can compute anything a desktop can compute. It may take longer, much longer, yet the XO has, at a fundamental level, the same power to unlock the secrets of the universe as does the desktop, or the world’s largest supercomputer.

All computers are fundamentally equivalent. Some are smaller, others are bigger. Some are faster, others are slower. Yet all do the same thing. It is a matter of degree, not a qualitative difference.

I wrote in a previous post, Python-XO: The Farmer in the Dell that programming is just a form of writing. The key point I wish to make here , especially in understanding the importance of Turing’s ideas to the nature of programming itself, is that computing itself is but a combination of reading and writing. This is why I emphasized “scanned symbol,” for this is the reading part. The writing part can be found in “writes down a new symbol” and “liable to erasure.”

Computing is a form of writing, as is a shopping list, a novel, or a computer program written in Python that instructs the computer how to do its reading and writing.