Turing first described the Turing machine in an article published in 1936, ‘On Computable Numbers, with an Application to the Entscheidungsproblem’.
| A Turing machine |
The read/write head is programmable. It is be helpful to think of the operation of programming as consisting of altering the head’s internal wiring by means of a plugboard arrangement. To compute with the device, you program it, inscribe the input on the tape (in binary or decimal code, say), place the head over the square containing the leftmost input symbol, and set the machine in motion. Once the computation is completed, the machine will come to a halt with the head positioned over the square containing the leftmost symbol of the output (or elsewhere if so programmed).
The head and the tape
A Turing machine is an idealised computing device consisting of a read/write head (or ‘scanner’) with a paper tape passing through it. The tape is divided into squares, each square bearing a single symbol–‘0’ or ‘1’, for example. This tape is the machine’s general purpose storage medium, serving both as the vehicle for input and output and as a working memory for storing the results of intermediate steps of the computation.
States
The head contains a subdevice that I call the indicator. This is a second form of working memory. The indicator can be set to any one of a number of ‘positions’. In Turing machine jargon, the position of the indicator at any time is called the state of the machine at that time. To give a simple example of the indicator’s function, it may be used to keep track of whether the symbol last encountered was ‘0’ or ‘1’. If ‘0’, the indicator is set to its first position, and if ‘1’, to its second position.
Atomic operations
There are just six types of fundamental operation that a Turing machine performs in the course of a computation. It can:
- read (i.e. identify) the symbol currently under the head
- write a symbol on the square currently under the head (after first deleting the symbol already written there, if any)
- move the tape left one square
- move the tape right one square
- change state
- halt.
The instruction table
A program or ‘instruction table’ for a Turing machine is a finite collection of instructions, each calling for certain atomic operations to be performed if certain conditions are met. Every instruction is of the form:
If the current state is n and the symbol currently under the head is x, then write y on the square currently under the head [y may be identical to x], go into state m [m may be n], and – – – .
In place of – – – may be written either ‘move left one square’ or ‘move right one square’ or ‘halt’.
An example
The machine in this example starts work with a blank tape. The tape is endless. The problem is to set up the machine so that if the scanner is positioned over any square and the machine is set in motion, it will print alternating binary digits on its tape, 0 1 0 1 0 1…, working to the right from its starting place, and leaving a blank square in between each digit.
In order to do its work the machine makes use of four states, labelled ‘a‘, ‘b‘, ‘c‘ and ‘d‘. The machine is in state a when it starts work.
The table of instructions for this machine is as follows.The top line of the table reads: if you are in state a and the square you are scanning is blank then print 0 on the scanned square, move right one square, and go into state b.
| state | scanned symbol | move | next state | |
| a | blank | 0 | R | b |
| b | blank | R | c | |
| c | blank | 1 | R | d |
| d | blank | R | a |
A machine acting in accordance with this table of instructions toils endlessly on, printing the desired sequence of digits and leaving alternate squares blank.
