What is a Turing machine?

A Turing machine $M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$ is given by the following data

• A finite set $Q$ of states,

• A finite set $\Sigma$ of symbols (the alphabet),

• A finite set $\Gamma$ of tape symbols s.t. $\Sigma\subseteq\Gamma$. This is the case because we use the tape also for the input.

• A transition function
  $$\delta\in Q\times \Gamma \to \{\textrm{stop}\} \cup Q\times\Gamma\times\{\textrm{L},\textrm{R}\}$$

  The transition function defines how the function behaves if is in state $q$ and the symbol on the tape is $x$. If $\delta(q,x)=\textrm{stop}$ then the machine stops otherwise if $\delta(q,x)=(q',y,d)$ the machines gets into state $q'$, writes $y$ on the tape (replacing $x$) and moves left if $d=\textrm{L}$ or right, if $d=\textrm{R}$

• An initial state $q_0 \in Q$,

• The blank symbol $B\in\Gamma$ but $B\notin\Sigma$. In the beginning only a finite section of the tape containing the input is not blank.

• A set of final states $F\subseteq Q$.

In the course text the transition function is defined without the stop option as $\delta\in Q\times \Gamma \to \{\textrm{stop}\} Q\times\Gamma\times\{\textrm{L},\textrm{R}\}$. However they allow $\delta$ to be undefined which correspond to our function returning stop.

This defines deterministic Turing machines, for non-deterministic TMs we change the transition function to

$$\delta\in \ Q\times \Gamma \to {\cal P}(Q\times\Gamma\times\{\textrm{L},\textrm{R}\})$$

Here stop corresponds to $\delta$ returning an empty set. As for finite automata (and unlike for PDAs) there is no difference in the strength of deterministic or non-deterministic TMs.

As for PDAs we define instantaneous descriptions $\textrm{ID}$ for Turing machines. We have $\textrm{ID}=\Gamma^*\times Q \times \Gamma^*$ where $(\gamma_l,q,\gamma_r)\in \textrm{ID}$ means that the TM is in state $Q$ and left from the head the non-blank part of the tape is $\gamma_l$ and starting with the head itself and all the non-blank symbols to the right is $\gamma_r$.

We define the next state relation $\vdash_M$ similar as for PDAs:

1. $(\gamma_l,q,x\gamma_r) \vdash_M (\gamma_l y,q',\gamma_r)$ if $\delta(q,x)=(q',y,R)$
2. $(\gamma_l z,q,x\gamma_r) \vdash_M (\gamma_l ,q',z y \gamma_r)$ if $\delta(q,x)=(q',y,L)$
3. $(\gamma_l,q,\epsilon) \vdash_M (\gamma_l y,q',\gamma_r)$ if $\delta(q,B)=(q',y,R)$
4. $(\epsilon,q,x\gamma_r) \vdash_M (\gamma_l ,q',B y \gamma_r)$ if $\delta(q,x)=(q',y,L)$

The cases 3. and 4. are only needed to deal with the situation if we have reached the end of the (non-blank part of) the tape.

We say that a TM $M$ accepts a word if it goes into an accepting state, i.e. the language of a TM is defined as

$$L(M) = \{ w\in\Sigma^* \mid (\epsilon,q_0,w) \vdash_M^* (\gamma_l,q',\gamma_r) \wedge q'\in F \}$$

I.e. the TM stops automatically if it goes into an accepting state. However, it may also stop in a non-accepting state if $\delta$ returns stop - in this case the word is rejected.

A TM $M$ decides a language if it accepts it and it never loops (in the negative case).

To illustrate this we define a TM $M$ which accepts the language $L=\{a^nb^nc^n \mid n\in\mathbb{N}\}$ -- this is a language which cannot be recognized by a PDA or be defined by a CFG.

We define $M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$ by

• $Q=\{q_0,q_1,q_2,q_3,q_4,q_5,q_6\}$

• $\Sigma = \{ \texttt{a},\texttt{b},\textrm{c} \}$

• $\Gamma = \Sigma \cup \{ X,Y,Z,\verb*+ +\}$

• $\delta$ is given by
  

  $$\ \delta(q_0,\verb*+ +) = (\verb*+ +,q_6,\textrm{R})$$

  $$\ \delta(q_0,\texttt{a}) = (X,q_1,\textrm{R})$$

  $$\ \delta(q_1,\texttt{a}) = (a,q_1,\textrm{R})$$

  $$\ \delta(q_1,X) = (X,q_1,\textrm{R})$$

  $$\ \delta(q_1,\texttt{b}) = (Y,q_2,\textrm{R})$$

  $$\ \delta(q_2,\texttt{b}) = (\texttt{b},q_2,\textrm{R})$$

  $$\ \delta(q_2,Y) = (Y,q_2,\textrm{R})$$

  $$\ \delta(q_2,\texttt{c}) = (Z,q_3,\textrm{R})$$

  $$\ \delta(q_3,\verb*+ +) = (\verb*+ +,q_4,\textrm{L})$$

  $$\ \delta(q_3,\texttt{c}) = (\texttt{c},q_5,\textrm{L})$$

  $$\delta(q_4,Z) = (Z,q_4,\textrm{L})$$

  $$\delta(q_4,\texttt{b}) = (\texttt{b},q_4,\textrm{L})$$

  $$\delta(q_4,Y) = (Y,q_4,\textrm{L})$$

  $$\delta(q_4,\texttt{a}) = (\texttt{a},q_4,\textrm{L})$$

  $$\delta(q_4,X) = (X,q_0,\textrm{R})$$

  $$\delta(q_5,Z) = (Z,q_5,\textrm{L})$$

  $$\delta(q_5,Y) = (Y,q_4,\textrm{L})$$

  $$\delta(q_5,X) = (X,q_6,\textrm{R})$$

  $$\delta(q,x) = \textrm{stop} \qquad \textrm{everywhere else}$$

  
  

• $q_0 = q_0$

• $B = \verb*+ +$

• $F = \{q_6\}$

The machine replaces an a by $X$ ($q_0$) and then looks for the first b replaces it by $Y$ ($q_1$) and looks for the first c and replaces it by a $Z$ ($q_2$). If there are more cs left it moves left to the next a ($q_4$) and repeats the cycle. Otherwise it checks whether there are no as and bs left ($q_5$) and if so goes in an accepting state ($q_6$).

E.g. consider the sequence of IDs on aabbcc:

$$\ (\epsilon,q_0,\texttt{aabbcc}) \ \vdash (\texttt{X},q_1,\texttt{abbcc})$$

$$ \vdash (\texttt{Xa},q_1,\texttt{bbcc})$$

$$ \vdash (\texttt{XaY},q_2,\texttt{bcc})$$

$$ \vdash (\texttt{XaYb},q_2,\texttt{cc})$$

$$ \vdash (\texttt{XaYbZ},q_3,\texttt{c})$$

$$ \vdash (\texttt{XaYb},q_4,\texttt{Zc})$$

$$ \vdash (\texttt{XaY},q_4,\texttt{bZc})$$

$$ \vdash (\texttt{Xa},q_4,\texttt{YbZc})$$

$$\vdash (\texttt{X},q_4,\texttt{aYbZc})$$

$$\vdash (\epsilon,q_4,\texttt{XaYbZc})$$

$$\vdash (\texttt{X},q_0,\texttt{aYbZc})$$

$$\vdash (\texttt{XX},q_1,\texttt{YbZc})$$

$$\vdash (\texttt{XXY},q_1,\texttt{bZc})$$

$$\vdash (\texttt{XXYY},q_2,\texttt{Zc})$$

$$\vdash (\texttt{XXYYZ},q_2,\texttt{c})$$

$$\vdash (\texttt{XXYYZZ},q_2,\epsilon)$$

$$\vdash (\texttt{XXYYZ},q_5,\texttt{Z})$$

$$\vdash (\texttt{XXYY},q_5,\texttt{ZZ})$$

$$\vdash (\texttt{XXY},q_5,\texttt{YZZ})$$

$$\vdash (\texttt{XX},q_5,\texttt{YYZZ})$$

$$\vdash (\texttt{X},q_5,\texttt{XYYZZ})$$

$$\vdash (\epsilon,q_6,\texttt{XXYYZZ})$$

We see that $M$ accepts aabbcc. Since $M$ never loops it does actually decide $L$.