The Standard Turing Machine

How a Turing machine works

Like the queue machine, a Turing machine does not have a separate input channel besides its working storage. A $\text{TM}$ is a state machine that has a two-way infinite tape, consisting of cells that hold a single symbol. We assume that the input is already written somewhere on the tape, and a read-write head is positioned at the first symbol of the input. The rest of the cells are “preformatted” with a special symbol called a “blank,” which is not allowed to be part of the alphabet of any language.

The difference between a queue machine and a $\text{TM}$ is how the data is accessed. Each step of a $\text{TM}$'s computation reads the current cell, overwrites that cell (sometimes with the current contents, so there is no change in symbol), and then moves one cell either to the left or right. For this reason, we say that a $\text{TM}$ has unrestricted memory: we can reach any cell we want by a series of moves. Since the tape is infinite in length, $\text{TM}$s also have unlimited memory. The following $\text{TM}$ accepts the language L = \{ a^nb^nc^n \;|\; n>0 \}.

Note: We use $\square$ for blank. When drawing Turing machines by hand, it is convenient to use either $B$ or an underscore for a blank, $L$ for $\leftarrow$, and ...