Turing machine tape The tape head of the Turing machine scans the tape one cell at a time. We refer to the cell being scanned as the active cell and the symbol it contains as the input symbol. At each time step, the tape head reads the input symbol, and leaves it either unchanged or overwrites it with a new symbol. At the end of each time step, the tape head moves one position to the left or right. We highlight the active cell in light yellow. In the example below, the A is replaced with an The ticker-tape X and the tape head stores the input, the moves one cell to the intermediate results, left. and the output. The tape is one arbitrarily machine long strip, divided into Turing cells. Each cell stores tape head one of a finite alphabet of symbols. In the example below, we use The control unit a 4 character alphabet is the analog version consisting of: 0, 1, A, of the CPU in modern day microprocessors. It X, and #. consists of a state tran32
sition diagram, which is a finite table of instructions that specifies exactly what action the machine takes at each step. Each state represents one of the possible configurations of the machine. Depending on its current state and input symbol, the Turing machine overwrites the input symbol with a new symbol and moves to a new state. Each transition connects one state, say ‘s’, to another state, say ‘t’, and is labeled with two symbols, say ‘A’ and ‘X’: this means that if the Turing machine is in state ‘s’ and the input symbol is ‘A’, then it overwrite the ‘A’ with an ‘X’ and transitions to state ‘t’. Each state is labeled with one of five designations: L (left), R (right), Y (yes), N (no), or H (halt). Upon entering a state, the Turing machine either moves its tape head or halts according to the state’s designation.