The Touring Machine – spoken text

The text below is the spoken part of the composition The Touring Machine by Deborah Edwards, and was first performed on 11 May 2013. The text is extracted from an extremely important publication by the British mathematician Alan Turing in 1936. This was entitled ‘ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM’ and described the operation of a computing machine that became known as the Turing Machine. This machine is a conceptually simple computer that can emulate all modern computers; in effect, anything that can be calculated on these can be calculated by a Turing machine. In addition, Turing applied his conceptual machine to the ‘Entscheidungsproblem‘, which essentially posed the question as to whether it was possible to devise an algorithm that, coupled with the axioms of mathematics, could be applied to prove or disprove any arbitrary mathematical theorem. In other words, whether it was possible to construct a computer that could mechanically solve any mathematical problem put to it, and thus presumably make mathematicians largely redundant. Turing showed that such a machine is impossible in principle, and his result can be seen as an extension of Godel’s famous incompleteness theorem a few years earlier. The full text of Turing’s paper can be viewed here.

The “computable” numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means. Although the subject of this paper is ostensibly the computable numbers, it is almost equally easy to define and investigate computable functions of an integral variable or a real or computable variable, computable predicates, and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique. I hope shortly to give an account of the relations of the computable numbers, functions, and so forth to one another. This will include a development of the theory of functions of a real variable expressed in terms of computable numbers. According to my definition, a number is computable if its decimal can be written down by a machine.

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 to qn; 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 r-th symbol 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 (r). This pair qn (r) will be called the ”configuration”: thus the configuration determines the possible behaviour of the machine.

In some of the configurations in which the scanned square is blank (i.e. bears no symbol) the machine writes 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 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 be these 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.

Automatic machines

If at each stage the motion of a machine is completely determined by the configuration, we shall call the machine an “automatic machine” (or a-machine).

For some purposes we might use machines (choice machines or a-machines) whose motion is only partially determined by the configuration. When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems. In this paper I deal only with automatic machines.

Computing machines

If an a-machine prints two kinds of symbols, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine. If the machine is supplied with a blank tape and set in motion, starting from the correct initial m-configuration, the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine.
At any stage of the motion of the machine, the number of the scanned square, the complete sequence of all symbols on the tape, and the m-configuration will be said to describe the complete configuration at that stage. The changes of the machine and tape between successive complete configurations will be called the moves of the machine.