6.1Introduction to Turing Machines

6.1.1Turing Machines, Informally¶

Recall the view of finite automata as a finite-state machine whose input is on a tape and controls a tape head (High Level Framework for Automata).

The finite automata can:

• move its tape head to the right by one cell

• read the symbol under the tape head

• the tape contains only its input

• accepts or rejects once it has reached the end of the tape

A Turing machine (TM) on the other hand can in addition:

• move the tape head to the left by one cell

• write a symbol to the tape cell under the tape head (overwriting whatever is in the tape cell)

• has an infinite tape (the input appears first and is followed by an infinite number of blanks, denoted by the blank symbol “˽”)

• can accept or reject at any time (not only at the end of the input)

6.1.2Formal Definition¶

The transition function can also be represented using a state transition diagram as was done for finite and pushdown automata. The transition $\delta(q,a) = (r,b,d)$ is represented by $q \xrightarrow{a \rightarrow b, d} r$. For transitions that do not overwrite the symbol under the tape head with a different symbol, i.e. $\delta(q,a) = (r,a,d)$, we use $q \xrightarrow{a \rightarrow d} r$.

Let $M$ be a Turing machine. Consider an input string $w = v_1 v_2 \cdots v_n$ where each $v_i$ is a symbol of the alphabet. The TM processes $w$ as follows:

1. Initially, the first $n$ tape cells of the tape contain the symbols of $w$, with the remaining cells containing the blank symbol ˽

2. Start at the start state and with the tape head at the start (i.e. left end) of the tape

3. Repeat the following:

   • Let $q$ be the current state and $x$ be the symbol under the tape head

   • If $q = q_{acc}$, $M$ halts and accepts

   • If $q = q_{rej}$, $M$ halts and rejects

   • Else:

     • let $(r,y,d) = \delta(q,x)$

     • write $x$ to the cell under the tape head, move tape head in direction $d$, and move to state $r$

Configurations¶

We now explain in more detail exactly what a single step of computation in a Turing machine looks like.

Let $C$ and $C'$ be two configurations. We say that $C$ yields $C'$ iff applying $\delta$ to $C$ results in $C'$ and write $C \Rightarrow C'$.

The initial configuration of $M$ on $w$ is $q_0w$: the state is the initial state, the tape contains the input $w$ and the tape head is at the start of the tape.

With these definitions, it is now clear that:

• $M$ halts and accepts on input $w$ if after applying the transition function to the initial configuration a finite number of times, we obtain a configuration whose state is $q_{acc}$.

• $M$ halts and rejects on input $w$ if after applying the transition function to the initial configuration a finite number of times, we obtain a configuration whose state is $q_{rej}$.

• $M$ never halts if it is not possible to obtain a configuration whose state is either $q_{acc}$ or $q_{rej}$ after applying the transition function to the initial configuration a finite number of times.