Turing Machines

Definition of a Turing Machine

A Turing Machine (TM) is a device consisting of the following components:

1. A tape containing (infinite) sequence of cells.

   • The cells are indexed by their positions: 0, 1, 2, 3, $\dots$
   • Each cell can contain 0, 1, or blank.

2. A head that can perform read or write of the cells. The head can only move along the tape in order to access a specific cell.

   • The head can be instructed to move left or right along the tape.
   • The head can be instructed to write 0, 1, or blank to the cell.

3. A control logic which is a finite state machine that controls the movement and the action of the head.

    +----+----+----+----+----+----+----+
    | 0  | 1  | 1  |  0 | 0  |    | ...
    +----+----+----+----+----+----+----+
                ^
                |
                |
           +-----------+
           | control   |
           | logic     |
           +-----------+

Control Logic

The control logic is a finite state machine with states $Q$, input symbols $\Sigma=\{0, 1, a, b, \dots, \mathrm{blank}\}$.

1. The head being at a specific cell, inputs the current cell content, $X$, to the control logic.

2. The controller is at some state $q$, and the control logic is a transition function $$ \delta(q,X) = \left<p, Y, D\right>$$ where:

   • $p$ is the next state in $Q$
   • $Y$ is the new symbol to be written to the current cell, replacing the current symbol $X$.
   • $D$ is the direction to move the head.

3. The controller starts at a specific initial state $q_0$.

4. One or more states are final or accepting states, written $F\subseteq Q$.

   When the controller reaches any of the final states, the whole TM terminates executing.

Definition: Turing Machine

A TM is given by a tuple: $$ M = \left<Q, \Sigma, \delta, q_0, F\right>$$ where

• $Q$ is the set of states of the control logic.
• $\Sigma$ the set of symbols that can be stored on the tape. There is always the $\mathrm{blank}$ symbol to represent empty cells.
• $\delta : Q\times\Sigma \to Q\times\Sigma\times\{\mathrm{left},\mathrm{right}\}$ is the transition function.
• $q_0$ the initial state.
• $F$ are the final states.

The execution of a TM

The execution of a TM $\left<Q, \Sigma, \delta, q_0, F\right>$ can be described by the following pseudo code:

$q$ : current state
$T$ : the (infinite) tape, represented as an array
$i$ : the position of the head as an index of $T$

$q = q_0$
$i = 0$
while $q\not\in F$ {
    /* read the current symbol */
    $\sigma = T[i]$
    /* compute the next state, symbol and movement */
    $(q', \sigma', D) = \delta(q, \sigma)$

    $T[i] = \sigma'$ /* update the tape */
    $q = q'$ /* update the state */

    /* move the head */
    if $D$ is "left" {
        $i = i - 1$
    } else if $D$ is "right" {
        $i = i + 1$
    }
}

Transition of a TM

split

Figure 1: a Turing machine $M^*$

A Turing Machine can be represented by a transition diagram.

• The nodes are the states of the TM.
• Edges are the transition function.
• The labels are
  • the current symbol, followed by
  • the next symbol and the direction.

An example of the running of a TM

TM and Computable Functions

Let's see how a TM solves problems $\mathbf{P}$.

• Start with a problem $\mathbf{P}$.

  $\mathbf{P}$ is a (possibly infinite) set of instances, with an encoding function $\mathbf{Encode}:P\to\Sigma^*$

• Construct a Turing Machine ${M}$ whose control logic is very specific in solving $\mathbf{P}$.

  To make use of ${M}$ to solve an instance $I\in P$, we initialize the tape of ${M}$ with the encoding string of $I$ given by $\mathbf{Encode}(I)$.

• We run the TM ${M}$.

  • If $M$ terminates:

    We use the read the tape content using $\mathbf{decode}(\mathrm{tape})$.

  • If $M$ does not halt:

    The control logic is insufficient to solve the problem $\mathbf{P}$.

An example:

• The problem:

  Given a binary string of the form $000\dots0111\dots 1$. Decide if there are equal number of 0s as the 1s.

• A theorem:

  box

  The TM in Figure 1. correctly decides the problem: $\#(0) = \#(1)$ in a give binary string of the form $000\dots 0111\dots 1$.