Turing Machines Configurations

Snapshot as a String

A configuration of a Turing Machine is a snapshot of the current state of the machine. It is expressed as a string.

The string has three components

the tape contents to the left of the tape-head
the current state
the tape contents to the right of the tape-head (including the current cell)

These components are shown in different colors below

Rendered by QuickLaTeX.com

The configuration of the above snapshot will be

$\begin{equation*} x_1 x_2 x_3 q x_4 x_5 x_6 \end{equation*}$

Formal Definition

A configuration of a Turing Machine is a string $x_1 \cdots x_{n} q y_1 \cdots y_m$ where

the tape contents are $x_1, \cdots x_n \cdots y_1 \cdots y_m$ . This is followed by infinite blanks $\textvisiblespace$ .
the tape-head is pointing at $y_1$
the current state is $q$

Rendered by QuickLaTeX.com

Note that after $x_m$ all the tape cells are $\textvisiblespace$ . Thus there are infinite such configurations for a given snapshot.

$\begin{align*} & x_1 \cdots x_{n} q y_1 \cdots y_m \\ & x_1 \cdots x_{n} q y_1 \cdots y_m \textvisiblespace \\ & x_1 \cdots x_{n} q y_1 \cdots y_m \textvisiblespace \textvisiblespace \\ & \vdots \end{align*}$

A configuration can thus be written as $xqy$ where $x = x_1 \cdots x_{n}$ and $y = y_1 \cdots y_m$ are the tape-contents in the red and blue region respectively.

It makes perfect sense for $x$ to be the empty string, but $y$ should have at least one symbol (the cell the tape-head is pointing to).

Right Transition

Suppose that the current configuration is $xqay$ where $x, y \in \Gamma^*$ , $a \in \Gamma$ and $q \in Q$ .

Rendered by QuickLaTeX.com

Consider the following transition $\delta(q, a) = (q', b, R)$

The configuration changes to $xbq'y$ .

Rendered by QuickLaTeX.com

This is denoted as

$\begin{equation*} xqay \vdash xbq'y \end{equation*}$

Left Transition

Suppose that the current configuration is $xcqay$ where $x, y \in \Gamma^*$ , $a,c \in \Gamma$ and $q \in Q$ .

Rendered by QuickLaTeX.com

Consider the following transition $\delta(q, a) = (q', b, L)$

The configuration changes to $xbq'y$ .

Rendered by QuickLaTeX.com

This is denoted as

$\begin{equation*} xcqay \vdash xq'cby \end{equation*}$

$c$ ensures that the tape-head is not pointing at the left end of the tape. If the configuration is $qay$ , the same transition will not move the tape-head.