Turing Machine

Turing Machine

A Turing Machine consists of a linear tape, potentially infinite in both directions, divided into cells, with each cell containing a 1 or blank $\varnothing$, and at most a finite number of cells not blank. There is a reading head which at time $t(t=1,2,3,...)$ is in one of a finite set $Q=\{q_0,...,q_n\}$ of possible states and is reading a particular cell. Depending on this state $q_i$ , and the cell content $m_j(=1or\varnothing )$, and the fixed set of instructions initially supplied with the machine, the machine either (i) stops or (ii) changes to state $q_k$ and moves the whole tape one cell to the left or one cell to the right or puts 1 into the cell it is reading or puts $\varnothing$ into the cell it is reading.