More precisely, a Turing machine consists of:
1. A tape divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol( here written as ' 0 ') and one or more other symbols. The tape is assumed to be arbitrarily extendable to the left and to the right, i. e., the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written to before are assumed to be filled with the blank symbol. In some models the tape has a left end marked with a special symbol; the tape extends or is indefinitely extensible to the right.
2. A head that can read and write symbols on the tape and move the tape left and right one( and only one) cell at a time. In some models the head moves and the tape is stationary.
3. A state register that stores the state of the Turing machine, one of finitely many. There is one special start state with which the state register is initialized. These states, writes Turing, replace the " state of mind " a person performing computations would ordinarily be in.
4. A finite table( occasionally called an action table or transition function) of instructions( usually quintuples [ 5-tuples ]: qiaj�qilajld k, but sometimes quadruples [ 4-tuples ]) that, given the state( qi) the machine is currently in and the symbol( aj) it is reading on the tape( symbol currently under the head) tells the machine to do the following in sequence( for the 5-tuple models): � �
Either erase or write a symbol( replacing aj with a ji), and then Move the head( which is described by d and can have values: ' L ' for one step left or ' R ' for one step right or ' N ' for staying in the same place), and then � Assume the same or a new state as prescribed( go to state q i1).
5. In the 4-tuple models, erasing or writing a symbol( a _ ji) and moving the head left or right( d k) are specified as separate instructions. Specifically, the table tells the machine to( ia) erase or write a symbol or( ib) move the head left or right, and then( ii) assume the same or a new state as prescribed, but not both actions( ia) and( ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state then the machine will halt; other models require all entries to be filled. Note that every part of the machine( i. e. its state and symbol-collections) and its actions( such as printing, erasing and tape motion) is finite, discrete and distinguishable; it is the potentially unlimited amount of tape that gives it an unbounded amount of storage space.
Cryptanalysis
During the Second World War, Turing was a leading participant in the breaking of German ciphers At Bletchley Park. The historian and wartime codebreaker Asa Briggs has said:
genius. k
You needed exceptional talent, you needed genius at Bletchley and Turing ' s was that
( 62)