Turing machine

In some models, the tape moves and the unused tape is truly blank. The instruction to be performed (q4) is shown over the scanned square.

In some models, the head moves along the stationary tape. The instruction to be performed (q₁) is shown inside the head. In this model, the "blank" tape is all 0's. The shaded squares, including the blank scanned by the head, and the squares marked 1, 1, B, and the head symbol, constitute the system state.

Turing machines, described by Alan Turing in 1936, are extremely basic abstract symbol-manipulating devices. Despite their simplicity, they can be adapted to simulate the logic of any computer that could possibly be constructed. Though intended to be technically feasible to build, Turing machines were not meant to be a practical computing technology, but a thought experiment about the limits of mechanical computation. Studying their abstract properties yields many insights into computer science and complexity theory.

2.   A Turing machine consists of:

1. A tape which is divided into adjacent cells. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as 'B') 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. The symbols are sometimes referred to as colors.
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 table of instructions that, given the state the machine is currently in, and the symbol it is reading on the tape tells the machine to do the following in sequence (for the 5-tuple models):
   
   1. either erase or write a symbol;
   2. move the head ('L' for one step left or 'R' for one step right)
   3. assume the same or a new state as prescribed.
   In the 4-tuple models, the table tells the machine to (ia) erase or to 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. Also 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.

4. A state register that stores the state of the Turing table. The number of different states is always finite and there is one special start state with which the state register is initialized. Turing defined this as a "note of instructions" to preserve the computation of the "computer" (a person) who is working in a "desultory manner".

3.   Note that every part of the machine, i.e. (1) its state and symbol-collections; and (2) its actions (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.  more... at Wikipedia