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 $R$ for $\rightarrow$.

The pattern for transitions in a $\text{TM}$ is <read>/<write>,<direction>. This machine marks each leading $a$, $b$, and $c$ with $X$, $Y$, and $Z$, respectively, on each pass through the string. We don’t need an end-of-string marker since blanks can serve that purpose. Also, to skip over a symbol, we merely write it over itself. Having no out-edges, $q_5$ is a halt state. Most of the time we don’t include a nonaccepting halt state because an invalid string will cause the machine to crash, and we consider a crash as a rejection. The trace of $aabbcc$ appears below.

Note: The brackets are not actually present on the tape. They only serve to show under which symbol the read/write head is positioned. ...

State	Tape Contents
$q_0$	$[a]abbcc$
$q_1$	$X[a]bbcc$
$q_1$	$Xa[b]bcc$
$q_2$	$XaY[b]cc$
$q_2$	$XaYb[c]c$
$q_3$	$XaY[b]Zc$
$q_3$	$Xa[Y]bZc$